Subject: Certificate life-cycle costs.

From: "Bob Jueneman" <[email-masked]>
Date: Thu, 20 May 1999 09:45:58 -0600

Ed, it took me about three readings to get it -- I had to keep scrolling 
back to see what I had written, and the "s" (current time, as you interpreted
it), was a simple typo when I was manually formatting the line.

Nonetheless, I hereby award you the pony award -- three bags full. :-)

Although you are the only person  know with an even worse 
reputation for lengthy messages than myself (good company, though!),
I think we are on to something here that is worth the bandwidth.

Off list, Hans Neilson and I were discussing the Novell Security 
Attributes that I had proposed as a partial solution to some of the
issues that had been raised with the Qualified Certificates, namely
how to identify the fact that a user was an anonymous user, that the CA
was a licensed or otherwise qualified CA, reliance limits, etc.

One of the valid concerns he expressed was the cost of "overloading"
the certificate with such additional information.  Of course I responded that
it wasn't overloading if that was the information you had to have, and if
it was less costly to include it once, rather than make someone fetch it 
from somewhere else very time it was needed. In addition, I opined 
that the attributes that were contained were approximately as stable as 
the key itself, and/or the identity of the end-entity itself.

With your work I think we can now model the impact of adding such 
additional parameters, and their influence on the decay of trust.

But it would be useful to close the loop and model the cost of 
certificate reissuance and redistribution in this entire process,
and then to boil it down to something that even the "suits"
can understand.

At first glance, it seems desirable to issue certificates that are
relatively long lived, especially if reissuance is costly or a real
nuisance, requiring personal appearance in front of a notary, etc.

But the validity period of a certificate primarily affects one thing, and 
one thing only -- the length of time that the CA is responsible for
issuing CRLs or otherwise accounting for a change in status of the 
certificate. 

So there are two competing trends -- as certificate validity periods
increase, the cost of issuance decreases, but the cost of
reissuance due to a change in the attributes tends to increase.
In addition, as the validity time increases, the cost of carrying
a revoked certificate in a CRL also increases.

My expectation is that these competing trends are likely to
add together, producing a classic bathtub curve that may be quite 
shallow, indicating that the total cost is relatively insensitive
to certificate validity periods. If the total cost to the user 
only varies by say 5% from a one month to a three year validity 
period, then it probably doesn't matter.

However, the distribution of the various pieces of the cost
equation may differ dramatically between the various components,
and one segment of the industry might find their particular ox
being gored, and so it might matter a lot to the individual 
players.

Care to go for a second pony?  Three gets you the brass ring,
to switch metaphors.

Bob

>>> Ed Gerck <[email-masked]> 05/19/99 07:49PM >>>

Bob Jueneman wrote:

> Ed,
>
> There must be a pony in here somewhere, but other than an interesting
> mathematical exercise, I'm not sure that I can put my finger on it yet.

Bob:

Well, perhaps this deserves more than just a "pony award" ;-)

Because, in my view, it answers the fundamental question that must
be addressed *before* a certificate is ever issued: "What is to be
this certificate's stated lifetime so that its data is expectedly
valid during its lifetime?". 

Additionally, the following list may be helpful to guide your finger ;-)
and our discussion, where the quotes refers to text in my original 
posting unless otherwise noted:

1. The equation

1/T = 1/T1 + 1/T2 + ... + 1/TN               (1)

is simple enough to be quickly used. It allows one to use engineering
where before one only had guess-work and a bad formula -- outcounting 
Blackley's formula, which deals with a particular case but can be cast
in the same form as Eq. (1).

2. "Since any certificate has attributes (e.g., the date it was issued,
the company name it was issued to, etc.) which may be invalid sooner 
(e.g., Y2K, misspelling, CA error) than the originally intended key 
lifetime, this discussion may be important to provide an upper bound 
for key lifetimes for any type of certificates."

3. "Certificate lifetime with M multiple attributes can be modeled 
in average behavior and without imposing attribute independence, 
by using an exponential decay formula for each effective attribute".

4. "The number N of effective attributes can be larger than the number
M of original multiple attributes in the certificate, which allows the 
representation of sub-attributes that are too significant to be ignored."

5. Attribute certification is no longer a murky situation as described
by David, which lifetime behavior cannot be proved or disproved for 
each calculation. An exponential decay rate can be generally assumed 
for each attribute, which can be made as accurate as desired by 
dividing each attribute into sub-attributes and assigning an 
additional decay rate for each one. This allows even square-function
and abruptly fall offs to be considered in the same certificate.

