Subject: Re: [pkix] AuthKeyId and CrlEntryExtension.CertificateIssuer

From: Martin Rex <[email-masked]>
Date: Wed, 15 Feb 2012 01:11:10 +0100 (MET)

Erwann Abalea wrote:
> 
> "Martin Rex":
> >
> > Santosh Chokhani wrote:
> > >
> > > Originally, CRL DP was designed to partition the CRL.
> > > If CRL DP is not included in a certificate, that certificate
> > > cannot go in a partition.
> > >
> > > When you ignore a critical IDP extension in CRL, you are insecure.
> 
> This point is important.
>
> If you ignore a *critical* extension, then you fail. Completely. You're
> free to ignore any non critical extension (at least in X.509, not RFC5280),
> but if you encounter a critical extension that you don't understand, you
> MUST reject the object.

I would agree to criticality of X.509 certificate(!) extensions,
but I believe that the expectations are unjusitified with respect
to criticial CRL extensions (and entirely misled about criticial
CRLEntryExtensions)

The default configuration for CRL checking, similar to OCSP checking
is to *not* hard-fail.  Sticking one's head in the sand about this
is not going to change reality.

>From the definition of the IssuingDistributionPoint CRL Extension:

   http://tools.ietf.org/html/rfc5280#section-5.2.5

   5.2.5. Issuing Distribution Point

   The issuing distribution point is a critical CRL extension that
   identifies the CRL distribution point and scope for a particular CRL,
   and it indicates whether the CRL covers revocation for end entity
   certificates only, CA certificates only, attribute certificates only,
   or a limited set of reason codes.  Although the extension is
   critical, conforming implementations are not required to support this
   extension.  However, implementations that do not support this
   extension MUST either treat the status of any certificate not listed
   on this CRL as unknown or locate another CRL that does not contain
   any unrecognized critical extensions.

Scoping of the CRL by the Distribution Point, rather than by
"entity certificates ony, CA certificates only, attributes certificates only
 or a limited set of reason codes" goes beyond the specified design goals,
so don't be surprised if it breaks.

The wording of the last sentences is particularly confusing:

                      However, implementations that do not support this
   extension MUST either treat the status of any certificate not listed
   on this CRL as unknown or locate another CRL that does not contain
   any unrecognized critical extensions.

"unknown" is not a status known to the CRL Validation algorithm in
section 6.2.  And while our implementation (the software module above the
ASN.1 parser) does not "support this extension", the ASN.1 parser of our
implementation *DOES* recognize it. 

> 
> > If someone fubars his PKI so badly, so that there is no
> > CRL DP with full scope listed in his certs, or that the CRL
> > returned from that URL is unusable for the promised purpose,
> > then for our RP the customer will have to manually configure a download
> > URL for that issuerName so that our CRL cache can populated/updated
> > out-of-band with conforming CRLs ... or disable revocation checking
> > for that issuerName.
> 
> Would you trust such a CA?

That question does not apply to us.

We do not ship a single CA as pretrusted with out implementation,
our customers have to configure *each* CA that they want to trust
explicitly.  And because of buggy PKI software and non-conforming CAs,
there is a non-marginal amount of non-conformance that your PKI
software has to tolerate.

Keep in mind that rfc5280 is VERY explicit about being liberal
about conformance during certificate path validation:

   http://tools.ietf.org/html/rfc5280#page-72

   Therefore, the algorithm only includes checks to verify that the
   certification path is valid according to X.509 and does not include
   checks to verify that the certificates and CRLs conform to this
   profile.  While the algorithm could be extended to include checks for
   conformance to the profiles in Sections 4 and 5, this profile
   RECOMMENDS against including such checks.

So rfc5280 explicitly RECOMMENDS against including conformance checks
from Section 5 of rfc5280, and that includes 5.2.5 Issuing Distribution Point
above!

So one may claim conformance to PKIX rfc5280 in spite of ignoring
conformance checks from Sections 4 & 5 of rfc5280.  That is what it says. 

-Martin

---

From: Tomas Gustavsson <[email-masked]>
Date: Wed, 15 Feb 2012 09:30:12 +0100

<snip>

> so don't be surprised if it breaks.

That is probably the only CRL partitioning that actually does not exists
in the wild(?).
I know of at least two used CRL partitioning schemes out there and both
target the same use case. The common use case for CRL partitioning is to
limit the size of CRLs. CRLs basically only consists of entity
certificates, so the suggested partitioning scheme in rfc seems totally
redundant.
Naturally RPs must understand CRL partitioning, it's out there in the wild.
There's nothing wrong with designing your validation code to a specific
use case of course. If you know these CRL partitioning schemes are not
used in your environment, skip it. The standard for CRL partitioning is
extremely open ended though, and also used so.

