Re: Comments to SCVP ID 17

Hello,

I have been reading SCVP draft 17 in detail and I send you my reading 
notes. I hope it will help you work on this topic. Since I began 
reading, draft 18 has appeared but I kept working on draft 17. Sorry if 
any of the following remarks have already been addressed.

Please keep in mind that I did not read the previous drafts and thus may
miss some of the design context. I am though quite familiar with
RFCs 2560 and 3280.

The following email deals first with my major remarks/questions on draft
17. I have also written down a non-exhaustive list of minor remarks, 
which you will find at the end of this email.

1- Some general considerations

The abstract and introduction refer to a specification for
implementating DPD/DPV ("certificate path construction and validation"
as stated in the abstract), whereas the rest of the draft specifies 
certificate validation as a whole (certificate content validation + 
revocation status + building and validation of the certification paths, 
depending of the chosen checks).

I would suggest :
- that you rewrite the abstract and introduction so that the purpose of 
the document becomes clearer (SCVP includes DPD/DPV but also deals with 
certificate content and revocation)
- that you distinguish in the text the "DPD" and the "DPV" part.

Re: One final week of Last Call for SCVP

> 
> Denis,
> 
> We are both sensitive to the fact that Tim is a co-editor of the 
> document and co-chair.  I believe that is why Tim made the comment 
> you quoted in his message, i.e., noting that I will act to determine 
> WG consensus for SCVP.
> 

There are several comments from 
Denis Pinkas, Nathalie Jolly, and Wen-Cheng Wang
which I support (not all).

X.509 certificate collision, via MD5 collisions

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

Re: X.509 certificate collision, via MD5 collisions

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.
>
>>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 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

Re: Comments to SCVP ID 17

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.
>>
>>
>> http://eprint.iacr.org/2005/067
>
> 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.

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)

**

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

Paul Hoffman wrote:
> 
> 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.
>>
>>> 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 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

Re: X.509 certificate collision, via MD5 collisions

On Mar 1, 2005, at 18:08, Paul Hoffman wrote:

>> http://eprint.iacr.org/2005/067
>
> 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.)

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.

Re: X.509 certificate collision, via MD5 collisions

Matt Crawford <crawdad <at> fnal.gov> writes:

> On Mar 1, 2005, at 18:08, Paul Hoffman wrote:
>
>>> http://eprint.iacr.org/2005/067
>>
>> 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.)
>
> 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

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

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: 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.
>>
>>
>> http://eprint.iacr.org/2005/067
>
> 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.

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)

**