Subject: [pkix] Range responses in OCSP

From: Piyush Jain <[email-masked]>
Date: Thu, 15 Mar 2012 13:57:04 -0700

In the other OCSP thread, PHB proposed  range responses in OCSP to represent "not issued" certificates.I'll leave the discussion of possible status values to that thread.
However, that idea of returning the status of a list of serial number can be very useful in existing OCSP deployments that pre-sign the responses.
There are few limitations with one status/serial number in OCSP if the responder is getting its information from the CRL.- No way to generate OCSP responses ahead of time for CAs that issue certificates with non-sequential serial numbers- Size of collection of pre-signed OCSP responses is much bigger when compared to CRLS.- Number of signatures required to create OCSP responses for the population of issued certificates is huge.
All of these issues could be addressed if an OCSP response can associate a status with a range of serial numbers, as opposed to a single serial number.
Thoughts?
-Piyush

---

From: Santosh Chokhani <[email-masked]>
Date: Thu, 15 Mar 2012 17:08:50 -0400

I remain concerned about these added features without a discussion of the need.

As I mentioned previously, if the concern is CA compromise, this does not help unless trust in the Responder is established independent of trust in the CA that issued the certificate in question.

From: [email-masked] [mailto:[email-masked]] On Behalf Of Piyush Jain
Sent: Thursday, March 15, 2012 4:57 PM
To: [email-masked]
Subject: [pkix] Range responses in OCSP

In the other OCSP thread, PHB proposed  range responses in OCSP to represent "not issued" certificates.
I'll leave the discussion of possible status values to that thread.

There are few limitations with one status/serial number in OCSP if the responder is getting its information from the CRL.
- No way to generate OCSP responses ahead of time for CAs that issue certificates with non-sequential serial numbers
- Size of collection of pre-signed OCSP responses is much bigger when compared to CRLS.
- Number of signatures required to create OCSP responses for the population of issued certificates is huge.

Thoughts?

-Piyush

---

From: Piyush Jain <[email-masked]>
Date: Thu, 15 Mar 2012 14:36:04 -0700

Santosh,
I understand and agree with you concern about CA compromise that you raised in the other thread.However, this proposal is simply optimizes the representation of same information that current OCSP protocol supports.
Consider the example where you need to represent the status of certificates with serial number 1 to 10000 and none of those certificate serials are listed in the CRL.
To comply with current OCSP specification, a responder would generate 10000 responsed (10000 signatures). If it is bundling multiple serial numbers in one response, lets say 20, then it would need to sign 500 responses. In either case, these 10000 serials would need to be explicitly listed in one or more OCSP responses.
With the range approach, the responder can just create one response which says, start serial is 1, end serial is 10000 and the status is good.
-Piyush
From: [email-masked]
To: [email-masked]; [email-masked]
Date: Thu, 15 Mar 2012 17:08:50 -0400
Subject: RE: [pkix] Range responses in OCSP

I remain concerned about these added features without a discussion of the need.
As I mentioned previously, if the concern is CA compromise, this does not help unless trust in the Responder is established independent of trust in the CA that issued the certificate in question. From: [email-masked] [mailto:[email-masked]] On Behalf Of Piyush Jain
Sent: Thursday, March 15, 2012 4:57 PM
To: [email-masked]
Subject: [pkix] Range responses in OCSP In the other OCSP thread, PHB proposed  range responses in OCSP to represent "not issued" certificates.I'll leave the discussion of possible status values to that thread. However, that idea of returning the status of a list of serial number can be very useful in existing OCSP deployments that pre-sign the responses. There are few limitations with one status/serial number in OCSP if the responder is getting its information from the CRL.- No way to generate OCSP responses ahead of time for CAs that issue certificates with non-sequential serial numbers- Size of collection of pre-signed OCSP responses is much bigger when compared to CRLS.- Number of signatures required to create OCSP responses for the population of issued certificates is huge. All of these issues could be addressed if an OCSP response can associate a status with a range of serial numbers, as opposed to a single serial number. Thoughts? -Piyush

---

From: Robert Kisteleki <[email-masked]>
Date: Fri, 16 Mar 2012 08:51:38 +0100

> With the range approach, the responder can just create one response which
> says, start serial is 1, end serial is 10000 and the status is good.

But then it only applies if the serial is actually a sequence number;
there's zero benefit in case the serial is a hash or semi-random value. Are
there CAs out there that still use sequence numbers?

Robert

---

From: "Miller, Timothy J." <[email-masked]>
Date: Fri, 16 Mar 2012 12:54:58 +0000

>there CAs out there that still use sequence numbers?

Yes.

-- T

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Fri, 16 Mar 2012 09:10:01 -0400

I hope they are not doing so with SHA1.

On Fri, Mar 16, 2012 at 8:54 AM, Miller, Timothy J. <[email-masked]> wrote:
> _______________________________________________
> pkix mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/pkix

-- 
Website: http://hallambaker.com/

---

From: Erwann Abalea <[email-masked]>
Date: Fri, 16 Mar 2012 16:05:10 +0100

2012/3/16 Phillip Hallam-Baker <[email-masked]>

> I hope they are not doing so with SHA1.

They probably do. Governmental PKIs used for biometric passports use
sequential serial numbers (nearly all of them), some of them still use
SHA1, with RSA or ecDSA.

