Subject: [pkix] Questioning the benefit of random serials over sequential ones in x.509 certificates

From: "Piyush Jain" <[email-masked]>
Date: Fri, 14 Dec 2012 09:09:21 -0800

Hi All,

It seems that the current best practice is to use non-sequential serial
numbers when issuing x.509 certificates.

I understand that it had some value when weak hashing algorithms were being
used to create the signature.  
But if you are using a strong hashing algorithm, what is the benefit of
issuing certificates with random serial values?

Thanks a lot in advance for any insights.

-Piyush

---

From: Erwann Abalea <[email-masked]>
Date: Fri, 14 Dec 2012 18:25:42 +0100

Bonjour,

2012/12/14 Piyush Jain <[email-masked]>

> numbers when issuing x.509 certificates.

That's not only a "best practice", but also a requirement for several root
programs.

> used to create the signature.

It still has some value, because weak hash functions are still used in a
signature context. SHA1 isn't over.

> issuing certificates with random serial values?

I don't see any benefit in such a situation.

-- 
Erwann.

---

From: "Kemp, David P." <[email-masked]>
Date: Fri, 14 Dec 2012 17:34:16 +0000

Sparse namespaces are generic good security hygiene.  Data mining, like telemarketer robocalling, is enabled by compact namespaces, and the large random-looking URLs employed by, e.g., photo sharing websites are an attempt to make mining more difficult.

If the only way to retrieve a certificate from a directory or web repository is to know its name or serial number, then making valid S/Ns difficult to guess makes trawling more difficult and easier to detect.

Dave

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of Piyush Jain
Sent: Friday, December 14, 2012 12:09 PM
To: [email-masked]
Subject: [pkix] Questioning the benefit of random serials over sequential ones in x.509 certificates

Hi All,

It seems that the current best practice is to use non-sequential serial numbers when issuing x.509 certificates.

I understand that it had some value when weak hashing algorithms were being used to create the signature.  
But if you are using a strong hashing algorithm, what is the benefit of issuing certificates with random serial values?

-Piyush

_______________________________________________
pkix mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/pkix

---

From: "Piyush Jain" <[email-masked]>
Date: Fri, 14 Dec 2012 10:04:31 -0800

Thanks Erwann,

I’m not sure what value does a root CA gets out of this.

Since the intermediate certificates (issued by root) are also publicly visible, it does not matter if the serial is random or not.

Isn’t it true that this works only if the attacker does not have access to the issued certificate?

Assuming the PK certificates are not public is sort of counter-intuitive.

-Piyush

From: Erwann Abalea [mailto:[email-masked]] 
Sent: Friday, December 14, 2012 9:26 AM
To: Piyush Jain
Cc: [email-masked]
Subject: Re: [pkix] Questioning the benefit of random serials over sequential ones in x.509 certificates

Bonjour,

That's not only a "best practice", but also a requirement for several root programs.

It still has some value, because weak hash functions are still used in a signature context. SHA1 isn't over.

-- 
Erwann.

---

From: Erwann Abalea <[email-masked]>
Date: Fri, 14 Dec 2012 19:16:57 +0100

> I’m not sure what value does a root CA gets out of this.

When mentioning root programs, I'm talking about root inclusion into public
software (browsers, mainly), not certificates issued by the root CA. The
"random serial" requirement is to be applied to CA software that issue
end-user certificates.

> ****
>
> Since the intermediate certificates (issued by root) are also publicly
> visible, it does not matter if the serial is random or not.
>

This has nothing to do with secretly issued certificates, but with known
prefix collision attacks.

> ****
> Assuming the PK certificates are not public is sort of counter-intuitive.*
> ***
>
> **
>

I'm not sure I'm following you.
A certificate is a public object, for sure.
I can't imagine what could be the use of a CA software accepting
certificate requests but refusing access to the issued certificate.

*From:* Erwann Abalea [mailto:[email-masked]]
> *Sent:* Friday, December 14, 2012 9:26 AM
> *To:* Piyush Jain
> *Cc:* [email-masked]
> *Subject:* Re: [pkix] Questioning the benefit of random serials over
> sequential ones in x.509 certificates****
>
> ** **
>
> Bonjour,****
>
> 2012/12/14 Piyush Jain <[email-masked]>****
>
> numbers when issuing x.509 certificates.****
>
> ** **
>
> programs.****
>  ****
> used to create the signature.****
>
> ** **
>
> signature context. SHA1 isn't over.****
>
>  ****
>
> issuing certificates with random serial values?****
>
> ** **
>
> I don't see any benefit in such a situation.****
>
>  ****
>
> --
> Erwann.****
>