6. Equation (1) can handle delayed attributes, piecewise exponential
decays, square-function atrributes and any non-increasing function of
attribute validity with time, for any number of attributes.

7. It is irrelevant whether the mean attribute lifetime is significantly
shorter than the mean PK lifetime or not, as David questioned.

8. The distribution of attribute lifetimes is correctly assumed to 
be discrete in Eq. (1), answering a concern by David.

9. It is irrelevant whether the attributes within a single certificate 
are mutually independent or not in order to calculate certificate 
lifetime, answering a concern by David.

10. It is irrelevant whether the attributes within a single certificate
are all jointly independent or not in order to calculate certificate 
lifetime, answering a concern by David.

11. It rolls trippingly off the tongue: "The inverse of the certificate 
lifetime is equal to the sum of the inverses of each effective attribute
lifetime". (a previous good-humored requirement by David)

12. "The lesson here is that you have to make the key lifetime VERY short 
compared to the shortest attribute lifetime in order to get the actual 
lifetime of an attribute certificate close to its nominal lifetime", as 
written by Bob Blackley when showing why his formula could be useful. The
same result applies to Eq. (1), of course.

13. "Certificate lifetime is always shorter than the shortest lifetime".

14. "Key lifetime should be at most 1/3 the shortest attribute's lifetime."

15. "Two attributes with lifetime equal to the key will reduce
certificate lifetime to only 30% of the key lifetime."

16. "Three attributes that each have a lifetime equal to twice the key 
lifetime will nonetheless reduce certificate lifetime to 40% of the key 
lifetime." 

17. "Long-lived certificates should have a least number of attributes".

18. "Denies the usefulness of overloading public-key certificates with 
data in an attempt to increase reliance"

19. "Even for no key the least number of attributes will again result in 
a much longer-lived certificate."

20. It allows one to use the same formalism both for a priori certificate
lifetime calculations as in Eq. (1), as well as for a posteriori 
certificate lifetime calculations -- also called certificate validation.
This will be discussed elsewhere but is mentioned in my answer to your 
question (2).

21. Because it is mathematically sound in a very general context, so
that one can rely on it, forget the math and concentrate on using it ;-)

> What I'm groping for is something that would tie the expected
> certificate lifetime back to a useful cost measure, I.e.,
>
> 1.  You should use individual attribute certificates rather than
> compound attribute identity certificates if X>Y, for suitable values of
> X and Y??

Yes and No -- and I am not being humorous, it is a fundamental limitation
(though one that I did not yet address here). You need to compromise:

- An individual attribute certificate will be more reliable by itself -- 
so it is a "yes" if your objective is to increase certificate lifetime 
(see item 17 above).

- A compound attribute certificate will be more accurate by itself -- so, 
it is a "no" if your objective is to increase certificate "strength".

>
> 2.  If certificate retrieval costs X, the cost of incorrectly relying on
> an revoked certificate for some transaction is Y, and the time s
> since the certificate was last validated by CL or OCSP checking is T,
> then you should/should not revalidate the certificate??

Well-stated. We need cost-functions and "merit figures" (as usual in 
engineering) in order to facilitate decisions, and what you suggest
is one that must surely face a relying-party. I will cut some corners
below, but hopefully not too many -- I hope it still qualifies for the
"pony award" ;-)

Let me change your "T" for D -- to avoid confusion with the given 
formulas. Here, T is the certificate lifetime.

Please recall the function C(t) = exp (-t/T) given in reference [1] of
my original posting -- the a priori certificate validity function. 
Suppose this function is correctly weighed for its components, so that
it can also be considered as the probability distribution function for *a 
posteriori* certificate validity (it can be, if done as in [1], but note 
that eq. (1) deals with a priori certificate validity). Then,

Y(s) = (1 - C(s - D)) * S , for s > D,

where Y and s are as you defined and S is the value at stake.  To simplify the equation, I will forget the insurance cost, the maximum
risk covered by your insurance policy, the number of times you may
rely on it per month on average, capital costs and non-financial costs 
for  failure (such as good-will), for the moment. Then, I define a
merit-function Q as:

Q(s) = (X - Y(s))/X

and state my rule:

"If Q > 0 then proceed, otherwise validate certificate".

Note that Y(0) = 0 and Q(0) = 1 -- otherwise, Q(s) < 1 for any s.

>
> Any thoughts as to where this can take us?

