Subject: Re: delta-CRLs

From: "David A. Cooper" <[email-masked]>
Date: Thu, 03 May 2001 16:26:35 -0400

At 06:05 PM 5/2/01 +0200, Denis Pinkas wrote:

The current is
wrong on two major aspects:

a) the numbering of the delta CRLs

Since you claim to want to support "traditional" delta-CRLs, I
will quote the text on delta-CRLs from section 12.6.3.3 of X.509 3rd
edition (1997):

a
delta-CRL shall not be issued without a corresponding complete CRL being
issued

at the
same time. The value of the CRL number, as conveyed in the CRL number
extension

field (if
present), shall be identical for both the delta-CRL and the corresponding
complete CRL

Similar text was included in one of the old proposed draft amendments to
the 1997 standard:

At reset
time, concurrent with publication of a new base CRL is publication of the
final

delta-CRL
for the old base CRL. Both CRLs published concurrently (new base and
final

delta for
old base) shall contain identical values of the
cRLNumber extension as well as

identical
values of thisUpdate time. The values of
nextUpdate time will be different in each.

Both texts are quite clear that when a complete CRL and a delta-CRL are
issued at the same time, and the two CRLs provide the same information,
they must have the same cRLnumber. This is because the are effectively
two instantiations of the same CRL.

Notice also that the requirement is that when a new base is issued, the
delta that is issued at the same time provides changes since the previous
base. One does not issue an empty delta. If one did, then every relying
party would be forced to download every base CRL.

b) the lack of use
of the fields thisUpdate and nextUpdate in the
delta-CRLs.

As I stated before, the thisUpdate field specifies the time at which the
CRL was issued. There is absolutely no reason to check that the current
time is after thisUpdate. We can re-visit this issue, if necessary, once
you have built a machine that allows people to travel back in time while
simultaneously validating an X.509 certificate. Until then, we can assume
that time increases monotonically and that the current time is always
after thisUpdate.

The nextUpdate field in a delta-CRL has the same meaning an in any other
type of CRL, so there is no reason to discuss it here. As I said before,
though, one can not say that any CRL whose nextUpdate time has not passed
is the most current. There may have been an "emergency" CRL
issued since that one was issued. If nextUpdate has passed, then you know
the CRL is not the most current. If nextUpdate has not passed, then the
CRL MAY be the most current, but there is no way to know for
certain.

> They seem to
depart from the traditional

> deltas in certain details,

They certainly do not.

As I stated above, you state that whenever a base CRL is issued, an empty
delta-CRL should be issued at the same time, with the delta-CRL using the
concurrently issued base CRL as its base. This is not how traditional
delta-CRLs work.

> but prevent
use of sliding window deltas.

Maybe. However, if you really want them to be part of this document,
then

they MUST *not* be mandatory. So the only way would be to add
additional

text that would explain how this can be done as an option. However I got
the

fealing that the traditional method may be in some way incompatible with
the

sliding window deltas, i.e. if the sliding method is chosen by the
CRL

Issuer relying parties may have difficulties to use the traditional
method.

But, maybe, you have the right text just ready to explain how this can
be

done. :-)

When I referred to the "traditional" method in my paper, I was
referring to the way delta-CRLs are issued, not how they are processed by
relying parties. Notice, however, that the deltaCRLIndicator requires
that "[t]he base CRL referenced by a
deltaCRLIndicator extension shall be a CRL that is
issued as complete for its scope (i.e. it is not itself a dCRL)." If
by "relying parties using the traditional method" you mean
always applying the delta-CRL to a full CRL whose cRLNumber is equal to
the value in BaseCRLNumber, this requirement on the deltaCRLIndicator
extension ensures that this can be done no matter how delta-CRLs are
issued (traditional method, sliding window, or other). I don't think that
anyone ever intended for this to be way that delta-CRLs are processed,
but you can do it if you want.

Even if delta-CRLs are issued using the "traditional" method,
relying parties may choose to maintain a locally generated revocation
list which they update which each successive delta-CRL that they
download. Remember that RFC 2459 stated:

The use of
delta-CRLs can significantly improve processing time for
applications

which
store revocation information in a format other than the CRL
structure.  This

allows
changes to be added to the local database while ignoring unchanged

information
that is already in the local database.

We should not write text that seems to preclude this option.

The text that is in the document now was painstakingly crafted by the ISO
Directory group and was carefully profiled by PKIX. The text does not
mandate sliding window delta-CRLs, nor does it specify a particular way
that relying parties must use delta-CRLs. It provides options to both CRL
issuers and relying parties, but does not impose requirements on either.
Please do not suggest that we change the text to preclude useful options
when doing so would provide no benefits.

> >[David] A
delta-CRL is nearly the same as a full CRL. It has a thisUpdate,

> >nextUpdate, cRLNumber, etc. just as a full CRL. It just has an
incomplete

> >list of revoked certificates.

> >[Denis] Yes, but you have to explain detail how a relying party
will use

> >thisUpdate, nextUpdate for a base CRL and thisUpdate, nextUpdate
for a delta

> >to make sure that in both cases he got the freshest
information.

