Subject: when can an entry not appear on a CRL?

From: [email-masked]
Date: Mon, 14 Dec 1998 16:16:44 -0500

And while I'm airing my confusions about revocation, I have another.
Section 3.3 states:
" An entry may be removed from
   the CRL after appearing on one regularly scheduled CRL issued beyond
   the revoked certificate's validity period."
This seems to be there to ensure that a revoked cert actually appears on
some regularly scheduled CRL, which seems sensible. The text is silent
on what to do for an on-demand CRL. It seems that no entries that are on
the "current" scheduled CRL should be removed from any on-demand
CRLs, as that would mean applications who picked up the on-demand
CRL but not the regularly scheduled one would miss the event. Does
that seem sensible? Does it cover the motivation of that statement?
     Mez

---

From: Al Arsenault <[email-masked]>
Date: Wed, 16 Dec 1998 08:41:02 -0500

>that seem sensible? Does it cover the motivation of that statement?

Mez,

	I think that the text is silent on how to handle the on-demand CRLs issued
later than the first regularly-scheduled CRL after the certificate's
expiration date because it really doesn't matter what you do. 

	You are correct, the purpose of the requirement as worded is to ensure
that the revoked certificate appears on at least one regularly-scheduled
CRL.  The additional thought is that even if there are on-demand CRLs,
relying parties should still be getting regularly-scheduled CRLs as well as
the on-demand ones.  Thus, all relying parties will see the revocation
notice from the regularly-scheduled CRLs.  (You can do this by setting the
next-issue date in the on-demand CRL to be the date of the next
regularly-scheduled CRL.)   

	That is:  suppose that regularly-scheduled CRL  R1 is issued on 15
December; on-demand CRL O is issued on 17 December; and regularly scheduled
CRL R2 is issued on 22 December.  If a revoked certificate with an
expiration date of 14 December is on R1, it doesn't matter whether or not
it's on O, as long as all relying parties will see R1.

	Once a revocation has been "seen" by the relying parties, it shouldn't
matter when it drops off the CRL - that is, it doesn't matter whether the
the certificate is on O but not on R2, or not on O.   The certificate will
have expired on 14 December, so all relying parties should reject
transactions occurring after O is issued involving that certificate because
of certificate expiration.  For historical purposes, there will be a formal
record of the certificate having been revoked, at a bare minimum on R1, so
transactions dated between 15 December and 17 December but being processed
after the fact can be rejected due to R1.

	(Of course, an assumption I'm making is that the prior regularly-scheduled
CRL, R0, and any intervening on demand CRLs all had next-issue dates of 15
December.  Thus, anybody who missed R1 will know that, and can go look for it.)

	 Thus, I think that the document is okay being silent on removing certs
from on-demand CRLs, because it doesn't matter.  If people would like
explicit text that states this, though, I wouldn't object.

						Al Arsenault

---

From: Juergen Walter <[email-masked]>
Date: Wed, 16 Dec 1998 13:21:58 +0100

Hi Mez,
Hi Al,

I think, that your question is strongly related to the concept of
validity of signatures. It remains undone in the current PKIX draft. The
certificate path validation there specified covers essentially two cases
(see Remark below). I want to refer to these cases as short-term
signatures and long-term signatures, respectively.(I will not consider
path validation for simplification.)

A short-term signature is valid if and only if
(i) the signature is correct, and
(ii) the corresponding certificate is AT THE TIME OF VERIFICATION within
its validity period, and
(iii) the CURRENT CRL doesn´t contain an entry for this certificate.

This concept of validity doesn`t fit for those communities where
non-repudiation is needed. Hence, it makes sense to remove the expired
certificates from the CRL. After the certificate is expired all
corresponding signatures are invalid, whenever the signature was
generated.

Secondly, a long-term signature is valid if and only if
 (i) the signature is correct, and
(ii) the corresponding certificate is AT THE TIME OF SIGNATURE
GENERATION within its
validity period, and
(iii) this certificate was not revoked AT THE TIME OF SIGNATURE
GENERATION.

The second concept may give non-repudiation services. All signatures
that have been produced before the corresponding certificate was revoked
or expired are still valid. Hence, the relying party needs the CRL entry
beyond the _notAfter_ date. I think the minimum requirements to CRL
management are (i) the CRL issued next to the revocation date of the
certificate must contain the adequate CRL entry, and (ii) the relying
party must have access either to this CRL or to this CRL entry on any
on-demand CRL.

Provided that these requirements are fulfilled, a relying party may
"hunt" through the issued CRLs. Whether the relying party has success or
has not, it depends on the application used. I think, that Mez wanted to
make the point, that this "hunting" isn`t  simple at all. Especially, if
the CA provider supports only short-time signatures, then the result of
the "hunting" through CRLs may be the following. The signature is valid.
But, the PKI may be designed only for short-time signatures. How does
the relying party know that?