Towards a mathematical theory of certification, for which much
help and discussions will be, undoubtably, necessary. You may
recall some of the origins of this model of validation, when 
we both discussed the decay of trust after certificate issuance
with time, in list and private discussions. The a priori decay
of trust with time is what makes the attribute validity decay
for the a priori determination of its lifetime. This also shows
that a certificate has many unseen attributes, if you recall
the list I used to discuss the topics, which will nonetheless
reduce its lifetime. One example, of several discussed in
http://www.mcg.org.br/cert.htm , is the validity of the CA 
signing certificate -- which is not mentioned in the subscriber certificate as an attribute but can render it invalid if the CA
cert expires or is revoked before the subscriber's certificate
lifetime expires.

The end objectives are to qualify, quantify and increase 
certificate accuracy and reliance, as well as to provide support
for all modes of certification [http://www.mcg.org.br/cie.htm] 

Since this focused list has a different task, my objective here
was primarily to show that Blackley's formula is not an YARRFS
(Yet Another Random Result From Statistics) as David Kemp 
correctly IMO questioned, but rooted in a more general framework
which validates the intuition behind it and offers some good
tips -- my list of "finger tip" points 1-21 above.

Thus, I expect that this can indeed be useful for the PKIX effort
and for all kinds of certificates, in a simple equation (1) that 
may accomodate all needs -- so far ;-)

Comments?

Cheers,

Ed Gerck
______________________________________________________________________
Dr.rer.nat. E. Gerck                                 [email-masked]

---

From: Ed Gerck <[email-masked]>
Date: Thu, 20 May 1999 10:54:10 -0700

Bob Jueneman wrote:

> back to see what I had written, and the "s" (current time, as you
> interpreted it), was a simple typo when I was manually formatting the line.
>

Bob:

I also award you the "pony award" for a good question that allowed me
to reply on a focused direction. This is much easier than having to do both,
question and reply ;-) Besides, I have no qualms about using "s" for time,
after all, it's just a name ;-)

> how to identify the fact that a user was an anonymous user, that the
> CA was a licensed or otherwise qualified CA, reliance limits, etc.
>
> the certificate with such additional information.  Of course I responded
> that it wasn't overloading if that was the information you had to have, and
> if it was less costly to include it once, rather than make someone fetch it

Until your last phrase, I note that what you and Hans were diverging about
is a simple instance of the paradox between accuracy and reliability for
intersubjective and objective systems. An example of it was given in my
reply to your question #1 in my former e-mail, which I believe fits and
explains the problem in your discussion above -- a compromise solution
is needed since both accuracy and reliability, though fully independent,
cannot be independently optimized in intersubjectrive and objective
systems. The mathematical reasons for this would not fit the margins of
this e-mail but I can send a draft note to whoever is interested.

But your last phrase is, you may realize, contradicted by the equation I
presented for the certificate lifetime as the inverse of the sum of the
inverses of the atttribute lifetimes contained in it -- because the attributes
as a whole will very much lower the certificate lifetime even if  each
attribute and the key have the *same* lifetime.

> additional parameters, and their influence on the decay of trust.

Yes, where I note that trust is fully intersubjective here, as "that which I
rely upon for my decisions" -- it is not objective trust, which is simply
an authorization or, as oftentimes expressed, a license that is being
extended.  So, in our case, the authorization is there as the certificate
itself -- but, do I trust it, do I rely on it for my decisions? To what
extent of reliance? This is the question being addressed here -- the
decay of trust for that certificate as measured by the extent of
reliance. For context on this, please see the reference
http://www.mcg.org.br/trustdef.htm

> But the validity period of a certificate primarily affects one thing,
> and one thing only -- the length of time that the CA is responsible
> for issuing CRLs or otherwise accounting for a change in status of
> the certificate.

Yes -- to the CA. But not necessarily to the relying-party, nor the
r-p application that reads and processes the certificate. In fact,
today, certificates are used without much concern to CRLs -- even
by the browsers that are supposed to query them. So, in practice,
the validity period of the certificate is a welcome liability cap to the
CA and perhaps a nuisance to the user that will need to handle
multiple annoying messages that he cannot shut off for any period
of time, just to continue to use that certificate which he justifiedly
trusts.

So, the question arises -- could the r-p calculate the validy of a
certificate, a posteriori? This was positively answered in my reply
to your question #2 -- and, quantitatively.

Thus, certificate issuance in PKIX/X.509 model is CA-centric but
certificate validity does not have to be CA-centric even in the
PKIX/X.509 model -- though, I stress, it is today. But only on
paper ;-)