There is no way, using CRLs, to ensure that you have the freshest
information. If nextUpdate has passed, then you know that fresher
information is available. If nextUpdate has not passed, then you do not
know whether you have the freshest information or not. This is true for
full CRLs, delta-CRLs, indirect CRLs, and any other type of CRL. If more
text is needed to explain the use of the nextUpdate field then it should
go in section 5.1.2.5 on the nextUpdate field, since it would apply to
all CRLs, not just delta-CRLs.

>[Denis]

> >As said later, your paper provides the right answer (on page 1):
" A

> >delta-CRL is a CRL that only provides information about
certificates who

> >statuses have changed since the issuance of a specific,
previously issued

> >CRL". The text says " *a* specific, previously issued
CRL", it does NOT say

> >"or any, more recently, issued
CRL".

You are misinterpreting the quote. The sentence states what information
is provided in a delta-CRL. It does not say anything about how the
delta-CRL can be used. A delta-CRL provides information about
certificates whose statuses have changed since the issuance of a
specific, previously issued CRL. The delta-CRL may, however, be applied
to more recently issued CRLs.

> > >
>This paper is proposing a method for over-issuing the CRLs. It omits
to take

> > > >into consideration that in PKIX-1 we mandate the CRL
number extension

> > > >(section 5.2.3) so we need to advertise the
nextUpdate. If you issue a CRL

> > > >before the next update you have no more way to know
which base CRL is the

> > > >freshest CRL. I believe this is a major security
weakness and for that

> > > >reason this mechanism should be
deprecated.

Over-issuing is really out-of-scope for this discussion. However,
over-issuing is merely one way to distribute revocation information more
efficiently. If you issue CRLs once every 4 hours and I issue CRLs once
an hour, but with a nextUpdate time 4 hours in the future, the
information relying parties get from me will be no more stale than the
information they get from you. If there is any "security
weakness" it is from the delay in distributing revocation
information, not from over-issuing.

>
>[David]  Finally, since a CRL issuer may issue
"emergency" delta-CRLs, there

> >is no guarantee that any delta-CRL whose nextUpdate time is
later than the

> >current time is the most current delta-CRL.

> >[Denis] If you issue such "emergency" delta-CRLs then
once again there is no

> >guarantee that they will ever be seen. The "most recent
delta-CRL" is any

> >delta CRL which satisfies the following condition :

> >" A delta-CRL which contains a Delta CRL Indicator equal to
the cRLNumber of

> >the base CRL and where the validation date (which may be the
current time)

> >is between thisUpdate and nextUpdate from that
delta-CRL;"

This seems to be a semantic problem. There can only be one "most
recent CRL". You seem to want to mandate that people always use the
"most recent CRL", but there is no way guarantee that you have
the most recent CRL.

> > >
>Any other method would first need to be proven to be secure
(over-issuing

> > > >CRLs and sliding window delta-CRLs have security
problems)

> >[Denis] There ARE security problems with sliding window
delta-CRLs. I have

> >descibed at length what the problems are. However, this does not
mean that

> >this technique cannot be supported as an OPTIO and IF we
indicate in the

> >text what are their security problems. The current text places
the two

> >techniques at the same level. The traditional way offers a
guarantee while

> >the other does not. There is indedd added complexity for
building the

> >software from the relying party.

You have not described any security problems with sliding window
delta-CRLs. You suggest that sliding window delta-CRLs should not be used
until they have been proven secure. What type of proof are you looking
for? Where are the proofs that CRLs of any type are secure? Where is the
proof that X.509 certificates are secure? Once you provide me with the
proofs that everything else in X.509 is secure, I'll try to find time to
write a similar proof to show that sliding window delta-CRLs are secure.
Until then, any suggestion that sliding window delta-CRLs need to be
proven to be secure before they can be used is nothing but a red
herring.

Dave

---

From: Denis Pinkas <[email-masked]>
Date: Fri, 04 May 2001 14:22:02 +0200

David,

This thread is now taking me (too) much time for my processing power. :-(

> >> The current is wrong on two major aspects:
> >>
> Since you claim to want to support "traditional" delta-CRLs, I will quote
> the text on delta-CRLs from section 12.6.3.3 of X.509 3rd edition (1997):
> 
> a delta-CRL shall not be issued without a corresponding complete
> CRL being issued at the same time. The value of the CRL number, 
> as conveyed in the CRL number extension field (if present), shall 
> be identical for both the delta-CRL and the corresponding complete CRL
> 
> At reset time, concurrent with publication of a new base CRL is
> publication of the final delta-CRL for the old base CRL. Both CRLs 
> published concurrently (new base and final delta for old base) shall 
> contain identical values of the cRLNumber extension as well as
> identical values of thisUpdate time. The values of nextUpdate time
> will be different in each.
> 
> they must have the same cRLnumber. This is because the are effectively two
> instantiations of the same CRL.

The ISO text has two major problems:

1) It makes a major assumption, ... which is wrong: once a CA has started to
issue a base CRL (and hence it will issue delta-CRLs) then it must do it for
ever. A CA can issue a base CRL and then delta CRLs but then simply issue
complete CRL (i.e. full CRLs that do not support the delta mechanism) and
later one can start to issue a base a delta CRLs again.

