Subject: RE: delta CRLs

From: Santosh Chokhani <[email-masked]>
Date: Sat, 12 May 2001 07:18:02 -0400

Denis:

You assumptions and recommendations may be appropriate for your environment
and PKIX should accommodate your design.  In my mind PKIX DOES accommodate
your design.

However, others may want to design PKI where the freshness of revocation
information is not guaranteed beyond nextUpdate, but could be published be
available, modulo network security assumptions.  In that scenario,
publishing revocation information via full or delta CRL's that are not
promised via nextxUpdate is also fine, knowing full well that the CA can not
guarantee that RP will be ensured of out of cycle CRL availability.

In short, RP knows that the non-repudiation between thisUpdate of CRL and
current time is up in air.

Thus, I am not in favor of the constraints on the CA you cited.

-----Original Message-----
From: Denis Pinkas [mailto:[email-masked]]
Sent: Friday, May 11, 2001 12:58 PM
To: Housley, Russ
Cc: [email-masked]; Tim Polk; David A. Cooper
Subject: Re: delta CRLs

Russ, 

Thanks for this very detailed collective response.

I have been hoping to have a phone call with some of you today, but since
this had not been possible, here is an answer to your email.

FYI, I will be out of my office during three days, so do no expect a reply
before next Thursday.

The thread has been focussing on the mechanisms, forgetting what is the
rational about them. So let us come back to the rationals. One of them
relates top the use of CRLs when applied to a non repudiation service.

X.509 has been originally written to use CRLs for other security services
and for these other services, the problems are different.

We all want to be able to use either CRLs or OSCP responses for non
repudiation purposes. In fact we want to allow any of these two techniques
to be used in single or in combination. Right ?

Having said this, we can now explain some of the rational. 

When validating a digital signature, for a given time T, for non repudiation
purposes, it is important for a verifier to be able to prove that the
certificate was NOT revoked. It is also important that two different
verifiers come to the same result, for the same time T, because of the goal
of non repudiation is to solve disputes.