One can guess that a government PKI used for MRTD is informed of good
practices to use and deduce that a "garage-made" CA has a lot of chances to
do more bad things.

The first guess is obviously wrong.

-- 
Erwann.

---

From: brennan security <[email-masked]>
Date: Fri, 16 Mar 2012 12:05:02 -0400

Piyush,

I was thinking of some of the same things, and apparently some other people
are too.. http://www.links.org/files/sunlight.html

The change I was thinking included Merkle hash trees used with statements,
previously called Certificate Good Trees?

I don't know if that would be a good solution though.

regards,

-b

On Thu, Mar 15, 2012 at 4:57 PM, Piyush Jain <[email-masked]> wrote:

> However, that idea of returning the status of a list of serial number can
> be very useful in existing OCSP deployments that pre-sign the responses.
>
> There are few limitations with one status/serial number in OCSP if the
> responder is getting its information from the CRL.
> - No way to generate OCSP responses ahead of time for CAs that issue
> certificates with non-sequential serial numbers
> - Number of signatures required to create OCSP responses for the
> population of issued certificates is huge.
>
> All of these issues could be addressed if an OCSP response can associate a
> status with a range of serial numbers, as opposed to a single serial number.
>
> Thoughts?
>
> -Piyush
>
>
>
>

---

From: "Miller, Timothy J." <[email-masked]>
Date: Fri, 16 Mar 2012 17:21:29 +0000

>I hope they are not doing so with SHA1.

I'm familiar with the certificate collision work from Lenstra et.al. and
I'm sure that this specific use is currently safe even with MD5.
Certificates from the PKI in question are not completely unconstrained;
the public keys and other data fields further down in TBSCertificate are
checked by the system for reasonableness and receive human review, so
there's no place where a significant collision resistance attack could be
mounted.

-- T

---

From: [email-masked]
Date: Fri, 16 Mar 2012 18:41:16 +0100

Tim,

You said that "there's no place where a significant collision resistance 
attack could be mounted".

Humm! I can include a non critical extension that nobody recognizes and 
according to RFC 5280 rules, 
it will be ignored and then the certificate will not be declared invalid 
because this extension is present.

Within this extension, I can place a bit string and then I have all the 
data I need to compute a match.

Denis

De :    "Miller, Timothy J." <[email-masked]>
A :     Phillip Hallam-Baker <[email-masked]>
Cc :    "[email-masked]" <[email-masked]>
Date :  16/03/2012 18:21
Objet : Re: [pkix] Range responses in OCSP
Envoyé par :    [email-masked]

-- T

---

From: "Ryan Hurst" <[email-masked]>
Date: Fri, 16 Mar 2012 20:51:33 -0700

As others have pointed out the ability to do ranges is essentially dependent
on serial numbers being non-random values, in the context of publicly
trusted roots the two largest root programs (MSFT and MOZ) basically require
random serial numbers, the Microsoft text is the clearest, you can find it
here: http://social.technet.microsoft.com/wiki/contents/articles/1760.aspx

Additional Security for Intermediate and End-Entity Certificates (random
value)

1.       For all intermediate and end-entity certificates issued after
December 31, 2010, the CA must include an 8-byte random or pseudo-random
value in either the Serial Number certificate field or the first component
of the Subject Name certificate field.
a.      This requirement is for all certificates signed with SHA1, and
optional but recommended for certificates signed with SHA2 until SHA2 begins
to show weakness to collision attacks.
b.      By SerialNumber field, Microsoft does not refer to the serial number
component of the subject name, identified by OID 2.5.4.5.  
c.       The random number must appear before all other fields in the
Subject Name.
d.      The random or pseudo-random number generator must be provided by an
operating system or by a hardware crypto module.
e.      There is also the possibility of a 3-byte random value in the
Hour:Minute:Second part of the Validity Period field.  This 3-byte random
value is shorter than the 8-byte value for other certificate fields, but if
there is no other option to introduce a random value, it will mitigate a
potential attack and will be accepted.

The Mozilla language is a little more flexible, it is here:
http://www.mozilla.org/projects/security/certs/policy/MaintenancePolicy.html

We expect CAs to maintain current best practices to prevent algorithm
attacks against certificates. As such, the following steps will be taken:

.         all new end-entity certificates must contain at least 20 bits of
unpredictable random data (preferably in the serial number).

In both cases the text is pretty bad in my opinion in that one could
interpret conformance a few ways but its clear (due to SHA1 collisions) they
have adopted a policy that in-net should result in all CAs using random
numbers for serial numbers.

With that said I like the idea of ranges, in the 90s we (ValiCert - as I am
sure Piyush remembers) did this with Certificate Revocation Trees which was
a signed Merkel Hash Tree based revocation scheme.

Ryan

From: [email-masked] [mailto:[email-masked]] On Behalf Of
Piyush Jain
Sent: Thursday, March 15, 2012 2:36 PM
To: [email-masked]; [email-masked]
Subject: Re: [pkix] Range responses in OCSP

Santosh,

I understand and agree with you concern about CA compromise that you raised
in the other thread.

However, this proposal is simply optimizes the representation of same
information that current OCSP protocol supports.

Consider the example where you need to represent the status of certificates
with serial number 1 to 10000 and none of those certificate serials are
listed in the CRL.