2)  RFC 2459 in section 5.2.3 (CRL Number) says: 

   The CRL number is a non-critical CRL extension which conveys a
   monotonically increasing sequence number for each CRL issued by a CA.

Since two CRLs (whether they are base, delta, complete, whatever) cannot
have the same number, this means that the following sentence extracted from
the ISO text is wrong: "The value of the CRL number, as conveyed in the CRL
number extension field (if present), shall be identical for both the
delta-CRL and the corresponding complete CRL". 

> base. 

This is wrong as well because there is not necessarilly this previous base
(see the first major problem).

> One does not issue an empty delta. If one did, then every relying

This is the intent, otherwise delta CRLs would grow for ever.

> >> b) the lack of use of the fields thisUpdate and nextUpdate in the
> >> delta-CRLs.

> time is after thisUpdate. 

There is no notion of current time. The evaluation is made at time T, which
may be the current time or a time in the past.

> We can re-visit this issue, if necessary, once

No need to invent such a machine, but I appreciate your sense of humor.
Please keep flames away. See the previous comment.

> is the most current. There may have been an "emergency" CRL issued since
> that one was issued. If nextUpdate has passed, then you know the CRL is
> not the most current. If nextUpdate has not passed, then the CRL MAY be
> the most current, but there is no way to know for certain.

See my response to Tim on that topic.

> >> > They seem to depart from the traditional
 
> concurrently issued base CRL as its base. This is not how traditional

Think about it. To do that you have to take an example: a *first* base CRL
is issued at midnight (no base CRL *ever* exists before). A delta is
supposed to be issued every hour. Think first about the processing done by a
relying party at 3:30 a.m. Then think about the processing that will be done
at 0:30 a.m. You will then come to the same conclusion. Now if a base
existed before, then the proposal would not be consistant with the
definition of the construction of the updated CRL which is: 

   An application can construct an updated CRL, for a specific time T, 
   by retrieving the appropriate base CRL for that scope, and combining 
   it with a delta CRL which contains a delta CRL indicator extension 
   with the same CRL number as the base CRL.

Futhermore, the size of the delta CRLs would grow for ever.
 
> >> > but prevent use of sliding window deltas.
> >>
> >> text that would explain how this can be done as an option. However I
> >> got the
> >> fealing that the traditional method may be in some way incompatible
> >> with the
> >> sliding window deltas, i.e. if the sliding method is chosen by the CRL
 
> When I referred to the "traditional" method in my paper, I was referring
> to the way delta-CRLs are issued, not how they are processed by relying
> parties. Notice, however, that the deltaCRLIndicator requires that "[t]he
> base CRL referenced by a deltaCRLIndicator extension shall be a CRL that
> is issued as complete for its scope (i.e. it is not itself a dCRL)." If by
> "relying parties using the traditional method" you mean always applying
> the delta-CRL to a full CRL whose cRLNumber is equal to the value in
> BaseCRLNumber, this requirement on the deltaCRLIndicator extension ensures
> that this can be done no matter how delta-CRLs are issued (traditional
> method, sliding window, or other). I don't think that anyone ever intended
> for this to be way that delta-CRLs are processed, but you can do it if you
> want.

I undersand clearly that you would like relying parties to take advantage of
sliding windows, by the "algorithm" that you proposed, which is based on the
ISO text, has flaws in it. See above.

> Even if delta-CRLs are issued using the "traditional" method, relying
> parties may choose to maintain a locally generated revocation list which
> they update which each successive delta-CRL that they download. 

I have addressed that point in details in my response to Tim. I think we
agree on this point.

> Remember that RFC 2459 stated:
> 
> The use of delta-CRLs can significantly improve processing time
> for applications
> which store revocation information in a format other than the CRL
> structure.  This
> allows changes to be added to the local database while ignoring
> unchanged information that is already in the local database.
> 

The ISO text has problems, so the text based on it has problems too. 

> >> > >[David] A delta-CRL is nearly the same as a full CRL. It has a
> >> thisUpdate,
> >> > >to make sure that in both cases he got the freshest information.
> >
 
> There is no way, using CRLs, to ensure that you have the freshest

True. But if you are using both base CRLs and delta-CRLs then you have that
guaranty up to the period of refresh of the delta-CRL (which is of course
much better than the period of refresh from the base CRL).

> If nextUpdate has passed, then you know that fresher
> go in section 5.1.2.5 on the nextUpdate field, since it would apply to all
> CRLs, not just delta-CRLs.
> 
> >> > >[Denis]
> >> > >
> >> > >As said later, your paper provides the right answer (on page 1): "
> >> A
> >> > >statuses have changed since the issuance of a specific, previously
> >> issued
> >> > >CRL". The text says " *a* specific, previously issued CRL", it does
> >> NOT say
> >> > >"or any, more recently, issued CRL".
 
> You are misinterpreting the quote. The sentence states what information is
> provided in a delta-CRL. It does not say anything about how the delta-CRL
> can be used. A delta-CRL provides information about certificates whose
> statuses have changed since the issuance of a specific, previously issued
> CRL. The delta-CRL may, however, be applied to more recently issued CRLs.