-- 
Erwann.

---

From: "Piyush Jain" <[email-masked]>
Date: Fri, 14 Dec 2012 10:17:13 -0800

Thanks David,

Please see inline.

> From: [email-masked] [mailto:[email-masked]] On Behalf Of
> Kemp, David P.
> Sent: Friday, December 14, 2012 9:34 AM
> To: [email-masked]
> Subject: Re: [pkix] Questioning the benefit of random serials over
sequential
> ones in x.509 certificates
> 
> Sparse namespaces are generic good security hygiene.  Data mining, like
> telemarketer robocalling, is enabled by compact namespaces, and the large
> random-looking URLs employed by, e.g., photo sharing websites are an
> attempt to make mining more difficult.
> 
[Piyush] Good analogy. But in this case it is applicable only if certificate
access is based on knowledge of the serial number.

> If the only way to retrieve a certificate from a directory or web
repository is
> to know its name or serial number, then making valid S/Ns difficult to
guess
> makes trawling more difficult and easier to detect.
> 
[Piyush] Are there such mechanisms in place for securing access to the
directory? Can't you achieve the same by using a combination of serial and
some other cert attribute such as CN?

> But if you are using a strong hashing algorithm, what is the benefit of
issuing
> certificates with random serial values?
>

---

From: "Piyush Jain" <[email-masked]>
Date: Fri, 14 Dec 2012 10:27:29 -0800

May be I am missing something very basic.

If the certificate is available to the attacker, how does random serial help avoid a prefix collision attack.

The attacker just forges another certificate with same serial and keeps on changing an extension with random value to force a hash collision.

Whether the serial in the certificate is random or not should not have any impact on the above process.

-Piyush

From: Erwann Abalea [mailto:[email-masked]] 
Sent: Friday, December 14, 2012 10:17 AM
To: Piyush Jain
Cc: [email-masked]
Subject: Re: [pkix] Questioning the benefit of random serials over sequential ones in x.509 certificates

When mentioning root programs, I'm talking about root inclusion into public software (browsers, mainly), not certificates issued by the root CA. The "random serial" requirement is to be applied to CA software that issue end-user certificates.

This has nothing to do with secretly issued certificates, but with known prefix collision attacks.

I can't imagine what could be the use of a CA software accepting certificate requests but refusing access to the issued certificate.

Bonjour,

-- 
Erwann.

-- 
Erwann.

---

From: "Schaen, Samuel I." <[email-masked]>
Date: Fri, 14 Dec 2012 18:51:33 +0000

From a practical perspective, use of random serial numbers precludes the use of OCSP pre-signed responses that rely on a CRL (rather than direct connection to a CA) and must produce responses for all possible certificates within the unexpired issuance range.

From: [email-masked] [mailto:[email-masked]] On Behalf Of Piyush Jain
Sent: Friday, December 14, 2012 1:27 PM
To: 'Erwann Abalea'
Cc: [email-masked]
Subject: Re: [pkix] Questioning the benefit of random serials over sequential ones in x.509 certificates

-Piyush

2012/12/14 Piyush Jain <[email-masked]<mailto:[email-masked]>>
I’m not sure what value does a root CA gets out of this.

From: Erwann Abalea [mailto:[email-masked]<mailto:[email-masked]>]
Sent: Friday, December 14, 2012 9:26 AM
To: Piyush Jain
Cc: [email-masked]<mailto:[email-masked]>
Subject: Re: [pkix] Questioning the benefit of random serials over sequential ones in x.509 certificates

Bonjour,
2012/12/14 Piyush Jain <[email-masked]<mailto:[email-masked]>>
It seems that the current best practice is to use non-sequential serial
numbers when issuing x.509 certificates.

--
Erwann.

--
Erwann.

---

From: Erwann Abalea <[email-masked]>
Date: Fri, 14 Dec 2012 19:59:17 +0100

> May be I am missing something very basic.****
>
> If the certificate is available to the attacker, how does random serial
> help avoid a prefix collision attack.****
>
> ** **
>
> The attacker just forges another certificate with same serial and keeps on
> changing an extension with random value to force a hash collision.
>

The attacker doesn't choose the serial number. If it's not random, it can
only guess it.
The attacker also can't choose the extensions it will have in its
certificate (or he might as well choose to simply get a
basicConstraints:CA=true certificate).
Maybe you're mistaking this attack with a complete CA compromise?

