re-issuing subkey binding signatures with alternate digests

[David Shaw]

On May 4, 2009, at 3:05 PM, Daniel Kahn Gillmor wrote:

> On 05/04/2009 02:14 PM, David Shaw wrote:
>> Let's say your key was originally generated with SHA-1 as the hash  
>> for
>> the subkey binding signature, and you're concerned that an attacker  
>> can
>> do nasty things with that binding signature if and when the SHA-1  
>> break
>> is extended.  You could probably do various pokings about and force  
>> that
>> binding signature to be reissued using SHA-256, but that key has  
>> already
>> (probably) been distributed far and wide with the original SHA-1  
>> binding
>> signature.  Even if you update the binding sig, an attacker can still
>> pull the old copy, with the original binding signature, from a  
>> keyserver.
>
> I understand the attack you describe, and realize that what i'm trying
> to do doesn't defend against it.  However, i'm concerned that if we
> start to explicitly deprecate MD5, then people with MD5-based subkey
> binding signatures will suddenly find their subkeys not properly
> associated.  If they were able to re-issue the subkey binding  
> signature
> using a more palatable digest, they'd be able to continue using them
> even if everyone were to decide that MD5 has the same security
> properties as sum(1).

Are there many subkey binding signatures using MD5?  Talking about  
subkeys at all means we're talking about something closer to OpenPGP,  
which implies SHA-1 to me.

>> I think your best bet is to allow your current subkeys to expire or
>> forcibly revoke them and then make new ones with the proper binding
>> signature from day 1.
>
> This doesn't address the attack you describe above either, does it?   
> the
> SHA1 signatures are still out there, published.

It really depends on the exact details of the attack (I used the "do  
nasty things with" attack, which isn't terribly specific!)  The logic  
I'm using is: if we're nervous enough about the binding signature hash  
that we want to reissue it, we aren't actually changing anything by  
just reissuing the signature.  The attacker can just get a copy of the  
old key and the old signature from any handy keyserver.  If, however,  
we issue a brand new binding sig, on a brand new subkey, then we are  
changing something.  The attacker may be able to attack the old key,  
but they can't (presumably) attack the new one.

Basically, it comes down the attacker being able to attack both the  
old and new setup, or being only able to attack the old setup.

The details, as always, depend on the attack.  What attack are you  
concerned about?

David