In the same spirit as you did, I could say that we would need a machine that
allows people to travel in the future. However, delta-CRLs cannot be applied
to more recently issued CRLs, unless you provide a clear example of how this
can be done.

> >> > > > >This paper is proposing a method for over-issuing the CRLs. It
> >> omits to take
> >> > > > >into consideration that in PKIX-1 we mandate the CRL number
> >> extension
> >> > > > >(section 5.2.3) so we need to advertise the nextUpdate. If you
> >> issue a CRL
> >> > > > >before the next update you have no more way to know which base
> >> CRL is the
> >> > > > >freshest CRL. I believe this is a major security weakness and
> >> for that
> >> > > > >reason this mechanism should be deprecated.

> efficiently. If you issue CRLs once every 4 hours and I issue CRLs once an
> hour, but with a nextUpdate time 4 hours in the future, the information
> relying parties get from me will be no more stale than the information
> they get from you. If there is any "security weakness" it is from the
> delay in distributing revocation information, not from over-issuing.

Over-issuing of full CRLs provides a guaranty up to (usually less than) the
period of validity of the full CRL. A base CRL followed by delta-CRLs
provides a guaranty up to the period of validity of the delta CRLs (which is
indeed better). If mis-used, over-issuing of full CRLs provides could
provide a guaranty *equal* to the period of validity of the full CRL (which
is indeed worse).
 
> >> > >[David]  Finally, since a CRL issuer may issue "emergency"
> >> delta-CRLs, there
> >> > >is no guarantee that any delta-CRL whose nextUpdate time is later
> >> than the
> >> > >[Denis] If you issue such "emergency" delta-CRLs then once again
> >> there is no
> >> > >guarantee that they will ever be seen. The "most recent delta-CRL"
> >> is any
> >> > >" A delta-CRL which contains a Delta CRL Indicator equal to the
> >> cRLNumber of
> >> > >is between thisUpdate and nextUpdate from that delta-CRL;"
 
> This seems to be a semantic problem. There can only be one "most recent
> CRL". You seem to want to mandate that people always use the "most recent
> CRL", but there is no way guarantee that you have the most recent CRL.

See the response above and my response to Tim.

> >> > > > >CRLs and sliding window delta-CRLs have security problems)
> >>
> >> > >[Denis] There ARE security problems with sliding window delta-CRLs.
> >> I have
> >> > >this technique cannot be supported as an OPTIO and IF we indicate
> >> in the
> >> > >text what are their security problems. The current text places the
> >> two
> >> > >the other does not. There is indedd added complexity for building
> >> the
 
> proven to be secure before they can be used is nothing but a red herring.

No comment.

Denis

---

From: Tim Polk <[email-masked]>
Date: Fri, 04 May 2001 10:12:40 -0400

Denis,

Yes, I would agree.  This thread is consuming far too much time for all of 
us.  As we have diametrically opposed views, that cannot be helped.  I will 
try to be brief, though....

>later one can start to issue a base a delta CRLs again.

I would agree that a CA is not required to issue deltas forever.  A CA 
could issue a complete CRL (call it CRL-1), a series of deltas fusing CRL-1 
as a base base, then a new complete CRL (CRL-2), then more deltas using 
CRL-2 as a base.  I do not believe the ISO text precludes this scenario.

>delta-CRL and the corresponding complete CRL".

Denis, a delta CRL may only be used in combination with a base CRL, 
right?  The CRL number in the delta is the CRL number of the *constructed* 
CRL.  When the delta and base combine to form *the same* CRL as a complete 
CRL, the complete CRL will have the same CRL number.  Since the delta and 
*any legal base CRL* will combine to form *the same* CRL, the complete CRL 
and the delta MUST have the same CRL number.

Note that this is *crucial* if we intend to use the constructed CRL as a 
base CRL in the future.  If you cannot assign a CRL number to the 
constructed CRL you cannot use it as a base.

>Futhermore, the size of the delta CRLs would grow for ever.

If you issue one complete CRL and only issue deltas in the future, all of 
which refer to the one complete CRL as a base, the delta will grow 
forever.  I am certain *no one* has suggested that scenario, though.  It

---

From: "David A. Cooper" <[email-masked]>
Date: Fri, 04 May 2001 11:23:02 -0400

David,

This thread is now taking me (too) much time for my processing power.
:-(

1) It makes a major assumption, ... which is wrong: once a CA has started
to

issue a base CRL (and hence it will issue delta-CRLs) then it must do it
for

ever. A CA can issue a base CRL and then delta CRLs but then simply
issue

complete CRL (i.e. full CRLs that do not support the delta mechanism)
and

later one can start to issue a base a delta CRLs
again.