To comply with current OCSP specification, a responder would generate 10000
responsed (10000 signatures). If it is bundling multiple serial numbers in
one response, lets say 20, then it would need to sign 500 responses. In
either case, these 10000 serials would need to be explicitly listed in one
or more OCSP responses.

-Piyush

  _____  

I remain concerned about these added features without a discussion of the
need.

As I mentioned previously, if the concern is CA compromise, this does not
help unless trust in the Responder is established independent of trust in
the CA that issued the certificate in question.

From: [email-masked] [mailto:[email-masked]] On Behalf Of
Piyush Jain
Sent: Thursday, March 15, 2012 4:57 PM
To: [email-masked]
Subject: [pkix] Range responses in OCSP

In the other OCSP thread, PHB proposed  range responses in OCSP to represent
"not issued" certificates.

However, that idea of returning the status of a list of serial number can be
very useful in existing OCSP deployments that pre-sign the responses.

- Size of collection of pre-signed OCSP responses is much bigger when
compared to CRLS.

- Number of signatures required to create OCSP responses for the population
of issued certificates is huge.

Thoughts?

-Piyush

---

From: Piyush Jain <[email-masked]>
Date: Fri, 16 Mar 2012 22:10:13 -0700

Ryan,

Ability to do ranges is actually more useful in pre-signing if the serial numbers are big random numbers.
Without ranges it is computationally infeasible to pre-sign OCSP responses for large random serials if the responder does not have access to issued serial list.

-Piyush

From: [email-masked]
To: [email-masked]; [email-masked]; [email-masked]
Subject: RE: [pkix] Range responses in OCSP
Date: Fri, 16 Mar 2012 20:51:33 -0700

As others have pointed out the ability to do ranges is essentially dependent on serial numbers being non-random values, in the context of publicly trusted roots the two largest root programs (MSFT and MOZ) basically require random serial numbers, the Microsoft text is the clearest, you can find it here: http://social.technet.microsoft.com/wiki/contents/articles/1760.aspxAdditional Security for Intermediate and End-Entity Certificates (random value)1.       For all intermediate and end-entity certificates issued after December 31, 2010, the CA must include an 8-byte random or pseudo-random value in either the Serial Number certificate field or the first component of the Subject Name certificate field.
a.      This requirement is for all certificates signed with SHA1, and optional but recommended for certificates signed with SHA2 until SHA2 begins to show weakness to collision attacks.
b.      By SerialNumber field, Microsoft does not refer to the serial number component of the subject name, identified by OID 2.5.4.5.  
c.       The random number must appear before all other fields in the Subject Name.
d.      The random or pseudo-random number generator must be provided by an operating system or by a hardware crypto module.
e.      There is also the possibility of a 3-byte random value in the Hour:Minute:Second part of the Validity Period field.  This 3-byte random value is shorter than the 8-byte value for other certificate fields, but if there is no other option to introduce a random value, it will mitigate a potential attack and will be accepted.The Mozilla language is a little more flexible, it is here: http://www.mozilla.org/projects/security/certs/policy/MaintenancePolicy.html We expect CAs to maintain current best practices to prevent algorithm attacks against certificates. As such, the following steps will be taken:·         all new end-entity certificates must contain at least 20 bits of unpredictable random data (preferably in the serial number).  In both cases the text is pretty bad in my opinion in that one could interpret conformance a few ways but its clear (due to SHA1 collisions) they have adopted a policy that in-net should result in all CAs using random numbers for serial numbers. With that said I like the idea of ranges, in the 90s we (ValiCert – as I am sure Piyush remembers) did this with Certificate Revocation Trees which was a signed Merkel Hash Tree based revocation scheme. RyanFrom: [email-masked] [mailto:[email-masked]] On Behalf Of Piyush Jain
Sent: Thursday, March 15, 2012 2:36 PM
To: [email-masked]; [email-masked]
Subject: Re: [pkix] Range responses in OCSP Santosh, I understand and agree with you concern about CA compromise that you raised in the other thread.However, this proposal is simply optimizes the representation of same information that current OCSP protocol supports. Consider the example where you need to represent the status of certificates with serial number 1 to 10000 and none of those certificate serials are listed in the CRL. To comply with current OCSP specification, a responder would generate 10000 responsed (10000 signatures). If it is bundling multiple serial numbers in one response, lets say 20, then it would need to sign 500 responses. In either case, these 10000 serials would need to be explicitly listed in one or more OCSP responses.
With the range approach, the responder can just create one response which says, start serial is 1, end serial is 10000 and the status is good. -PiyushFrom: [email-masked]
To: [email-masked]; [email-masked]
Date: Thu, 15 Mar 2012 17:08:50 -0400
Subject: RE: [pkix] Range responses in OCSPI remain concerned about these added features without a discussion of the need.
As I mentioned previously, if the concern is CA compromise, this does not help unless trust in the Responder is established independent of trust in the CA that issued the certificate in question. From: [email-masked] [mailto:[email-masked]] On Behalf Of Piyush Jain
Sent: Thursday, March 15, 2012 4:57 PM
To: [email-masked]
Subject: [pkix] Range responses in OCSP In the other OCSP thread, PHB proposed  range responses in OCSP to represent "not issued" certificates.I'll leave the discussion of possible status values to that thread. However, that idea of returning the status of a list of serial number can be very useful in existing OCSP deployments that pre-sign the responses. There are few limitations with one status/serial number in OCSP if the responder is getting its information from the CRL.- No way to generate OCSP responses ahead of time for CAs that issue certificates with non-sequential serial numbers- Size of collection of pre-signed OCSP responses is much bigger when compared to CRLS.- Number of signatures required to create OCSP responses for the population of issued certificates is huge. All of these issues could be addressed if an OCSP response can associate a status with a range of serial numbers, as opposed to a single serial number. Thoughts? -Piyush

