Subject: Example with sub-attributes,was Re: Attribute certificate lifetimes

From: "Bob Jueneman" <[email-masked]>
Date: Wed, 19 May 1999 09:31:07 -0600

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.

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??

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??

Any thoughts as to where this can take us?

Bob

>>> Ed Gerck <[email-masked]> 05/18/99 11:06PM >>>

List:

I received some private requests to work out the example provided
by David Kemp, using sub-attributes to calculate the certificate lifetime.

The example, regrouped for its parts, is:

>Assume that a company has a policy of reassigning its employees
> every three years.  A certificate might have the following
> collection of attributes:
>
>    eye color (lifetime = 72 years)
>    department (lifetime = 3 years)
>    telephone  (lifetime = 3 years)
>    manager    (lifetime = 3 years)
>
> Assume that everyone is happy at this company, so that turnover is very
> low (<1%) and unexpected changes in assignment are rare.
..
> The probability that the phone number remains valid does not decay
> exponentially with time, it remains nearly constant (perhaps decaying
> slightly) for three years, at which point it falls abruptly to near zero.

The lifetime calculation has the following steps:

1. Modelling of effective attributes

1.1 eye color (lifetime = 72 years), single exponential decay
      Te = 1/72

1.2 department (lifetime = 3 years), single exponential decay
       Td = 1/3

1.3 telephone  (lifetime = 3 years), nearly constant for 3 years, then falls
      abruptly to zero. The "telephone" attribute has then two sub-attributes,
      ts and tf:

ts. a very slow decay for three years, which corresponds to a very large
    lifetime, so that Tts >> 1 and 1/Tts ~ 0

tf. a very fast decay if the certificate is more than three years old, which
    corresponds to a very short lifetime, so that Ttf ~ 0 and 1/Ttf >> 1

1.4 manager    (lifetime = 3 years), single exponential decay
      Tm = 3

1.5 certificate holder turnover of < 1% is neglected in period, Th >> 1
      and 1/Th ~ 0.

There are then 7 effective attributes (N = 7) and 5 original attributes (M =  5).

2. Lifetime calculation:

The average certificate lifetime, with calculation valid before three years are
passed from issuance, is:

1/T =  1/72 + 1/3 + 0 + 1/3 + 0 =  1/1.47

So, the average certificate lifetime is 1.47 years. Since the limit of three years
has not been exceeded, the fast Ttf rate is not used. The certificate should
be invalid due to the other reasons before the telephone changes.

This result can now be compared with the two answers tentatively supplied by
David:

- "I contend that the expected lifetime of this certificate is closer to the minimum
    attribute lifetime (3 years)". This is not so -- the expected lifetime of 1.47 years
    is nearly 50% the minimum attribute lifetime of 3 years.

- "the value indicated by your formula (1/3+1/3+1/3+1/72 = .986 years)". This
   is not so, since the value indicated by the formula is actually 1.47 years when
   Ttf is correctly taken into account.

Comments?

Cheers,

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

---

From: Ed Gerck <[email-masked]>
Date: Wed, 19 May 1999 18:49:59 -0700

> 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 ;-)

> compound attribute identity certificates if X>Y, for suitable values of

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".

> 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