I not sure why you think the text is making an assumption, but there
seems to be a misunderstanding here. There is nothing special about a
base CRL. There are no flags that are placed in a CRL to indicate that it
is a base CRL. A base CRL is simply "[a] CRL that is used as the
foundation in the generation of a dCRL" [X.509 4th ed.] Thus, any
CRL that is referenced in the BaseCRLNumber field of a delta-CRL is a
base CRL. The deltaCRLIndicator extension imposes a requirement that only
CRLs that were issued as complete for scope CRLs can be used as base
CRLs, but this is beside the point. One does not issue a "base
CRL" to advertise that delta-CRLs will be issued in the future. One
issues full CRLs. If, at some point in the future, a delta-CRL species a
full CRL as its base, then that full CRL is a base CRL.

2)  RFC 2459 in section 5.2.3 (CRL
Number) says:

The CRL number is a non-critical CRL extension which conveys
a

monotonically increasing sequence number for each CRL issued
by a CA.

Since two CRLs (whether they are base, delta, complete, whatever)
cannot

have the same number, this means that the following sentence extracted
from

the ISO text is wrong: "The value of the CRL number, as conveyed in
the CRL

number extension field (if present), shall be identical for both
the

Again, you are misinterpreting this text. If a full CRL and a delta-CRL
cover the set of certificates and revocation reasons (i.e., scope) and
are issued at the same time, then they are effectively two instantiations
of the same CRL. They must then (as the standard requires) have the same
cRLNumber.

> base.

This is wrong as well because there is not necessarilly this previous
base

> party would be forced to download every base CRL.

This is the intent, otherwise delta CRLs would grow for
ever.

This is not true. I have constructed an example below (hopefully it is
well formatted so that it is readable). The example below shows the
"traditional" method of issuing delta-CRLs. In this example,
full CRLs are issued once every 3 hours and deltas are issued once an
hour. As you have stated, if one wishes to begin issuing deltas at the
same time that the very first full CRL, the delta must use the
concurrently issued full CRL as its base. After that, however, a delta
can always use a previously issued full CRL as its base. Notice that
starting with cRLNumber 4, the delta CRL issued at the same time as a
full CRL uses the previously issued full CRL as its base. However, the
delta-CRLs never provide more than 3 hours of history. They do not grow
forever.

current   revoked

time
certificates full
CRL                        delta-CRL

------------------------------------------------------------

12:00           {14}            cRLNumber
=
1                   cRLNumber
= 1

thisUpdate
=
12:00              thisUpdate
= 12:00

nextUpdate
=
15:00              nextUpdate
= 13:00

BaseCRLNumber
= 1

CertificateList
=
{14}          CertificateList
= {}

13:00           {14,
124}                                       cRLNumber
= 2

thisUpdate
= 13:00

nextUpdate
= 14:00

BaseCRLNumber
= 1

CertificateList
= {124}

14:00           {14,
124}                                       cRLNumber
= 3

thisUpdate
= 14:00

nextUpdate
= 15:00

BaseCRLNumber
= 1

CertificateList
= {124}

15:00           {14,
124, 39}   cRLNumber =
4                   cRLNumber
= 4

thisUpdate
=
15:00              thisUpdate
= 15:00

nextUpdate
=
18:00              nextUpdate
= 16:00

BaseCRLNumber
= 1

CertificateList
= {14, 124, 39} CertificateList = {124, 39}

16:00           {14,
124,
39,                                   cRLNumber
= 5

67}                                            thisUpdate = 16:00

nextUpdate = 17:00

BaseCRLNumber = 4

CertificateList = {67}

17:00           {14, 124, 39,                                   cRLNumber = 6

67}                                            thisUpdate = 17:00

nextUpdate = 18:00

BaseCRLNumber = 4

CertificateList = {67}

18:00           {14, 124, 39,   cRLNumber = 7                   cRLNumber = 7

67}            thisUpdate = 18:00              thisUpdate = 18:00

nextUpdate = 21:00              nextUpdate = 19:00

BaseCRLNumber = 4

CertificateList = {14, 124, 39, CertificateList = {67}

21}

19:00           {14, 124, 39,                                   cRLNumber = 8

67}                                            thisUpdate = 19:00

nextUpdate = 20:00

BaseCRLNumber = 7

CertificateList = {}

In the note to which I was responding, you had proposed the following text:

> > > > An application can construct a CRL that is the most current for

> > > > a given scope, at the current time, by retrieving the current

> > > > base CRL for that scope, and combining it with a delta-CRL which

> > > > contains a Delta CRL Indicator equal to the cRLNumber of the base

> > > > CRL and where the current date from that delta-CRL is between

> > > > thisUpdate and nextUpdate;

In the proposed text, you specifically stated that the goal was to construct a CRL that is most current *at the current time*. If the text is changed to also describe how to determine the status of a certificate at some point in the past, then the situation becomes more complicated.

I saw your response. X.509 states: "nextUpdate, if present, indicates the date/time by which the next revocation list in this series will be issued. The next revocation list could be issued before the indicated date, but it will not be issued any later than the indicated time." While the term "emergency CRL" is not in the text, it does state that a new CRL may be issued before the date indicated in nextUpdate. Can you find anywhere in the text that suggests that this does not apply to delta-CRLs?

Not true. See the example above.

Your belief that there are flaws in the ISO text is based on a misinterpretation of the cRLNumber field. Since this field is vital to the efficient use of delta-CRLs, this misinterpretation may be the reason for your confusion.