---

From: Paul Hoffman <[email-masked]>
Date: Sat, 17 Mar 2012 08:01:03 -0700

My reading of the Microsoft and Mozilla requirements is that the serial number must have a random component of the given size, but does not have to be all random. After the Lenstra paper came out, some CAs went to serial numbers that were sequential (the high-order bits were a counter) with a random component in the low-order bits. That scheme does seem to work for the Microsoft and Mozilla rules as long as the serial number is greater than 64 or 20 bits long, respectively. Of course, it is up to Microsoft and Mozilla to decide this, not us.

--Paul Hoffman

---

From: Piyush Jain <[email-masked]>
Date: Sat, 17 Mar 2012 08:01:10 -0700

> Date: Fri, 16 Mar 2012 08:51:38 +0100
> From: [email-masked]
> To: [email-masked]
> CC: [email-masked]
> But then it only applies if the serial is actually a sequence number;It applies for non sequential serial numbers as well. Actually, it is impossible (in practice) to pre-sign responses for non sequential CAs if the responder does not have access to the list of issued serial numbers. In most enterprise deployments, that's the case.
Consider this example where CRL has 2 entries00-12............................................34 andFF-FE.............................................FD
A detached responder cannot presign responses based on this CRL because range of non revoked certificates is too big. If there is a provision for range responses, the responder can pre-sign following 5 entries and capture all the information provided in the CRL.1. -infinity to 00-12............................................34 - 1  (good)2. 00-12............................................34 (revoked)3. 00-12............................................34 to FF-FE.............................................FD (good)4. FF-FE.............................................FD (revoked)5 FF-FE.............................................FD to +infinity (good)

---

From: Santosh Chokhani <[email-masked]>
Date: Sat, 17 Mar 2012 11:15:33 -0400

For the hash collision, why not add random skew to the validity period and leave the serial number alone as sequential.

Another option which is really cool, but will screw some or all applications is to put randomness in the parameters field of signature field since this is supposed to be ignored anyway.  I see little benefit from security viewpoint to verify that the parameters are "NULL" (e.g.. for RSA).

I do not see why MSFT or Mozilla should dictate a solution when better options can be had to defeat the collision threat.

Finally, the number of bits is also an issue in my mind.  One should not worry about bit security, but work factor.  Given, the time it takes to craft a collision attack and even if you give the attacker a generous speed of one hour, 20 bits of randomness is more than sufficient since it results in over one million possibilities and 100 year work factor.

From: [email-masked] [mailto:[email-masked]] On Behalf Of Piyush Jain
Sent: Saturday, March 17, 2012 11:01 AM
To: [email-masked]
Cc: [email-masked]
Subject: Re: [pkix] Range responses in OCSP

> From: [email-masked]<mailto:[email-masked]>
> To: [email-masked]<mailto:[email-masked]>
> CC: [email-masked]<mailto:[email-masked]>
It applies for non sequential serial numbers as well. Actually, it is impossible (in practice) to pre-sign responses for non sequential CAs if the responder does not have access to the list of issued serial numbers. In most enterprise deployments, that's the case.

Consider this example where CRL has 2 entries
00-12............................................34 and
FF-FE.............................................FD

A detached responder cannot presign responses based on this CRL because range of non revoked certificates is too big. If there is a provision for range responses, the responder can pre-sign following 5 entries and capture all the information provided in the CRL.
1. -infinity to 00-12............................................34 - 1  (good)
2. 00-12............................................34 (revoked)
3. 00-12............................................34 to FF-FE.............................................FD (good)
4. FF-FE.............................................FD (revoked)
5 FF-FE.............................................FD to +infinity (good)

---

From: "Ryan Hurst" <[email-masked]>
Date: Sat, 17 Mar 2012 09:19:25 -0700

Paul,

I agree that the text allows for lower order bits containing the minimum
necessary random data and keeping the upper bits sequential as well as other
fields where the required randomness can be present.

With that said it's my belief that many CAs supported pure random serial
numbers and as such quite a few simply enabled this capability as their
resolution to the issue highlighted by the Lenstra paper.

I am not saying this precludes the project, it just limits its
applicability.

Ryan

-----Original Message-----
From: Paul Hoffman [mailto:[email-masked]] 
Sent: Saturday, March 17, 2012 8:01 AM
To: Ryan Hurst
Cc: PKIX
Subject: Re: [pkix] Range responses in OCSP

My reading of the Microsoft and Mozilla requirements is that the serial
number must have a random component of the given size, but does not have to
be all random. After the Lenstra paper came out, some CAs went to serial
numbers that were sequential (the high-order bits were a counter) with a
random component in the low-order bits. That scheme does seem to work for
the Microsoft and Mozilla rules as long as the serial number is greater than
64 or 20 bits long, respectively. Of course, it is up to Microsoft and
Mozilla to decide this, not us.

