Subject: RE: delta CRLs - NR assumptions

From: "Tom Gindin" <[email-masked]>
Date: Thu, 14 Jun 2001 11:46:40 -0400

The critical point here is actually that NR normally operates on
archived evidence, and revocation evidence will have been archived before
(usually long before) the independent third party starts work.  Current
evidence about whether a CA key has been compromised may be relevant in
some cases, and current evidence about whether a TSA key has been
compromised will be relevant in many cases, but not current evidence about
the signer's key.

          Tom Gindin

"Manger, James H" <[email-masked]>@mail.imc.org on
06/06/2001 01:37:13 AM

Sent by:  [email-masked]

To:   [email-masked]
cc:
Subject:  RE: delta CRLs - NR assumptions

There are a couple of assumptions underlying some of Denis Pinkas's
arguments that warrant closer examination.  I have derived the assumptions
from the clear & helpful description of Denis's rational (in an e-mail on
12 May).  I think these assumptions are the root cause of much of the
disagreement.  I also believe these assumptions are incorrect.

     Assumption 1 (A1): Two different verifiers must get the same result
     about a certificate's revocation state at any instant in time for a
     non-repudiation service to work, since the goal of NR is to resolve
     disputes.

A non-repudiation service works because an independent 3rd party can
confirm that the evidence PRODUCED BY THE RELYING PARTY (signature,
certificates, CRLs, timestamps) is correct.  Whether or not there were
different sets of evidence - perhaps giving a different answer - that the
relying party could have collected (by noticing an "emergency" CRL for
instance) is irrelevant.  Only one set of evidence matters for a given NR
dispute: that produced by the relying party.

[Tom Gindin] A third party may be used as the archiver of such evidence, by
prior agreement.  This does not affect your argument, since the independent
third party is operating on an archived set of evidence.

The rule for deciding if NR evidence is "correct" is also very important,
which bring us to the 2nd assumption.

     Assumption 2 (A2): The validation rule, for a non-repudiation service,
     may say "use the freshest revocation information that is provided by
     the CA".

As Denis points out, the relying party cannot be sure they have the
freshest information if "emergency" CRLs are allowed.  The solution,
however, is not to impose rules on CRL extensions & update times, but to
recognize that A2 is a bad validation rule for a NR service.

A better validation rule for a NR service may be "the relying party must
use revocation information that they reasonably assume to be the freshest
information provided by the CA (delta CRLs do not need to be supported)".
Now a relying party can protected themself, as the nextUpdate field
indicates when it is reasonable to expect new revocation information to be
available.

Consequences: "emergency" CRLs should be allowed (but NR validation rules
should not require them to be noticed); thisUpdate values may be before the
previous nextUpdate (but NR validation rules should not require that the
new CRL is noticed until the old nextUpdate time); CRLs do not need to
include a freshedCRL extension (but NR validation rules should not require
a delta CRL to be noticed if neither the cert nor full CRL reference it).
In short, keep the X.509 CRL rules, change the NR validation rules.

In practise, NR validation rules are unlikely to mention "freshest
information" at all, as the period for which information is "freshest" is
controlled by the CRL issuer, not the relying party or signer.  Instead, a
NR validation rule should specify how fresh the revocation information has
to be (e.g. 12 hours).  This value will often be a time in the future (e.g.
the revocation information must be 24 hours fresher than the signature) to
give the signer time to detect & report a compromise of their key (and the
CA to publish it & relying parties to notice it) before they lose their
right to repudiate a signature created with the compromised key.

---

From: Denis Pinkas <[email-masked]>
Date: Thu, 14 Jun 2001 18:45:47 +0200

This a response to James Manger, rather than Tom, since I missed the e-mail
from James.

> dispute: that produced by the relying party.

What about when they are two differents sets of evidence from the same
relying party which are both valid (according to the way to use CRLs) but
are contradictory ?
 
> recognize that A2 is a bad validation rule for a NR service.

You are right, this is not stated correctly. The rule may be: "use
delta-CRLs (with full CRLs)". 

> information provided by the CA (delta CRLs do not need to be supported)".

I see a problem here. If you use delta-CRls, full CRL only or OCSP (from the
same CA) you do not necessarily get the same result. For a given signature
policy, allowing only one means to obtain the revocation status would allow
to make sure that everydody gets the same information.

> Consequences: "emergency" CRLs should be allowed 

I disagree.

