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

[Daniel Kahn Gillmor]

On 05/24/2009 02:15 AM, Robert J. Hansen wrote:
> It depends on what sort of threat you're facing.  In this case, the MD5
> attack is predicated on the victim signing documents they did not
> originate.  This is often considered bad policy, since it tends to
> facilitate attacks like this.  This usage case is kind of rare for GnuPG
> -- not unheard of, but rare.

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.  The only element in a standard OpenPGP
certification which changes is the timestamp of the certification
itself.  The timestamp is fairly predictable (the hash-clash rogue CA
X.509 MD5 compromise in December 2008 relied on timestamping with the
same granularity that OpenPGP uses).  Furthermore, the timestamp is
*appended* to the element in question that is signed (as are any
additional subpackets that the issuer of the certification elects to
include).  Certifier-authored appended data is less useful for defeating
a collision attack, since signatures are made over digests that are
one-pass.  With a one-pass digest, an attacker needs only to find a
collision in the lead-up to the appended data, and then subsequent
appended data can simply be copied from the tail of one message to the
other to maintain the collision in the digest output space.

> MD5 is best avoided, yes, please don't get me wrong -- but it's kind of
> a stretch to say that it is entirely broken for purposes of email
> cryptography.

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.  The ability to find two messages with identical
digests should be no less expensive than a so-called "birthday attack",
which is 2^64 digest calculations for a 128-bit digest like MD5.  MD5's
collision resistance is demonstrably less than 2^64 today.  Wikipedia
notes attacks that find MD5 collisions in a few hours on a notebook
computer.

Collision attacks have significant utility in subverting all kinds of
crypto-systems including e-mail cryptography, particularly because so
many mail clients are willing to ignore invalid or garbage-y data in an
e-mail message.

SHA-1's collision resistance is weakened as well, reportedly to the
level of 2^52 operations (it should be 2^80, since SHA-1 is a 160-bit
hash), but (a) no one has seen an exploit of this in the wild yet, and
(b) 2^52 is a fairly big number anyway (within reach of well-funded
organizations, but not nearly as bad as MD5).

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.

	--dkg

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 890 bytes
Desc: OpenPGP digital signature
URL: </pipermail/attachments/20090524/05618af6/attachment.pgp>