--Paul Hoffman

---

From: Paul Hoffman <[email-masked]>
Date: Sat, 17 Mar 2012 09:32:21 -0700

> I am not saying this precludes the project, it just limits its

Is it possible for someone to do a survey? This seems like something fairly easy for the CA/Browser Forum to answer.

--Paul Hoffman

---

From: Stefan Santesson <[email-masked]>
Date: Sun, 18 Mar 2012 23:48:52 +0100

Trying to return to the actual question I would like to take up in
Santosh's question.

What problem is this trying to solve?

Why would it not be enough to just craft one standard response saying "I
have no record of the certificate you are asking for"?
Yes, it would not be a signed proof that this is not a replay sent by Eve
in order to fool you to reject a perfectly valid cert.

But it would be an indication that something is fishy here and should be
investigated.

Either you have a MitM swapping the OCSP responses, or you have a bad OCSP
responder, or you have a compromised CA.
Time to push the alarm and figure out what's wrong.

What more would you get from prefabricating all these OCSP range responses?

/Stefan

---

From: Santosh Chokhani <[email-masked]>
Date: Sun, 18 Mar 2012 21:18:29 -0400

Stefan,

I have no objection to adding a response type (If you think unknown is not sufficient).

This will require a change to the standard, and the two classes of COTS: Responders and Clients. 

This group has also rejected my advice for a need for client side processing rules for 2560.  It would be good to identify what the clients are supposed to do with this.

Finally, we do not want this to be the mechanism advertised as the way to detect the possible CA compromise.  It simply gives us false sense of security.

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of Stefan Santesson
Sent: Sunday, March 18, 2012 6:49 PM
To: 'PKIX'
Subject: Re: [pkix] Range responses in OCSP

Trying to return to the actual question I would like to take up in Santosh's question.

Why would it not be enough to just craft one standard response saying "I have no record of the certificate you are asking for"?
Yes, it would not be a signed proof that this is not a replay sent by Eve in order to fool you to reject a perfectly valid cert.

But it would be an indication that something is fishy here and should be investigated.

Either you have a MitM swapping the OCSP responses, or you have a bad OCSP responder, or you have a compromised CA.
Time to push the alarm and figure out what's wrong.

/Stefan

---

From: "Ryan Hurst" <[email-masked]>
Date: Sun, 18 Mar 2012 19:09:18 -0700

It is, if its work the WG decides to take on Phil or I can take this up in
CA/Browser forum.

Ryan

-----Original Message-----
From: Paul Hoffman [mailto:[email-masked]] 
Sent: Saturday, March 17, 2012 9:32 AM
To: Ryan Hurst
Cc: 'PKIX'
Subject: Re: [pkix] Range responses in OCSP

On Mar 17, 2012, at 9:19 AM, Ryan Hurst wrote:

> I agree that the text allows for lower order bits containing the 
> minimum necessary random data and keeping the upper bits sequential as 
> well as other fields where the required randomness can be present.
> 
> With that said it's my belief that many CAs supported pure random 
> serial numbers and as such quite a few simply enabled this capability 
> as their resolution to the issue highlighted by the Lenstra paper.
> 

Is it possible for someone to do a survey? This seems like something fairly
easy for the CA/Browser Forum to answer.

--Paul Hoffman

---

From: Stefan Santesson <[email-masked]>
Date: Mon, 19 Mar 2012 03:18:53 +0100

OK,

Just to be clear, I did not propose to add any response type.
The question was meant to be hypothetical.

That is, if the solution which is asked for might as well be solved by a
simpler solution, then there is no point in discussing a more complex
solution.
It still remains to be determined that there is a problem worth solving.

/Stefan

On 12-03-19 2:18 AM, "Santosh Chokhani" <[email-masked]> wrote:

>This group has also rejected my advice for a need for client side
>processing rules for 2560.  It would be good to identify what the clients
>are supposed to do with this.
>
>Finally, we do not want this to be the mechanism advertised as the way to
>detect the possible CA compromise.  It simply gives us false sense of
>security.
>
>Stefan Santesson
>Either you have a MitM swapping the OCSP responses, or you have a bad
>OCSP responder, or you have a compromised CA.

---

From: Piyush Jain <[email-masked]>
Date: Sun, 18 Mar 2012 20:57:26 -0700

I think the proposal to have OCSP support range responses should be discussed separately from the proposal to add "does not exist" response.
Range response is just an optimal way of packing a large number of single responses in one OCSP response.
This is how pre-signing of OCSP is done today.One (or more) more keyed responders create a list of OCSP responses which is then mirrored to multiple keyless responders. Relying parties use these keyless responders to check the status of certificates. One OCSP response is usually packed with status of muliple certificates to minimize the number of signings. However, the trade off is that the OCSP response gets bloated.
Problem:1) The current representation of OCSP response is inefficient. Let's say that the range of issued certificates by a CA is 'M' and the number of revoked certificates in the CRL is 'N'. We know that typically M is much bigger than N. Using the current OCSP response representation , you need to create M  responses to account for every serial number that the CA issued. Using ranges you could  achieve the same thing using at most 2*N + 1 responses ( Think of it as an efficient representation of a sparse array). 
2)For CAs that issue certificates using random serial numbers, M is so big that it becomes computationally  impossible to pre-sign responses for those CAs unless the responder has access to the CA database. 
Range response will facilitate pre-signing of OCSP responses for CAs that issue certificates with non sequential serial numbers and reduce the computation and bandwidth requirements even for CAs who issue certificates with sequential serial numbers.
-Piyush
> Date: Sun, 18 Mar 2012 23:48:52 +0100
> From: [email-masked]
> To: [email-masked]