agree on this point.

The text on delta-CRLs has two basic parts. One part, which is normative, describes what information a CRL issuer needs to place in a delta-CRL. The other part, which is informative, describes what information relying parties need to make use of delta-CRLs. If we use your text (below), then we are being less informative than we could be.

The text hides from implementers the fact that a delta-CRL may be used in conjunction with a full CRL that was issued after the referenced base CRL was issued. The follow-up text ("Conforming implementations of this specification are not required to implement the above algorithm, but MUST provide functionality equivalent to the external behavior resulting from this procedure.") is only a source of confusion. The text above does not describe an algorithm, it merely states what information is required to construct an updated CRL using base CRLs and delta-CRLs. An algorithm would state how to construct an updated CRL.

At time T, you know that the information in a CRL (any type of CRL) is no older than T - thisUpdate. There is no guarantee that another CRL was not issued after thisUpdate, even if  T < nextUpdate (see above).

> >> > >As said later, your paper provides the right answer (on page 1): "A

> >> > >delta-CRL is a CRL that only provides information about certificates who

> >> > >CRL". The text says " *a* specific, previously issued CRL", it does NOT say

can be done.

OK. Here is an example. Suppose that you have a delta-CRL with a cRLNumber of 8 and a BaseCRLNumber of 5. You also have a full CRL with a cRLNumber of 6. The following algorithm can then be used to determine the status of a certificate that is covered by the CRL at the time that the delta-CRL was issued (assume the certificate in question has serial number 153):

1) If 153 is listed on full CRL number 6, but not the delta-CRL, then it is revoked with the revocation reason stated in full CRL number 6.

2) If 153 is listed on the delta-CRL with a revocation reason of removeFromCRL, then it would not be found on a full CRL issued at the time the delta-CRL was issued. In this case it does not matter whether 153 was listed on full CRL number 6. The reason that it would not be on the full CRL (number 8) is unknown. It could either be that the certificate was removed from hold or that the certificate expired.

3) If 153 is listed on the delta-CRL with a revocation reason other than removeFromCRL, then it is revoked with the revocation reason stated in the delta-CRL. Again, in this case, it does not matter whether 153 was listed on full CRL number 6.

4) If 153 is not listed on either full CRL number 6 or the delta-CRL, then it is not revoked (or it expired before CRL number 6 was issued).

I created this algorithm on the fly, so it may not be perfect, but it should be sufficiently close to correct to be understandable. Notice, however, that the cRLNumber field is very important here. In order for this algorithm to work you must ensure that cRLNumber of the full CRL you use is greater than or equal to the BaseCRLNumber in the delta-CRL and less than the cRLNumber in the delta-CRL. One must be able to compare the CRL numbers in order to check that the delta-CRL and full CRL can be combined.

> >> > > > >This paper is proposing a method for over-issuing the CRLs. It omits to take

> >> > > > >into consideration that in PKIX-1 we mandate the CRL number extension

> >> > > > >(section 5.2.3) so we need to advertise the nextUpdate. If you issue a CRL

> >> > > > >before the next update you have no more way to know which base CRL is the

> >> > > > >freshest CRL. I believe this is a major security weakness and for that

is indeed worse).

What guaranty are you talking about? You can compare the current time (or some other time T) to the time in thisUpdate to determine how fresh the revocation information is. What other guarantees do you think are provided?

> > You replace this with:

> > CAs must ensure that application of a delta CRL to the referenced

> > base revocation information accurately reflects the current status of

> > revocation. If a CA supports the certificateHold revocation reason

> > the following rules must be applied when generating delta CRLs:

> > (a) If a certificate was listed as revoked with revocation reason

> > certificateHold on a CRL (either a delta CRL or a CRL that is

> > complete for a given scope), and the hold is subsequently

> > released, the certificate must be listed with revocation reason

> > removeFromCRL until the next base CRL is issued.

> > Note: Should the certificate be subsequently revoked again for

> > one of the revocation reasons covered by the delta CRL,

> > then the certificate must be listed with the revocation

> > reason appropriate for the subsequent revocation.

> > (b) If the certificate was not removed from hold, but was

> > permanently revoked, then it must be listed as such on all

> subsequent delta CRLs until the next base CRL is issued .

> > This text presents the biggest problems of all. The text describes *what*

> > needs to be listed on *which* delta CRLs. By limiting this text to one

> > very narrow scenario, you increase the likeliehood that delta CRL issuers

> > that wish to do something efficient will get it wrong. That will result

> > in bad information from the relying party.

> This text has be simply adapted to remove the semantics that existed on the

> CRL number from delta-CRLs. It describes what a CA does, not what a relying

> party does. I do not believe that there is the limitation as you mention. If

> you really think that the text needs to be changed, please make a proposal

> on it, but without adding any new seamntics to the CRL number. :-)

It may have been your intention to simply re-word the text without changing the semantics, but this was not the result. The new text describes a different set of semantics and these new semantics prevent CRL issuers from issuing delta-CRLs in any way except one very inefficient manner. Without reference to CRL numbers, it is not possible to properly describe the rules for constructing delta-CRLs.

Dave

---

