laying groundwork for an eventual migration away from SHA1 with gpg

[Daniel Kahn Gillmor]

On 05/08/2009 02:16 PM, David Shaw wrote:
> On May 8, 2009, at 12:30 PM, Daniel Kahn Gillmor wrote:
> 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.

Agreed.

> 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.

Right, this computational project is exactly what the hashclash folks
did against MD5.

> 1) He can't do this to existing signatures on existing keys.  He has to
> make a new matching A+B pair.

Agreed.

> 2) If signers use SHA-256 for new signatures, he is completely foiled.

Right.  However, if you've got a DSA-1 key, you're using SHA-1 by
default, no?  At best, signatures from a DSA-1 key would be made by
160-bit truncated versions of other hashes.  This is good, because it's
not the same algorithm that has currently been attacked.  but it's also
not the full-strength SHA-2 families either.

> 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.

It depends on what someone has to gain from the impersonation.  For
example, i'm interested in seeing authentication-capable OpenPGP
certificates used for ssh access (bidirectionally), and i'd like to see
them useful on the web (for mutual client-server authentication).  Even
if you don't care about these uses, the WoT *is* a means of making
impersonation more difficult online.

If you don't think that strong crypto protection against impersonation
is important, that's fine.  But I'd like to be able to offer the people
i support the ability to have their cryptosystem *not* be the weakest
link in terms of identifying themselves.  At the moment, there do seem
to be certainly faster, easier, cheaper ways of doing it (though some
organizations don't publish their results, so i can't know for certain).
 Anyway, I'd rather not wait until the math and CS catches up and forces
our hand.

> 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.

Yup, i'm aware of that.  I don't particularly want to see the
demonstration before we switch over, though.

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

Sure, agreed.  But i can't reliably tell a new signature from an old
signature if the signature is forged ;)

I also can't currently be sure that the people i communicate with aren't
still issuing SHA-1 signatures in some context.  Those signatures may
well be made over arbitrary data supplied by a third party (have you
read what passes for specs of nonsense like gpgAuth?).  Those signatures
are vulnerable to misuse or re-purposing.

So, i have a few choices:

 A) decide to never trust any SHA-1 signature again as of right now, or

 B) continue to trust what appear to be old SHA-1 signatures, and hope
that everyone has the good sense (and reliable tools) to never ever
issue a signature over SHA-1 again, or

 C) trust SHA-1 signatures for the near term, convince everyone else to
switch to something better now, and then deprecate/blacklist SHA-1 once
enough people have switched, shielding myself (and other people who make
the same decision) from SHA-1 problems.

A an unreasonable, panicky reaction. It's also totally infeasible in
today's environment.  Not enough post-SHA1 signatures exist to form a
reasonable WoT, none of my OpenPGP tools are even capable of deprecating
SHA1 signatures, and (probably most importantly) it seems exceedingly
unlikely that an attack has already been carried out. So B is unacceptable.

B seems naive: i'm sure there are people who will continue making SHA-1
signatures long after the methods behind the recent exploits are widely
known, perhaps because their tools are misconfigured, or their tools
interpret the digest-preferences in such a way that they force the use
of SHA1 for signatures or certifications in certain cases.
Certifications (and other signatures) from those people/tools are now
suspect, and could potentially be transplanted onto certifications which
appear to be "old" (pre-attack) certs.

At any rate, even if i could trust the dates on the signatures, and i
could identify the users who i expect to practice good OpenPGP hygiene,
i don't have any way to configure my current OpenPGP toolchain to say
"Don't trust SHA-1 signatures made after $DATE" (or, more strongly,
"Don't trust any SHA-1 signatures at all from $KEYID if the keyholder
has made any SHA-1 signatures after $DATE" )

So C seems like a reasonable approach to me.  Do you have other suggestions?

> 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.

I agree.  I'd be happy if the defaults on gpg were changed to reflect
this.  Nonetheless, older versions of gpg will continue to exist and be
used for quite a long time.

> 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.

yup, i agree there's a difference.  But the former isn't going to happen
universally, any more than MD5 was universally phased out when it became
known-compromised.

So since new SHA-1 signatures *will* continue to be generated, we need
to consider how those of us who would prefer to not trust new signatures
 can move forward.  One (small) piece of that transition is to make sure
that a post-SHA-1 WoT exists.  Currently, it's pretty weak.  So i'm
trying to make sure we can get that bit in place, so that the rest of
the transition is possible in the future.

I really appreciate the discussion on this list, by the way (not to
mention the incredible infrastructure that y'all have given us in the
form of gnupg).  Even if we find we can't come to an agreement on the
transition steps to take right now, it's certainly a respectful
disagreement from my end.

Regards,

	--dkg


-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 890 bytes
Desc: OpenPGP digital signature
URL: </pipermail/attachments/20090508/e11d54f4/attachment.pgp>