The only safe implementation in your software module is to break if it
encounters an unsupported critical extension (not the asn.1 parser of
course but your software on top of it).

Current CRL partitioning schemes that I know of are:
- Limiting a certain max no of entries per CRL
- Issuing different CRLs for different cert classes, i.e. one CRL for
signature certs, and another (or none at all) for auth certs (because
the RPs use OCSP).

Cheers,
Tomas

---

From: Tom Gindin <[email-masked]>
Date: Wed, 15 Feb 2012 22:37:02 -0500

Martin:

        I think you're misreading that sentence.  One of the examples in 
RFC 5280 section 5 is "a set of certificates based on arbitrary local 
information, such as 'all certificates issued to the NIST employees 
located in Boulder'", which cannot be done if the scope criteria is 
limited to certificate type or reason code.
        There was a lot of discussion about this extension and possible 
alternatives in April '98 (see 
http://www.ietf.org/mail-archive/web/pkix/current/msg22720.html).  One of 
the alternative proposals described some of the reasoning as follows:
CRL partitioning involves two functions:

(a)  a CRL location function, which allows for a certificate-using system 
to find a CRL applicable to a given certificate;
(b)  a certificate-CRL validation function, which provides for the 
certificate-using system to confirm that a CRL to hand is indeed an 
applicable CRL for the certificate under consideration.

The CDP mechanism merged these two functions into one mechanism.  In 
contrast, the OpenCDP mechanism separates these two functions and thereby 
achieves various benefits. 
        It's clear that you don't need function b) if there is a CRL 
containing all certificates for the specified issuer.  So CRL DP has 
always enabled partitioning, and the broken piece is not a PKI which uses 
partitioning but rather a general-purpose RP library which cannot support 
such partitioning.

Tom Gindin
P.S. - The opinions above are mine, and not necessarily those of my 
employer

From:   Martin Rex <[email-masked]>
To:     [email-masked] (Erwann Abalea), 
Cc:     [email-masked]
Date:   02/14/2012 07:12 PM
Subject:        Re: [pkix] AuthKeyId and 
CrlEntryExtension.CertificateIssuer
Sent by:        [email-masked]

Scoping of the CRL by the Distribution Point, rather than by
"entity certificates ony, CA certificates only, attributes certificates 
only
 or a limited set of reason codes" goes beyond the specified design goals,
so don't be surprised if it breaks.

So rfc5280 explicitly RECOMMENDS against including conformance checks
from Section 5 of rfc5280, and that includes 5.2.5 Issuing Distribution 
Point
above!

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

---

From: "Kemp, David P." <[email-masked]>
Date: Thu, 16 Feb 2012 09:14:35 -0500

To reinforce Tom's point, Section 5.2.5 says:

   identifies the CRL distribution point and scope for a particular CRL,
   **and** it indicates whether the CRL covers revocation for end entity
   certificates only, CA certificates only, attribute certificates only,
   or a limited set of reason codes.

(emphasis added).  It doesn't say identifies scope **by** indicating
reason code; IDP allows partitioning by local scope **in addition to**
reason code.

CAs with large subscriber populations benefit from limiting the size of
CRLs to subsets of the population - in many cases it is better to have
1000 small CRLs covering 1000 subscribers each than a single gigantic
CRL covering 1,000,000 subscribers, because the RP's download overhead
is 1000 times less when validating a single certificate.  An
implementation (above the ASN.1 parser) that does not correctly support
IDP will fail (not be suitable for use in) in any size-optimized
environment.

Dave

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of
Tom Gindin
Sent: Wednesday, February 15, 2012 10:37 PM
To: [email-masked]
Cc: [email-masked]
Subject: Re: [pkix] AuthKeyId and CrlEntryExtension.CertificateIssuer

        Martin:

http://www.ietf.org/mail-archive/web/pkix/current/msg22720.html).  One
of the alternative proposals described some of the reasoning as follows:

(a)  a CRL location function, which allows for a certificate-using
system to find a CRL applicable to a given certificate;
(b)  a certificate-CRL validation function, which provides for the
certificate-using system to confirm that a CRL to hand is indeed an
applicable CRL for the certificate under consideration.

The CDP mechanism merged these two functions into one mechanism.  In
contrast, the OpenCDP mechanism separates these two functions and
thereby achieves various benefits. 
        It's clear that you don't need function b) if there is a CRL
containing all certificates for the specified issuer.  So CRL DP has
always enabled partitioning, and the broken piece is not a PKI which
uses partitioning but rather a general-purpose RP library which cannot
support such partitioning.

Tom Gindin

Scoping of the CRL by the Distribution Point, rather than by
"entity certificates ony, CA certificates only, attributes certificates 
only
 or a limited set of reason codes" goes beyond the specified design
goals,
so don't be surprised if it breaks.