Firstly, I don`t want to advocate such "short-term" PKI designs. But, it
may happen in the real world. Secondly, in general, one can not expect,
that the certificate validation is simple, but the discussion about
invalidity dates has shown that the _revocationDate_ may be not a
constant. Provided that the _revocationDate_ may vary, the signature
validation becomes a hard job. Is there someone interested in a concept
of signature validation, which may be formulated at the requirement
level? I would prefer the requirement level because I don`t see a
consensus about the underlying bussiness models.

Does the non-repudiation bit come into question? If the non-repudiation
bit of the keyUsage field of the certificate is seated, then this
implies that the on-demand/current CRL will contain all revoked
certificates including the expired certificates. And, in addition, that
the CRL information is still available. I would argue that this
implication is well.

Remark. The PKIX Part 1 draft contains a certification path validation
chapter (chapter 6). There the variable T refers to time. The lower
limit "T = date of signature generation" corresponds to the long-term
signatures, whereas  the upper limit "T = date of signature
verification" corresponds to the short-term signatures. I will not
consider T earlier than date of signature. Nevertheless, it is allowed
that T is an element of the full intervall between the two mentioned
extremal points.

Juergen 

--

---

From: Al Arsenault <[email-masked]>
Date: Wed, 16 Dec 1998 08:32:52 -0500

Juergen,

At 01:21 PM 12/16/98 +0100, Juergen Walter wrote:
><snip>

AWA:  this is almost correct.  You do have to deal with those cases at the
fringes of certificate validity.  For example, suppose that a certificate
expires at 120000Z (Noon, GMT) on 16 December 1998.  That certificate's key
is used to sign a message timestamped 110000Z on 16 December 1998.  Because
of network  delivery problems, the recipient doesn't get the message until
110000Z on 18 December 1998 (two days later).  If you use TIME OF
VERIFICATION, you reject this message; if you use TIME OF SIGNATURE, you
accept it.  Mostly, I've seen TIME OF SIGNATURE used in this case, although
if you're willing to accept unnecessary rejections (or possibly the
acceptance of messages sent minutes/hours actually sent after cert
expiration), you can probably use either one.

>party must have access either to this CRL or to this CRL entry on any

AWA:  Okay, I think I agree with this, given the standard disclaimers about
needing to have a reliable time source.  I keep having to remind potential
users that a signature key which is compromised can be used to sign
information with any arbitrary date on it, so unless you've got a reliable
time stamp or notary service, you don't have non-repudiation.

>the relying party know that?

AWA:  the only way I know of is to put that information in the CP and/or
CPS.  But then you're back to the previously-unsolved problem of how the
relying party really understands what's in any CP or CPS.

>consensus about the underlying bussiness models.

AWA:  I don't think that the revocationDate should change.  That indicates
the time at which a CA formally declared a certificate to be revoked.  That
shouldn't change.  It's possible that an invalidityDate would change, based
on further investigation, but I'd personally oppose that, too.  Once a CRL
entry is created, it shouldn't change.

<snip>

					Al Arsenault

---

From: Paul Koning <[email-masked]>
Date: Wed, 16 Dec 1998 11:17:40 -0500

It's not clear to me why it is useful to distinguish "short term" and
"long term" signatures and then define different validation algorithms 
for them.  For example, what property distinbuishes the two flavors?

On a related issue, if you use "time of signature generation" how do
you know what that is?  It can't just be the timestamp in the
signature, since that would allow the thief of a key which was revoked
at time T to generate a "valid" signature by constructing one with
signing time T-epsilon.

If I have independent evidence I trust that a signature is at least as
old as T2 where T2 >= T, my inclination would be to verify that the
certificate wasn't revoked at T2, and was valid during the interval
T..T2.   Without independent evidence about the time of signing, I
basically have T2==now, which gets me what you describe as the "short
term" algorithm.

	paul