> (but NR validation rules
 
> information" at all, 

Correct.

> as the period for which information is "freshest" is

In other words, it will be necessary to wait to make sure that a report of
key compromise can be done. 

Denis

---

From: "Housley, Russ" <[email-masked]>
Date: Fri, 15 Jun 2001 09:18:07 -0400

> > Consequences: "emergency" CRLs should be allowed

I believe that this is the core of the disagreement, and I do not see 
anyone changing their minds.  The PKIX Profile does not require CAs to 
issue CRLs, or emergency CRLs.  However, when CAs choose to employ CRLs, 
the CAs policy will dictate whether emergency CRLs are issued or not.

The PKIX Profile is NOT going to be changed to prohibit the issuing of 
emergency CRLs.

Russ

---

From: Denis Pinkas <[email-masked]>
Date: Mon, 18 Jun 2001 18:39:59 +0200

Russ,

 
 
> The PKIX Profile is NOT going to be changed to prohibit the issuing of

This seems fine as far as CAs are concerned: this leaves the choice to the
CAs. 

However, this has implications on the way relying parties should process
CRLs.

It would be appropriate to give some guidance or some warnings
in the security considerations section.

If a CA issues no emergency CRLs, then there is no problem. Only one CRL may
be valid at one time.

If a CA indicates that it MAY issue emergency CRLs at any time (for some
scope or reason), then a cache for that CRL should not be used. In this way,
the client will always try to fetch the latest CRL, ... but will have no 
guarantee that he ever got the latest.

Finally, when CRLs are used for supporting non repudiation, since one goal
of non repudiation is to solve disputes, we had better to have non
conflicting information from the same authority while using the same
revocation mechanism.

A few words in the security considerations section would certainly be
appropriate. If you agree in principle, I would be happy to provide them.

Denis

---

From: "David P. Kemp" <[email-masked]>
Date: Mon, 18 Jun 2001 19:27:04 -0400

> guarantee that he ever got the latest.

The client, not the CA, should determine the client's caching policy.
And given a CA with a specific practice (emergency CRLs yes/no,
deltas yes/no), different clients may use different caching policies.
One client may check for emergency CRLs at a specific interval, and
a different client may check for them at a different interval, without
even needing to know if the CA ever issues them.  And one client may
use deltas and another client may not use them even when both clients
are validating certs from the same CA.

Realtime clients can eliminate the impact of denial of service by
fetching CRLs through a secure pipe.  If a connection is established
to the distribution point, then the client is guaranteed that it has
that DP's latest CRL.  If the fetch times out, then the client
can either refuse to validate certs or proceed, at risk, using a
cached CRL.

> conflicting information from the same authority while using the same

If there were an accepted business standard for NR, then that standard
would surely take into account all available evidence.  As Tom Gindin says,
dispute resolution will take place long after the next CRL has been
issued - if two parties present what you call "conflicting" CRLs, there
is still no conflict.  The judge will know that the cert was revoked at
time T (where T is between thisUpdate of one CRL and thisUpdate of the
other CRL) and will overturn or let stand a transaction according to all
the facts known at the time of adjudication.  Proof of clock
synchronization is a far bigger issue here than whether or not a CA
issues emergency CRLs.

> appropriate. If you agree in principle, I would be happy to provide them.

I don't believe "a few words" can do justice to the topic of NR :-).

Linking a CA's issuance of emergency CRLs to whether some clients might
use CRLs in support of NR is an entirely unnecessary complication.  You
create the complication yourself by believing that CRLs are "valid" until
nextUpdate. Purge this notion from your mind and instead focus on clients'
freshness requirements.  The highest value real-time irrevocable transactions
(e.g., disclosure of confidential information, execution of a critical signed
applet, etc.) will require the freshest available information regardless of
what nextUpdate says.  Non-realtime transactions (including those subject to
dispute resolution) don't need nextUpdate either; they just need any CRL
with thisUpdate after the transaction commit time.  Any business process
that doesn't require positive acknowledgement before committing high value
resources is flawed.  Thinking along the lines of "cacheable/valid until
nextUpdate" is therefore flawed.

For low-value purposes, some clients may choose to accept a CRL until
nextUpdate or even well beyond.  If a CA issues a CRL every minute, there
is no reason to force every client to fetch that often when caching for
an hour might be quite sufficient for the purpose at hand.

Dave

---

From: Denis Pinkas <[email-masked]>
Date: Tue, 19 Jun 2001 11:26:09 +0200

David,

> The client, not the CA, should determine the client's caching policy.

True, but what the client can do is dependent from what the CA does.

> fetching CRLs through a secure pipe.  

 .. if such a secure pipe is available, which is not an assumption of the
X509 model, nor the PKIX model. 

> If a connection is established

Once again, if a secure pipe is available. This also means that if a
replication mechanism has been used to feed the server under query, secure
pipes for the replication of the revocation information shall also be used.
Then trust should also be placed in the managers of the replica servers.
This is quite a long chain of trust that the X509 model has *not* assumed.

> other CRL) 