"unknown" is not a status known to the CRL Validation algorithm in
section 6.2.  And while our implementation (the software module above
the
ASN.1 parser) does not "support this extension", the ASN.1 parser of our
implementation *DOES* recognize it. 

So one may claim conformance to PKIX rfc5280 in spite of ignoring
conformance checks from Sections 4 & 5 of rfc5280.  That is what it
says. 

-Martin

---

From: Tomas Gustavsson <[email-masked]>
Date: Thu, 16 Feb 2012 15:59:57 +0100

Just as a funny of-topic mention. A CRL with 10M revoked entries is
about 400-500MB large. Very useful :-)

Cheers,
Tomas

---

From: Martin Rex <[email-masked]>
Date: Thu, 16 Feb 2012 16:54:28 +0100 (MET)

> reason code; IDP allows partitioning by local scope **in addition to**

I understand just the opposite.  For this to mean scoping by distribution
point, it must have said "identifies the CRL distribution scope for a
particular CRL",  but instead the distribution point and the scope
are clearly seperated by an and, and the remainder of the sentence
describes the details of the scoping.

> IDP will fail (not be suitable for use in) in any size-optimized

Now that last sentence is just the opposite of what rfc5280 says.

The final sentence of section 5 explicitly says this:

                                        Conforming applications are not
   required to support processing of delta CRLs, indirect CRLs, or CRLs
   with a scope other than all certificates issued by one CA.

which means that it is PERFECTLY OK for RPs to not support
partitioning of CRLs _at_all_.  Presumably because the only
scoping that is defined is that by certificate type and reason
code, and hardly anyone actually uses that!

-Martin

---

From: Martin Rex <[email-masked]>
Date: Fri, 17 Feb 2012 16:03:48 +0100 (MET)

> about 400-500MB large. Very useful :-)

As I indicated here:
  https://www.ietf.org/mail-archive/web/pkix/current/msg29842.html

I strongly believe that a CA (i.e. that specific DName) should be
retired when the expected growth of the CRL during the remaining
lifetime of the all certs singed with that exact issuer DName exceeds
a reasonable size.

The US government is operating several CAs with CRLs carrying >1 million
CRLEntries (1080 Millon = 22 MBytes), which is IMO far beyond
a resonably sized CRL.

Instead of partitioning CRLs, the CA should simply get a new CA cert
issued (simply bumping a Serialnumber AVA in the subject DName
of the CAs certificate would be sufficient), at which point
it will automatically start with a fresh, empty CRL, and this
will work nicely with *ALL* RPs.

-Martin

---

From: Anders Rundgren <[email-masked]>
Date: Fri, 17 Feb 2012 16:23:35 +0100

> will work nicely with *ALL* RPs.

I guess you are talking about Sub-CAs here, otherwise
you end up with trust-anchor distribution issues, right?

Yet another alternative would be to have short-lived automatically
renewed client-certificates which would keep CRLs in reasonable size.
The only thing stopping this is that CAC and PIV cannot perform
secure auto-renewals, at least not through PKIX protocols.

Anders

---

From: Tomas Gustavsson <[email-masked]>
Date: Sat, 18 Feb 2012 18:37:53 +0100

Hi Martin,

On 02/17/2012 04:03 PM, Martin Rex wrote:
> The US government is operating several CAs with CRLs carrying>1 million

I think the logic is slightly flawed.

Since CRLs needs to be maintained as long as the end entity certificates 
are active, all issued end entity certificates of a given CA can 
potentially become revoked, hence the CRL may contain all these entries.

This means that any given CA is only allowed to issue as many 
certificates as is reasonable to have on a CRL. If you think it is 
500.000, any given CA is only allowed to issue 500.000 CRLs, this seems 
cumbersome way beyond usability.

In reality CAs can issue 10M certificates within days, I surely don't 
want to renew these CAs as that pace.

Cheers,
Tomas

---

From: Tomas Gustavsson <[email-masked]>
Date: Sat, 18 Feb 2012 18:39:17 +0100

> want to renew these CAs as that pace.

I think a better alternative is to abandon CRLs for these types of CAs 
and use other mechanisms, like OCSP. If appropriate for the RPs of course...

As usual the number of different use cases are not bounded.

/Tomas

---

From: "Miller, Timothy J." <[email-masked]>
Date: Mon, 20 Feb 2012 14:24:55 +0000

>and use other mechanisms, like OCSP. If appropriate for the RPs of

And since OCSP implementation is uneven and a large number of use cases
involve unreliable networking, OCSP isn't really an option either.

I personally have used CRL-over-FedEx[1] (once) because it was more cost
effective than supporting a network in the same environment.[2]  :)

-- T

[1] "Never underestimate the bandwidth of a station wagon full of tapes
hurtling down the highway." ‹Andy Tanenbaum

[2] And no, the operations guys just would not consider alternative risk
mitigations that *didn't* involve revocation validation no matter how much
I justified it.

