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

["Santosh Chokhani" <chokhani@xxxxxxxxxxxx>]

Russ,

See responses in-line under [Santosh:]



-----Original Message-----
From: Russ Housley [mailto:housley@xxxxxxxxxxxx] 
Sent: Wednesday, March 02, 2005 1:41 PM
To: Santosh Chokhani
Cc: ietf-pkix@xxxxxxx
Subject: RE: [saag] X.509 certificate collision, via MD5 collisions


Santosh:

>When I read the paper, the primary concern I come away with and the 
>authors tend to communicate is "proof of possession" of private key.  
>That is not done using X.509 certificates.  It is done using PKCS-10 
>requests.  When you look at the PKCS-10 structure, there is no serial 
>number and the authors' attack is still plausible.  Randomizing the 
>serial number or adding a random number will not help there.

The serial number is selected by the CA; however, there are CAs that issue 
very few certificates, so it is easy to guess the serial number that they 
will pick.  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.  I am 
totally confused by your assertion that it will not.  Please explain.

[Santosh: I am not saying that a subscriber who can predict the serial
number can not mint the second certificate.  She can.  But, them what?  What
practical break she can cause?  I am not in favor of changing the standard
when there is no practical threat and folks are using an algorithm that they
should have stopped using a while back, not just last summer.  64 bits of
unbroken MD5 security was not same is 78-80 bits of 1024 RSA.] 

>But, it does not seem to violate the security of PKI since all it does 
>is allow the subscriber to get one public key certified and have 
>another key that matches the certificate.

The concern is that it will appear that the subject has two 
certificates.  The CA's signature value is the same on both of the 
certificates.

[Santosh: And then how does some one exploit it?]

I disagree with this conclusion.  Consider a replying party that validates 
a signed message using such a certificate.  They take some action based on 
the content of the signed message; say they send 1000 widgets to an address 
in the message.  The relying party then sends a bill for the widgets.  The 
subject says: "Hey, I did not order these widgets, and I am not going to 
pay for them."  The subject then produces the second certificate, claiming 
that it is his, not the one used to sign the message.  He says: "If you 
produce a message ordering the widgets that can be validated with this 
certificate, then I will pay."

[Santosh: Both scenarios boil down to trusting the mathematics of
cryptography.  Just the way mathematics tells no one other than the
subscriber possesses the private key corresponding to a public key, the
Lenstra paper shows that the subscriber possesses both keys.]

Russ