> impact on the above process.

You should read http://www.win.tue.nl/hashclash/rogue-ca/
It's well written.

> *Sent:* Friday, December 14, 2012 10:17 AM
>
> *To:* Piyush Jain
> *Cc:* [email-masked]
> I’m not sure what value does a root CA gets out of this.****
>
> ** **
>
> When mentioning root programs, I'm talking about root inclusion into
> public software (browsers, mainly), not certificates issued by the root CA.
> The "random serial" requirement is to be applied to CA software that issue
> end-user certificates.****
>
>  ****
>
> visible, it does not matter if the serial is random or not.****
>
> ** **
>
> prefix collision attacks.****
>
>  ****
>
> Isn’t it true that this works only if the attacker does not have access to
> the issued certificate?****
>
> I'm not sure I'm following you.****
>
> A certificate is a public object, for sure.****
>
> certificate requests but refusing access to the issued certificate.****
>
> ** **
>

-- 
Erwann.

---

From: Erwann Abalea <[email-masked]>
Date: Fri, 14 Dec 2012 20:01:43 +0100

That's right.
Some root programs accept the randomness to be added in the subjectName,
before any user-supplied data, in a dedicated AVA. That's acceptable.

2012/12/14 Schaen, Samuel I. <[email-masked]>

>  From a practical perspective, use of random serial numbers precludes the
> use of OCSP pre-signed responses that rely on a CRL (rather than direct
> connection to a CA) and must produce responses for all possible
> certificates within the unexpired issuance range.****
>
> ** **
>
> *From:* [email-masked] [mailto:[email-masked]] *On Behalf
> Of *Piyush Jain
> *Sent:* Friday, December 14, 2012 1:27 PM
> *To:* 'Erwann Abalea'
>
> *Cc:* [email-masked]
> changing an extension with random value to force a hash collision.****
>
> Whether the serial in the certificate is random or not should not have any
> impact on the above process.****
>
> ** **
>
> -Piyush****
>
> ** **
>
> ** **
>
>  Isn’t it true that this works only if the attacker does not have access
> to the issued certificate?****
>

-- 
Erwann.

---

From: "Piyush Jain" <[email-masked]>
Date: Fri, 14 Dec 2012 11:02:40 -0800

J You are a mind reader.

I guess you can consider it a benefit from certain perspectives.

From: Schaen, Samuel I. [mailto:[email-masked]] 
Sent: Friday, December 14, 2012 10:52 AM
To: Piyush Jain; 'Erwann Abalea'
Cc: [email-masked]
Subject: RE: [pkix] Questioning the benefit of random serials over sequential ones in x.509 certificates

-Piyush

 

Bonjour,

-- 
Erwann.

-- 
Erwann.

---

From: Santosh Chokhani <[email-masked]>
Date: Fri, 14 Dec 2012 14:04:21 -0500

Piyush,

This requires understanding what a collision attack is.  In layperson’s terms, the adversary who is a legitimate applicant for a certificate,  creates names and keys such when the CA signs a certificate, the hash will be the same as the adversary has created collision for while submitting the request.  Now the adversary can present the other certificate with basic constraint extension, with different name, or with different policies as issued by the CA.  In this process, the adversary while computing the collision needs to know the likely serial number the CA will assign, among other things. Randomizing serial number is one way of defeating the attack.  Putting randomness is not after is another.  Randomness needs to come before Subject DN since that is the most likely first input from the attacker when you scan the certificate.  My favorite is the parameter field in signature field since it is not supposed to be used.  But, I am afraid it is not practical since it will freak out most applications.

-Piyush

Bonjour,

--
Erwann.

--
Erwann.

---

From: "Kemp, David P." <[email-masked]>
Date: Fri, 14 Dec 2012 19:11:13 +0000

From: Piyush Jain [mailto:[email-masked]] 

> If the only way to retrieve a certificate from a directory
> or web repository is to know its name or serial number,
> then making valid S/Ns difficult to guess makes trawling
> more difficult and easier to detect.
 
[Piyush] Are there such mechanisms in place for securing access to the directory? Can't you achieve the same by using a combination of serial and some other cert attribute such as CN?

Sure, but why bother.  It isn't difficult for a CA to generate random (or "random-ish", as with AKI/SKI) serial numbers, and doing so mitigates both the weak hash security issue and the serial-only privacy issue.  IMO it's a generic good practice just like "don't use a key for more than one purpose".  Following good practices can head off problems that haven't been thought of yet.