---

From: Martin Rex <[email-masked]>
Date: Mon, 20 Feb 2012 16:38:14 +0100 (MET)

Tomas Gustavsson wrote:
> Martin Rex wrote:

I had that case explicitly covered above.  Not a problem.  Just move
to a different CA cert early enough.  This is not about worst case,
but what should be reasonably expected, with some safety margin.

> cumbersome way beyond usability.

Just the contrary.  Managing risk sensibly means that you want to limit
the value of any single CA keypair, so that if anything very bad happens,
you don't have to nuke the entirey PKI, but only that part of it that
is actually affected.  Limiting the number of certs that are signed
with a single CA keypair can significantly help here, and will work
with every conforming RP, while only partitioning CRLs based on
distribution point will not help at all, but may create interop problems
with conforming RPs and makes things actually slower, because the CA
MUST still provide the full CRL in addtion to the zoo of partitioned
CRLs, and it is difficult to see how you can mix them in a fashion
that they not intefere with each other, becaus the CRL distribution
point extension of the certificate (rather than that of the CRL)
does not support paritioning of CRLs based on distribution
point names, only on reason codes.

> want to renew these CAs as that pace.

That is not necessarily a problem, if you do not expect your CRLs to grow
at the same rate (10M revocations within days).

The partitioning of CRLs by distribution point is ill-conceived, no
matter how you look at it.  Whether a CA uses partitioning by
CRL distribution point is *NOT* visible in the CRL distribution
point extension of the Certificate at all!

Quoting from rfc5280 Section 6.3:
   http://tools.ietf.org/html/rfc5280#section-6.3

   This algorithm assumes that all of the needed CRLs are available in a
   local cache.  Further, if the next update time of a CRL has passed,
   the algorithm assumes a mechanism to fetch a current CRL and place it
   in the local CRL cache.

An RP with an efficient implementation of revocation checking will
be using CRLs, cache the CRLs and update the CRL cache strictly
out-of-band, so that a revocation check will incur a single table lookup
keying on issuer&serial, and zero PK-crypto operations and zero third
party network communication in-band while authenticating peers.

-Martin

---

From: "Miller, Timothy J." <[email-masked]>
Date: Mon, 20 Feb 2012 15:41:30 +0000

>but what should be reasonably expected, with some safety margin.

You make it sound so simple.

CAs don't come cheap at higher assurance levels.  They are expensive to
deploy and expensive to maintain.

-- T

---

From: Tomas Gustavsson <[email-masked]>
Date: Tue, 21 Feb 2012 00:24:32 +0200

Consider this (real world) use case.

50M certificates issued in 10 days. 5M revoked.

Far from easy to maintain any type of renewals under this load.

IMHO it just shows that the use cases for PKI today is virtually 
unbounded. PKIX must (and often does) provide mechanisms to encompass a 
broad range of use cases. Each use case/CA/RP must select the mechanisms 
that are suitable. If you don't like CRL partitioning in your use case, 
don't use it. I have tried to avoid it so far, but are being forced to 
look into it now. If you don't need CRLs, but OCSP works, forget about 
CRLs and only use OCSP. If you want to replace your CAs every week, do 
it. Etc etc.

Today we really need to be open minded about PKI, because it is 
ubiquitous in a way it has never been before, in new and improved use cases.

Standards gets a bit more complex having to adapt to all these different 
scenarios. But that means better work for us PKI geeks :-)
Seriously it is hard to (currently) see many alternatives to the 
complexity of this infrastructure.

cheers,
Tomas

---

From: Peter Gutmann <[email-masked]>
Date: Tue, 21 Feb 2012 14:33:15 +1300

"Miller, Timothy J." <[email-masked]> writes:

>And no, the operations guys just would not consider alternative risk
>mitigations that *didn't* involve revocation validation no matter how much I
>justified it.

Magical thinking demands magical solutions, so I can certainly belive this.

Peter.

---

From: Martin Rex <[email-masked]>
Date: Tue, 21 Feb 2012 15:30:37 +0100 (MET)

> 50M certificates issued in 10 days. 5M revoked.

That looks like a serious design flaw of the PKI.

A sensible PKI design would seperate certs that need to be frequently revoked
from those that are rarely revoked and at least adjust the certificate
validity so that the necessity to revoke becomes the exception, but
preferably these two kinds of certificates with completely different
usage patterns would be signed by seperate intermediate CA certs.

> Far from easy to maintain any type of renewals under this load.

Switching to a different intermediate CA cert is _not_ a CA cert roll-over
as far as the RP is concerned, so there is ZERO pain involved (for the RPs).
btw. the use of the term "renewal" should be limited to a successor
cert with the exact same public key and the exact same subject DName.

> don't use it.