---

From: Juergen Walter <[email-masked]>
Date: Wed, 16 Dec 1998 20:45:03 +0100

Paul Koning wrote:
> for them.  

The algorithms are the same. They differ in the choosen time variable T
in chapter 6 of [PKIX1]. [PKIX1] says that T is less or equal NOW. I
don`t know exactly the origin of the notation "short term" and "long
term". The origin might be the Digital Signature Law Interoperability
Guide (SIGI) published by German Bundesamt fuer Sicherheit in der
Informationstechnik. But, I am not sure. I apologize when I have made a
mistake. The motif for use of this notation was just the following. I
wanted a name for the limits of the interval, where T lives in. In
addition, I wanted to avoid certificate paths for simplification. As a
result, these two definitions appeared.   

>For example, what property distinbuishes the two flavors?

The validity of those signatures that corresponds to revoked and/or
expired certificates. 

> at time T to generate a "valid" signature by constructing one with

This is right under the assumption that the thief can sign with signing
time T-epsilon. If the signer has included an appropriate
non-repudiation token (e. g. a token generated by a trusted time stamp
server), then this attack fails.

> old as T2 where T2 >= T, 

This refers to a time stamp outside the signed data. It makes sense
provided that T2 is close to T, say T2=T+ epsilon, where epsilon is
sufficiently small.

>my inclination would be to verify that the
> T..T2.   Without independent evidence about the time of signing,
> I basically have T2==now, which gets me what you describe as the "short
> term" algorithm.
> 
Let T3 be the time, when the relying party validates the signature. We
have T3 > T2. As T3 tends to T2 the difference between these two dates
is getting smaller. Hence, the result of certification path validation
will be almost the same. Note, T3 may be indentically to the
_nextUpdate_ of the CA`s CRL. Is it now?

Of course, the relying party is free to get a time stamp over the signed
data. This procedure yields a upper limit of the date, when the
signature was generated. The signature validation itself may be later.
... 
-- 

Juergen

---

From: Paul Koning <[email-masked]>
Date: Wed, 16 Dec 1998 14:49:08 -0500

>>>>> "Juergen" == Juergen Walter <[email-masked]> writes:

 Juergen> Paul Koning wrote:
 >> On a related issue, if you use "time of signature generation" how
 >> do you know what that is?  It can't just be the timestamp in the
 >> signature, since that would allow the thief of a key which was
 >> revoked at time T to generate a "valid" signature by constructing
 >> one with signing time T-epsilon.

 Juergen> This is right under the assumption that the thief can sign
 Juergen> with signing time T-epsilon. If the signer has included an
 Juergen> appropriate non-repudiation token (e. g. a token generated
 Juergen> by a trusted time stamp server), then this attack fails.

Not quite.  It fails if the verifier insists that all signatures it
verifies must be accompanied by a trusted time stamp token if they are 
to be verified to a time older than the time of verification.

The fact that the legitimate signer includes tokens doesn't prevent
the intruder from generating signatures without tokens unless the
verifier insists on them.

	paul

---

From: Juergen Walter <[email-masked]>
Date: Wed, 16 Dec 1998 22:18:52 +0100

> verifier insists on them.
This is right. A non-repudiation token has no worth unless the relying
party insists on it. I think that a pure digital signature is not
appropriate to non-repudiation. There are many scenarios. I believe that
trusted time stamp servers or notary services are necessary, whenever
non-repudiation is required. Hence, it is required that either the
relying party insists on them or the relying party initiate them.

-- 

Juergen

---

From: Denis Pinkas <[email-masked]>
Date: Thu, 17 Dec 1998 16:09:11 -0800

Juergen,

I agree in principle with your comments and with the amended way to verify
digital signatures in any case (i.e. taking the time of GENERATION of the
signature and NOT the time of verification of the signature). However see a
clarification question below.

> appropriate to non-repudiation.

Correct.

> There are many scenarios.

Many scenarios for proving this  ? or ... many scenarios for having
appropriate non-repudiation tokens ?At the time being, I am aware of very few
(secure) non-repudiation tokens definitions. I also know some which are
insecure . :-(

> I believe that
> non-repudiation is required.

Correct.

Denis

> Hence, it is required that either the