As for Sam's pre-signed OCSP question, I'm not sure how an OCSP responder could pre-sign responses solely from a CRL without also having either a connection to the CA or a list of issued certs.  Where do the DN's in the responses come from if the only information available to the signer is a CRL?  If the issued list isn't updated fast enough, then update it faster :-).

---

From: "Piyush Jain" <[email-masked]>
Date: Fri, 14 Dec 2012 11:11:54 -0800

The goal of the attacker is to get Hash(m1) to be equal to Hash of(m2 + junk) to ensure that signatures on m1 and (m2+junk) are same

If m1 is visible to the attacker (public key certificate in this case), does the content of m1 really matter?

From: Erwann Abalea [mailto:[email-masked]] 
Sent: Friday, December 14, 2012 10:59 AM
To: Piyush Jain
Cc: [email-masked]
Subject: Re: [pkix] Questioning the benefit of random serials over sequential ones in x.509 certificates

The attacker doesn't choose the serial number. If it's not random, it can only guess it.

The attacker also can't choose the extensions it will have in its certificate (or he might as well choose to simply get a basicConstraints:CA=true certificate).

It's well written.

To: Piyush Jain
Cc: [email-masked]

Bonjour,

-- 
Erwann.

-- 
Erwann.

-- 
Erwann.

---

From: Santosh Chokhani <[email-masked]>
Date: Fri, 14 Dec 2012 14:18:08 -0500

Dave,

What DN are you talking about?  If the Responder has the CRL, it has the issuer DN.  It verifies the signature on the CRL using the issuer public key which it obtains using any proper means (say a certificate).

I do not see any other data required for request or response that Responder needs.

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of Kemp, David P.
Sent: Friday, December 14, 2012 2:11 PM
To: [email-masked]
Subject: Re: [pkix] Questioning the benefit of random serials over sequential ones in x.509 certificates

> repository is to know its name or serial number, then making valid 
> S/Ns difficult to guess makes trawling more difficult and easier to 
> detect.

---

From: "Piyush Jain" <[email-masked]>
Date: Fri, 14 Dec 2012 11:46:37 -0800

Thanks a lot Santosh. This clarifies things.

My assumption was that the attack happens after the certificate is issued. 

The attacker looks at the certificate and tries to forge a certificate with same hash by inserting an irrelevant extension and changing its contents.

So based on what you are saying, Is it correct to say that finding a prefix p1 such that Hash (m1) = Hash(m2+p1) is computationally much harder than finding prefixes p1 and p2 such that Hash(m1+p1) = Hash(m2+p2).

-Piyush

From: Santosh Chokhani [mailto:[email-masked]] 
Sent: Friday, December 14, 2012 11:04 AM
To: Piyush Jain; 'Erwann Abalea'
Cc: [email-masked]
Subject: RE: [pkix] Questioning the benefit of random serials over sequential ones in x.509 certificates

Piyush,

 

-Piyush

 

Bonjour,

-- 
Erwann.

-- 
Erwann.

---

From: Erwann Abalea <[email-masked]>
Date: Fri, 14 Dec 2012 20:52:43 +0100

> Thanks a lot Santosh. This clarifies things.****
>
> ** **
>
> The attacker looks at the certificate and tries to forge a certificate
> with same hash by inserting an irrelevant extension and changing its
> contents.
>

That's not a collision attack, but a second preimage attack. MD5 is still
resistant to this.

****
>
> So based on what you are saying, Is it correct to say that finding a
> prefix p1 such that Hash (m1) = Hash(m2+p1) is computationally much harder
> than finding prefixes p1 and p2 such that Hash(m1+p1) = Hash(m2+p2).
>
> **
>

p1 is not a prefix but a postfix here.

H(m1)=H(m1||p1) won't work here because of the structure of a certificate
(DER, encoded lengths, etc). It could work for other types of signed
objects.

H(m1||p1)=H(m2||p2) is a collision attack. Just replace it with H(n1)=H(n2).

