----- Original Message -----
Sent: Friday, March 04, 2005 7:46
AM
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.