Subject: PKIX implications of SHA-1 collisions

From: Russ Housley <[email-masked]>
Date: Wed, 16 Feb 2005 12:26:47 -0500

I am sure that almost everyone on this list is already aware of the news 
regarding SHA-1.  For those who have not, see 
http://www.schneier.com/blog/archives/2005/02/sha1_broken.html

A 2^69 work factor is bad, but not a complete disaster.  At least not 
yet.  Of course, as Bruce Schneier has noted, attacks never get worse; they 
only improve.

 From the information that we have so far, two messages that have 
collisions will have a particular structure.  I propose we have a pretty 
easy way to make sure that we can avoid that structure in X.509 
certificates.  We can construct the certificate serial number, which is 
always part of the first hash block, from a random number in addition to 
any other CA-specific serial number assignment scheme.  For example, the 
serial number might be a counter concatenated with a 64-bit random value.

I think this can documented very quickly in a BCP.  It should just be a few 
pages.  I am willing to help write it.

Russ

---

From: Tim Polk <[email-masked]>
Date: Wed, 16 Feb 2005 14:47:16 -0500

Russ,

This is extremely important to us here at NIST, of course.  I expect that 
we will be applying significant resources to this topic in general, and its 
impact on PKI specifically, over the coming weeks.  Count on us to 
participate in this effort.

Tim Polk

At 12:26 PM 2/16/2005 -0500, Russ Housley wrote:

>yet.  Of course, as Bruce Schneier has noted, attacks never get worse; 
>they only improve.
>
>I think this can documented very quickly in a BCP.  It should just be a 
>few pages.  I am willing to help write it.
>
>Russ
>
>

---

From: [email-masked] (Peter Gutmann)
Date: Thu, 17 Feb 2005 17:26:43 +1300

>pages.  I am willing to help write it.

I think it'd be better to wait a bit to get the full details.  Here's a
boilerplate summary I've been sending out to people who have mailed me about
this (personal opinion disclaimer, etc etc):

- It only affects the use of SHA-1 as a hash function, not as a PRF or HMAC,
  so the core of SSH, SSL/TLS, etc etc are unaffected.

- I've seen one report that it only affects the compression function and not
  the full hash function, which sounds plausible.  SHA-1 (and indeed all of
  the MD4-type UFN hashes) use a core compression function and then perform
  extra operations for the full hash function, so finding collisions in the
  full hash is somewhat more difficult than just the compression function.

- It takes 2^69 ops on average to find a second input value that produces the
  same output as the first one (the ambiguous phrasing here is meant to
  indicate that probably what's meant is that the compression function
  produces the same output rather than the full SHA-1 hash producing the same
  output, see above).  The second input value can't be chosen by the attacker,
  so the chances of forging a signature on structured data like a certificate
  or CMS/PGP message are fairly remote.

So while it's a very interesting result, it's more a hint to consider moving
to something else rather than time to hit the panic button.  RIPEMD-160 still
looks fairly secure, my gut feeling is that its dual-path construction is
safer than the SHA-1 derived SHA-256 et al, but I suspect that in the light of
the current work on attacking UFN-based designs we'll be seeing a pile of new
non-UFN hash functions in the same way that differential cryptanalysis spurred
a burst of work on new ciphers.

Peter.

---

From: "Santosh Chokhani" <[email-masked]>
Date: Thu, 17 Feb 2005 10:21:09 -0500

I agree with Peter that we should first understand the attack well enough
(which I do not) before providing the solutions.

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On
Behalf Of Peter Gutmann
Sent: Wednesday, February 16, 2005 11:27 PM
To: [email-masked]; [email-masked]
Subject: Re: PKIX implications of SHA-1 collisions

- It takes 2^69 ops on average to find a second input value that produces
the
  same output as the first one (the ambiguous phrasing here is meant to
  indicate that probably what's meant is that the compression function
  produces the same output rather than the full SHA-1 hash producing the
same
  output, see above).  The second input value can't be chosen by the
attacker,
  so the chances of forging a signature on structured data like a
certificate
  or CMS/PGP message are fairly remote.

So while it's a very interesting result, it's more a hint to consider moving
to something else rather than time to hit the panic button.  RIPEMD-160
still looks fairly secure, my gut feeling is that its dual-path construction
is safer than the SHA-1 derived SHA-256 et al, but I suspect that in the
light of the current work on attacking UFN-based designs we'll be seeing a
pile of new non-UFN hash functions in the same way that differential
cryptanalysis spurred a burst of work on new ciphers.

Peter.

---

From: "todd glassey" <[email-masked]>
Date: Thu, 17 Feb 2005 13:27:06 -0800

It also may be true that in the risk models where SHA-1 is used it could be
fine still. This may be more as important as understanding the attack.

Todd

---

From: [email-masked] (Peter Gutmann)
Date: Fri, 18 Feb 2005 14:54:33 +1300

>(which I do not) before providing the solutions.

Ian Grigg has posted more info at 
http://www.financialcryptography.com/mt/archives/000357.html#more.

Peter.