> *From:* Santosh Chokhani [mailto:[email-masked]]
> *Sent:* Friday, December 14, 2012 11:04 AM
> *To:* Piyush Jain; 'Erwann Abalea'
> *Cc:* [email-masked]
> *Subject:* RE: [pkix] Questioning the benefit of random serials over
> Piyush,****
> This requires understanding what a collision attack is.  In layperson’s
> terms, the adversary who is a legitimate applicant for a certificate,
>  creates names and keys such when the CA signs a certificate, the hash will
> be the same as the adversary has created collision for while submitting the
> request.  Now the adversary can present the other certificate with basic
> constraint extension, with different name, or with different policies as
> issued by the CA.  In this process, the adversary while computing the
> collision needs to know the likely serial number the CA will assign, among
> other things. Randomizing serial number is one way of defeating the
> attack.  Putting randomness is not after is another.  Randomness needs to
> come before Subject DN since that is the most likely first input from the
> attacker when you scan the certificate.  My favorite is the parameter field
> in signature field since it is not supposed to be used.  But, I am afraid
> it is not practical since it will freak out most applications.****
>
> ** **
>
> ** **
>
> *From:* Erwann Abalea [mailto:[email-masked] <[email-masked]>]

-- 
Erwann.

---

From: "Kemp, David P." <[email-masked]>
Date: Fri, 14 Dec 2012 19:53:40 +0000

Santosh,

You are correct.  For some reason my old brain got the idea that OCSP requests and responses contained subject DNs.  I have no clue where that came from, since:

   CertID          ::=     SEQUENCE {
       hashAlgorithm       AlgorithmIdentifier,
       issuerNameHash      OCTET STRING, -- Hash of Issuer's DN
       issuerKeyHash       OCTET STRING, -- Hash of Issuers public key
       serialNumber        CertificateSerialNumber }

As Roseanne Rosannadanna said, "never mind".

However, a list of issued CertificateSerialNumber's could be distributed to OCSP responders that don't have a direct CA connection, in addition to CRLs.  That is an added complication, but hardly an engineering challenge.

Dave

-----Original Message-----
From: Santosh Chokhani [mailto:[email-masked]] 
Sent: Friday, December 14, 2012 2:18 PM
To: Kemp, David P.; [email-masked]
Subject: RE: [pkix] Questioning the benefit of random serials over sequential ones in x.509 certificates

Dave,

---

From: "Piyush Jain" <[email-masked]>
Date: Fri, 14 Dec 2012 11:55:04 -0800

Actually the pre-signing model that Sam referred to is heavily deployed in
enterprises. 
The responder computes the namehash (or keyhash) from the CA certificate.
Revoked response is generated for serials in the CRL and good for everything
that is not in the CRL.
Assumption about the range of issued serials is made by looking at the
smallest and the largest serial in the CRL.

> Sent: Friday, December 14, 2012 11:11 AM
> To: [email-masked]
sequential
> Sure, but why bother.  It isn't difficult for a CA to generate random (or
> "random-ish", as with AKI/SKI) serial numbers, and doing so mitigates both
> the weak hash security issue and the serial-only privacy issue.  IMO it's
a
> generic good practice just like "don't use a key for more than one
purpose".
> Following good practices can head off problems that haven't been thought
of
> yet.
> 
> As for Sam's pre-signed OCSP question, I'm not sure how an OCSP responder
> could pre-sign responses solely from a CRL without also having either a
> connection to the CA or a list of issued certs.  Where do the DN's in the
> responses come from if the only information available to the signer is a
CRL?
> If the issued list isn't updated fast enough, then update it faster :-).

---

From: Santosh Chokhani <[email-masked]>
Date: Fri, 14 Dec 2012 15:03:18 -0500

Piyush,

I am not a crypto mathematician  So, I do not consider myself qualified to answer the question you pose.

I can say that what you assumed is called a second pre-image and would entail a work factor on the order of hash size.

From: Piyush Jain [mailto:[email-masked]]
Sent: Friday, December 14, 2012 2:47 PM
To: Santosh Chokhani; 'Erwann Abalea'
Cc: [email-masked]
Subject: RE: [pkix] Questioning the benefit of random serials over sequential ones in x.509 certificates

-Piyush

Piyush,

From: [email-masked]<mailto:[email-masked]> [mailto:[email-masked]]<mailto:[mailto:[email-masked]]> On Behalf Of Piyush Jain
Sent: Friday, December 14, 2012 1:27 PM
To: 'Erwann Abalea'
Cc: [email-masked]<mailto:[email-masked]>
Subject: Re: [pkix] Questioning the benefit of random serials over sequential ones in x.509 certificates

-Piyush

Bonjour,

--
Erwann.

--
Erwann.

---

From: "Miller, Timothy J." <[email-masked]>
Date: Mon, 17 Dec 2012 13:27:59 +0000

Theoretically, we could dispense with SNs altogether, given a robust SKID.

-- T

