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

[Daniel Franke]

I <df at dfranke.us> wrote:
> 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.

*Sigh*.  Unfortunately, I have to retract this, due to my earlier
misreading of RFC4880.  The order of the data being hashed is first the
signee's key packet, then his userid, then the signature packet
constructed by the signer.  So first of all, what Mallory actually needs
is a chosen-*suffix* attack, not a chosen prefix, since the userids
(which need to be chosen) come after the key packets (which can be
mostly random).  More important, though, is that everything that can be
customized by the signer comes after the parts that the signer is
authenticating.  Since SHA-1 does only a single pass over the data, this
means that once Mallory finds a collision over the parts that he wants
to forge (the key and userid), what comes after them is irrelevant as
long as it is the same on the legitimate key as the forged one.  So even
without knowing in advance what digest Trent is going to sign, Mallory
can get a valid forgery by copying Trent's nonce onto the forged key
along with Trent's signature.

This also means that my previous remark about the possible difficulty of
predicting the creation time offers no mitigation at all.

It still seems that the idea of dispersing signer-chosen random bytes
throughout the input to the hash could mitigate many sorts of likely
future attacks against SHA-1 or other hash algorithms.  This though is
useless to us at present, since it could not be implemented in anything
resembling a backward-compatible manner, and once we're willing to
forget about backwards compatibility we can simply banish SHA-1.

-- 
 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/20090503/5c85b5e8/attachment.pgp>