Subject: RE: OCSP request

From: Al Arsenault <[email-masked]>
Date: Tue, 8 Aug 2000 09:16:34 -0400

Irene Gassko wrote:

So, it looks like efficiency really depends on how those certificates are 
used.

This part I'll agree with completely!  As experience has shown repeatedly, 
there's no "one best way" that always gives best performance from a PKI 
implementation.  It's a function of what application(s) you're trying to 
support, what risks you're willing to take, what your constraints are in 
terms of time, money, and technology, and a lot of other things, besides.

I guess I started this by using the term "normal processing mode", so I'll 
attempt to clarify - in some environments - e.g., where certificates are 
being used to sign, encrypt, and verify e-mail messages - the approach 
suggested by Irene seems to me to be less efficient than the approaches 
currently defined in PKIX today, and in more-or-less common use.  In other 
environments, the approach she suggested MAY be more efficient, depending 
on a lot of the factors identified above.

Some specific comments in-line:

-----Original Message-----
From:	Irene Gassko [SMTP:[email-masked]]
Sent:	Tuesday, August 08, 2000 8:19 AM
To:	Al Arsenault
Cc:	[email-masked]
Subject:	RE: OCSP request

At 10:45 AM 08/07/2000 -0400, Al Arsenault wrote:
>The problem with this scheme is that, even if it does help with archiving
>and recovery in the case of CA key compromise, it doesn't help in the
>normal certificate processing operations.
>
>With a certificate signed by a CA, I know that "the CA has vouched for the 
>correctness of each of the data items in this certificate", subject to the 
>normal discussions on how thoroughly the CA has verified them, yada, yada, 
>yada.
>
>With a certificate not being signed, or being signed by the originator, I
>just know that I have a data structure, and I'm not sure about the CA's
>willingness to vouch for those items, until such time as I go fetch the
>signed Merkle tree that pertains and verify it, recursively to where I get 
>to a trusted root.  That is, I don't know if I have a complete spoof
>attempt, a corrupted cert, or anything else, until such time as I do the
>"revocation check".
>
>So it seems to me that in the normal processing mode, this proposal is
>actually somewhat *less* efficient than the current scheme, where I can do 
>some checks on the cert BEFORE I fetch the CRL or ping the OCSP responder, 
>and thus not even bother with revocation checking on things that have
>already failed.
>
This is absolutely correct if you only want to check one individual
certificate,
do not care about the possibility of revocation much and are not worried
about potential CA key compromise. Yes, and also if you trust directories
to tell you truthfully whether they have a particular certificate you are
looking
for.

AWA:  I disagree to a greater or lesser extent with every clause in this 
paragraph.  The number of certificates does not have to be one; "small" for 
appropriate values of that word will suffice.

"Do not care about the possibility of revocation much" - huh?  Where did 
that come from?  I pointed out that sometimes you're going to reject a 
putative cert even BEFORE you check revocation status; e.g., because it got 
garbled in transit and thus the signature fails.  Why does "reject because 
the signature failed before I ever bothered to check revocation" equal 
"don't care about revocation"?

"Are not worried about potential CA key compromise" - bear in mind that 
there are a lot of factors that come into play if a CA key has been 
compromised.  Thus, making a decision to accept a certificate originally 
signed with a key known to have been compromised requires a lot of 
consideration.

If you are checking a number of certificates from the same CA (say, Visa 
cards)
then you only need to check one signature and a few hashes, which is much
more efficient then checking a signature from every certificate. You can 
even
check that signature in advance, for example a vendor can do it outside of 
rush
hours and then only a few hashes need to be computed: this is more 
efficient
than verifying a signature each time. If your certificate is your credit
card and today
is your shopping day, you can prefetch verification path to speed up
approval for
your purchases (in this case I assume it to be a smartcard, as is common in
Europe).

AWA:  yes, for this environment, the approach you suggest may be more 
efficient than the traditional one.

Besides efficiency issues there are other properties that a current scheme 
does
not possess. For example, if a CA key gets silently compromised, and
a certificate is forged quietly, with the current technology there is no 
way
to discover that a certificate is fake. However, in our scheme, in order to 
fabricate a certificate, the root value of the Merkle tree has to be 
altered,
which will be too conspicuous to miss.

AWA:  forgive me if I get the technology wrong - I have some familiarity 
with Merkle trees, but I'm certainly no expert on them.  However, as I 
understand the technology proposed, every time the CA issues a new 
legitimate certificate, the root value has to be altered.  In any kind of 
dynamic environment - e.g., certificates issued every few (seconds, 
minutes, hours,...), new certs are issued and thus the root value has to 
change regularly. Thus, the event "root value altered because of a fake 
cert signed by a compromised key" is very difficult to distinguish from 
"root value altered because of legitimate cert signed by the real CA", 
EXCEPT to the CA itself.  Yes, if the CA is "eternally vigilant", you might 
catch this happening, but then again you might not.

And another property. Even though directories are supposed to be untrusted 
(or
we would not need a CA signature at all), if we are looking for a
certificate, we
are willing to believe that a particular certificate is not in the
directory, on the
directory's say so. Our approach allows you get a get a proof that this
directory
really does not possess a cert you are looking for. No more trust needed 
for
untrusted directories.

AWA:  If the directory tries to say "I have some certs, but not the one for 
which you're looking", your approach works. If the directory says "I have 
no certs at all", your approach provides the same results as the previous 
approach.  About which "attack" do you care?

So, it looks like efficiency really depends on how those certificates are 
used.