---

From: Stefan Santesson <[email-masked]>
Date: Mon, 19 Mar 2012 11:35:14 +0100

My fear is that this will glue CAs to sequential serial numbers and prevent
them from moving to non sequential serial numbers when needed.

/Stefan

From:  Piyush Jain <[email-masked]>
Date:  Sun, 18 Mar 2012 20:57:26 -0700
To:  Stefan Santesson <[email-masked]>, <[email-masked]>
Subject:  Re: [pkix] Range responses in OCSP

> I think the proposal to have OCSP support range responses should be discussed
> separately from the proposal to add "does not exist" response.
> 
> This is how pre-signing of OCSP is done today.
> One (or more) more keyed responders create a list of OCSP responses which is
> then mirrored to multiple keyless responders. Relying parties use these
> keyless responders to check the status of certificates. One OCSP response is
> usually packed with status of muliple certificates to minimize the number of
> signings. However, the trade off is that the OCSP response gets bloated.
> 
> Problem:
> 1) The current representation of OCSP response is inefficient. Let's say that
> the range of issued certificates by a CA is 'M' and the number of revoked
> certificates in the CRL is 'N'. We know that typically M is much bigger than
> N. Using the current OCSP response representation , you need to create M
> responses to account for every serial number that the CA issued. Using ranges
> you could  
> achieve the same thing using at most 2*N + 1 responses ( Think of it as an
> efficient representation of a sparse array).
> 
> 2)For CAs that issue certificates using random serial numbers, M is so big
> that it becomes computationally  impossible to pre-sign responses for those
> CAs unless the responder has access to the CA database.
> 
> Range response will facilitate pre-signing of OCSP responses for CAs that
> issue certificates with non sequential serial numbers and reduce the
> computation and bandwidth requirements even for CAs who issue certificates
> with sequential serial numbers.
> 
> -Piyush
> 
> _______________________________________________ pkix mailing list
> [email-masked] https://www.ietf.org/mailman/listinfo/pkix

---

From: "Miller, Timothy J." <[email-masked]>
Date: Mon, 19 Mar 2012 12:35:37 +0000

> For the hash collision, why not add random skew to the validity period and leave the serial number alone as sequential.

I've always preferred this method.  A random wiggle to the low-order time bits would have essentially no observable impact.  :)

-- T

---

From: "Miller, Timothy J." <[email-masked]>
Date: Mon, 19 Mar 2012 12:42:34 +0000

> Range response is just an optimal way of packing a large number of single responses in one OCSP response.

I concur.  I could use OCSP response ranges to significantly reduce pre-signing workload in a deployed enterprise PKI. 

Of course, I'd still have the installed base to worry about, but in the enterprise environment this is more approachable.  I can redirect non-enterprise requests to a keyed responder.  We only use keyless responders internally.

-- T

---

From: "Miller, Timothy J." <[email-masked]>
Date: Mon, 19 Mar 2012 12:45:03 +0000

On Mar 16, 2012, at 12:41 PM, <[email-masked]>
 wrote:

> You said that "there's no place where a significant collision resistance attack could be mounted". 

> Humm! I can include a non critical extension that nobody recognizes and according to RFC 5280 rules, 
> it will be ignored and then the certificate will not be declared invalid because this extension is present. 

> Within this extension, I can place a bit string and then I have all the data I need to compute a match. 

A fair point.   Caught me thinking sloppily again.  I forgot the case where the collision candidates are only computed in the cert the CA will never see.  :)

However, for SHA1 it's still computationally infeasible.  For now.  

-- T

---

From: Piyush Jain <[email-masked]>
Date: Mon, 19 Mar 2012 07:53:26 -0700

On the contrary, it'll address the objections to move to non sequential numbers.
There are installations today that are using the unadvertised feature in Microsoft CA to generate sequential serial numbers, just because the current OCSP spec makes pre-signing for certificates with random serial numbers impossible.
-Piyush
Date: Mon, 19 Mar 2012 11:35:14 +0100
Subject: Re: [pkix] Range responses in OCSP
From: [email-masked]
To: [email-masked]; [email-masked]

My fear is that this will glue CAs to sequential serial numbers and prevent them from moving to non sequential serial numbers when needed.
/Stefan

---

From: Santosh Chokhani <[email-masked]>
Date: Mon, 19 Mar 2012 11:06:17 -0400

Piyush,

If the serial numbers truly random, how would you do this without declaring unissued certificates as valid?

I suspect you are saying that if the CA is compromised, all of this does not matter and if the CA is not compromised, declaring unissued as legitimate hurts nothing.

Is this what you are saying.  If so, this is yet another reason not to include never issued.

BTW, the most folks deal with pre-signing today by having multiple responses in a pre-signed bundle.  The bundle is generally configurable and I have seen bundle size as high as 20, reducing the signing workload by a factor of 20.

