more on Top crypto algorithms 'fully broken?'

[David Farber <dave () farber net>]

Begin forwarded message:

From: odlyzko () dtc umn edu (Andrew Odlyzko)
Date: August 18, 2004 11:08:06 PM EDT
To: dave () farber net
Subject: Re: Top crypto algorithms 'fully broken?'

Dave,

The article by Declan McCullagh that is referenced is accurate.  But
it definitely does not mean that "top crypto algorithms are fully 
broken."
Only a few hash algorithms are affected.  Furthermore, these attacks by
themselves are not all that much of a threat.  To simplify things, what
was discovered by the researchers who spoke at Crypto is that for those
algorithms (which do not include the most important one, the one that
is a U.S. national standard, SHA-1), there do exist pairs of messages
that have the same signature.  More precisely, there are messages

    x*m;ut0%Wb#crr)q"-Tvmaa^@39fl
    &bfpR([wez$1l8gI@S{=!snv&Wnf+

such that if you happened to send the first one to your bank, I could
instead substitute the second one, and the forgery would not be 
detected.
However, you would not likely want to send the first message, since it
is gibberish, and even if by accident you did happen to send it, I would
gain nothing from the forgery, since the second message is also 
gibberish,
and the bank would reject it.

Still, the attacks are significant theoretically, since until now it
was not even known how to accomplish this.  This might lead to attacks
at higher levels.  The next step would be to find attacks that would
enable a forger, when faced with a signed message from you of the form

   Transfer $36.97 from my checking account 1234567 to MCI.  Dave 
Farber.

to find another message that would have the same signature, and so would
initially be accepted by the bank as authentic.  But in most cases that
forged message would be something like

   &bfpR([wez$1l8gI@S{=!snv&Wnf+x*m;ut0%Wb#crr)q"-Tvmaa^@39flr$cDk,K.Oxx

and so again would not gain the forger anything, since it would be 
gibberish.

For a really practical attack, one would have to go up another level, 
and
find a message of the form

   Pay $65,876.99 from my account 1234567 to John M. Smith.  Dave 
Farber.

that would have the same signature as your original one.  At that stage
real harm could be done.  But we are still far from that.

Andrew





    From: David Farber <dave () farber net>
    Subject: Top crypto algorithms 'fully broken?'
    Date: Wed, 18 Aug 2004 10:05:21 -0400



    Begin forwarded message:


    DAN FARBER

    Top crypto algorithms 'fully broken?'

    Do you think your encrypted communications and  documents are 
secure?
    Think again.  In separate findings, French and Chinese researchers
    last week uncovered fallibilities in some of the most commonly used
    encryption techniques. And last night, at the Crypto 2004 
conference,
    security researchers delivered the good, the bad, and the ugly news.
    The good news:  SHA-1, embedded in popular programs such as SSL and
    PGP, is still standing--so far. The bad news, according to 
conference
    chair James Hughes, is that "the break of MD4, which was already 
broken,
    is unique because the techniques could be done by hand."  The ugly 
news:
    "full breaks" of the MD5, HAVAL-128, RIPEMD, and SHA-0 hash 
functions
    were announced as well--and  SHA-1 is under serious attack. The
    discoveries
    could make it easier for intruders to insert undetectable back doors
    into computer code or to forge electronic signatures.
    http://ct.com.com/click?q=89-h28bQ~JAj6DPkIRfpwDCBVM5LWcR


-------------------------------------
You are subscribed as interesting-people () lists elistx com
To manage your subscription, go to
 http://v2.listbox.com/member/?listname=ip

Archives at: http://www.interesting-people.org/archives/interesting-people/