It's not whether we "like" it.  We simply do not support it at all in
our RP (fully conforming with rfc5280).  It is squarely incompatible with
efficient processing of revocation during online authentication.

> 
> I have tried to avoid it so far, but are being forced to 

OCSP is a complete no-go.  It is prohibitively expensive.  Efficient
revocation checking based on CRLs is possible with zero PK-operations
and zero network communication in-band during authentication.
Obtaining the OCSP responses inband (like with multiple-OCSP-responses
TLS extension) might be a future possibility, although this will
incur at least one PK-operation.

If PK-authentication want to be taken seriously as an alternative
to Kerberos authentication, then it MUST be efficient on the server-side
processing, which means NO third-party communication during communication,
as few PK-operations as possible, and manageable risk.  The TLS X.509 PKI
as used by web browsers is pretty close to no security at all.

> ubiquitous in a way it has never been before, in new and improved

The only thing that is ubiquitous about PKI today is the security problem
from having hundreds of omnipotent rootCAs pretrusted.

-Martin

---

From: "Kemp, David P." <[email-masked]>
Date: Tue, 21 Feb 2012 17:04:11 -0500

OCSP requires more bandwidth (at least 4x, usually much more) for any
given number of certs.  In the limit (infinite number of certs, none
revoked), OCSP requires infinite bandwidth while an empty CRL is ~200
octets.  CRL stapling is quite practical for CRLs partitioned to cover
100 certs each, and can be regarded as a very efficient replacement for
short-lived certs.

Dave

-----Original Message-----
From: Tomas Gustavsson

I think a better alternative is to abandon CRLs for these types of CAs
and use other mechanisms, like OCSP. If appropriate for the RPs of
course...

/Tomas

---

From: Ryan Hurst <[email-masked]>
Date: Tue, 21 Feb 2012 14:08:05 -0800

Short lived certificates however have the side effect of addressing the key management issues that plague operational environments.

Sent from my iPhone

---

From: Tomas Gustavsson <[email-masked]>
Date: Wed, 22 Feb 2012 01:00:00 +0200

> 100 certs each, and can be regarded as a very efficient replacement for

If we are into unrealistic scenarios, how about inifinite number of 
certificates, 50% revoked, inifinite number of CAs, 10 minute CRL expire 
period, 1 client connection every 20 minutes? I think OCSP wins in this 
case. God thing the world is not quite infinite :-)

Cheers,
Tomas

---

From: "Kemp, David P." <[email-masked]>
Date: Wed, 22 Feb 2012 09:53:58 -0500

Only in very limited circumstances.

1) Short-lived certificates can renew (extend validity only) or rekey.
Renew is trivially easy and is the normal use case for short-lived
certs, but it doesn't address key management.
2) Key management must address loss/destruction of key, detected
compromise, and undetected compromise.  Loss/destruction/detected
compromise are all handled the same way regardless of cert lifetime: a
new cert is issued since the old key can't be used to support rekey.
3) Undetected compromise allows either the adversary or the subscriber,
but not both, to rekey, so it provides some compromise detection
capability when the subscriber is denied a rekey.  This detection
happens more quickly with short-lived certs.

So rekeying at frequent intervals provides a potential advantage over
infrequent rekeying in the case of undetected exposure of a key that
remains usable by the subscriber.  But that's a pretty small subset of
key management issues.

Dave

-----Original Message-----
From: Ryan Hurst [mailto:[email-masked]] 
Sent: Tuesday, February 21, 2012 5:08 PM
To: Kemp, David P.
Cc: <[email-masked]>
Subject: Re: [pkix] AuthKeyId and CrlEntryExtension.CertificateIssuer

Short lived certificates however have the side effect of addressing the
key management issues that plague operational environments.

Sent from my iPhone

On Feb 21, 2012, at 2:04 PM, "Kemp, David P." <[email-masked]>
wrote:

> 100 certs each, and can be regarded as a very efficient replacement 
> for short-lived certs.
> 
> Dave
> 
> 
>

---

From: Rene Struik <[email-masked]>
Date: Wed, 22 Feb 2012 10:57:39 -0500

Dear collagues:

Some papers of interest here include Ron Rivest's [1] advocacy for short-lived certs (1998) and Rubin et al's [2] response (2001).

In those papers, arguments underlying picks for short-lived certs vs. certificate checks during stated lifetime center around
a) computational overhead.
Cost of generating a certificate (or, more precisely, cost of certificate [renewal] request, response sequence).
b) communication overhead.
Cost of the protocol messaging to and from the CA for issuing a new cert, resp. cost for messaging to and from server 
who arbitrages into okaying a current certificate on the spot.

My own perspective is as follows:

