Re: delta-CRLs (was Re: LastCall:draft-ietf-pkix-new-part1-06.txt comments)

[Denis Pinkas <Denis.Pinkas@xxxxxxxx>]

David,


This is a LONG e-mail and a last e-mail to you, before leaving for a trip
that will keep me away from my e-mails during a week. So, don't think I am
giving up if you do not receive a reply soon.

> Denis,
> 
> My comments are in line.
> 
> At 06:50 PM 4/20/01 +0200, Denis Pinkas wrote:
> >[Denis] This is the case I had in mind. However I would disagree to say that
> >the locally contructed CRL is equal to the full CRL number 8, because there
> >is no need to issue such CRL (see the first comment). It is simply the
> >"freshest CRL constructed from the base CRL number 5 for 3:10 am". This
> >locally contructed CRL bears no number, or if you assign one, this is a
> >local matter and is not part of the standard. This also avoids the later
> >confusing between CRL numbers.
 
[David] This is simply not true. 

[Denis] The sentence above is technically correct: "It is simply the
freshest CRL constructed from the base CRL number 5 for 3:10 am".
 
[David] A delta-CRL can (will) contain the cRLNumber extension just as a
full CRL will. 

[Denis] The cRLNumber extension is simply an identifier that allows you to
uniquely identify it and to know whether it is earlier or later another CRL
issued by the same CRL issuer.

[David] If a full CRL and a delta-CRL are issued at the same time, the
combination of the delta-CRL and an appropriate base CRL must be equivalent
to the full CRL, and both the delta-CRL and the full CRL must have the same
cRLNumber. 

[Denis] This is where we do not agree. The delta-CRL and the full CRL MUST
NOT have the same cRLNumber because this would violate the definition of
what is a CRLnumber. RFC 2459 says: 

5.2.3  CRL Number

   The CRL number is a non-critical CRL extension which conveys a
   monotonically increasing sequence number for each CRL issued by a CA.
   This extension allows users to easily determine when a particular CRL
   supersedes another CRL.  CAs conforming to this profile MUST include
   this extension in all CRLs.

Maybe you are making some confusion with the deltaCRLindicator. 

The construction you mention is not acceptable and is no even part of the
ISO X509 document.

[David] If a delta-CRL is issued, and no corresponding full CRL issued, then
the combination of the delta-CRL and an appropriate base CRL should be
equivalent to the full CRL that would have been issued at that time, if a
full CRL had been issued. 

[Denis] Here is the problem ! Let us take an example: A base CRL
is issued at midnight. thisUpdate is set to midnight while nextUpdate is
midnight for the next day. This means that there is no guarantee at all that
any other base/full CRL will necessarily be seen within the next 24 hours.
Certainly a base can be issued before, but once again there is no guarantee
that it will ever be seen. If someone is now using the CRL as a proof to be
presented later on that the certificate was not revoked, a relying party 
is perfectly right to use the base from midnight (if allowed by the
validation policy) or the base plus a delta (if mandated by the validation
policy).    

Now if you issue a full CRL (I did not say a base CRL) every hour at the
same time you issue a delta, the problem becomes worse because at 11:30 p.m.
you have now 23 full CRLs, and you cannot know which one is the right one to
use (if someone purposely is blocking the transmission of the latest full
CRLs), unless precisely you introduce he statement that is the cause of all
this trouble:

   When a conforming CA issues a delta CRL, the CA MUST also issue a CRL
   that is complete for the given scope.  

Now understand better the problem: this is a stone fundation of the whole
edifice. If we take it away, the whole edifice collapses.

Anyway, the intention has never been that relying parties will necessarilly
get the same level of information when using only base CRLs and when using
base CRLs plus deltas.

The question which arises now is what are the implications if a full CRL is
issued at the same time a delta is issued and when we apply the modified
sentence:

   When a conforming CA issues a delta CRL, the CA MAY also issue a full CRL
   that is complete for the given scope.  

In this case the relying pary is using the delta (*in the way I have
described it*), i.e. testing thisUpdate and nextUpdate from the delta CRL,
it will get a GUARANTEE to obtain either the freshest revocation
information or it will know that the freshest revocation information is not
available.

In the case the relying pary is using not using the delta, he will have no
GUARANTEE that the information he got is the freshest.

[David] The delta-CRL should have the same cRLNumber as would have been
assigned to a full CRL issued at the same time.

[Denis] Once again, I disagree, since this would violate the definition of
CRL Number given in section 5.2.3. 
 
