Subject: X.509 certificate collision, via MD5 collisions

From: Russ Housley <[email-masked]>
Date: Tue, 01 Mar 2005 18:24:00 -0500

I have not had an opportunity to review this document yet, but the findings 
need to be shared with the whole Internet security community.

>We announce a method for the construction of pairs of valid X.509 
>certificates in which the "to
>be signed" parts form a collision for the MD5 hash function. As a result 
>the issuer signatures
>in the certificates will be the same when the issuer uses MD5 as its hash 
>function.

http://eprint.iacr.org/2005/067

---

From: Paul Hoffman <[email-masked]>
Date: Tue, 1 Mar 2005 16:08:30 -0800

At 6:24 PM -0500 3/1/05, Russ Housley wrote:
>I have not had an opportunity to review this document yet, but the 
>findings need to be shared with the whole Internet security 
>community.
>
>>be signed" parts form a collision for the MD5 hash function. As a 
>>result the issuer signatures
>>in the certificates will be the same when the issuer uses MD5 as 
>>its hash function.
>

 From the description in the paper, it appears that step 1 requires 
that the template for the certificate must be known before you create 
the two RSA keys. If that is true, then a CA who uses long serial 
numbers either randomly or based on a secret would automatically foil 
this attack. (I could be misreading the requirement, of course.)

--Paul Hoffman, Director
--Internet Mail Consortium

---

From: Jean-Marc Desperrier <[email-masked]>
Date: Wed, 02 Mar 2005 12:32:42 +0100

Paul Hoffman wrote:

>>> in the certificates will be the same when the issuer uses MD5 as its 
>>> hash function.
>>
>>

I reach the following conclusion from reading the article :

- The attacker must be able to know beforehand the serial number
- The attacker must be able to know beforehand the validity limit
- The attacker must be able to choose both keys
- Everything in the two certificates will be identical except for the 
public key information
This can change if a method fo find a collision if the IV vector value 
is not identifical is found.
Also if a method can be found to create a delayed collision (I mean by 
that a collision where the choosen value does not directly create the 
collision, where the collision appears only after appending to it some 
fixed data), it will completely change the scale of the attack.

Right now, the attack I see enabled by this method is a deniability attack.

The method would be the following :
- construct a pair of colliding certificate with the two associated key 
pairs, A and B
- register key pair A with a public CA
- Require a service from a provider
- Sign to prove you required the service with key pair B.
- Show to the provider the certificate associated with key pair B to 
prove your identity. All verifications will succeed.
- To be usable, the method require that the provider, instead of keeping 
the certificat you provided for verification, only keeps it's 
identification with regard to the CA, for exemple issuer/serial
- Later, you can deny having signed the transaction, and verification 
using the certificate registered with the CA will fail, apparently 
showing that the provider had initially failed to correctly check the 
signature.

Signature scheme that include a hash of the certificat that was used to 
do the signature will protect against this attack. In the other case, 
people should be certain they keep a copy of the certficate they used to 
verify the signature, and not rely on the possibility to get it again 
from a directory.

