Subject: RE: Proposal for a new CRL extension

From: "Kurn, David" <[email-masked]>
Date: Thu, 12 Nov 1998 13:04:30 -0800

Paul

If I am not mistaken, CRL's are signed.  How can you verify the signature
unless you read the entire CRL?

David Kurn
Compaq Computer Corp.

-----Original Message-----
From: Paul Hoffman / IMC [mailto:[email-masked]]
Sent: Thursday, November 12, 1998 12:16 PM
To: [email-masked]
Subject: Proposal for a new CRL extension

The entries in CRLs are not ordered. This means that a CRL-reading client
must read the entire CRL to know if a particular certificate is revoked.
That's pretty wasteful, it seems to me.

I would like to propose a new non-critical CRL extension that would say
that the revokedCertificates sequence is in the ascending order either by
userCertificate or by revocationDate. I don't see any problem with this,
but wanted input before I wrote up the draft.

Comments?

--Paul Hoffman, Director
--Internet Mail Consortium

---

From: Sharon Boeyen <[email-masked]>
Date: Thu, 12 Nov 1998 15:48:59 -0500

Paul,

fyi - in the X.509 meeting in Sept, a new extension that does some of
what you want, was added to to the text that will be issued for PDAM
ballot shortly.

The extension is:

The ordered list extension identifies that a list of revoked
certificates in the revokedCertificates field of a CRL is ordered by
certificate serial number, in increasing order. This field is defined as
follows:
orderedList EXTENSION	::= {
	SYNTAX	BOOLEAN DEFAULT FALSE
	IDENTIFIED BY	id-ce-orderedList }
This extension is always non-critical. 
If orderedList is present and set to TRUE, the list of certificates is
ordered by serial number in increasing order. If orderedList is present
and set to FALSE, the list of certificates is either unordered or in
some order other than increasing by serial number. If orderedList is not
present, no information is provided as to the ordering, if any, of the
list of revoked certificates in the CRL.

I'm still working on the editing from the meeting but the document
should be posted on the Bull ftp site maintained by Hoyt Kesterson
sometime next week.

Although for this particular extension, this is the extent of what was
agreed at that meeting, changes and further enhancements can be made
during the PDAM ballot phase. 

As with the current edition of X.509, input from IETF groups on relevant
parts of that spec will obviously be welcome inputs to the 509 process.
The revocation enhancements will be of particular relevance to the PKIX
WG. 

> ----------
> From: 	Paul Hoffman / IMC[SMTP:[email-masked]]
> Sent: 	November 12, 1998 3:16 PM
> To: 	[email-masked]

---

From: "Jim Schaad (Exchange)" <[email-masked]>
Date: Thu, 12 Nov 1998 13:49:14 -0800

Additionally there is a big difference between just running the set of items
on the CRL through a hash function to verify the signature (which can be
done as a binary stream), and parsing the contents of the list and doing
comparisions of the serial numbers on each item in the list.   Having the
list sorted allows one to optimize the search and reduce the number of
comparisons done.

jim schaad

-----Original Message-----
From: Paul Hoffman / IMC [mailto:[email-masked]]
Sent: Thursday, November 12, 1998 1:37 PM
To: Kurn, David; [email-masked]
Subject: RE: Proposal for a new CRL extension

>unless you read the entire CRL?

Your read the entire CRL once to verify the signature. You store the CRL
with some marking that it is valid. You later read it looking for
certificates.

Yes, you could extract and sort the certificates when you validated the
CRL, but that means many more steps than just keeping the CRL in some place
that you trust.

--Paul Hoffman, Director

---

From: Paul Hoffman / IMC <[email-masked]>
Date: Thu, 12 Nov 1998 13:34:11 -0800

>what you want, was added to to the text that will be issued for PDAM

I'll take this as meaning that I don't need to do the extension draft. I
think someone (probably an implementor) should be keeping track of
extensions to PKIX part 1 that are being added by the PDAM folk so that we
can pull them together in a draft, maybe in six months or so.

--Paul Hoffman, Director

---

From: "Kurn, David" <[email-masked]>
Date: Thu, 12 Nov 1998 15:17:17 -0800

Paul

Going back to the "you have to read it all anyways argument", it seems to me
that there are several ways to improve the CRL checking speed already
without inventing any new modifiers.  Consider the following:

a)  The size of any given CRL message can be controlled at the CA by simply
assigning the distribution points judiciously.  For example, one could
switch to a new CRL after every 500 certificates, thus putting an absolute
upper bound on the size of any given CRL.

b)  The clever programmer, after retrieving and checking the signature of a
CRL record, can easily construct searchable lists internally using his own
favorite algorithm (B-tree, hash-table, linked lists ... the list is
endless).

I'd say that all of this is an implementation issue, and should not be
present in a standard.

David