RE: [saag] X.509 certificate collision, via MD5 collisions
Santosh Chokhani <chokhani <at> orionsec.com>
2005-03-02 15:51:06 GMT
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
In summary, I do not see a practical threat from the attack and any
mitigation should be for PKCS-10 and not X.509.
From: owner-ietf-pkix <at> mail.imc.org [mailto:owner-ietf-pkix <at> mail.imc.org] On
Behalf Of Jean-Marc Desperrier
Sent: Wednesday, March 02, 2005 6:33 AM
To: ietf-pkix <at> imc.org; phoffman <at> imc.org
Subject: Re: [saag] X.509 certificate collision, via MD5 collisions
Paul Hoffman wrote:
> At 6:24 PM -0500 3/1/05, Russ Housley wrote:
>>> 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.
> 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 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 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 saag <at> mit.edu from the distribution, I'm not registered)