Subject: RE: [saag] X.509 certificate collision, via MD5 collisions

From: "Stefan Santesson" <[email-masked]>
Date: Fri, 4 Mar 2005 18:10:02 -0000

I agree that it is too early to specify specific countermeasures and I
also believe that we start walking a somewhat tricky and dangerous path
if we start to specify specific rules to construct data objects to be
hashed. Certificates are just one of many hashed objects in the chain of
a securing a signed message or transaction.

Stefan Santesson 
Microsoft Security Center of Excellence (SCOE) 

________________________________

From: [email-masked] [mailto:[email-masked]]
On Behalf Of Robert Zuccherato
Sent: den 4 mars 2005 16:46
To: 'Russ Housley'; [email-masked]
Subject: RE: [saag] X.509 certificate collision, via MD5 collisions

I'd like to comment on the following suggestion from Russ: 

> In the past, I have recommended the use of large serial numbers 
> where the first part is a monotonically increasing integer and the
second 
> part is random.  A 64-bit random value should thwart this attack.  

This idea has a number of good points.  It seems that a CA that includes
randomness in its serial number would be able to prevent collisions like
the one produced by Lenstra, 

Wang and de Wegner.  Including the randomness in the serial number in
the way that has been suggested is also nice because it's done in such a
way that PKIX conformant applications shouldn't choke on them.  A CA can
also continue to issue serial numbers using monotonically increasing
values, or any other scheme that they wish to use, in the non-random
part.  

However, I really wonder if we should be recommending that people change
their implementations at this point.  I don't think we know enough yet
about the potential attacks on MD5, SHA-1 to say with any certainty that
any particular counter-measures are worth implementing.  This
infrastructure was built assuming that people will use strong hash
functions.  I see no reason at this point to change that assumption.
People should have stopped using MD5 a long time ago.  Over the next
couple of years they will likely have to stop using SHA-1 as well.  I
think that is the real advice that we should be giving people at this
time.

There are also some practical problems with overloading the serial
number.  CRLs will, in most circumstances, increase in size.  Also, OCSP
responders that pre-compute responses may have trouble pre-computing
"good" responses if they cannot predict which serial numbers have been
used.  This issue would come up with responders that work from CRLs and
assume that a certificate is "good" if it's serial number doesn't appear
on a CRL.

I'd also like to point out that the serial number proposal would only
help X.509 certificates and not CRLs, RFC 3161 time stamp tokens (there
was already a message to the CFRG list today showing how to extend the
MD5 X.509 work to 3161 tokens), OCSP responses, etc.  One might consider
defining a non-critical extension that would simply contain a random
integer of an appropriate size that is freshly generated by the signer
at signing time.  But, I don't believe that would solve the problem.
Once the collision has been produced using the public keys, anything
added to the certificate after that (i.e., an extension) will also
produce a collision.

        Robert Zuccherato.

---

From: "Guida, Richard [JJCUS]" <[email-masked]>
Date: Fri, 4 Mar 2005 14:08:41 -0500

Thanks very much, Stephen; excellent idea on using an extension that just
includes a stronger hash.  As you noted, we are not in crisis mode, but we
are following this area closely and if a consensus forms about the best way
to deal with the matter until a stronger hashing function emerges (outside
the SHA family), then we certainly want to consider it.  Migrating to
SHA-256 or SHA-512 is certainly fine and also in the plans.  Thanks again --
Rich

Richard A. Guida
Director, Information Security

Johnson & Johnson
Room GS8217
410 George Street
New Brunswick, New Jersey  08901
Phone:  732 524 3785

-----Original Message-----
From: Stephen Farrell [mailto:[email-masked]]
Sent: Friday, March 04, 2005 1:55 PM
To: Guida, Richard [JJCUS]
Cc: [email-masked]
Subject: Re: [saag] X.509 certificate collision, via MD5 collisions

Rich,

I believe that randomness after the public key isn't much
use, but others'll know better.

However, instead of including an extension with a random value,
you could include an extension with a better hash over the
rest of the TBS-cert, (e.g. using sha256 or better). If you
just don't have any other hash algorithm available for some
reason, then you could add an extension which contains a
random value ("V") and H("V"||TBS-cert).

In both cases a client that can process the extension can
detect problems. You can also detect bad certs via filtering
on e.g. an ldap server. Not sure how much of this'd be
worthwhile though.

In any case, I'd agree with others who've said that its a
bit too soon to be deciding how to fix this.

Next week's meetings should be interesting anyway!
Stephen.

Guida, Richard [JJCUS] wrote:

> Robert - can you help me understand the substance of your last 
> sentence?  We are indeed considering adding a proprietary extension 
> which would be populated with just random data (for certs issued by our 
> enterprise PKI).  Is the issue that the extension appears after the 
> public key in the TBS blob - and the attack thus would work regardless 
> of that random data?  Thanks very much.  Wish I had more time to 
> understand the details of the attack myself, but at my age I am lucky to 
> remember the definition of the Fibonacci sequence.....
>  
> 
> *Richard A. Guida*
> *Director, Information Security*
> 
> */Johnson & Johnson/*//
> Room GS8217
> 410 George Street
> New Brunswick, New Jersey  08901
> Phone:  732 524 3785
> 
>     -----Original Message-----
>     *From:* Robert Zuccherato [mailto:[email-masked]]
>     *Sent:* Friday, March 04, 2005 10:46 AM
>     *To:* 'Russ Housley'; [email-masked]
>     *Subject:* RE: [saag] X.509 certificate collision, via MD5 collisions
> 
>      > where the first part is a monotonically increasing integer and
>     the second
>     This idea has a number of good points.  It seems that a CA that
>     includes randomness in its serial number would be able to prevent
>     collisions like the one produced by Lenstra,
> 
>     Wang and de Wegner.  Including the randomness in the serial number
>     in the way that has been suggested is also nice because it's done in
>     such a way that PKIX conformant applications shouldn't choke on
>     them.  A CA can also continue to issue serial numbers using
>     monotonically increasing values, or any other scheme that they wish
>     to use, in the non-random part. 
> 
>     However, I really wonder if we should be recommending that people
>     change their implementations at this point.  I don't think we know
>     enough yet about the potential attacks on MD5, SHA-1 to say with any
>     certainty that any particular counter-measures are worth
>     implementing.  This infrastructure was built assuming that people
>     will use strong hash functions.  I see no reason at this point to
>     change that assumption.  People should have stopped using MD5 a long
>     time ago.  Over the next couple of years they will likely have to
>     stop using SHA-1 as well.  I think that is the real advice that we
>     should be giving people at this time.
> 
>     number.  CRLs will, in most circumstances, increase in size.  Also,
>     OCSP responders that pre-compute responses may have trouble
>     pre-computing "good" responses if they cannot predict which serial
>     numbers have been used.  This issue would come up with responders
>     that work from CRLs and assume that a certificate is "good" if it's
>     serial number doesn't appear on a CRL.
> 
>     I'd also like to point out that the serial number proposal would
>     only help X.509 certificates and not CRLs, RFC 3161 time stamp
>     tokens (there was already a message to the CFRG list today showing
>     how to extend the MD5 X.509 work to 3161 tokens), OCSP responses,
>     etc.  One might consider defining a non-critical extension that
>     would simply contain a random integer of an appropriate size that is
>     freshly generated by the signer at signing time.  But, I don't
>     believe that would solve the problem.  Once the collision has been
>     produced using the public keys, anything added to the certificate
>     after that (i.e., an extension) will also produce a collision.
> 
>             Robert Zuccherato.
>