> a revoked certificate in a CRL also increases.

The two competing trends only exist if both certificate issuance and
certificate validity are CA-centric. If one of them is not, the "loop"
is at least partially broken -- for example, if certificate validity is not
CA-centric (as above discussed) then the r-p can apply different decay
times for each attribute and calculate an instantaneous confidence limit
for each different  use of the certificate, at different times. Certificate
validity is then IMO properly centered on the r-p --  who is
the party at risk *and* knows what the certificate is being used for.
This allows the r-p to cope with  revoked but partially valid certificates
("false positives" as mentioned by Blakley as his concern), with
expired but unrevoked certificates (as I exemplified in time logic),
and other combinations of validity qualifiers.

Alternatively, to center it on the CA will introduce artificial conflicts
(as you describe above) and increase r-p risks.

> to certificate validity periods.

Agreed, but the trends can also negatively reinforce each other
so that the total cost does not decrease much as you change validity
periods in PKIX. Longer-validity certificates can and will probably
cost more than short-validity certificates because the liability cap is
higher for the CA -- the question is how much more?  And, this is
a commercially-defined question -- no longer in the r-p hands.

> If the total cost to the user only varies by say 5% from a one month
> to a three year validity period, then it probably doesn't matter.

It may vary only 0.05% -- but the real question is: how much
is being charged for a three-year validity certificate? Does it
matter if the same value is divided in 36 installments?  One way
(by dividing the payments for one certificate into 36) or another
(by dividing the certificates into 36, with one payment for each
one)?

> being gored, and so it might matter a lot to the individual

Especially to r-ps.

> Care to go for a second pony?  Three gets you the brass ring,

As above, but the gold plate should go to you .. as you made it
to here ;-)

Thanks for the good comments and for sharing the blame of long
postings.

Cheers,

Ed Gerck

---

From: "Linn, John" <[email-masked]>
Date: Fri, 21 May 1999 15:50:45 -0400

Bob wrote, excerpting: 
 
> Dan Geer has a very succint statement of this problem, which he
> uses to compare the costs of secret-key and public-key systems.
> He observes that in secret-key systems, the costs tend to be 
> concentrated
> at the time of issuance, whereas in public-key systems they tend to
> be concentrated at the time of validation (e.g. through 
> revocation checks
> etc...).  Hence, as he puts it, "you can pay me now or you 
> can pay me later".
> 

It strikes me that some consideration of high costs of revocation in PKI
systems, with a strong attendant goal of minimizing the proportion of
certificates revoked before their validity expires, has derived from the
traditional premise of CRL-based revocation. OCSP-based revocation may
motivate different analysis; if the backing store behind an OCSP responder
is a non-CRL database describing the status of issued certificates,
revocation doesn't incur the incremental costs of generating, propagating,
and maintaining growing CRLs. If CRL management costs are removed, it may
become reasonable to accept more statistically frequent revocation in order
to gain the information value of additional certified attributes.

--jl

---

From: "Bob Blakley" <[email-masked]>
Date: Fri, 21 May 1999 15:00:58 -0500

John Linn writes

>and maintaining growing CRLs.

This is undoubtedly true, ...

>If CRL management costs are removed, it may

but this really depends on the environment.  Everyone is familiar with the
usual explanation given for the popularity of smartcards in Europe, namely
that the telco infrastructure is so expensive to use that merchants can't
afford
to do online credit-card status verification, so there's value in assigning
this
function to a dialog between the merchant and the card itself.

I don't actually know how much truth there is in this explanation, but I *do*
know
that the economics of online verification are different in Europe and the USA.

I think the high costs of revocation come from several different sources:

(1) The cost to the issuer of actually KNOWING what the correct status of
        a certificate is, and

(2) The cost to the issuer of distributing status information

(3) The cost to the relying party of consulting status information

#2 is certainly different in OCSP vs. CRL configurations; Some constituent
of #3 is also different, but some of the processing is the same for OCSP as
for
CRLs.

#1 is the same in both configurations.

--bob

Bob Blakley ([email-masked])
Chief Scientist, Dascom

---

From: "Bob Jueneman" <[email-masked]>
Date: Wed, 26 May 1999 11:02:28 -0600

Before we propagate yet another urban myth, that certificate revocation 
is expensive, we ought to at least quantify that "fact".  Then we can
decide the merits of alternative approaches.

