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

From: Robert Zuccherato <[email-masked]>
Date: Fri, 4 Mar 2005 13:58:15 -0500

Yes, the two public keys are produced so that after they are processed there
is a collision in the hash function chaining variable.  Anything added after
this point will similarly produce a collision, as long as the same data is
added to both.  Thus, even if the CA includes randomness after the public
key in the TBS blob, an identical certificate with the second public key
will produce the same hash, and thus the same signature.
 
The reason why the randomness in the serial number is able to prevent this
particular attack is that the attacker cannot predict it's value and thus
cannot predict the value of the hash function chaining variable at the point
the public keys begin to get processed.  This appears to prevent the
construction of collisions in the public keys.
 
    Robert.

-----Original Message-----
From: Guida, Richard [JJCUS] [mailto:[email-masked]] 
Sent: March 4, 2005 1:31 PM
To: Robert Zuccherato; 'Russ Housley'; [email-masked]
Subject: RE: [saag] X.509 certificate collision, via MD5 collisions

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

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: J Adrian Pickering <[email-masked]>
Date: Sat, 05 Mar 2005 19:17:41 +0000

At 18:58 04/03/2005, Robert Zuccherato wrote:
>cannot predict the value of the hash function chaining variable at the 
>point the public keys begin to get processed.  This appears to prevent the 

This was why I suggested in TSP we removed the 'monotonic increasing' 
requirement for a TSA serial number during final draft. Mananaging 'random' 
serial numbers is not so easy but I rather think it is a requirement.

The attacks highlight the importance of making every bit significant in the 
message to be hashed. Aside from certificates, I've got increasingly 
worried about the non-rendered and/or highly redundant junk in documents. I 
trust logos aren't going to cause problems here.

Adrian Pickering/
University of Southampton, UK