For networks with lack of "online" connectivity, availability of an arbitraging server on the spot cannot be assumed *and* could
impose a huge communication bandwidth burden (case in point: sensors). For those networks, short-lived certs (that provide positive 
evidence of authentic binding, without "only maybe valid, but please check" semantics), seem to be more suitable. Here, a device can
try and obtain a new credential (with associated "new lease of life") from the CA, when it is available to do so (and a moment of its choosing). 
Contrast this with longer-lived certs (with "only maybe valid, but please check" semantics), where the ambiguous assertion on validity 
forces an almost immediate connection with an arbitraging agent somewhere in the network (be it using OCSP or for CRL checking).

The traditional argument that computational cost of generating certificates is too expensive seems to be less valid now, witness the 
progress in efficient implementations of cryptographic algorithms over the last decade. Moreover, some of the cost can be amortized 
via hybrid schemes, such as Micali's [3], that essentially trade the cost of generating n certificates, each valid for 1 time unit, for 
the cost of generating 1 certificate conditionally valid for n time units and the cost of computing a Lamport-style hash chain of 
length n, each representing validity for another time unit. 

The main reason for certificate revocation right now seems to be "change of authorization" (organizational change, change of policies), rather than
"change of authentication" (compromised device or key). For authorization triggers, providing a "positively valid" credential seems far more 
effective than providing a "maybe valid, but please check" credential. For authentication changes, indeed, all bets are off until detection, irrespective
of the scheme, but once compromise has been detected, long-lived credentials keep polluting the network and requiring checks with an arbitraging agent, 
while short-lived certs just cease to exist after their short moment under the sun. Here, one should bear in mind that detection time windows are often
of human time-scale, so trying and making certs extremely short-lived (i.e., well below practical loss/compromise reporting and processing time window) 
may not add too much value here. 

In summary, the case for short-lived certs seems to be quite compelling (presuming devices have a reliable notion of time). This being said, I would 
suggest revisiting the papers below, re-weighing the arguments and metrics used over a decade ago, and seeing for yourself.

[1] R.L. Rivest, 
“Can We Eliminate Certificate Revocation Lists?,” 
in Financial Cryptography - FC’98, R. Hirschfeld, Ed., 
Lecture Notes in Computer Science, Vol. 1465, pp. 178-183, 
Springer, 1998.

[2] P. McDaniel, A. Rubin, 
“A Response to “Can We Eliminate Certificate Revocation Lists?”,” 
in Financial Cryptography - FC 2000, Y. Frankel, Ed., 
Lecture Notes in Computer Science, Vol. 1962, pp. 245-258, 
Springer, 2001.

[3] S. Micali, 
“Efficient Certificate Revocation,” Technical Report TM-542b, 
MIT Laboratory for Computer Science, 
March 22, 1996

-- 
email: [email-masked]
Skype: rstruik
cell: +1 (647) 867-5658
USA Google voice: +1 (415) 690-7363

---

From: Piyush Jain <[email-masked]>
Date: Wed, 22 Feb 2012 11:04:36 -0800

Interesting observation even though the example given doe not represent real worl deployments.
The CRLs (non partitioned) tend to grow in size as the number of certificates issued of the CA grows.
 
But it makes me wonder, why OCSP does not have the provision for efficiently returning the response for a range of certs without including the serial numbers explicitly.

 One enhancement in OCSP V2 (if it happens) could be to change certID so it represents a range as opposed to single serial number.
 
For the example given below a single OCSP response (srart serial = -infinity, end serial = +infinity, status=good) can be used for all the certificates issued by that CA.
 
And this approach would greatly reduce the computational and bandwidth requirement in deployments that pre-sign OCSP responses.
 
-Piyush

 > Date: Tue, 21 Feb 2012 17:04:11 -0500
> From: [email-masked]
> To: [email-masked]

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Wed, 22 Feb 2012 14:07:20 -0500

There are two separate questions:

1) Where should we go
2) How do we get there

I think Rivest's argument is essentially sound on CRLs with respect to
the first question. The original paper was written round about the
time that we were developing OCSP and even then it was apparent that
the OCSP model is very close to being a certificate model.

The second part is rather more difficult. Short lived certs and
stapled OCSP responses have almost identical properties. But that does
not mean that they are interchangeable. There is a deployed
infrastructure that expects to make use of OCSP and CRLs.

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

---

From: Rene Struik <[email-masked]>
Date: Wed, 22 Feb 2012 14:27:55 -0500

Dear Phil:

Unfortunately, current deployment in areas that could bear a particular solution direction often spills over in areas that cannot.  

