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

From: Robert Zuccherato <[email-masked]>
Date: Fri, 4 Mar 2005 10:46:28 -0500

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.

---

From: Paul Hoffman <[email-masked]>
Date: Fri, 4 Mar 2005 09:45:57 -0800

At 10:46 AM -0500 3/4/05, Robert Zuccherato wrote:
>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.

The first sentence fully contradicts the last one. To use a new hash 
algorithm is a *much* larger change than to have CAs change the 
method they issue serial numbers; one involves changing every 
validating client, the other doesn't.

>There are also some practical problems with overloading the serial number.

The term "overloading" is silly here. Before now, no one has accused 
VeriSign of "overloading" its serial numbers.

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

Those are valid points. However, weigh them against asking every 
validating client to change its software (and not even assuring them 
that they won't have to again later when we discover that the 
"better" hash algorithm has some other flaws). Which is the better 
way to get the public to trust PKI more?

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

Please explain the attack scenario for these. What possible value is 
there for a CRL signature spoofing attack, for example? As for 
timestamps and OCSP responses, what Eric said yesterday still stands: 
if you are relying on a particular signed object for a valuable 
transaction, keep the object around.

--Paul Hoffman, Director
--VPN Consortium

---

From: "todd glassey" <[email-masked]>
Date: Fri, 4 Mar 2005 11:17:49 -0800

RE: [saag] X.509 certificate collision, via MD5 collisionsIf use models had been required in the x509 standards team and here as well this would be much less of an issue if at all.

Todd 
  ----- Original Message ----- 
  From: Robert Zuccherato 
  To: 'Russ Housley' ; [email-masked] 
  Sent: Friday, March 04, 2005 7:46 AM
  Subject: RE: [saag] X.509 certificate collision, via MD5 collisions

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

---

From: Stephen Kent <[email-masked]>
Date: Fri, 4 Mar 2005 16:31:25 -0500

At 9:45 AM -0800 3/4/05, Paul Hoffman wrote:
>>enough yet about the potential attacks on MD5, SHA-1 to say with 
>>any certainty that any particular counter-measures are worth 
>>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.
>

Paul,

This is not entirely true.  I have noted in the past that there are 
subtle vulnerabilities associated with issuing serial numbers that 
are not serial. This is a concern with VeriSign and with the CA built 
into Microsoft desktop product as well.  Still, IF the collision 
problem is determined to be a serious concern, then I agree that 
changing the serial number generation process has much less impact 
than changing the hash algorithm.

Steve

---

From: Eric Rescorla <[email-masked]>
Date: Fri, 04 Mar 2005 15:47:36 -0800

Stephen Kent <[email-masked]> writes:
> subtle vulnerabilities associated with issuing serial numbers that are
> not serial. This is a concern with VeriSign and with the CA built into
> Microsoft desktop product as well.  Still, IF the collision problem is
> determined to be a serious concern, then I agree that changing the
> serial number generation process has much less impact than changing
> the hash algorithm.

Steve,

By "not serial" do you mean "not monotonically increasing" or do you
mean "must increase by one each time"?

Thanks,
-Ekr

---

From: Stephen Kent <[email-masked]>
Date: Fri, 4 Mar 2005 18:43:19 -0500

At 10:46 AM -0500 3/4/05, Robert Zuccherato wrote:
>	<SNIP>
>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.

An OCSP responder is only supposed to indicate whether a cert is 
revoked or not.  so, if the cert is not in the CRL,  it it not known 
to be revoked, and if it is there is it revoked. absence from the CRL 
is not necessarily an indication of a "good" cert and any inference 
of that sort is an error.

Steve

---

From: Dave Engberg <[email-masked]>
Date: Fri, 4 Mar 2005 18:15:45 -0700

I think Robert was using the formal RFC 2560 definition of "good":

The "good" state indicates a positive response to the status inquiry.
At a minimum, this positive response indicates that the certificate
is not revoked, but does not necessarily mean that the certificate
was ever issued or that the time at which the response was produced
is within the certificate's validity interval. [...]

This is slightly different than the intuitive sense of good-ness, and I think it matches with your description.  Mr. Myers (et.al) could chime in, but I belive this definition was specifically chosen so that a responder could operate using only the CRL and not a DB of issued certs.  (Pre-signing aside.)