>Sent: Friday, December 14, 2012 12:34 PM
>To: [email-masked]
>If the only way to retrieve a certificate from a directory or web repository is to
>know its name or serial number, then making valid S/Ns difficult to guess
>Piyush Jain

---

From: "Miller, Timothy J." <[email-masked]>
Date: Mon, 17 Dec 2012 13:32:12 +0000

Randomizing the low-order bits of the validity dates is my favorite.  No-one would notice.

-- T

>Santosh Chokhani
>Sent: Friday, December 14, 2012 2:04 PM
>This requires understanding what a collision attack is.  In layperson’s terms,
>the adversary who is a legitimate applicant for a certificate,  creates names
>and keys such when the CA signs a certificate, the hash will be the same as the
>adversary has created collision for while submitting the request.  Now the
>adversary can present the other certificate with basic constraint extension,
>with different name, or with different policies as issued by the CA.  In this
>process, the adversary while computing the collision needs to know the likely
>serial number the CA will assign, among other things. Randomizing serial
>number is one way of defeating the attack.  Putting randomness is not after is
>another.  Randomness needs to come before Subject DN since that is the
>most likely first input from the attacker when you scan the certificate.  My
>favorite is the parameter field in signature field since it is not supposed to be
>used.  But, I am afraid it is not practical since it will freak out most applications.
>
>
>
>
>
>impact on the above process.
>
>
>
>-Piyush
>
>
>
>
>
>"random serial" requirement is to be applied to CA software that issue end-
>user certificates.
>
>
>
>the issued certificate?
>I can't imagine what could be the use of a CA software accepting certificate
>requests but refusing access to the issued certificate.
>
>
>
>sequential ones in x.509 certificates
>
>
>
>	Bonjour,
>

---

From: "Miller, Timothy J." <[email-masked]>
Date: Mon, 17 Dec 2012 13:43:35 +0000

That's a preimage attack, which have an average case of 2^(hashlen-1).  Collision attacks have an average case of 2^(hashlen/2).

Ref. the Hashclash project, Marc Stevens, Arjen Lenstra, et.al.  Also Marc's analysis of the Flame certificates.  Great work.

-- T

>To: 'Santosh Chokhani'; 'Erwann Abalea'
>Cc: [email-masked]
>The attacker looks at the certificate and tries to forge a certificate with same
>hash by inserting an irrelevant extension and changing its contents.
>
>
>
>So based on what you are saying, Is it correct to say that finding a prefix p1
>such that Hash (m1) = Hash(m2+p1) is computationally much harder than
>finding prefixes p1 and p2 such that Hash(m1+p1) = Hash(m2+p2).
>
>
>
>-Piyush
>
>
>
>
>
>
>

---

From: Santosh Chokhani <[email-masked]>
Date: Mon, 17 Dec 2012 09:28:33 -0500

No.  There is no requirement for SKID in the Standards.  It is simply an advisory thing.

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of Miller, Timothy J.
Sent: Monday, December 17, 2012 8:28 AM
To: 'Kemp, David P.'; [email-masked]
Subject: Re: [pkix] Questioning the benefit of random serials over sequential ones in x.509 certificates

-- T

>telemarketer robocalling, is enabled by compact namespaces, and the 
>large random-looking URLs employed by, e.g., photo sharing websites are 
>an attempt to make mining more difficult.
>
>repository is to know its name or serial number, then making valid S/Ns 
>difficult to guess makes trawling more difficult and easier to detect.
>
>Dave
>
>

---

From: "Miller, Timothy J." <[email-masked]>
Date: Mon, 17 Dec 2012 16:38:17 +0000

There comes a time when even standards should change.  I'm not advocating, I'm just pointing it out.

-- T

>Sent: Monday, December 17, 2012 9:29 AM
>To: Miller, Timothy J.; 'Kemp, David P.'; [email-masked]
>Miller, Timothy J.

---

From: "Piyush Jain" <[email-masked]>
Date: Mon, 17 Dec 2012 09:05:19 -0800

I think the problem with using SKID is that key life is different from cert
life.

So using keyed as a way to identify a cert could be problematic in cert
rollover scenarios or in situation where you have multiple certificates
associated with same key.

> Sent: Monday, December 17, 2012 8:38 AM
> To: 'Santosh Chokhani'; 'Kemp, David P.'; [email-masked]
sequential
> >>Sparse namespaces are generic good security hygiene.  Data mining,
> >>like telemarketer robocalling, is enabled by compact namespaces, and
> >>the large random-looking URLs employed by, e.g., photo sharing
> >>websites are an attempt to make mining more difficult.
> >>
detect.
> >>It seems that the current best practice is to use non-sequential
> >>serial numbers when issuing x.509 certificates.
> >>
> >>But if you are using a strong hashing algorithm, what is the benefit
> >>of issuing certificates with random serial values?
> >>