From: [email-masked] [mailto:[email-masked]] On Behalf Of Piyush Jain
Sent: Monday, March 19, 2012 10:53 AM
To: [email-masked]; [email-masked]
Subject: Re: [pkix] Range responses in OCSP

-Piyush
________________________________
Date: Mon, 19 Mar 2012 11:35:14 +0100
Subject: Re: [pkix] Range responses in OCSP
From: [email-masked]<mailto:[email-masked]>
To: [email-masked]<mailto:[email-masked]>; [email-masked]<mailto:[email-masked]>
My fear is that this will glue CAs to sequential serial numbers and prevent them from moving to non sequential serial numbers when needed.

/Stefan

From: Piyush Jain <[email-masked]<mailto:[email-masked]>>
Date: Sun, 18 Mar 2012 20:57:26 -0700
To: Stefan Santesson <[email-masked]<mailto:[email-masked]>>, <[email-masked]<mailto:[email-masked]>>
Subject: Re: [pkix] Range responses in OCSP

This is how pre-signing of OCSP is done today.
One (or more) more keyed responders create a list of OCSP responses which is then mirrored to multiple keyless responders. Relying parties use these keyless responders to check the status of certificates. One OCSP response is usually packed with status of muliple certificates to minimize the number of signings. However, the trade off is that the OCSP response gets bloated.

Problem:
1) The current representation of OCSP response is inefficient. Let's say that the range of issued certificates by a CA is 'M' and the number of revoked certificates in the CRL is 'N'. We know that typically M is much bigger than N. Using the current OCSP response representation , you need to create M  responses to account for every serial number that the CA issued. Using ranges you could
achieve the same thing using at most 2*N + 1 responses ( Think of it as an efficient representation of a sparse array).

-Piyush

> From: [email-masked]<mailto:[email-masked]>
> To: [email-masked]<mailto:[email-masked]>
> [email-masked]<mailto:[email-masked]>
_______________________________________________ pkix mailing list [email-masked]<mailto:[email-masked]> https://www.ietf.org/mailman/listinfo/pkix

---

From: Piyush Jain <[email-masked]>
Date: Tue, 20 Mar 2012 12:59:55 -0700

I thought that I had responded to this but Santosh pointed out that I did not.So here we go.

From: [email-masked]
To: [email-masked]; [email-masked]; [email-masked]
Date: Mon, 19 Mar 2012 11:06:17 -0400
Subject: RE: [pkix] Range responses in OCSP

Piyush, If the serial numbers truly random, how would you do this without declaring unissued certificates as valid?[Piyush] Since the RP does the signature verification before sending the OCSP request, responder returning 'good' for unissued certificates is a non issue. i

I suspect you are saying that if the CA is compromised, all of this does not matter and if the CA is not compromised, declaring unissued as legitimate hurts nothing.[Piyush]  Right on Target Is this what you are saying.  If so, this is yet another reason not to include never issued.[Piyush] Even if not issued is included, the responder can use ranges to pre-sign not issued status. Not that i believe that 'not issued' serves a purpose big enough  to be made part of the standard. BTW, the most folks deal with pre-signing today by having multiple responses in a pre-signed bundle.  The bundle is generally configurable and I have seen bundle size as high as 20, reducing the signing workload by a factor of 20.[Piyush]  That's true. Very familiar with this model. However, this does not help with pre-signing for CAs that issue certs with non sequential certificates.
 From: [email-masked] [mailto:[email-masked]] On Behalf Of Piyush Jain
Sent: Monday, March 19, 2012 10:53 AM
To: [email-masked]; [email-masked]
Subject: Re: [pkix] Range responses in OCSP On the contrary, it'll address the objections to move to non sequential numbers. There are installations today that are using the unadvertised feature in Microsoft CA to generate sequential serial numbers, just because the current OCSP spec makes pre-signing for certificates with random serial numbers impossible. -PiyushDate: Mon, 19 Mar 2012 11:35:14 +0100
Subject: Re: [pkix] Range responses in OCSP
From: [email-masked]
To: [email-masked]; [email-masked] fear is that this will glue CAs to sequential serial numbers and prevent them from moving to non sequential serial numbers when needed. /Stefan From: Piyush Jain <[email-masked]>
Date: Sun, 18 Mar 2012 20:57:26 -0700
To: Stefan Santesson <[email-masked]>, <[email-masked]>
Subject: Re: [pkix] Range responses in OCSP I think the proposal to have OCSP support range responses should be discussed separately from the proposal to add "does not exist" response. Range response is just an optimal way of packing a large number of single responses in one OCSP response. This is how pre-signing of OCSP is done today.One (or more) more keyed responders create a list of OCSP responses which is then mirrored to multiple keyless responders. Relying parties use these keyless responders to check the status of certificates. One OCSP response is usually packed with status of muliple certificates to minimize the number of signings. However, the trade off is that the OCSP response gets bloated. Problem:1) The current representation of OCSP response is inefficient. Let's say that the range of issued certificates by a CA is 'M' and the number of revoked certificates in the CRL is 'N'. We know that typically M is much bigger than N. Using the current OCSP response representation , you need to create M  responses to account for every serial number that the CA issued. Using ranges you could  achieve the same thing using at most 2*N + 1 responses ( Think of it as an efficient representation of a sparse array).  2)For CAs that issue certificates using random serial numbers, M is so big that it becomes computationally  impossible to pre-sign responses for those CAs unless the responder has access to the CA database.  Range response will facilitate pre-signing of OCSP responses for CAs that issue certificates with non sequential serial numbers and reduce the computation and bandwidth requirements even for CAs who issue certificates with sequential serial numbers. -Piyush > Date: Sun, 18 Mar 2012 23:48:52 +0100
> https://www.ietf.org/mailman/listinfo/pkix_______________________________________________ pkix mailing list [email-masked] https://www.ietf.org/mailman/listinfo/pkix