From: Stephen Kent
Sent: Fri 3/4/2005 6:43 PM
To: Robert Zuccherato
Cc: Russ Housley; [email-masked]
Subject: RE: [saag] X.509 certificate collision, via MD5 collisions

Steve

---

From: "Santosh Chokhani" <[email-masked]>
Date: Fri, 4 Mar 2005 20:19:01 -0500

Some of us have suggested that the Lenstra attack does not break
non-repudiation. I would like to add another evidence for NR.

If there is a dispute between the signer and the relying party and the
signer (or CA) and the relying party produce two certificates resulting in
the same hash, signer could be required to produce further evidence for the
modulii and one would notice that one of the factors is 512 bits for 2048
modulus, something FIPS does not recommend.  That would be viewed as
additional evidence of mischief by the subscriber.

Santosh Chokhani
Orion Security Solutions, Inc.
1489 Chain Bridge Road, Suite 300
McLean, Virginia 22101
(703) 917-0060  Ext. 35 (voice)
(703) 917-0260 (Fax)
[email-masked]
Visit our Web site
http://www.orionsec.com

---

From: "Michael Myers" <[email-masked]>
Date: Fri, 4 Mar 2005 19:53:57 -0700

RE: [saag] X.509 certificate collision, via MD5 collisionsThe cited text was
authored by Dave Solo in response to an ad-hoc caucus held many years ago in
Chicago, with Mack Hicks' concurrence. Dave's text was not written to ratify
reliance on CRLs, but rather to define the meaning of "good" in the context
of OCSP.

Mike

-----Original Message-----
From: [email-masked] [mailto:[email-masked]]On
Behalf Of Dave Engberg
Sent: Friday, March 04, 2005 6:16 PM
To: Stephen Kent; Robert Zuccherato
Cc: [email-masked]
Subject: RE: [saag] X.509 certificate collision, via MD5 collisions

I think Robert was using the formal RFC 2560 definition of "good":
     The "good" state indicates a positive response to the status inquiry.
     At a minimum, this positive response indicates that the certificate
     is not revoked, but does not necessarily mean that the certificate
     was ever issued or that the time at which the response was produced
     is within the certificate's validity interval. [...]
This is slightly different than the intuitive sense of good-ness, and I
think it matches with your description.  Mr. Myers (et.al) could chime in,
but I belive this definition was specifically chosen so that a responder
could operate using only the CRL and not a DB of issued certs.  (Pre-signing
aside.)

----------------------------------------------------------------------------
----
From: Stephen Kent
Sent: Fri 3/4/2005 6:43 PM
To: Robert Zuccherato
Cc: Russ Housley; [email-masked]
Subject: RE: [saag] X.509 certificate collision, via MD5 collisions

Steve

---

From: Denis Pinkas <[email-masked]>
Date: Mon, 07 Mar 2005 09:36:19 +0100

Santosh,

> the same hash, 

When RFC 3126 is used, then ESSCertID MUST be used as a signed attribute 
which means that not only there MUST be the same hash value but also the 
same CA DN and the same serial number.

    ESSCertID ::=  SEQUENCE {
         certHash                 Hash,
         issuerSerial             IssuerSerial OPTIONAL
    }

    Hash ::= OCTET STRING -- SHA1 hash of entire certificate

    IssuerSerial ::= SEQUENCE {
         issuer                   GeneralNames,
         serialNumber             CertificateSerialNumber
    }

Denis

> signer could be required to produce further evidence for the

---

From: Denis Pinkas <[email-masked]>
Date: Mon, 07 Mar 2005 15:50:13 +0100

Santosh,

> Denis,

> But, that alone will not support NR in case of the Lenstra attack since cert
> hash, issuer, and serial will be all the same.

But the collision is on the *content* of the certificate computed using MD5 
while ESSCertID requires the use of SHA-1 to compute a hash over the 
*entire* certificate.

This solves the issue.

Denis

> I think NR claim ties to showing Lenstra paper and then showing that forcing
> the subscriber to show the primes or private key to show that one of the
> primes for a 2048 modulus is only 512 bits (should be around 1024 bits).
> 
> From: [email-masked] [mailto:[email-masked]] On
> Behalf Of Denis Pinkas
> Sent: Monday, March 07, 2005 3:36 AM
> To: Santosh Chokhani
> Cc: [email-masked]
> Subject: Re: [saag] X.509 certificate collision, via MD5 collisions
> 
> 
> 
> Santosh,
> 
> 
>>signer (or CA) and the relying party produce two certificates 
>>resulting in the same hash,
> 
> 
>>signer could be required to produce further evidence for the modulii 
>>and one would notice that one of the factors is 512 bits for 2048