A vivid example of this is smart grid/cybersecurity, where one has networks with sleepy devices and spotty connectivity at best and where minimizing
communication traffic density (esp. the one that needs to be almost on-demand) is highly desirable. Here, emphasis on CRLs and OCSP may kill off
the prospect of getting all those 30-50 billions of devices actually deployed or, in an attempt to make this work no matter what, will lead to network designs
that at first may not hurt that much (e.g., centralized management approaches), but ultimately do not scale that well (but then it may be "too late", 
since the "backward compatibility requirement crowd" will make lots of noise on sunk investments and make it very hard to change course - not realizing
that this may ultimately also significantly limit the deployment potential. For those networks (where "the other 99%" is not deployed yet), one should
try and avoid imposing CRLs and other constructs that put a heavy just-in-time messaging demand on the network. In that respect, e.g., NIST IR 7628's Smart
Grid Cybersecurity Framework may need some rethink and erasing of CRL/OCSP terms that may work or have worked reasonably well elsewhere, but 
transplanting this to a domain with entirely different characteristics may not.

So, agreed with your question split, with the caveat that we should look beyond areas we are currently confortable with and know the characteristics of.

Rene

---

From: Anders Rundgren <[email-masked]>
Date: Wed, 22 Feb 2012 21:01:52 +0100

Mozillas recent BrowserID scheme relies on certificates that typically
only last a web session so it seems that short-lived certificate actually
"live", albeit not that long :-)

A combination of short-lived certificates and thus comparatively small
CRLs could also be an alternative for large enterprise or citizen CAs.

Short-lived certificates is an intrinsic part of our passport system
created by BSI and ICAO.  Unfortunately they got it wrong and did the
assumption that just because the initial key is an HSM, the renewed
keys are automatically there as well.  For that you need an attesting
HSM and protocol, both which are unavailable or at least completely
non-standard.

Cheers,
Anders

---

From: "Kemp, David P." <[email-masked]>
Date: Wed, 22 Feb 2012 15:22:14 -0500

CRLs, OCSP, and/or short- or long- lifetime certs do not "put a heavy
just-in-time messaging demand" on the network, currency requirements for
authentication and authorization information, in whatever form it is
encoded, do that.  PKIX has long eschewed the placement of authorization
information in PK certificates for exactly the reason Phill cites:
authorization changes more rapidly.  "Looking beyond" includes looking
beyond current counterproductive practices (mixing static and dynamic
information in the same data structures) and properly deploying PK
certificates, authentication revocation mechanisms, and separate
authorization attributes.

What is your proposed alternative that achieves appropriate information
currency for billions of devices using less network demand?  My
assertion is that proper application of currently-defined data
structures (including full, delta, and partitioned CRLs) for
authorization-free PK certs will be strongly competitive with whatever
you propose.

Dave

-----Original Message-----
From: Rene Struik [mailto:[email-masked]] 
Sent: Wednesday, February 22, 2012 2:28 PM
To: Phillip Hallam-Baker
Cc: Kemp, David P.; [email-masked]
Subject: Re: [pkix] The case for short-lived vs. long-lived certificates

Dear Phil:

Unfortunately, current deployment in areas that could bear a particular
solution direction often spills over in areas that cannot.  