[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.

Remember that RFC 2459 says:

   The behavior of clients processing CRLs which
   omit nextUpdate is not specified by this profile.

So, in order to be PKIX compliant, you cannot escape a sentence which tells
what use is made of that field.

> > > A few hours later, at 6:30am, the relying party performs another validation. The relying party has, in its local cache, the contents of CRL number 8 (which it constructed at 3:10am). It wants to update the information in its local case to based on the newly available revocation information. So, it obtains the latest delta-CRL. This delta-CRL has a CRL number of 11 and a BaseCRLnumber of 5. Since it has a BaseCRLNumber of 5, the delta-CRL provides status information for all certificates whose status has changed since CRL number 5 was issued. (midnight). So, clearly the delta-CRL provides status information for all certificates whose status has changed since 3:00am when CRL number 8 was issued. Thus, the relying party can combine the delta-CRL with its locally cached version of full CRL number 8 to obtain the contents of CRL number 11. This is a case where the CRL number of the complete CRL used is greater than the BaseCRLNumber specified in the delta-CRL.

> >[Denis] This is a local matter and I would not mandate this in the document
> >since there is another and simpler way to do it: you keep in the cache the
> >base CRL (instead of the previously recontructed full CRL). This has the
> >same end result, except that the method your recommend is not optimum: it
> >will include many duplicates and deleting the duplicates is more painfull
> >than making a simple addition.
 
[David]  I'm not sure what you are saying is a local matter. The contents of
the delta-CRL is not a local matter and must be mandated in the certificate
and CRL profile. If you prefer to always apply the delta-CRLs to the
referenced base CRL instead of to a locally generated, more recent CRL, that
is your choice. The document states that the delta-CRL may be combined with
the referenced base CRL or a more recently issued full CRL.

[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". Now I understand that you may get the
same final result (in a less efficient way), if such a CRL has been issued
and if it could have been seen by the relying party. I would propose that we
describe in the text, the basic rule. I would have no problem to mention in
a note that the same result COULD also be obtained, IF a full CRL were
issued
after the base.

> >The basic algorithm is to take the base CRL and to add the delta. This is
> >the standard. As soon as you get the same end result this is fine. This is
> >the approach we have taken for path validation. Other ways do not need to be
> >mentionned.
> >
> > > There are other reasons why the two numbers may not match, but I will not go into them. If you are interested, you can read my paper.
> >
> >[Denis] I read it (and skipped the mathematical formulas)
> >
> >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.

[David]  The paper does discuss over-issuing of CRLs, but there is plenty of
information about using delta-CRLs efficiently without over-issuing. Bear in
mind, however, that the nextUpdate field only specifies the time by which a
new CRL will be issued. Many people intend to issue a new CRL whenever a
revocation occurs (or a revocation for key compromise) without waiting until
the regularly scheduled time.

[Denis] As said earlier, without any guarantee that the fullCRL issued
before nextUpdate will be seen until the validation time has passed
nextUpdate. 

> >BTW, the same security problem would occur as soon as a base would be used
> >for every delta. Hence another good reason to delete the sentence which
> >originally triggered all this discussion.
> 
> I don't understand this at all.
> 
> >BTW, I noticed that you have precisely deleted from my previous e-mail all
> >the text dealing with this nextUpdate. :-(
> >
> >So I am still insisting on the major text change to make to that section:
> >
> >    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;
> >
> >It is important to notice that the algorithm does NOT use the individual CRL
> >numbers assigned to the delta-CRLs, but uses instead thisUpdate and
> >nextUpdate. This is *very* important.
 
[David]  I thought I did respond to this. First, one should expect that
delta-CRLs will always be at least as recent as base CRLs. So the first step
should be to obtain the current delta-CRL. Next, one obtains a base CRL that
can be used in combination with that delta-CRL. You may choose to only use
the full CRL whose cRLNumber is equal to the BaseCRLNumber specified in the
delta-CRL, however, any full CRL with a cRLNumber greater than or equal to
the BaseCRLNumber is acceptable. 

[Denis] Your algorithm is looking at the CRL Numbers only. My algorithm is
looking at thisUpdate and nextUpdate only. This is a major difference. In
particular you do not say how "to obtain the current delta-CRL".

[David] Since the cRLNumber of the base can be greater than the specified
BaseCRLNumber, the document should say so. 

[Denis] This can be mentionned in a note (see earlier).  

[David] There is no need to state that the current time must be after the
thisUpdate time in the delta-CRL as this will always be true by
construction. 

[Denis] There is definitively a need to state this because the end result of
the two algorithms will not be identical as soon as someone will block some
of the information coming from the repository where the full/base CRLs are
stored or where the delta CRLs are stored.

[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;"
 
> > > >Finally we should explain what happens at the boundaries, i.e. when a CA
> > > >decides to generate a (new) base CRL. Here is a text proposal:
> > > >
> > > >   When issuing a base CRL that supports a delta-CRL mechanism then the
> > > >   CRL Issuer MUST at the same time issue a delta CRL that points to that
> > > >   base CRL. This first delta CRL will usually be empty (or will include
> > > >   last-minute additions to the base CRL).

> > > This is not acceptable. The rule is that when a base CRL is issued a delta-CRL must be issued that has the same cRLNumber. The base CRL referenced by the delta must either be the previously issued base CRL or a base CRL issued before that one. Since the new base and the delta must have the same cRLNumber, there can be no differences as a result of "last-minute additions to the base CRL".

> >[Denis] This does not work. Let me explain it differently. Suppose that
> >during the week you do not generate delta-CRLs but for the week-end you
> >decide to do it (e.g. more risk, more transactions done by citizens). So you
> >issue a CRL with the freshest CRLindicator. You say that the delta points to
> >the previous base CRL. The one from yesterday or the one from last week ?
> >In either case this simply does not work.
 
[David]  Why? A delta-CRL must include a BaseCRLNumber that corresponds to a
CRL that was issued at some time in the past.

[Denis]  A delta-CRL must include a BaseCRLNumber that corresponds to a CRL
that was issued at some time in the past *or to the current time*. The above
example demonstrates that the rule does not work the first time you use it
since there is no such past base CRL or an ambiguity about which one is the
right one. Since it is not possible to answer the question I raised (i.e.
does the first delta points to one from yesterday or the one from last 
week ?) this is one way to demonstrate that there is a problem.

> >The rule you mention, i.e. "The rule is that when a base CRL is issued a
> >delta-CRL must be issued that has the same cRLNumber" is also wrong. The
> >notion of a base CRL that would have the same number as a delta does not
> >exist.

> > > >Suppose we issue a base CRL every midnight. The question is whether we
> > > >should issue a delta and, if yes, does this delta refer to the previous
> > > >base or to the new one ?

> > > The delta must refer either to the previous base or a base issued before the previous base.

> >[Denis] Certainly not. Your paper however 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".
 
[David] Where is the difference? A CRL that is referenced in the
BaseCRLNumber of a delta-CRL is by definition a base CRL.

[Denis] The difference lies in the fact that the sentence is using the
wording "*a* specific, previously issued CRL". If it is *a* (i.e. one)
specific CRL, it cannot be more than one.
 
> > > >Suppose it refers to the previous one. According to the current sentence:
> > > >"The constructed CRL has the CRL number specified in the CRL number
> > > >extension found in the delta CRL used in its construction.", it is
> > > >impossible. If that was the case the delta CRL would have a CRL number equal
> > > >to the base CRL and it is not allowed for two CRLs to have the same CRL
> > > >number.
> >
> > > I think you are confusing two different extensions. The deltaCRLIndicator extension contains a BaseCRLNumber which is used to determine against which base CRLs the delta-CRL can be applied. The cRLNumber extension specifies the CRL number of the full CRL that will be generated by applying the delta-CRL to a base CRL. The sentence above states that the CRL number of the constructed CRL is taken from the cRLNumber extension, not the BaseCRLNumber of the deltaCRLIndicator extension.
> >
> >[Denis] I do not think I make a confusion. The confusion comes from the
> >numbering you introduce (see my earlier comment).
> >
> >Let me conclude:
> >
> >1) I do not have the time to spend hours of discussions on that topic.
> >However the current text needs to be corrected and I have provided text
> >for this. Please take again a look at it in the light of the following.
> >
> >2) In your paper you advertise the "traditional delta-CRLs". Let us stay in
> >the tradition and let us mandate the implementation of the "tradition" if
> >someone wans to support the delta-CRL mechanism.
> >
> >Any other method would first need to be proven to be secure (over-issuing
> >CRLs and sliding window delta-CRLs have security problems) and should
> >*anyway* fall in the MAY category, so that noone needs to implement to claim
> >conformance with the delta CRL mechanism. Standard track documents need to
> >make choices among multiple methods, otherwise two different implementations
> >will never interoperate.
 
[David] you say that you want to stick with "traditional" delta-CRLs,
however you are proposing changes to the text that would not result in
"traditional" delta-CRLs but would result in broken implementations. 

[Denis] You have provided no evidence of what you say just above. Tell me
precisely what is wrong in the text I propose that would not allow the
support of the "traditional" delta-CRLs. If something is wrong, we can fix
it.

[David] We do not prevent people from implementing "traditional" delta-CRLs,
but we should not force them to either. 

[Denis] We disagree here. Standards are there to support at least one
(simple) method that all implementations have to support( if they support
delta). In addition, implementations may support additional methods and it
will be up to the final customer to decide which one to use. We MAY describe
these additional methods, but MUST clearly indicate the difference.
 
[David] There are no security problems with sliding window delta-CRLs and
they do not add any complexity for those who choose not to
implement them.

[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. 

[David]  I want to be sure that the delta-CRL text is correct just as you
do, 

[Denis]  At least one point on which we both agree. :-)

[David] ... but I still feel that many of your comments are based on a
misunderstanding and are not based on actual problems in the text.

[Denis] I do hope that after this response you will think differently.

Regards,

Denis

> Dave