No. The judge will have to use the same rules that are supposed to be
followed by the verifier to settle a decision. Unless these rules are
clearly stated, no decision can be taken. Hence why these rules have to
exist. So the basic question is : what are the rules to be used by a
verifier to make sure that the certificate was not revoked ? These rules
must be clearly stated and not conflicting. 

> and will overturn or let stand a transaction according to all

> nextUpdate. 

The use of nextUpdate is the core of the debate, because the text in PKIX-1
does not say what kind of use shall be done of that information by a relying
party. The basic question is whether this information should be used :

   1) to make sure that a CRL is usable for a time T, or
   2) to make sure that a CRL is not usable for a time T.

Unless PKIX-1 provides some guidance the debate will continue for ever.

> Purge this notion from your mind and instead focus on clients'
> what nextUpdate says.  

There is no guarantee that the freshest information can ever be obtained.
See above the problem of denial of service where, in case of a problem, the
responsibilities will be undetermined between the CRL Issuer and the
managers 
from the replicas where the CRLs are stored.

> Non-realtime transactions (including those subject to
> dispute resolution) don't need nextUpdate either; 

So why does PKIX-1 mandate it ?

> they just need any CRL with thisUpdate after the transaction commit time.  

Certainly not. A relying party has to take a decision to accept or reject a
signature at a time T. If a signature is deemed valid at time T, then no
other information, according to the verification rules, should change this 
condition.  

> Any business process
> resources is flawed.  

Yes.

> Thinking along the lines of "cacheable/valid until nextUpdate" is therefore flawed.

You provide no evidence to support that sentence.
 
> nextUpdate or even well beyond.  

Yes.

> If a CA issues a CRL every minute, 

Do you really see this situation as realistic ?

Denis

> there

---

From: "David P. Kemp" <[email-masked]>
Date: Tue, 19 Jun 2001 12:04:59 -0400

> Unless PKIX-1 provides some guidance the debate will continue for ever.

Yes.  My position is that there are two purposes for certificate validation,
realtime and non-realtime, and that a CA can provide one cert/CRL series that
satisfies both purposes for a variety of clients.  A specific RP client,
however, must make a decision to accept a certificate using validation
rules appropriate to that client's purpose.

For realtime validation, the client can say "I have a CRL issued at time T,
and my security policy allows me to assume that a certificate which was
not revoked at time T has a sufficiently (for this purpose) small chance
of being revoked at time T+e".  e is the client's caching interval, and T+e
can be less than, equal to, or greater than nextUpdate (*).

For high-value transaction validation, the client can (and I argue SHOULD)
say "I have a CRL issued at time T.  My security policy requires me to confirm
that the certificate was not revoked at time T, and forbids me from accepting
a probabilistic guess that the certificate will not be revoked between
T and T+e".

(*) I agree that if a client has a cache interval of less than the CRL
publication
period, reliably satisfying that client's needs requires secure distribution
points and transmission channels which are outside the PKIX model.  My point
is that those extra-PKIX measures can in theory be provided to "special" clients
without creating any incompatibility with pure PKIX clients or requiring any
changes to the PKIX untrusted distribution model.  In practice, it would be
easier to up the frequency of CRLs until the most demanding client's needs
are met, and forget about trusted distribution.  Whether a CRL per minute
is realistic or not depends on the application; use 15 minutes as the extreme
example if you prefer.

> other information, according to the verification rules, should change this

The verification rule "Signature valid at time T requires a CRL with
thisUpdate >= T" satisfies your requirement.  No rule requiring the CA to
guess the future (e.g., a rule involving nextUpdate) can satisfy it.

> You provide no evidence to support that sentence.

Positive acknowledgement is by definition not probabilistic.  The entire purpose
of this discussion is to reach general agreement that when a transaction is
"committed" (becomes difficult to roll back, in the sense of a database
two-phase-commit), no information should come along later that would cause
doubts about the validity of the transaction.  The CA can at time T have high
confidence that a certificate is not revoked at time T.
The CA can have no confidence, only a statistical belief, that a cert which
is not revoked at time T=thisUpdate will still not be revoked at time
nextUpdate.

For realtime purposes, the RP's or the CA's statistical belief is good enough.
For some other purposes, it is not.

PKIX should recognize both cases in its validation rules, and if we want
to say something in the security considerations, it should be that a CRL
is an assertion by the CA concering revocation status at time thisUpdate.
Revocation status at any later time (<, =, > nextUpdate) is at best a
guess, and a CRL is explicitly NOT an assertion by the CA concerning
revocation status at any time T > thisUpdate.  NextUpdate is merely a
promise to publish another CRL by a certain time.

Dave

---

From: Denis Pinkas <[email-masked]>
Date: Wed, 20 Jun 2001 15:10:22 +0200