Seems to me that whatever the costs are (and I don't have ANY
quantitative data) are made up of multiple factors:  (1) The R-P's cost of 
status checking, especially status checking that returns an "all is
well" message for the umpteenth time.  (2) The cost of running the 
server CA or repository) that provides the status, whether CRLS or 
OCSP, (3) the human cost of actually doing the revocation,
(4) the human/system cost of deciding what to do about the
revoked certificate and/or transaction, (5) the cost of reissuing 
new certificates.

Clearly, if one of the larger components of "revocation" is really the
cost of issuing replacement certs, then decreasing certificate
lifetimes won't help.

What would probably help more would be considerably finer 
granularity in the response as to the reason for the revocation,
especially of the more benign cases where the entity is still
with the company, the key has not be compromised, and all 
that changes is her name, or OU.

Bob (Jueneman)

>>> "Bob Blakley" <[email-masked]> 05/21/99 02:00PM >>>
John Linn writes

--bob

---

From: "Bob Blakley" <[email-masked]>
Date: Wed, 26 May 1999 13:54:26 -0500

Bob,

>decide the merits of alternative approaches.

Good advice...

>revoked certificate and/or transaction, (5) the cost of reissuing 

All clearly right.

>that changes is her name, or OU.

I think this is a really important point, since probably 90% of all
revocations will have the reason code "forgot password for private key".
However, be careful what you wish for.  If you have lots of reason codes,
you have really complicated policy at the relying party.  Which
means that you either have to present decisions to the user ("just say
yes"!) or you have really complicated code, which may be liable to 
bugs, subtle forms of fraud, etc...

--bob

---

From: Alan Lloyd <[email-masked]>
Date: Thu, 27 May 1999 09:22:41 +1000

Thanks Ed - I happen to be working in this space a bit - and the theory
sometimes gets to me - simply because that is what it is - 509 validity,
attr certs, signatures and CRLs, etc.

Operationally though - lets look a a real situation. Company X does
major business with company Y - Company X's directors wife uses
Company's y ATM or certificate credit system on the day the theory
mandates the certficate has expired. Theory says the wife gets refused,
the husband gets angry and Company Y loses major business.

I certainly see that based on customer information, origination and
destination of the transaction, the transaction value and context - that
a whole lot of policy based processing needs to be performed before a
"theoretical 509 refusal" is provided ...

So what goes in a "certficate" is part of a system design - in terms of
trusting the bond between Issuer/Subject - and sufficient information to
represent the policy/credentials for WHAT it is being used in a service
framework.

I therefore believe that the theory of "certficate costs" and its
validation is just that. One has to get into operational requirements,
business practices and customer loyalty/service issues before one can
calculate "costs" of certficate loading or validation.

The above is based on the real customer requirements (who realise the
implications of the 509 theory in a service delivery/customer
environment.)

regards alan

> -----Original Message-----
> From:	Ed Gerck 
> Sent:	Wednesday, May 26, 1999 5:11 AM
> To:	Alan Lloyd
> Cc:	'Tony Bartoletti'; Bob Blakley; Bob Jueneman; [email-masked]
> Subject:	Re: Certificate life-cycle costs.
> 
> 
> 
> Alan Lloyd wrote:
> 
> > I am lost on this one.
> >
> > I am sure that those who provide products and services that apply
> > certificate  functionality will work out the deployment costs as
> part of
> > the risks, ILS/LCC analysis. As certs may be used for bus tickets,
> > vehical tags, licences, identity, information integrity, etc, etc..
> Its
> > hard to determine life cycle "costs" without knowing the application
> -
> > trust, risk, market share, customer distribution and revenues..
> Costs,
> > be they called high or low are normally determined as a percentage
> of
> > revenue...
> >
> > Whats the context of this?
> 
> ;-) Costs, in several contexts -- including the one you mention. For
> example,
> in answering the questions:
> 
> 1. In terms of  the costs of "overloading" a certificate with
> additional information,
> should you use M individual attribute certificates rather than one
> compound
> M-attribute identity certificate?
> 
> 2. If certificate retrieval costs X, the cost of incorrectly relying
> on an revoked
> certificate for some transaction is Y, the value at stake is S and the
> time t since
> the certificate was last validated by CRL or OCSP checking is T, then
> when
> you should/should not revalidate the certificate?
> 
> For answers to these two questions, please check the last messages in
> the thread
> on "Re: Example with sub-attributes, was Re: Attribute certificate
> lifetimes" --
> which provide the context for this thread. See also the first two
> messages in this
> thread, by Bob Jueneman and myself.
> 
> Cheers,
> 
> Ed Gerck
>