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

[David Shaw]

On May 2, 2009, at 1:42 AM, Daniel Franke 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.

I rather like this idea.  I was thinking that a good way to tie it  
into the GPG way of doing things would be another one of the %- 
expandos.  So you could do something like set a notation for "random at example.com 
=%10r" for 10 digits of random hex, %15r for 15 digits, etc.

Before we go down this road, however, it might be worth waiting the  
(should be short) period of time before the new SHA-1 paper is  
formally published and people can give it a good read over.  The  
slides are good, but I think it's healthy to get a better notion of  
the attack before we implement a countermeasure (even one as harmless  
to compatibility as this).

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

True.  It's a very neat idea.

David