---

From: [email-masked] (Martin Rex)
Date: Mon, 17 Dec 2012 20:34:14 +0100 (CET)

Erwann Abalea wrote:
> <[email-masked]>

+1

>> May be I am missing something very basic.****

I believe you do (about the type of attack, collision vs. pre-image).

>> help avoid a prefix collision attack.****

I increases the work-factor for the attacker for pre-computing collisions,
but does not quite prevent the attack.

I believe that having the CA insert a dummy non-critical extension with
a strong random 128+ bit random OctetString would achieve better protection
without abusing/spoiling the serial numbers.

>> changing an extension with random value to force a hash collision.

The key point in understanding the "rogue CA" attack is, that under
the special conditions of CA cert issuance, creating a pair of
 [validly issued cert, rogue cert] can be made to succeed for a 
hash collision with a chosen internal hash state, it is _unnecessary_
to succeed a preimage attack.

If all of what the CA adds when issuing a cert is static and pre-known,
then it is up to the attacker to make a part of the key (such as the RSA
public modulus) collide with a part of an adequately tailored rogue
cert, and submit a certification request with the hash-colliding key parameter.

-Martin

---

From: Santosh Chokhani <[email-masked]>
Date: Mon, 17 Dec 2012 14:39:45 -0500

Others have suggested adding an extension to defeat the collision attack.

It shows lack of understanding of the attack.

You can put as many extensions as you like and put as many random number as you wish in them, they WILL NOT defeat the prefix attack as long as the size of those extension is known.  All of that junk will go in the so called tumor.

If the size of the extension itself and hence the size of the certificate itself changes, that mitigates the threat somewhat, but that is a silly logarithmic benefit. 

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of Martin Rex
Sent: Monday, December 17, 2012 2:34 PM
To: Erwann Abalea
Cc: [email-masked]
Subject: Re: [pkix] Questioning the benefit of random serials over sequential ones in x.509 certificates

+1

>>
>> If the certificate is available to the attacker, how does random 
>> serial help avoid a prefix collision attack.****

I increases the work-factor for the attacker for pre-computing collisions, but does not quite prevent the attack.

I believe that having the CA insert a dummy non-critical extension with a strong random 128+ bit random OctetString would achieve better protection without abusing/spoiling the serial numbers.

>>
>> The attacker just forges another certificate with same serial and 
>> keeps on changing an extension with random value to force a hash collision.

The key point in understanding the "rogue CA" attack is, that under the special conditions of CA cert issuance, creating a pair of  [validly issued cert, rogue cert] can be made to succeed for a hash collision with a chosen internal hash state, it is _unnecessary_ to succeed a preimage attack.

If all of what the CA adds when issuing a cert is static and pre-known, then it is up to the attacker to make a part of the key (such as the RSA public modulus) collide with a part of an adequately tailored rogue cert, and submit a certification request with the hash-colliding key parameter.

-Martin

---

From: [email-masked] (Martin Rex)
Date: Mon, 17 Dec 2012 21:10:00 +0100 (CET)

> It shows lack of understanding of the attack.

I believe that is incorrect.

> 
> You can put as many extensions as you like and put as many random number
> as you wish in them, they WILL NOT defeat the prefix attack as long as
> the size of those extension is known.  All of that junk will go in the
> so called tumor.

There is no "tumor" in the *REAL* (validly issued) certificate.
That blob only exists in the rogue cert of the pair.