From: Denis Pinkas <[email-masked]>
Date: Fri, 04 May 2001 17:28:31 +0200

Tim,

I would have no problem to continue the discussion with one of you and this
would have the benefit to cut down the number of exchanges by a factor of
two. I sent an e-mail to *you* and you answer to the e-mail sent to David.
:-(

I did answer the main point of your e-mail. I would appreciate your feeback.

I will nevertheless answer to the two comments you made on the e-mail sent
to David and delete the rest of the e-mail for readability for the moment. 
I guess you hit the "send" key too early since your third comment is
incomplete.

 
> CRL-2 as a base.  I do not believe the ISO text precludes this scenario.

The ISO text is implicitly saying that using a base CRL issued on January 1,
2001, and by applying all issued delta CRLs since then, you can get the
current CRL from May 4, 2001. The first problem is that base CRLs are not
necessarilly continously issued. The second problem is that all delta CRLs
would have to be obtained. The third problem is the way the cross the
border: when the new base CRL is issued the delta shall refer to the new
base CRL, not the previous base CRL (which does not necessarily exist).

 
> right?  

Yes. More precisely *ONE* base CRL. Right ?

> The CRL number in the delta is the CRL number of the *constructed*
> CRL.  

No. The *constructed* CRL is local one, which has no number assigned by the
CA. You can locally give it a reference, but this is a local matter. 

> When the delta and base combine to form *the same* CRL as a complete
> CRL, the complete CRL will have the same CRL number.

Do you mean that the complete CRL is issued by the CA or is it a locally
reconstructed one ?

Is, what you call, a "complete CRL", a new base CRL or the locally
reconstructed one ?

> Since the delta and *any legal base CRL* will combine to form 
> *the same* CRL, the complete CRL and the delta MUST have the same 
> CRL number.

Certainly not. Either this would infringe the text from RFC 2459:

or this numbering is a local matter, and thus that is a local implementation
detail.
 
> constructed CRL you cannot use it as a base.

Of course you can without using this numbering. You only need to know, as I
already said, that this is the CRL consructed from the base CRL numbered
XXXX, by adding the delta CRL which has the next update scheduled at YY:YY.

Regards,

Denis

---

From: Denis Pinkas <[email-masked]>
Date: Fri, 04 May 2001 17:57:58 +0200

David,

As I just said in the e-mail I sent to Tim, I would appreciate that you
coordinate your responses with Tim.

I cannot sustain any more so long e-mails.

I believe that we have now a private conference call on next Wednesday on
this topic.

Please read carefully the e-mails sent to Tim.

Regards,

Denis

> I not sure why you think the text is making an assumption, but there seems
> to be a misunderstanding here. There is nothing special about a base CRL.
> There are no flags that are placed in a CRL to indicate that it is a base
> CRL. A base CRL is simply "[a] CRL that is used as the foundation in the
> generation of a dCRL" [X.509 4th ed.] Thus, any CRL that is referenced in
> the BaseCRLNumber field of a delta-CRL is a base CRL. The
> deltaCRLIndicator extension imposes a requirement that only CRLs that were
> issued as complete for scope CRLs can be used as base CRLs, but this is
> beside the point. One does not issue a "base CRL" to advertise that
> delta-CRLs will be issued in the future. One issues full CRLs. If, at some
> point in the future, a delta-CRL species a full CRL as its base, then that
> full CRL is a base CRL.
> 
> cover the set of certificates and revocation reasons (i.e., scope) and are
> issued at the same time, then they are effectively two instantiations of
> the same CRL. They must then (as the standard requires) have the same
> cRLNumber.
> 
> "traditional" method of issuing delta-CRLs. In this example, full CRLs are
> issued once every 3 hours and deltas are issued once an hour. As you have
> stated, if one wishes to begin issuing deltas at the same time that the
> very first full CRL, the delta must use the concurrently issued full CRL
> as its base. After that, however, a delta can always use a previously
> issued full CRL as its base. Notice that starting with cRLNumber 4, the
> delta CRL issued at the same time as a full CRL uses the previously issued
> full CRL as its base. However, the delta-CRLs never provide more than 3
> hours of history. They do not grow forever.
> 
> current   revoked
> time       certificates full CRL                        delta-CRL
> 12:00           {14}            cRLNumber = 1                   cRLNumber
> = 1
>                                 thisUpdate = 12:00              thisUpdate
> = 12:00
>                                 nextUpdate = 15:00              nextUpdate
> = 13:00
>                                                                 BaseCRLNumber
> = 1
>                                 CertificateList =
> {14}          CertificateList = {}
> 
> 13:00           {14, 124}                                       cRLNumber
> = 2
>                                                                 thisUpdate
> = 13:00
>                                                                 nextUpdate
> = 14:00
>                                                                 BaseCRLNumber
> = 1
>                                                                 CertificateList
> = {124}
> 
> 14:00           {14, 124}                                       cRLNumber
> = 3
>                                                                 thisUpdate
> = 14:00
>                                                                 nextUpdate
> = 15:00
>                                                                 BaseCRLNumber
> = 1
>                                                                 CertificateList
> = {124}
> 
> 15:00           {14, 124, 39}   cRLNumber = 4                   cRLNumber
> = 4
>                                 thisUpdate = 15:00              thisUpdate
> = 15:00
>                                 nextUpdate = 18:00              nextUpdate
> = 16:00
>                                                                 BaseCRLNumber
> = 1
>                                 CertificateList = {14, 124,
> 39} CertificateList = {124, 39}
> 
> 16:00           {14, 124, 39,                                   cRLNumber
> = 5
>                  67}                                            thisUpdate
> = 16:00
>                                                                 nextUpdate
> = 17:00
>                                                                 BaseCRLNumber
> = 4
>                                                                 CertificateList
> = {67}
> 
>                  67}                                            thisUpdate
> = 17:00
> = 18:00
> = {67}
>                  67}                                            thisUpdate
> = 19:00
> = 20:00
> = 7
> In the proposed text, you specifically stated that the goal was to
> construct a CRL that is most current *at the current time*. If the text is
> changed to also describe how to determine the status of a certificate at
> some point in the past, then the situation becomes more complicated.
> 
> I saw your response. X.509 states: "nextUpdate, if present, indicates the
> date/time by which the next revocation list in this series will be issued.
> The next revocation list could be issued before the indicated date, but it
> will not be issued any later than the indicated time." While the term
> "emergency CRL" is not in the text, it does state that a new CRL may be
> issued before the date indicated in nextUpdate. Can you find anywhere in
> the text that suggests that this does not apply to delta-CRLs?
> 
> > referring
> Your belief that there are flaws in the ISO text is based on a
> misinterpretation of the cRLNumber field. Since this field is vital to the
> efficient use of delta-CRLs, this misinterpretation may be the reason for
> your confusion.
> 
> The text on delta-CRLs has two basic parts. One part, which is normative,
> describes what information a CRL issuer needs to place in a delta-CRL. The
> other part, which is informative, describes what information relying
> parties need to make use of delta-CRLs. If we use your text (below), then
> we are being less informative than we could be.
> 
> The text hides from implementers the fact that a delta-CRL may be used in
> conjunction with a full CRL that was issued after the referenced base CRL
> was issued. The follow-up text ("Conforming implementations of this
> specification are not required to implement the above algorithm, but MUST
> provide functionality equivalent to the external behavior resulting from
> this procedure.") is only a source of confusion. The text above does not
> describe an algorithm, it merely states what information is required to
> construct an updated CRL using base CRLs and delta-CRLs. An algorithm
> would state how to construct an updated CRL.
> 
> At time T, you know that the information in a CRL (any type of CRL) is no
> older than T - thisUpdate. There is no guarantee that another CRL was not
> issued after thisUpdate, even if  T < nextUpdate (see above).
> 
> > > >> > >[Denis]
> > > >> > >
> > "A
> OK. Here is an example. Suppose that you have a delta-CRL with a cRLNumber
> of 8 and a BaseCRLNumber of 5. You also have a full CRL with a cRLNumber
> of 6. The following algorithm can then be used to determine the status of
> a certificate that is covered by the CRL at the time that the delta-CRL
> was issued (assume the certificate in question has serial number 153):
> 
> 1) If 153 is listed on full CRL number 6, but not the delta-CRL, then it
> is revoked with the revocation reason stated in full CRL number 6.
> 
> 2) If 153 is listed on the delta-CRL with a revocation reason of
> removeFromCRL, then it would not be found on a full CRL issued at the time
> the delta-CRL was issued. In this case it does not matter whether 153 was
> listed on full CRL number 6. The reason that it would not be on the full
> CRL (number 8) is unknown. It could either be that the certificate was
> removed from hold or that the certificate expired.
> 
> 3) If 153 is listed on the delta-CRL with a revocation reason other than
> removeFromCRL, then it is revoked with the revocation reason stated in the
> delta-CRL. Again, in this case, it does not matter whether 153 was listed
> on full CRL number 6.
> 
> 4) If 153 is not listed on either full CRL number 6 or the delta-CRL, then
> it is not revoked (or it expired before CRL number 6 was issued).
> 
> I created this algorithm on the fly, so it may not be perfect, but it
> should be sufficiently close to correct to be understandable. Notice,
> however, that the cRLNumber field is very important here. In order for
> this algorithm to work you must ensure that cRLNumber of the full CRL you
> use is greater than or equal to the BaseCRLNumber in the delta-CRL and
> less than the cRLNumber in the delta-CRL. One must be able to compare the
> CRL numbers in order to check that the delta-CRL and full CRL can be
> combined.
> 
> What guaranty are you talking about? You can compare the current time (or
> some other time T) to the time in thisUpdate to determine how fresh the
> revocation information is. What other guarantees do you think are
> provided?
> 
> > > You replace this with:
> > >
> It may have been your intention to simply re-word the text without
> changing the semantics, but this was not the result. The new text
> describes a different set of semantics and these new semantics prevent CRL
> issuers from issuing delta-CRLs in any way except one very inefficient
> manner. Without reference to CRL numbers, it is not possible to properly
> describe the rules for constructing delta-CRLs.
> 
> Dave