David,

> realtime and non-realtime, 

I would not phrase it exactly like that. The validation is made for a
*security service*. Security services be grouped into two categories; the
first one being: Authentication, Access control, Integrity and
Confidentiality; while the second one being: Non-repudiation.

For the first category, a real time decision is needed (not waiting is
possible). Revocation status information available at that time is taken.
Some graduations exist using: CRL, delta-CRL + CRL, or OCSP responses.

For the second category, depending upon the importance of the transaction
different waiting times (including none) and sources of information may be
appropriate.

> and that a CA can provide one cert/CRL series that

Yes.

> points and transmission channels which are outside the PKIX model.  

So we both agree on this ... and this is not mentionned anywhere in PKIX-1.

> My point
 
> thisUpdate >= T" satisfies your requirement.  

This is not always sufficient. See my detailed response to Tom sent earlier
this day.

> No rule requiring the CA to

Here also, see my response to Tom. I would say that in general, all
revocation status responses are probabilistic, because we don't know for
sure how long it takes for a signer to discover and report that his private
key has been compromised. However, a decision has to be taken and an
arbitrary time limit has to be placed, depending upon the importance of the
transaction. Hence the reason for the caution period.

The important point is that at the end of that caution period (whatever its
value is) it should not be possible to capture different (i.e. opposite)
revocation status information from the same source using the same means.

This is not the case when emergency CRLs are issued. So my conclusion is: 

1) emergency CRLs are fine for realtime purposes. A verifier takes the best
   he can, with no guarantee that he ever got the best.

2) emergency CRLs are dangerous for non-repudation purposes because two
   verifiers could get opposite results.

> promise to publish another CRL by a certain time.

The problem is not to say what the CA means with nextUpdate (we already know
it), but how a relying party should use nextUpdate. Two cases should be
described, whether or not emergency CRLs are issued.

Denis

---

From: "David P. Kemp" <[email-masked]>
Date: Wed, 20 Jun 2001 15:51:25 -0400

>    verifiers could get opposite results.

Since we are talking about a caution period, which I agree is necessary,
there is no reason to say that emergency CRLs are dangerous for NR.
You are creating the potential for opposite results by using CRL T-10 and
claiming that it is valid through T+10.  The danger disappears by
requiring a CRL with thisUpdate >= T, where T is the end of the caution
period (the commit time of the transaction).

Assume the CRLs:
  scheduled  T-10
  emergency  T-1
  emergency  T+2
  scheduled  T+10

Using the above rule, emergency CRL T+2 and scheduled CRL T+10 give the
identical result for every in-scope cert at time T.  When all CRLs are
known to the verifiers, there is no possibility opposite results.

Now consider the case of a revocation at T+3 and a verifier which has
CRL T+10 but not CRL T+2.  The verifier can reject a transaction which
he might have accepted had he been in possession of all CRLs.  There
are three ways to resolve this problem:

1) require that NR verifiers ignore all emergency CRLs which have been
issued by a CA.

2) require that CAs issue CRLs with 1-up CRLNumbers, so that an NR
verifier knows after fetching T+10 that there are two emergency CRLs
that might need to be fetched before making a decision on cert X.

3) declare that for NR purposes, "false rejection" is not a harm.  If a
verifier rejects on the basis of CRL T+10, and someone later produces
CRL T+2 which would have allowed the transaction to proceed, the rejection
will not be overturned.  The verifier could voluntarily agree to accept
the new evidence and the signature, but if he chooses not to do so the
argument might be "we know the cert was revoked between T+2 and T+10, but
we can't be sure that the reason for revocation did not exist at time T".
This situation would not even be called a "false rejection" using Denis'
rules; it would be a correct rejection since emergency CRLs would not
be used for NR purposes.

I disagree with option 1.  I'm in Hal's "accuracy" camp, and believe
emergency CRLs, if issued and received, must be processed.  More
accurately, I believe that CRLs must be processed, whether they
are issued before or at nextUpdate of the previous CRL.  We routinely
issue CRLs before nextUpdate and don't call them emergency CRLs.

I like option 2 because it appears to have an advantage with no
disadvantages.  There might be reasons not to adopt such a generation
requirement, but I can't think of one.

I don't have a problem with option 3 or variants of it.  As soon as
we start talking about "later evidence" and "overturning decisions"
we are out of the realm of electronic processing and into human
procedures which are outside the scope of PKIX.

PKIX needs an algorithm that unambiguously says "given this set
of CRLs, cert X {is/is not} revoked at time T".  The algorithm
"thisUpdate>=T" satisfies the requirement.  An algorithm
which uses nextUpdate does not satisfy the requirement because it
produces internally-conflicting results for some sets of CRLs.

Dave