A coming attack on PGP, and a way to mitigate it

[Daniel Franke]

For those who haven't yet heard, it's rumored that a new attack on SHA-1
finds collisions in 2^52 operations.  That's on the order of one hour of
computation for the Storm botnet.  The details of the attack haven't
been published yet, but the slides are here:
http://eurocrypt2009rump.cr.yp.to/837a0a8086fa6ca714249409ddfae43d.pdf

This is not, as best I can tell, a chosen-prefix attack, and therefore
does not immediately translate to an attack against OpenPGP.  The
technical summary of the attack is somewhat beyond my expertise, so I
could be mistaken about this in both the antecedent and the inference.
If so, it's already time to panic.  Regardless, however, I think this
discovery should be interpreted as writing on the wall for SHA-1, and
we should assume that a practical chosen-prefix attack is imminent.

Here's what a chosen-prefix collision would allow.  Suppose that Alice
trusts Trent to sign PGP keys.  Per GnuPG's default settings, Trent's
key is 1024-bit DSA with a 160-bit 'q' parameter, so it uses SHA-1 for a
hash algorithm.  Suppose that Mallory wants to send Alice a message
impersonating Bob.  So, Mallory generates two new keys, one with his
name on it and the other with Bob's, such that Trent's signature packets
for each would have the same SHA-1 digest.  Then, he takes the key with
his own name on it over to Trent along with his passport, and Trent
checks Mallory's credentials and dutifully signs the key.  Then Mallory
wanders off, copies Trent's signature onto to the fake key that has
Bob's name on it, and uses it to sign a message addressed to Alice.

(n.b., this is basically the same approach as the attack that produced a
rogue PKI CA last December, using an MD5 collision:
http://www.win.tue.nl/hashclash/rogue-ca/)

A necessary precondition for this attack to succeed is that the contents
of the packet that Trent signs be predictable.  Right now, they are.
Guessing the signature creation time could be problematic, but if we're
relying on that, then that's a hell of a way to run a cryptosystem.
However, there's no reason this has to be so.  Without breaking backward
compatibility, GnuPG could include in every signature packet a hashed
'Notation' subpacket containing a random nonce.  Now the SHA-1 digest
that Trent signs is no longer predictable in advance, so if Mallory
wants to find a collision, he needs a preimage attack rather than just a
birthday attack.  This is much more difficult.

This seems like a worthwhile precaution regardless of the strength of
the hash algorithm being used.

-- 
 Daniel Franke         df at dfranke.us         http://www.dfranke.us
 |----| =|\     \\\\    
 || * | -|-\---------   Man is free at the instant he wants to be. 
 -----| =|  \   ///     --Voltaire
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 228 bytes
Desc: not available
URL: </pipermail/attachments/20090501/ee2c1e6e/attachment.pgp>