Re: Crypto Mini-FAQ

From: David Wagner (daw_at_taverner.cs.berkeley.edu)
Date: 01/19/04 

Date: Mon, 19 Jan 2004 04:41:48 +0000 (UTC)

Roger Schlafly wrote:
>1. There are lots of low-security apps for which MD5 is fine.

Yup, but SHA1 is also fine for those. The general rule of thumb
that says "use SHA1" is fine for these settings.

>2. Even if it becomes easy to find MD5 collisions, then it might still
>be fine for some apps in which people write their own messages.
>As far as we know, no one has any idea how to attack the problem
>of finding Y, given X, such that MD5(Y)=MD5(X).

Maybe, but in practice, you usually can't rely on users to write their
own messages. In most cases, it's probably easy to trick the typical
user into using a message written by someone else. Consequently, this
is not much of a saving grace. For future systems, it seems safer to
avoid relying on user behavior at all, and simply use SHA1.

>3. A hash function is not "broken" just because the author of a
>competing hash function thinks that it is "at the edge". (Dobbertin
>is a coauthor of RIPEMD.)

I'm not sure that's quite fair, though I do agree that such comments
have to be evaluated with care and with examination of context. In
this case, I'm inclined to agree with Dobbertin, but you can draw your
own conclusions. Certainly Dobbertin and others were right in their
predictions, after early results about MD4 came to light, that MD4 would
fall; it eventually did.

It's also worth noting that RSA Labs themselves caution against
using MD5 for future applications, and recommend gradually swapping
it out of existing applications. This recommendation dates back to
1996:
  `Given the surprising speed with which techniques on MD4 were extended to
  MD5, we feel that it is only prudent to draw a cautious conclusion and to
  expect that collisions for the entire hash function might soon be found.''
   -- RSA Laboratories Security Bulletin #4
      ftp://ftp.rsasecurity.com/pub/pdfs/bulletn4.pdf
Given that RSA Labs is in some sense the owner of MD5, and were
originally one of the primary proponents of MD5, this statement is
significant.

>Consider this analogy. There are reputable cryptographers who have
>published attacks on reduced-round versions of AES, and there
>are those who think that AES is at the edge because it doesn't
>have enough rounds. I don't know whether they are right or not,
>but it certainly doesn't justify a conclusion that AES is "broken".

First, I'm not saying MD5 is "broken" (though some others are,
I agree with you that this is a little misleading).

Second, it seems to me the situation with MD5 is not analogous.
If Vincent Rijmen or Joan Daemen said that AES is "at the edge"
or recommended against using AES in future systems, I'd tend to
take that advice pretty seriously. When RSA Labs recommends against
using MD5 in future systems, I treat that as significant, too.
This is not just some lone cryptographer out to advance his own
design by finding academic attacks on his competitors.

Relevant Pages

  • Re: [fw-wiz] MD5 x SHA-1
    ... | file in backup, put that on backup tape, then the backup ... % openssl speed md5 ... | nonce bytes to a modified file to get same hash with MD5 than SHA1 ... Generally the attacks are birthday attacks; they allow you to find two ...
    (Firewall-Wizards)
  • RE: SHA-1 vs. triple-DES for password encryption?
    ... Same did not happen against the full MD5 yet and who knows when/if it will. ... Cryptographers call an attack something that ... > than you would of SHA1 to get the difficulty up to the same level. ... > cryptographers who are under the impression that Dobbertin has ...
    (SecProg)
  • Re: F12-i386-DVD iso wont burn properly -- SOLVED
    ... and the disc to be checked against it. ... All files get an MD5 or SHA1 check performed on ... means to embed such a CRC in the program which does the checks. ...
    (Fedora)
  • Re: Best Performance File Compare: MD5/SHA1 or Byte-by-Byte Checking?
    ... SHA1 and MD5 will both require looping through the whole file just to ... generate the hash so in either method you're looping through both ... and assuming that the accuracy/reliability of SHA1 is ... What about MD5? ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: SHA-1 vs. triple-DES for password encryption?
    ... > birthday attack succeeds with probability 0.5 or 50%. ... > full MD5. ... > theoretical cryptographers call an "attack" create FUD on this issue. ... Note that you are correct in saying that SHA1 is of the same family as ...
    (SecProg)