MD5 is an unreliable digest algorithm [was: Re: Key Transition Letter 2009-05-21]

[Robert J. Hansen]

Daniel Kahn Gillmor wrote:
> Actually, it is fairly common in certain circumstances: Certifying
> that another user's key is correctly bound to their User ID (a.k.a.
> "signing someone's key") is effectively making a signature over a
> document that you did not originate.

Yes.  And then if you take a look at how often this happens with MD5 in
OpenPGP, you'll find the answer is effectively never, since SHA-1
generally gets used instead.  So this attack is mostly a nonissue for
OpenPGP usage.

> MD5 *is* broken in that it does not provide the exepcted level of 
> security that a digest of its length implies, particularly for 
> collision-resistance.

I am getting pretty frustrated with how people are misreading,
misinterpreting, or outright not listening to the qualifications I am
putting on the things I'm saying.

My original text was, "it's kind of a stretch to say that it is entirely
broken for purposes of email cryptography."  The word "entirely" is
pretty important there.

Algorithms are not, as is commonly believed, to be either "secure" or
"insecure".  OpenPGP in particular is used in a variety of different
ways.  There is a continuum of "secure for all known uses of OpenPGP" at
one end, and "insecure for all known uses of OpenPGP" at the other, and
a lot of gray area in the middle where "secure for some uses" lives.

MD5 is in that continuum.  It is not /entirely/ broken, as seems to be
the common misperception.

> So MD5 should indeed be avoided today, and we should be methodically
> and reasonably moving away from reliance on SHA-1 in circumstances
> where collision-resistance is necessary.

Yes.  Which is exactly what I've been saying.