---

From: Santosh Chokhani <[email-masked]>
Date: Tue, 20 Mar 2012 16:25:02 -0400

Piyush,

Random serial numbers do not necessarily mean you need range capability for pre-signing.  An alternative is Responder accessing the CA database to create the responses.

Note that the range response does not fix the problem with the pre-signed response for the certificates issued during the time window since the previous pre-signing.  This will also require access to CA database or accepting the newly issued certificates without the status information.  To my knowledge there are no standards or product capabilities in this area.

From: Piyush Jain [mailto:[email-masked]]
Sent: Tuesday, March 20, 2012 4:00 PM
To: Santosh Chokhani; [email-masked]; [email-masked]
Subject: RE: [pkix] Range responses in OCSP

I thought that I had responded to this but Santosh pointed out that I did not.
So here we go.
From: [email-masked]<mailto:[email-masked]>
To: [email-masked]<mailto:[email-masked]>; [email-masked]<mailto:[email-masked]>; [email-masked]<mailto:[email-masked]>
Date: Mon, 19 Mar 2012 11:06:17 -0400
Subject: RE: [pkix] Range responses in OCSP
Piyush,

If the serial numbers truly random, how would you do this without declaring unissued certificates as valid?
[Piyush] Since the RP does the signature verification before sending the OCSP request, responder returning 'good' for unissued certificates is a non issue. i

[Piyush]  Right on Target

Is this what you are saying.  If so, this is yet another reason not to include never issued.
[Piyush] Even if not issued is included, the responder can use ranges to pre-sign not issued status. Not that i believe that 'not issued' serves a purpose big enough  to be made part of the standard.

BTW, the most folks deal with pre-signing today by having multiple responses in a pre-signed bundle.  The bundle is generally configurable and I have seen bundle size as high as 20, reducing the signing workload by a factor of 20.
[Piyush]  That's true. Very familiar with this model. However, this does not help with pre-signing for CAs that issue certs with non sequential certificates.

From: [email-masked]<mailto:[email-masked]> [mailto:[email-masked]]<mailto:[mailto:[email-masked]]> On Behalf Of Piyush Jain
Sent: Monday, March 19, 2012 10:53 AM
To: [email-masked]<mailto:[email-masked]>; [email-masked]<mailto:[email-masked]>
Subject: Re: [pkix] Range responses in OCSP

-Piyush

/Stefan

Problem:

-Piyush

---

From: Piyush Jain <[email-masked]>
Date: Tue, 20 Mar 2012 13:35:48 -0700

Santosh,
That's why I said that it is needed for responders who do not have access to CA database.You  of most people, with you experience with some of the largest PKIs would know that in most large scale enterprise OCSP deployments responders are detached from the CA and pre-sign responses based on CRLs alone.
I'm aware of at least one product that uses the approach that you stated below and its all based on custom protocol/mechanisms that are used to share the list of issued serials between the CA and the responder.

From: [email-masked]
To: [email-masked]; [email-masked]; [email-masked]
Date: Tue, 20 Mar 2012 16:25:02 -0400
Subject: RE: [pkix] Range responses in OCSP

Piyush, Random serial numbers do not necessarily mean you need range capability for pre-signing.  An alternative is Responder accessing the CA database to create the responses. Note that the range response does not fix the problem with the pre-signed response for the certificates issued during the time window since the previous pre-signing.  This will also require access to CA database or accepting the newly issued certificates without the status information.  To my knowledge there are no standards or product capabilities in this area. From: Piyush Jain [mailto:[email-masked]] 
Subject: RE: [pkix] Range responses in OCSP I thought that I had responded to this but Santosh pointed out that I did not.So here we go.From: [email-masked]
Subject: RE: [pkix] Range responses in OCSPPiyush, If the serial numbers truly random, how would you do this without declaring unissued certificates as valid?[Piyush] Since the RP does the signature verification before sending the OCSP request, responder returning 'good' for unissued certificates is a non issue. i I suspect you are saying that if the CA is compromised, all of this does not matter and if the CA is not compromised, declaring unissued as legitimate hurts nothing.[Piyush]  Right on Target Is this what you are saying.  If so, this is yet another reason not to include never issued.[Piyush] Even if not issued is included, the responder can use ranges to pre-sign not issued status. Not that i believe that 'not issued' serves a purpose big enough  to be made part of the standard. BTW, the most folks deal with pre-signing today by having multiple responses in a pre-signed bundle.  The bundle is generally configurable and I have seen bundle size as high as 20, reducing the signing workload by a factor of 20.[Piyush]  That's true. Very familiar with this model. However, this does not help with pre-signing for CAs that issue certs with non sequential certificates.  From: [email-masked] [mailto:[email-masked]] On Behalf Of Piyush Jain