laying groundwork for an eventual migration away from SHA1 with gpg

[David Shaw]

On May 8, 2009, at 12:30 PM, Daniel Kahn Gillmor wrote:

> On 05/07/2009 08:07 PM, David Shaw wrote:
>> I don't think that the SHA-1 situation is nearly that dire.  What  
>> is the
>> attack that you're worried about here?
>
> Some attacks i'm concerned about are similar to the one demonstrated
> against MD5/X.509 at the end of last year:
>
> http://www.win.tue.nl/hashclash/rogue-ca/
>
> OpenPGP is in better shape than X.509 already because there isn't a
> handful of central authorities that everyone chain-trusts absolutely.
> So there isn't room for a 'net-wide compromise of the type  
> demonstrated
> by the hashclash folks.  But there is still room for bogus
> certifications compromising pockets of the existing web of trust.

To perform that attack requires the attacker to supply both the  
original key being signed as well as the new key that the attackers  
want the forged signature to fit.  It cannot (even with MD5) be done  
against an arbitrary signature or key in the web of trust.

Essentially it would be some attacker doing some fairly dramatic  
computational project to come up with two different-but-related keys.   
He then comes to a key signing event and gets people to sign his "A"  
key.  Then, he moves the signatures over to his "B" key, and proceeds  
to wreak havoc.

So two comments:

1) He can't do this to existing signatures on existing keys.  He has  
to make a new matching A+B pair.
2) If signers use SHA-256 for new signatures, he is completely foiled.

Actually, three comments:

3) *What* havoc?  What does this actually enable him to do in the  
context of OpenPGP?  For example, let's say that I have a way to  
perform this attack.  I carefully generate my A+B key pairs, and show  
up to a key signing event and get lots of people to sign A.  Then I  
move those signatures over to B.  So what have I gained?  In the case  
of rogue CA, they were able to create a certificate that turned them  
into a CA, but since everyone in OpenPGP is more or less a CA, that  
doesn't really apply here.  The main thing they seem to have  
accomplished is to impersonate someone.  So they could burn a lot of  
time and money in order to get some signatures on a key claiming to be  
someone they're not?  If that's the goal, there are much easier,  
faster, and cheaper ways of going about it.

On top of that, keep in mind that this attack is completely  
theoretical at this point.  Nobody has ever even shown a SHA-1  
collision at all, much less a collision with the kind of finesse that  
would be required to mount the rogue CA attack.

>> Sure, let's all switch over to
>> something better, but I think that the idea that we have to quickly
>> rebuild the web of trust or that we're somehow in a race against time
>> before someone starts forging signatures is more than a bit  
>> excessive.
>
> I think it *is* something of a race against time, assuming the
> announcement from this year's eurocrypt is legitimate.  And the  
> writing
> has been on the wall for SHA-1 since Wang's results in 2005, no?

No.  The writing has been on the wall for *new* signatures.   
Compromising old signatures is a different type of failing in the hash.

> If we're picking arbitrary deadlines, a major user of cryptography  
> (the
> US gov't) has decreed a deadline to completely abandon reliance on  
> SHA-1
> for digital signatures by the end of 2010 (19 months away).  By what
> time do *you* think we should stop relying on SHA-1 as a community?

I think we should stop using SHA-1 for new signatures today.  It's  
prudent, and for all we know there will be some attack coming that  
nobody has conceived of yet.  Stopping using SHA-1 is a good, healthy  
thing to do.  However, there is a very substantial difference between  
stopping issuing new SHA-1 signatures, and proactively re-forming a  
new web of trust to exclude SHA-1.

David