A vivid example of this is smart grid/cybersecurity, where one has
networks with sleepy devices and spotty connectivity at best and where
minimizing communication traffic density (esp. the one that needs to be
almost on-demand) is highly desirable. Here, emphasis on CRLs and OCSP
may kill off the prospect of getting all those 30-50 billions of devices
actually deployed or, in an attempt to make this work no matter what,
will lead to network designs that at first may not hurt that much (e.g.,
centralized management approaches), but ultimately do not scale that
well (but then it may be "too late", since the "backward compatibility
requirement crowd" will make lots of noise on sunk investments and make
it very hard to change course - not realizing that this may ultimately
also significantly limit the deployment potential. For those networks
(where "the other 99%" is not deployed yet), one should try and avoid
imposing CRLs and other constructs that put a heavy just-in-time
messaging demand on the network. In that respect, e.g., NIST IR 7628's
Smart Grid Cybersecurity Framework may need some rethink and erasing of
CRL/OCSP terms that may work or have worked reasonably well elsewhere,
but transplanting this to a domain with entirely different
characteristics may not.

So, agreed with your question split, with the caveat that we should look
beyond areas we are currently confortable with and know the
characteristics of.

Rene

>> Some papers of interest here include Ron Rivest's [1] advocacy for
short-lived certs (1998) and Rubin et al's [2] response (2001).
>>
>> In those papers, arguments underlying picks for short-lived certs vs.

>> certificate checks during stated lifetime center around
>> Cost of generating a certificate (or, more precisely, cost of
certificate [renewal] request, response sequence).
>> Cost of the protocol messaging to and from the CA for issuing a new 
>> cert, resp. cost for messaging to and from server who arbitrages into
okaying a current certificate on the spot.
>> For networks with lack of "online" connectivity, availability of an 
>> arbitraging server on the spot cannot be assumed *and* could impose a

>> huge communication bandwidth burden (case in point: sensors). For 
>> those networks, short-lived certs (that provide positive evidence of
authentic binding, without "only maybe valid, but please check"
semantics), seem to be more suitable. Here, a device can try and obtain
a new credential (with associated "new lease of life") from the CA, when
it is available to do so (and a moment of its choosing).
>> Contrast this with longer-lived certs (with "only maybe valid, but 
>> please check" semantics), where the ambiguous assertion on validity
forces an almost immediate connection with an arbitraging agent
somewhere in the network (be it using OCSP or for CRL checking).
>>
>> The traditional argument that computational cost of generating 
>> certificates is too expensive seems to be less valid now, witness the

>> progress in efficient implementations of cryptographic algorithms 
>> over the last decade. Moreover, some of the cost can be amortized via

>> hybrid schemes, such as Micali's [3], that essentially trade the cost
of generating n certificates, each valid for 1 time unit, for the cost
of generating 1 certificate conditionally valid for n time units and the
cost of computing a Lamport-style hash chain of length n, each
representing validity for another time unit.
>>
>> The main reason for certificate revocation right now seems to be 
>> "change of authorization" (organizational change, change of 
>> policies), rather than "change of authentication" (compromised device

>> or key). For authorization triggers, providing a "positively valid" 
>> credential seems far more effective than providing a "maybe valid, 
>> but please check" credential. For authentication changes, indeed, all

>> bets are off until detection, irrespective of the scheme, but once
compromise has been detected, long-lived credentials keep polluting the
network and requiring checks with an arbitraging agent, while
short-lived certs just cease to exist after their short moment under the
sun. Here, one should bear in mind that detection time windows are often
of human time-scale, so trying and making certs extremely short-lived
(i.e., well below practical loss/compromise reporting and processing
time window) may not add too much value here.
>>
>> In summary, the case for short-lived certs seems to be quite 
>> compelling (presuming devices have a reliable notion of time). This
being said, I would suggest revisiting the papers below, re-weighing the
arguments and metrics used over a decade ago, and seeing for yourself.
>>
>>
>> [1] R.L. Rivest,
>> "Can We Eliminate Certificate Revocation Lists?,"
>> in Financial Cryptography - FC'98, R. Hirschfeld, Ed., Lecture Notes 
>> in Computer Science, Vol. 1465, pp. 178-183, Springer, 1998.
>>
>> "A Response to "Can We Eliminate Certificate Revocation Lists?","
>> in Financial Cryptography - FC 2000, Y. Frankel, Ed., Lecture Notes 
>> in Computer Science, Vol. 1962, pp. 245-258, Springer, 2001.
>>
>> [3] S. Micali,
>> "Efficient Certificate Revocation," Technical Report TM-542b, MIT 
>> Laboratory for Computer Science, March 22, 1996
>>
>>
>>> compromise are all handled the same way regardless of cert lifetime:

>>> a new cert is issued since the old key can't be used to support
rekey.
>>> 3) Undetected compromise allows either the adversary or the 
>>> subscriber, but not both, to rekey, so it provides some compromise 
>>> detection capability when the subscriber is denied a rekey.  This 
>>> detection happens more quickly with short-lived certs.
>>>
>>> So rekeying at frequent intervals provides a potential advantage 
>>> over infrequent rekeying in the case of undetected exposure of a key

>>> that remains usable by the subscriber.  But that's a pretty small 
>>> subset of key management issues.
>>>
>>> Dave
>>>
>>>
>>> Short lived certificates however have the side effect of addressing 
>>> the key management issues that plague operational environments.
>>>
>>> Sent from my iPhone
>>>
>>>> OCSP requires more bandwidth (at least 4x, usually much more) for 
>>>> any given number of certs.  In the limit (infinite number of certs,

>>>> none revoked), OCSP requires infinite bandwidth while an empty CRL 
>>>> is ~200 octets.  CRL stapling is quite practical for CRLs 
>>>> partitioned to cover

>>>> I think a better alternative is to abandon CRLs for these types of 
>>>> CAs and use other mechanisms, like OCSP. If appropriate for the RPs

>>>> of course...

---

From: Martin Rex <[email-masked]>
Date: Thu, 23 Feb 2012 04:05:33 +0100 (MET)

Miller, Timothy J. wrote:
> 
> "Martin Rex" <[email-masked]> wrote:
> 

Are you thinking of crypto hardware that is quite limited in the
amount of distinct keypairs it can handle?

One solution to that might be to re-use the same keypair with different
intermediate CA certs, i.e. instead of trying to partition
by an optional, overly complex "CRL distribution point name"
simply create the same number of intermediate CA certs
with distinct subject dnames for the same public key. 
That should be easy&straightforward, will _not_ interfere with
efficient CRL processing and will work with just everything
that supports CRLs at all?  But you should compute the
SPKID of those certs based on a concatenation of the 
public key and subject name, or some implementations
might get fatally confused and break.

-Martin