(Have to remove [email-masked] from the distribution, I'm not registered)

**

---

From: Ben Laurie <[email-masked]>
Date: Wed, 02 Mar 2005 12:37:01 +0000

Paul Hoffman wrote:
>> findings need to be shared with the whole Internet security community.
>>
>  From the description in the paper, it appears that step 1 requires that 
> the template for the certificate must be known before you create the two 
> RSA keys. If that is true, then a CA who uses long serial numbers either 
> randomly or based on a secret would automatically foil this attack. (I 
> could be misreading the requirement, of course.)

I believe that is correct.

Cheers,

Ben.

-- 
http://www.apache-ssl.org/ben.html       http://www.thebunker.net/

"There is no limit to what a man can do or how far he can go if he
doesn't mind who gets the credit." - Robert Woodruff

---

From: "Santosh Chokhani" <[email-masked]>
Date: Wed, 2 Mar 2005 10:51:06 -0500

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.

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.

I also find the assertions at the beginning and at the end of the paper
contradictory.  The beginning of the paper says that the CA does not have
proof of possession, but the SPKI generator knows the four primes and hence
can deduce the two private keys and that is asserted at the end of the
paper.

In summary, I do not see a practical threat from the attack and any
mitigation should be for PKCS-10 and not X.509.

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On
Behalf Of Jean-Marc Desperrier
Sent: Wednesday, March 02, 2005 6:33 AM
To: [email-masked]; [email-masked]
Subject: Re: [saag] X.509 certificate collision, via MD5 collisions

**

---

From: Eric Rescorla <[email-masked]>
Date: Wed, 02 Mar 2005 07:46:37 -0800

Matt Crawford <[email-masked]> writes:

> On Mar 1, 2005, at 18:08, Paul Hoffman wrote:
>
>> that the template for the certificate must be known before you
>> create the two RSA keys. If that is true, then a CA who uses long
>> serial numbers either randomly or based on a secret would
>> automatically foil this attack. (I could be misreading the
>> requirement, of course.)
>
> What's more, the two certificates are identical in every field before
> the public RSA modulus -- including the SubjectDN.  This is less
> interesting than it might be.  But clearly it would be foolish to
> believe that collisions with different SubjectDNs won't follow soon.

That's probably true, but they're likely to be basically random.
In Wang attack is that the colliding values aren't very
controllable...

-Ekr

---

From: "Santosh Chokhani" <[email-masked]>
Date: Wed, 2 Mar 2005 14:08:02 -0500

Russ,

See responses in-line under [Santosh:]

-----Original Message-----
From: Russ Housley [mailto:[email-masked]] 
Sent: Wednesday, March 02, 2005 1:41 PM
To: Santosh Chokhani
Cc: [email-masked]
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

---

From: Jean-Marc Desperrier <[email-masked]>
Date: Wed, 02 Mar 2005 19:41:52 +0100

>that matches the certificate.
Did you read my description of the signature denial threat ?

There's quite a few mitigating factors, but it seems to me to be a very 
real threat.

>[...]
And there I'm almost of complete opposite mind.

The attacker can only construct the attack by creating both key pairs, 
so owning both private keys.

Creating a collision over an already existing key would be IMO a very 
difficult extension of the attack.
I think we're more endangered by the risk someone may one day be able to 
extend the attack to finding a collision for two certificates where one 
or two bits of the content outside of the public modulus would be 
different, for exemple the CA bit in the Basic Property extension.

I know the author talk about what you say in the announcement.
I'm pretty confident they got it wrong.
Either the owner of the key pair created the collision, and owns both 
key pair, or we're talking of someone using a key pair he didn't create 
himself, which is an obvious security risk even without that attack.

---

From: "Santosh Chokhani" <[email-masked]>
Date: Wed, 2 Mar 2005 13:59:20 -0500

Jean-Marc,

I realize that the subscriber may be able to predict serial number can mint
a valid certificate, but needs to have both key pairs.

Thus, practically, I do not see what the threat is.

It is clearly something undesirable, but I am not in favor of trying to
accommodate something for MD5.  We should not be using that algorithm.  Why
beat a dead horse or spend money on a lost cause.

I am also worried about collisions that can cause you to masquerade as a CA
or another person.  But, this paper does not show that.

-----Original Message-----
From: Jean-Marc Desperrier [mailto:[email-masked]] 
Sent: Wednesday, March 02, 2005 1:42 PM
To: Santosh Chokhani; [email-masked]
Subject: Re: [saag] X.509 certificate collision, via MD5 collisions

I know the author talk about what you say in the announcement. I'm pretty
confident they got it wrong. Either the owner of the key pair created the
collision, and owns both 
key pair, or we're talking of someone using a key pair he didn't create 
himself, which is an obvious security risk even without that attack.

---

From: Russ Housley <[email-masked]>
Date: Wed, 02 Mar 2005 13:40:40 -0500

Russ

---

From: Tom Gindin <[email-masked]>
Date: Thu, 3 Mar 2005 08:44:17 -0500

Ben:

        The requirement for the attack is that the part of the 
TBSCertificate up to the public key be an even multiple of 64 octets.  The 
example is 256.  Using a 160 bit serial number instead of the 32 bits in 
the example would just require decreasing the length of the subject and 
issuer by a total of 16 octets or increasing it by a total of 48 octets. 
In practice, the issuer name doesn't change for a given CA, although ones 
shorter than 63 octets certainly exist, and subject names can exceed the 
length of their issuer by amounts quite different than 35 octets.  In 
fact, the example's junk subject OU is 27 octets long - reduce that to 11 
and you've reproduced the attack with a 20 octet serial number.
        Of course, RFC 2459 (6 years ago now) recommended that SHA-1 be 
preferred over MD5, as did RFC 3279, so we don't need to change the format 
of any fields in a certificate to prevent this attack for MD5.  However, 
if this class of attacks should be successfully extended to SHA-1, we 
might need to do something about it.
        If an issuer actually worried about an attack similar to this 
against SHA-1, he might be best off disrupting it by putting padding into 
a certificate if needed to make the actual public key (including any 
leading zero) start at an offset between (say) 6 and 58 mod 64.  The 
interoperability effects of that, of course, are worrying, even if all you 
did was replace the signature parameter field (a NULL normally for RSA 
with a hash) by a junk octet string not to exceed 12 octets.  Since this 
octet string itself permits more collision possibilities if it contains 
random data, it would need to be regulated as if it were PKCS#5 padding or 
something like that (i.e., every octet contains the length of the pad, or 
perhaps every octet in the pad is one more than its predecessor).

                Tom Gindin

P.S.    The above suggestion is mine, solely intended as a basis for 
discussion, and not that of my employer.  Even personally, I am NOT 
suggesting that any issuer implement this suggestion at present.

Ben Laurie <[email-masked]>
Sent by: [email-masked]
03/02/2005 07:37 AM
 
        To:     Paul Hoffman <[email-masked]>
        cc:     Russ Housley <[email-masked]>, [email-masked], 
[email-masked]
        Subject:        Re: [saag] X.509 certificate collision, via MD5 
collisions

Cheers,

Ben.

---

From: Ben Laurie <[email-masked]>
Date: Thu, 03 Mar 2005 14:54:35 +0000

> and you've reproduced the attack with a 20 octet serial number.

The issue is not the length of the serial number but its predictability. 
You have to know the serial number in advance in order to generate the 
collision (because you have to know what they call the IV - i.e. the 
chaining values).

Cheers,

Ben.

---

From: Sam Roberts <[email-masked]>
Date: Thu, 3 Mar 2005 11:46:58 -0500

> The issue is not the length of the serial number but its predictability. 

I thought most CAs put some random component into the serial number, and
even for ones that just using a simple integer count, it would seem
quite difficult to predict the number of the next cert to be issued.

So, can anybody describe practical prediction strategies?

Cheers,
Sam

-- 
Sam Roberts <[email-masked]>

---

From: Russ Housley <[email-masked]>
Date: Thu, 03 Mar 2005 14:27:11 -0500

Some CAs issue very few certificates, so it is very easy to predict the 
next serial number that will be used by looking at the last certificate 
that was issued.

Russ