(Looking at the picture in Section 5.3 of this page:
  http://www.win.tue.nl/hashclash/rogue-ca/ )

The reason is, that everything that the real CA puts into the ToBeSigned
part of a cert is covered by the hash of the CA-created digital signature.

-Martin

---

From: Santosh Chokhani <[email-masked]>
Date: Mon, 17 Dec 2012 15:14:58 -0500

The tumor in the rogue certificate is why the collision attack is not defeated by adding an extension whose size is known.  The actual certificate and the rogue certificate hashes will continue to match.

Have you read Lenstra paper?  Do you get it?

-----Original Message-----
From: Martin Rex [mailto:[email-masked]] 
Sent: Monday, December 17, 2012 3:10 PM
To: Santosh Chokhani
Cc: [email-masked]; Erwann Abalea; [email-masked]
Subject: Re: [pkix] Questioning the benefit of random serials over sequential ones in x.509 certificates

> 
> You can put as many extensions as you like and put as many random 
> number as you wish in them, they WILL NOT defeat the prefix attack as 
> long as the size of those extension is known.  All of that junk will 
> go in the so called tumor.

The reason is, that everything that the real CA puts into the ToBeSigned part of a cert is covered by the hash of the CA-created digital signature.

-Martin

---

From: [email-masked] (Martin Rex)
Date: Mon, 17 Dec 2012 21:21:49 +0100 (CET)

OK, you were correct.

What your probably meant (but I didn't understand) is that the octets
representing the extensions which the CA includes in the cert, are still
present 1:1 in the rogue cert, but due to how ASN.1 DER encoding works,
these attributes are no longer active since they're inside the body part
of an unrecognized extension (the "tumor") in the rogue cert.

So the part of the rogue cert, that contains the CA-supplied extensions
and the actual CA signature, becomes known when the CA issues the cert,
and its contents do otherwise not impair the creation of the rogue cert.

I'm sorry for the confusion.

-Martin

---

From: Santosh Chokhani <[email-masked]>
Date: Mon, 17 Dec 2012 15:26:06 -0500

Yes, except "active" is a red herring again.  If you are throwing in random meaningless extensions, RP is not going to check them and hence active and passive is not a meaningless distinction.

The basic thing to understand is that the subject DN is the first input from the user and it has potential for sufficient fidelity that unless you put randomness before the subject DN, you are inviting trouble.

-----Original Message-----
From: Martin Rex [mailto:[email-masked]] 
Sent: Monday, December 17, 2012 3:22 PM
To: [email-masked]
Cc: Santosh Chokhani; Erwann Abalea; [email-masked]
Subject: Re: [pkix] Questioning the benefit of random serials over sequential ones in x.509 certificates

OK, you were correct.

What your probably meant (but I didn't understand) is that the octets representing the extensions which the CA includes in the cert, are still present 1:1 in the rogue cert, but due to how ASN.1 DER encoding works, these attributes are no longer active since they're inside the body part of an unrecognized extension (the "tumor") in the rogue cert.

So the part of the rogue cert, that contains the CA-supplied extensions and the actual CA signature, becomes known when the CA issues the cert, and its contents do otherwise not impair the creation of the rogue cert.

-Martin

Martin Rex wrote:
> > number as you wish in them, they WILL NOT defeat the prefix attack 
> > as long as the size of those extension is known.  All of that junk 
> > will go in the so called tumor.
> 
> The reason is, that everything that the real CA puts into the 
> ToBeSigned part of a cert is covered by the hash of the CA-created digital signature.
> 
> 
> -Martin

---

From: [email-masked] (Martin Rex)
Date: Tue, 18 Dec 2012 03:59:18 +0100 (CET)

Santosh Chokhani wrote:
>
> Yes, except "active" is a red herring again.
> If you are throwing in random meaningless extensions, RP is not going to
> check them and hence active and passive is not a meaningless distinction.
> 
> The basic thing to understand is that the subject DN is the first input
> from the user and it has potential for sufficient fidelity that unless
> you put randomness before the subject DN, you are inviting trouble.

IMHO the thing to understand is that the composition, field ordering
and fairly unlimited extensibility of X.509v3 is what enables
a mere collision attack (with two distinct internal states) to
achieve what would normally require a 2nd preimage attack.

Looking at TBSCertificate:

TBSCertificate  ::=  SEQUENCE  {
     version         [0]  Version DEFAULT v1,
     serialNumber         CertificateSerialNumber,
     signature            AlgorithmIdentifier,
     issuer               Name,
     validity             Validity,
     subject              Name,
     subjectPublicKeyInfo SubjectPublicKeyInfo,
     issuerUniqueID  [1]  IMPLICIT UniqueIdentifier OPTIONAL,
                          -- If present, version MUST be v2 or v3
     subjectUniqueID [2]  IMPLICIT UniqueIdentifier OPTIONAL,
                          -- If present, version MUST be v2 or v3
     extensions      [3]  Extensions OPTIONAL
                          -- If present, version MUST be v3 --  }

maybe the AlgorithmIdententifier is finally not as useless as I
thought.  If there was more support for RSA-PSS (aka PKCS#1 v2.1)
signatures in the installed base, the CA would be able to sign
the EE-Cert with a RSA-PSS AlgId that has a random, hash-sized salt
in the signature AlgorithmIdentifier parameters field...

-Martin