---

From: "Santosh Chokhani" <[email-masked]>
Date: Mon, 7 Mar 2005 08:35:56 -0500

Denis,

-----Original Message-----

Santosh,

    ESSCertID ::=  SEQUENCE {
         certHash                 Hash,

Denis

---

From: "Santosh Chokhani" <[email-masked]>
Date: Mon, 7 Mar 2005 12:27:16 -0500

Denis,

Thanks.  When 3126 is used, there is additional basis for NR.  That is good.

Thinking ahead for SHA-1 (assuming it has similar vulnerability), I wonder
if 3126 should be revised to use a different hashing algorithm than the one
used to sign the certificate to shore up the NR argument.

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On
Behalf Of Denis Pinkas
Sent: Monday, March 07, 2005 9:50 AM
To: Santosh Chokhani
Cc: [email-masked]
Subject: Re: [saag] X.509 certificate collision, via MD5 collisions

Santosh,

> But, that alone will not support NR in case of the Lenstra attack 
> since cert hash, issuer, and serial will be all the same.

This solves the issue.

Denis

> I think NR claim ties to showing Lenstra paper and then showing that 
> forcing the subscriber to show the primes or private key to show that 
> one of the primes for a 2048 modulus is only 512 bits (should be 
> around 1024 bits).
> 
> From: [email-masked] 
> [mailto:[email-masked]] On Behalf Of Denis Pinkas

---

From: Stephen Kent <[email-masked]>
Date: Mon, 7 Mar 2005 16:26:46 -0500

At 8:15 PM -0500 3/4/05, Dave Engberg wrote:
>This is slightly different than the intuitive sense of good-ness, 
>and I think it matches with your description.  Mr. Myers (et.al) 
>could chime in, but I belive this definition was specifically chosen 
>so that a responder could operate using only the CRL and not a DB of 
>issued certs.  (Pre-signing aside.)
>

If that is the context in which to interpret "good," then no problem.

Steve

---

From: Denis Pinkas <[email-masked]>
Date: Tue, 08 Mar 2005 09:39:07 +0100

Santosh,

> used to sign the certificate to shore up the NR argument.

No revision will be necessary, since RFC 3126 already includes that option 
in section "3.8.2  Other Signing Certificate Attribute Definition". I copy 
that section underneath:

    The following attribute is identical to the ESS SigningCertificate
    defined above except that this attribute can be used with hashing
    algorithms other than SHA-1.

    This attribute must be used in the same manner as defined above for
    the ESS SigningCertificate attribute.

    The following object identifier identifies the signing certificate
    attribute:

    id-aa-ets-otherSigCert OBJECT IDENTIFIER ::= { iso(1)
        member-body(2) us(840) rsadsi(113549) pkcs(1) pkcs9(9)
        smime(16) id-aa(2) 19 }

    The signing certificate attribute value has the ASN.1 syntax
    OtherSigningCertificate

    OtherSigningCertificate ::=  SEQUENCE {
        certs        SEQUENCE OF OtherCertID,
        policies     SEQUENCE OF PolicyInformation OPTIONAL
                     -- NOT USED IN THIS DOCUMENT
    }

    OtherCertID ::= SEQUENCE {
         otherCertHash            OtherHash,
         issuerSerial             IssuerSerial OPTIONAL
    }

    OtherHash ::= CHOICE {
        sha1Hash OtherHashValue,  -- This contains a SHA-1 hash
        otherHash OtherHashAlgAndValue
    }

    OtherHashValue ::= OCTET STRING

    OtherHashAlgAndValue ::= SEQUENCE {
      hashAlgorithm  AlgorithmIdentifier,
      hashValue      OtherHashValue
    }

Denis

---

From: Denis Pinkas <[email-masked]>
Date: Tue, 08 Mar 2005 09:38:50 +0100

Santosh,

> used to sign the certificate to shore up the NR argument.

No revision will be necessary, since RFC 3126 alrady includes that option in 
section "3.8.2  Other Signing Certificate Attribute Definition". I copy that 
section underneath:

    OtherHash ::= CHOICE {

Denis