Irene

>			Al Arsenault
>			Chief Security Architect
>			Diversinet Corp.
>
>
>-----Original Message-----
>From:	Irene Gassko [SMTP:[email-masked]]
>Sent:	Monday, August 07, 2000 10:20 AM
>To:	Stephen Kent
>Cc:	[email-masked]
>Subject:	RE: OCSP request
>
>Steve,
>
>You are right and I know that currently signatures are mandatory.
>But making changes in order to solve serious problems is a part
>of the standards process, isn't it? A lot of discussion in this
>group is devoted to suggested improvements in the standard. If
>making signatures optional can help with CA key change and cert
>archiving, would not it be a good idea to allow such usage (as in
>MAY)?
>
>Irene
>
>At 05:55 PM 08/06/2000 -0400, Stephen Kent wrote:
>>Irene,
>>
>><snip>
>>
>>
>>>The main idea is to eliminate signatures in certificates and have CA
>>>sign a Merkle tree of certificates instead. Then CA key compromise
>>>requires the change in that signature (which can be downloaded
>separately)
>>>but leaves cards and certificates unperturbed. You can use multiple
>>>signatures with different signature algorithms and keep keys on 
different
>>>continents if you wish. This scheme also helps with archiving. And you 
do
>not
>>>need a CRL. It can be used with X.509 certificates, making the signature
>>>on a certificate optional, rather than mandatory. Or you can make it
>>>an owner's signature instead of a CA's signature.
>>
>>Irrespective of the merit of the approach to which you allude, the
>>result would not be an X.509 cert. Signatures are mandatory, not
>>optional, in the format that is the basis of this WG's activity.
>>
>>Steve
>
>------------------------------------------------------------------------
>----
>-------------------------------------------------------
>Irene Gassko			Bell Laboratories		http://www.lucent.com
>Lucent Technologies		Secure Technologies Dept.
>1600 Osgood Street			phone:	(978) 960-5767
>Room 30-2-A31			e-mail: 	[email-masked]
>N. Andover, MA 01845		fax: 	(978) 960-3240

------------------------------------------------------------------------  
----
-------------------------------------------------------
Irene Gassko			 Bell Laboratories		http://www.lucent.com
Lucent Technologies		Secure Technologies Dept.
1600 Osgood Street			 phone:	(978) 960-5767
Room 30-2-A31			 e-mail: 	[email-masked]
N. Andover, MA 01845		 fax: 	(978) 960-3240

---

From: Irene Gassko <[email-masked]>
Date: Thu, 10 Aug 2000 11:17:21 -0400

Al,

Thanks for your analysis. My replies are inline.

>on a lot of the factors identified above.
Now I understand what you mean by normal processing mode. You are right
that we have different examples in mind when talking about certificates. I do
not see why efficiency in cert processing is so important for email, when our
speed of reading is so slow. I suspect that the main bottleneck in efficient
processing of email is us, not certificate verification. When I think of 
certificates, I think more of hardware tokens and credit cards and cases
when these need to be verified in quantity, say, by a vendor. It is not the
only model I consider, but this is the first one I will think of when certs are
mentioned.

certificate,
>looking for.
You are right, I missed that part, sorry for the confusion. In our scheme you 
have 2 checks for the price of 1. And if half of your correspondents have 
Verisign certificates, you can schedule checking Verisign's signature 
anytime you want, say while you get your well-deserved rest, and then 
you will need to check only a few hashes for each of these guys. If 
efficiency of checking is important for some reason, the hashes you 
need may even be attached to the cert.

>signed with a key known to have been compromised requires a lot of 
Absolutely. Still our scheme allows much better recovery in this case,
and if we come back to archiving, then the original CA keys have a
substantial probability of being compromised over a long period of time
(say, 50 years).  OTOH, if the CA's key is quietly compromised only
our scheme helps to catch forgery fast.

>cards) then you only need to check one signature and a few hashes, 
>which is much more efficient then checking a signature from every 
>certificate. You can even check that signature in advance, 
>for example a vendor can do it outside of  rush hours and then only 
>a few hashes need to be computed: this is more 
>efficient than verifying a signature each time. If your certificate is your 
>credit card and today is your shopping day, you can prefetch 
>verification path to speed up approval for your purchases (in this 
>case I assume it to be a smartcard, as is common in Europe).
>
>does not possess. For example, if a CA key gets silently compromised, 
>and a certificate is forged quietly, with the current technology there is no 
>way to discover that a certificate is fake. However, in our scheme, in order 
>to fabricate a certificate, the root value of the Merkle tree has to be 
>altered, which will be too conspicuous to miss.
>
Let us look at the current practice of credit card companies. If you get 
your card or cancel it, all changes are actually done once a day.
If we do the same for Merkle tree, it will a be a root of the day, a forgery 
of which will be very visible. You can do it more often, but most probably
it will be at scheduled intervals and any update at inappropriate time will
be obviously suspicious.

>(or we would not need a CA signature at all), if we are looking for a
>certificate, we are willing to believe that a particular certificate is
not in the
>directory, on the directory's say so. Our approach allows you get a get 
>a proof that this directory really does not possess a cert you are looking
for. 
>No more trust needed  for untrusted directories.
>
If the directory says, "I have no certs", you go to another directory. If the
directory says "I have all the certs, but the one you are looking for does
not exist", you have either to double your effort by checking another,
independent directory each time, or risk the fact that you are being 
cheated. I think that this "attack" is worse.

Irene

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