The same properties must be achieved whether OCSP or CRLs are used. When an
OCSP response is received with a time T in it, there can be no dispute about
it: it contains three possible answers (not revoked, revoked, don't know).
If an OCSP responder produces one such answer with a time T and one of the
three statuses, no one else can present an answer with the same time T in it
with a different answer from the same OCSP responder. Once again, it would
not be acceptable that at a given time T two opposite responses could be
obtained. This would result in disputes.

This means that at time T, there is must be one and only one possible
answer. This allows to use OCSP responses for non repudiation purposes. The
same property must be supported so that CRLs can be used for non repudiation
purposes. So the goal is that when using CRLs in the context of non
repudiation, only one response (i.e. not revoked, revoked, don't know) can
be obtained.

I do know that non repudiation is only one use of the PKI and that there are
other usages such as authentication, integrity and confidentiality. So let
us now describe what is necessary, if the CRL contains at least one
certificate that can be used for non repudiation purposes (e.g. it has the
NR bit set).

If at time T there is more than one CRL valid, then there is a possibility
to miss the most recent, in case there is a denial of service attack on it
(i.e. suppression of the latest CRL while in transit).

This means that "emergency" CRLs will not necessarily be seen. "Emergency"
CRLs may be used for authentication, integrity and confidentiality, but may
create problems when used in the context of non repudiation.

This has several implications: we should deprecate the use of "emergency"
CRLs for being used for a non repudiation service, because they could
provide two different responses. 

People using full CRLs, i.e. without taking advantage of the delta CRLs,
would get only one result.

People using base CRLs and thus taking advantage of the delta CRLs would
also get one single result. For that reason we should also deprecate the use
of "emergency" delta CRLs.

This now explains why it is important to get one answer, at most, at a time.
I do understand that lacking this information, the mechanism seems to be
constrained without any "good" reason.

Now how can a verifier be sure to get the freshest information ?

This depends on the verification rules. Let us restrict the discussion to
the leaf certificate.

If the validation rules (be careful this has strong relationships with the
DPV protocol) say : "use full CRLs only" and there is no "emergency CRL",
then everything works nice.

If the validation rules say: "use the freshest information that is provided
by the CA", then the question is how can a verifier know how the freshest
information is obtained ? The answer is: only through extensions. Why ?

Let us assume first that no extension either in the certificate or the CRL
is being used. The answer would be : make a search for delta CRLs in the
directory. The problem is that, in case a denial of service attack, the
delta CRLs, even if they exist, will not be "seen". So the verifier will use
the base CRL and thus two verifications done at the same time T will provide
two different results. :-(

So there needs to be some way, so that, in the event of a denial of service
attacks, either the right information is obtained or that no information at
all is obtained. In the later case, if the revocation information is not
found, then the signature is not accepted (in some cases a try can be done
later on).

A consequence is the following: verifiers must know without ambiguity
whether a delta CRL mechanism is supported, so that if delta CRL are
supported it is possible to know unambiguously that it is the case. 

There are two options. 

1) Should we use the freshestCRL extension from the leaf certificate ? This
means that the CA MUST support delta CRLs at any time during whole the
life-time of the certificate. This is quite constraining for the CA, but
this is possible.

2) Should we use the freshestCRL extension from the CRL? This means that the
CA will only support delta CRLs for that CRL without any engagement to
support a delta CRL mechanism for the next one. This is more flexible.

What does this means ? That it is very likely that we will not end up wit
the same mechanism when using delta CRLs for a certificate used for non
repudiation purposes and when using a certificate for other purposes. One of
the algorithms may look first at the delta CRLs, whether they exist or not,
while the other will only take a look for them after making sure that they
must exit.

The best guess, if it succeeds, is certainly valid for "other purposes". So
I will now focus on the algorithm to be used for non repudiation purposes.

   An application that is willing to obtain the freshest CRL 
   information for a given certificate used for non repudiation 
   purposes, must know if a delta CRL mechanism is supported. 
   Either the certificate or any CRL that is able to reference 
   that certificate MUST include a freshestCRL extension 
   (a.k.a. a Delta CRL distribution point). 

   The application may then construct an updated CRL for that 
   base, for a specific time T, by combining it with a delta 
   CRL which contains a delta CRL indicator extension with the 
   same CRL number as the base CRL. Applications that support 
   delta CRLs MUST ensure that time T falls between thisUpdate 
   and nextUpdate for both the base CRL and the delta CRL.

   Note: An application could also reconstruct an updated CRL, 
   for a specific time T, by using a previously locally 
   reconstructed CRL based on the current base CRL, and 
   combining it with a delta CRL which contains a delta CRL 
   indicator extension with the same CRL number as the base 
   CRL.

For the constraint about the CA:

   For any CRL that may reference a certificate used for 
   non repudiation purposes, and for any time T until 
   the nextUpdate time indicated in a base CRL, the CA MUST 
   provide one and only one base CRL and one and only delta 
   CRL that refers to that base CRL and for which time T 
   falls between thisUpdate and nextUpdate from the delta CRL.

There are still other issues to discuss, like the CRL numbering,
whether it is unique or not, let us wait for next week for that topic.

Regards,

Denis

> Denis:
> 
> Please excuse the half-done message from this morning.  My mailer and I
had
> a disagreement...
> 
> Anyway, since I was not going to get the full message out before the end
of
> the business day in France, I took the time to coordinate a response with
> Tim Polk and David Cooper.  This mail thread is quite long, so hopefully
> our coordination on the side will reduce the overall number of messages to
> the list and help to reach consensus faster.
> 
> Here goes ....
> 
>  >There is difference between a base CRL and a full CRL : a base CRL MUST
>  >include a freshestCRL extension (a.k.a. a Delta CRL distribution point),
>  >whereas a full CRL may not include that extension. In other words, a
base
>  >CRL is a also a full CRL, but a full CRL is not necessarily a base CRL.
> 
> There is no requirement in X.509 to include any extension in a certificate
> or CRL advertising the availability of delta CRLs. PKIX makes the
> freshestCRL extension available for advertising the existence of delta
> CRLs, but again does not mandate its use. Furthermore, even if the
> freshestCRL extension is used, it may be placed in either the certificate
> or the full CRL. If the extension is placed in certificates, there is no
> need for it to be in the full CRL (but, it could be).
> 
> Finally, if delta CRLs are being issued, and are being advertised through
> the freshestCRL CRL extension, then the extension should be included in
all
> full CRLs for that scope, not just the base CRLs. If a relying party
> obtains the most recently issued full CRL for a scope from a repository,
> and that full CRL is not a base CRL, how will the relying party know that
> delta CRLs are available?
> 
>  >At any time a CA may issue a full CRL, whether or not a base CRL has
already
>  >been issued. This additional CRL SHOULD have nextUpdate equal to the
>  >nextUpdate of the last issued full CRL. However, there is no guarantee
that
>  >this additional CRL will ever be seen by the relying party (because
there
>  >will be two CRLs matching the thisUpdate and nextUpdate rule and if one
is
>  >deleted, this is not seen by a relying party).
> 
> The nextUpdate field in a full CRL (base or otherwise) should specify the
> time by which new revocation information will be available. So, if a new
> base CRL is issued once a day, but full CRLs are issued every hour, the
> nextUpdate field of each full CRL should one hour after that CRL's
> thisUpdate time.
> 
>  >Due to the fact that CRLs numbers are strictly increasing, two CRLs
whether
>  >they are a base CRL or delta CRL, CANNOT have the same CRL number. So a
>  >delta CRL and a full CRL that cover the same scope and are issued at the
>  >same time CANNOT have the same number.
> 
> We disagree.  If a full CRL and a delta CRL are issued at the same time
for
> the same scope, then they ARE the same CRL and MUST have the same CRL
number.
> 
>  >If a full CRL is issued, its CRL
>  >number bears no relationship with the previous base CRL, if any.
> 
> Again, we disagree. A sequence of CRLs for a given scope must contain a
> monotonically increasing sequence of CRL numbers. Relying parties that do
> not process delta CRLs, and thus do not recognize the non-critical
> freshestCRL extension, will not be able to distinguish between those full
> CRLs that are base CRLs and those full CRLs that are not base CRLs. The
CRL
> numbers for these full CRLs must be from one monotonically increasing
sequence.
> 
>  >The only
>  >relationship between the numbers is defined by the rule that CRLs
numbers
>  >are strictly increasing. As Santosh said : "the CRL number is unique
>  >whether it is a base or a delta ".
>  >
>  >This is fairly important to be able to unambiguously (and thus uniquely)
>  >refer to a CRL by only providing its CRL number.
> 
> Exactly. If a full CRL and the delta CRL are issued for the same scope at
> the same time, they are the same CRL. The CRL number unambiguously and
> uniquely refers to this ONE CRL.
> 
>  >Besides the fact that a CRL issued later MUST have a higher CRL number,
full
>  >CRLs and delta CRLs have independent numbering rules. As noticed by
Santosh,
>  >" if the delta thisUpdate > base thisUpdate, delta CRL number > base CRL
>  >number (for the same or no stream identifier).
> 
> If you agree that delta thisUpdate > base thisUpdate implies delta CRL
> number > base CRL, then you are acknowledging that the CRL numbers of the
> full CRLs and delta CRLs are not independent.
> 
>  >As Santosh said : "a check based on thisUpdate is more general and
>  >preferred [to the use of CRL numbers]. "
>  >
>  >Related to the three rules mentioned by Russ :
>  >
>  >1) the first rule is not understandable to me.
>  >2) the second rule does not say anything more than the basic rule valid
>  >    for any CRL (i.e. a CRL issued later MUST have a higher CRL number).
>  >3) we will debate the hold condition, once we will have sorted the main
>  >    issue.
>  >
>  >Russ said : "If separate number sequence is used, then you will have to
>  >periodically fetch base CRLs ". This is true.
>  >
>  >Tim said that he would *not* like to be forced to download new base
CRLs.
>  >This is the core of the "dispute".
> 
> Our goal should be to allow delta CRL enabled clients to obtain accurate
> information in the most efficient manner possible. Forcing clients to
> periodically download full CRLs, when this is not necessary, is
inefficient.
> 
>  > From the definition of what a delta CRL is, it is *not* possible to
>  >get rid of the fetching of base CRLs. Unless we add a new sentence to
>  >expand/change that definition, base CRL fetching will remain mandatory.
> 
> True. However, if one performs validations frequently enough, it is
> possible to obtain a single full CRL and then subsequently download only
> delta CRLs. We need to require that full CRL be issued periodically so
that
> clients whose locally stored information is not sufficiently up-to-date to
> apply the delta CRLs being issued can obtain the full CRLs that they need,
> but we should not require clients to download full CRLs when it is not
> necessary for them to do so.
> 
>  >Remember that the goal of delta CRLs is to provide the freshest
information,
>  >and to my knowledge the goal was not to get rid of the fetching of base
CRLs
>  >(which may less frequent due to the support of delta CRLs).
> 
> Yes, but the goal should be to minimize the fetching of full CRLs.
> 
>  >If I understand correctly, Tim/David/Russ would like to *always* achieve
the
>  >following property : it is possible to reconstruct the current CRL by
using
>  >a base CRL from, e.g. 1990, i.e. by capturing every delta CRL that has
been
>  >issued at the same time a base CRL was issued and which contains updates
>  >made to the *previous* base.
>  >
>  >By this way the fetching of base CRLs could be avoided. However, note
that
>  >it is perfectly " legal " to stop issuing base and delta CRLs during
some
>  >period of time and to issue full CRLs instead (see the difference
between
>  >"full" and "base" at the top of this e-mail). In other words there is no
>  >need to issue a new base CRL at the end of the validity period of the
>  >previous base CRL. Doing this would mandate to prescribe issuing rules
>  >for CAs that we have not prescripted.
> 
> You are mixing apples and oranges. Obviously the scheme of keeping
> up-to-date by obtaining a base from 1990 and then only downloading deltas
> will only work so long as deltas continue to be issued. If the CRL issuer
> ceases to issue deltas, then the relying parties will have to revert to
> downloading full CRLs.
> 
>  >I will now raise a series of questions, for which I believe we have
>  >different answers. Tim/David/Russ do not hesitate to correct
>  >if my guess is wrong. ;-)
>  >
>  >Common point:
>  >
>  >1) What will be the value of the nextUpdate field from the last issued
delta
>  >CRL for a given base CRL ?
>  >
>  >Denis: the nextUpdate field from the last issued delta CRL MUST be equal
to
>  >the value of nextUpdate from the base CRL.
>  >
>  >Tim/David/Russ: ???
> 
> The nextUpdate field in a base CRL states when the next full CRL will be
> available. This is important for supporting clients that do not handle
> delta CRLs. The nextUpdate field in a delta CRL states when the next CRL
> (either a delta CRL or a full CRL) will be available. As a general rule,
if
> the CA is continuing to issue deltas, the nextUpdate in the delta will be
> the time by which the next delta will be available. If this is the last
> delta that the CA is going to issue, then the nextUpdate in the delta will
> be the time by which the next full CRL will be available. ("Available"
> SHOULD reflect distribution delays associated with the repository
> architecture.)
> 
>  >2) Does a CA needs to issue a delta CRL at the time a full CRL is issued
?
>  >
>  >Denis: No.
>  >Tim/David/Russ : ???
> 
> No. A CA never is required to issue deltas. However, it would be helpful
to
> delta CRL enabled clients to allow them to construct the full CRL.
> 
> If the full CRL contains a freshestCRL extension, then it is a very good
> idea to generate a delta CRL at the same time. In this way, any client
will
> be able to find a current delta CRL.
> 
>  >3) Does a CA needs to issue a new base CRL at the end of the validity of
a
>  >current base CRL ?
>  >
>  >Denis: No.
>  >Tim/David/Russ : ???
> 
> No. HOWEVER, the CA must issue a new full CRL by the nextUpdate in the
> previously issued full CRL (whether that full CRL is a base CRL or not).
> There is no requirement that the next full CRL be a base CRL. (The CA
could
> quit issuing deltas, etc. etc.)
> 
> Every base CRL MUST be a full CRL, but not every full CRL is a base CRL.
> But, a CA could make every full CRL a base CRL if they wanted to.
> 
>  >4) Does a CA needs to issue a delta CRL at the same time a new base is
>  >issued ?
>  >
>  >Denis: Yes. The delta CRL refers to the *new* base.
>  >Tim/David/Russ : ???
> 
> No. HOWEVER, in practice we belive that CAs will do so. The delta CRL
needs
> to exist so that clients can follow the freshest CRL extension (either in
a
> certificate or a base CRL). The delta CRL that is issued at the same time
> SHOULD point to a previously issued full CRL (which will then, by
> definition be a base CRL) whenever possible. There is no information to
add
> to the new base CRL! By providing the delta as an update to a previous
base
> CRL, clients can download the delta CRL to construct the new base CRL.
> 
>  >The last point highlights the most noticeable difference. Other
differences
>  >appears when considering the guaranty to get the freshest information :
>  >using the traditional scheme and the thisUpdate and nextUpdate fields
the
>  >guaranty to get the freshest information is obtained, but cannot be
obtained
>  >using the other scheme. :-(
>  >
>  >Several people are referring to the X.509 document for arguments to
support
>  >that discussion. However, it is important to remember that we are
defining
>  >PKIX, not X.509, so we DO NOT need to copy and paste everything from
X.509,
>  >but only what we believe is relevant.
> 
> PKIX is a profile of X.509.  PKIX may impose additional requirements
beyond
> those in X.509 or may exclude features that are optional in X.509, but
> otherwise PKIX must be consistent with X.509. In that context, references
> to X.509 are appropriate.
> 
>  >We first need to clearly define the processing rules applicable to the
>  >relying parties. These rules will certainly contain SHALL/MUST
statements,
>  >but may also include some MAY statements which may even be conditional
to
>  >what the CA is doing. (I let Tim/David or Russ provide the MAY
statement).
>  >
>  >Here is a proposal for the MUST statement, based on the previous text I
>  >produced:
>  >
>  >    An application that is wishing to take advantage of delta CRLs
>  >    for a given scope, MUST first find a base CRL for that scope,
>  >    i.e. a full CRL that that contains a freshestCRL extension
>  >    (a.k.a. a Delta CRL distribution point).
> 
> No. The relying party needs a full CRL (either one that has been
downloaded
> from a repository or one that has been locally generated) against which
the
> delta CRL of interest may be applied. There is no requirement that the
full
> CRL be a base CRL.
> 
>  >    It may then construct
>  >    an updated CRL for that base, for a specific time T, by combining
>  >    it with a delta CRL which contains a delta CRL indicator extension
>  >    with the same CRL number as the base CRL.
> 
> It may construct an updated CRL by combining the delta CRL with any full
> CRL whose CRL number is greater than or equal to the CRL number of the
> referenced base.  By saying "equal" instead of "greater than or equal" we
> would be hiding useful information from implementors. We should not be
> hiding useful information.
> 
>  >    Applications that support
>  >    delta CRLs MUST ensure that time T falls between thisUpdate and
>  >    nextUpdate for both the base CRL and the delta CRL.
> 
> As stated above, the nextUpdate field in a base CRL specifies the time by
> which new revocation information will be available through full CRLs. A
> delta CRL may be applied to a base CRL as long as the CRL number in the
> base CRL is greater than or equal to the CRL number of the base CRL
> referenced by the delta CRL. The nextUpdate time of the base CRL is
irrelevant.
> 
>  >    Note: An application could also reconstruct an updated CRL, for
>  >    a specific time T, by using a previously locally reconstructed CRL
>  >    based on the current base CRL, and combining it with a delta CRL
which
>  >    contains a delta CRL indicator extension with the same CRL number as
>  >    the base CRL.
> 
> Same problem as above.  Need to say "greater than or equal to".
> 
>  >We also need to clearly separate the issuing rules applicable for the
CAs.
>  >These rules will certainly contain SHALL statements, but could also
include
>  >some MAY statements. (I let Tim/David or Russ provide the MAY
statement).
>  >
>  >Here is a proposal for the MUST statement, based on the previous text I
>  >produced:
>  >
>  >    A CA that supports delta-CRLs, MUST issue a base CRL,
> 
> This is an unnecessary statement. A delta CRL must include a
BaseCRLNumber.
> The CRL specified by that BaseCRLNumber is by definition a base CRL.  Of
> course, the referenced base CRL MUST be a full CRL.
> 
>  >    i.e. a full
>  >    CRL that contains a freshestCRL extension (a.k.a. a Delta CRL
>  >    distribution point).
> 
> While it might be a good idea to mandate the inclusion of the frestestCRL
> extension in full CRLs that are issued for scopes in which delta CRLs are
> also being issued, there is currently no such requirement in the draft
PKIX
> profile.
> 
>  >    For any time T until the nextUpdate time
>  >    indicated in a base CRL, the CA MUST provide one and only one
>  >    delta CRL that refers to that base CRL and for which time T
>  >    falls between thisUpdate and nextUpdate from the delta CRL.
> 
> This sentence has several problems:
> 
> 1) The nextUpdate time of a base CRL is the time when the next full CRL
> will be available, which may precede the time that the next base CRL will
> be issued.
> 
> 2) There is no requirement that a delta CRL use the most recently issued
> base CRL as its base.  I suppose that we could add this requirement for
the
> PKIX profile, but why?  Does it really simplify the client?  Or, does it
> just make it a wee bit harder to make a conforming CA that supports delta
CRLs?
> 
> 3) If the thisUpdate time of one delta CRL must equal the nextUpdate time
> of the previously issued delta CRL, then no time can be allotted to
account
> for propagation delays between when a delta-CRL is issued and when it is
> available in repositories for relying parties to obtain. Thus, there would
> be gaps between when the nextUpdate time of one delta-CRL was reached and
> when the next delta-CRL was available.
> 
> 4) There is nothing in either X.509 or the PKIX profile that prevents a CA
> from issuing an unscheduled (or "emergency") delta CRL. And, there should
> not be!  Many CAs intend to issue a new CRL (delta or otherwise)
> immediately upon the revocation of a certificate due to key compromise.
> When such an "emergency" delta CRL is issued, there will be two delta CRLs
> for which T falls between thisUpdate and nextUpdate. While it is true that
> there is no guarantee that relying parties will obtain the fresher of
these
> two delta CRLs, that is no reason to prevent the CA from issuing the
> "emergency" delta.  Some clients will obtain the emergency CRL.
> 
>  >In his e-mail from Wednesday, May 9, David said that delta-CRL
processing
>  >rules could be base on time instead of CRL numbers. This is a point of
which
>  >I strongly agree. Let us do it!
>  >
>  >(However, there is no need to add to PKIX, as he suggested, the support
of
>  >the baseUpdateTime extension from X.509 which would even more complicate
the
>  >problem.)
> 
> No. In order to base delta CRL processing on time, the baseUpdateTime
> extension must be present in the delta CRL. Furthermore, the presence of
> this extension would not complicate the problem. baseUpdateTime is a
> non-critical extension that merely provides useful information. If you
> don't think that the information provided by baseUpdateTime is useful,
> ignore it. Since the extension is non-critical and can be ignored, its
> presence can not complicate the problem.
> 
> At 09:05 AM 5/10/2001 -0400, Housley, Russ wrote:
> >Denis:
> >
> >>There is difference between a base CRL and a full CRL
> >
> >You are quite right.  I, for one, will try to be more careful about the
> >use of them.
> >
> >>Due to the fact that CRLs numbers are strictly increasing, two CRLs
whether
> >>they are a base CRL or delta CRL, CANNOT have the same CRL number.
> >
> >I disagree.  A full CRL (that may be a base CRL for subsequent delta
CRLs)
> >and a delta CRL issued at the same time as that full CRL may actually
> >represent the same revocation information.  In this case, they are the
> >same CRL, and they should have the same number.  There have been several
> >tables posted that illustrate this numbering scheme, and I do not see any
> >text in X.509-200 that indicates this scheme is
> [snip - truncate - the message is too long anyway]