Subject: Attribute certificate lifetimes: way too much math, but getting closer to correct

From: "Bob Blakley" <[email-masked]>
Date: Mon, 17 May 1999 12:05:25 -0500

All

I'm forwarding (with permission) the following private correspondence with
Dave Kemp, for
the group's interest.

==========================================================

David,

>C'mon Bob, you've been working too hard.

Seems likely :)

>Steve's original formula is
>(I assume) based on the apocryphal formula for the time required for a
>committee of n members to reach agreement; a situation which cannot be
>proved or disproved because the a-priori distributions of the members'
>attitudes are unknown, and in general, unknowable.

An interesting basis for quantification of any sort....  By the way, I used to
espouse exactly the same formula (Steve & I seem to have come to it
independently).  Then I revised it in the WRONG direction (and even told
the revised incorrect version to Steve) and began saying that it was 2**n
rather than n**2.  But I have now seen the light....

>Attribute certification is a similarly murky situation.  John
>originally stipulated "overlapping CA and AA responsibilities and
>lifetimes", but conventional wisdom suggests that the mean attribute
>lifetime is significantly shorter than the mean PK lifetime.

Right, which is exactly the case I analyzed in my note...

>I doubt
>that there is any conventional wisdom about the distribution of
>attribute lifetimes, but I would venture that it is a discrete, not a
>continuous distribution.  Therefore, one cannot say that  "with
>probability 1, attribute 2 doesn't expire at t1".

I very much doubt that it's discrete, given the difficulty of synchronizing
clocks, even if it might be "theoretically discrete".

>I would also venture
>that attributes within a single certificate will not have pairwise
>mutually independent lifetimes - a single AA may have issued multiple
>attributes and their lifetimes are more than likely correlated.

Exactly!! Which is why I put the qualifier into the forumla.  For attributes
whose lifetimes are correlated, you have to either analyze the correlation,
or lump them as if they were a single compound attribute.

>And I
>question whether pairwise mutual independence is sufficient for
>your formula to hold, or whether the stronger joint independence is
>required.

Might be....

>In short, the preconditions for your formult to be correct cannot be
>demonstrated.  I therefore prefer Steve's formula, simply because it
>rolls trippingly off the tongue.

Rolls trippingly off the tongue, but is wrong even at the level of O-notation.
If you want the right "tripping" formula, it's inversely proportional to the
number
of attributes, not inversely proportional to the square.  As much as I wish it
were otherwise, having told lots of audiences myself that it was the
square....

>Like Mozart's opera which had too
>many notes, your formula has not enough syllables.

Another point lurks in here though.  And that has to do with relative
lifetimes of
keys and attributes, to which you've already referred.  If you know the
lifetime of
the key (let's call it Lk), and the lifetimes of each of the (presumed
independent)
attributes (call them La1, ..., Lan) then you can use a generalized version of
the
formula I gave earlier to calculate the lifetime of the cert:

The probability of any attribute expiring during the lifetime of the key is
given by
the ratio of their respective lifetimes, i.e.

        for attribute i, the expected number of times that it will expire
during the lifetime of the
        certificate is (Lk / Lai)

Then the average number of intervals which attribute expirations divide the
cert.
lifetime into is

        SUM(i = 1..n) (Lk / Lai)

Thus the probability of an attr. cert. being valid throughout its nominal
lifetime is

        1 / (1+ SUM(i= 1..n) (Lk / Lai))

(The "1 +" is the contribution of the key expiration itself; if there are no
additional attributes,
the probability will be 1; otherwise it will be lower).

And the expected lifetime of an attr. cert. is

        Lk * (1 / (1+ SUM(i= 1..n) (Lk / Lai)))

(all these presume the appropriate assumption about independence of attribute
lifetimes).

Note that this takes into account the fact that attributes may expire ANY
number of times,
including zero, during the lifetime of the cert.  It also reflects the
advantage you get by
making attr. cert. lifetimes short, and gives you a way to figure out how
short they must
be, given that you know something about the volatility of the attributes
you're certifying.

To take an example, if you issue a cert. whose key lifetime is 365 days, and
include in
it three attributes

        eye color (lifetime = 72 years)
        department (lifetime = 1 quarter)
        telephone extension (lifetime = 2 years)

Then you get

        365 * (1 / (1+ (1/72) + 4 + (1/2))) =
        365 * (1 / 5.576) =
        365 * 0.179 =
        65 days

As expected, the short-lifetime attribute dominates; if there were more than
one
short-lifetime attribute the effect would be much more pronounced:

        eye color (lifetime = 72 years)
        department (lifetime = 1 quarter)
        telephone extension (lifetime = 2 years)
        manager (lifetime = 1 quarter)

Gives

        365 * (1 / (1+ (1/72) + 4 + (1/2) + 4)) =
        365 * (1 / 9.576) =
        365 * 0.104 =
        38 days (10% of nominal)

Shortening the lifetime of the cert. to 1 quarter helps in percentage but not
absolute terms:

        90 * (1 / (1+ (1/288) + 1 + (1/8) + 1)) =
        90* (1 / 3.129) =
        90 * 0.320 =
        28 days (32% of nominal)

Shortening the lifetime to one month again increases percentage of lifetime
but not duration:

        30 * (1 / (1+ (1/864) + (1/3) + (1/24) + (1/3))) =
        30* (1 / 1.709) =
        30 * 0.585 =
        18 days (59% of nominal)

Shortening the lifetime to one DAY gives a pretty good percentage result:

        1* (1 / (1+ (1/26280) + (1/90) + (1/730) + (1/90))) =
        1* (1 / 1.023) =
        1* 0.978 =
        0.978 days (98% of nominal)

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 attr. cert. close
to its nominal lifetime.

--bob

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

---

From: Ed Gerck <[email-masked]>
Date: Tue, 18 May 1999 12:25:40 -0700

All:

There was recent questioning on this list about the possible ways to
estimate certificate lifetime when attributes are included in the
certificate, not only the key.  There was also questioning whether
even discussing this subject might make sense, since the problem seems
to be so open-ended as to be indeterminate. I show that this is not so
and that the formula derived by Bob Blakley is indeed correct, even in
a much more general context than the one he used for its intuitive 
derivation. As a practical rule, I show that key lifetime should 
be at most 1/3 the shortest attribute's lifetime.

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. It will also clearly 
show that long-lived certificates should have a least number of 
attributes.

I report that 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 [1]. 
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.

The mathematical basis for the attribute certificate lifetime model 
considered here is that any attribute will always present a monotonically
decreasing time function, which can be well-approximated by a linear 
first-degree differential equation -- as is well-known.

In the general result obtained [1], one can calculate the lifetime T of 
a certificate in terms of each effective attribute's a priori lifetime 
Tn by the simple formula:

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

for "N" effective attributes, where the key is also one of the attributes. 
The M original attribute dependencies upon one another are directly 
reflected in the number N of effective attributes as well as in each a 
priori lifetime Tn in equation (1).

I further note that no other hypothesis was needed [1] to derive (1), such 
as those made by Bob Blakley in his derivation of a previous formula for 
the lifetime of an attribute certificate:

(i) attributes are independent,
(ii) attribute lifetimes have a continuous distribution and,
(iii) attribute n-1 does not expire before attribute n, for all 2<n<N.

However even though equation (1) lifts the three assumptions that were 
imposed by Bob Blakley, it yet achieves the same result in terms of the 
key-lifetime:

>(all these presume the appropriate assumption about independence of
> attribute lifetimes).

as can be seen by inspection. The distinctions are that equation (1)
may consider a larger number of attributes than originally given in the 
certificate, and that in equation (1) all lifetimes play an equal formal 
role, while in Bob's formula the key-lifetime Lk is formally singled out.

However, I note further that there is no reason to distinguish between
the key and any other attribute in equation (1) or in Bob's formula 
because all attributes (including the key) belong to the same certificate
in both studies.  Equation (1) and Bob's formula are therefore formally 
equal -- the difference being only that equation (1) was derived without 
any restrictions from (i), (ii) and (iii).

Thus, equation (1) validates the former result by Bob and answers in the 
negative all David Kemp's doubts about its validity, which I express in the
list below.

DOUBT 1: Attribute certification is a murky situation which lifetime 
behavior cannot be proved or disproved because the a priori distributions 
are unknown, and in general, unknowable.
REPLY:  Lifetime a priori distributions for each attribute are indeed 
unknown but their time evolution is all that is required for equation (1),
which can be approximated by linear first-degree differential equations for 
each attribute [1]. This yields an exponential decay law for each attribute, 
which can be made as accurate as desired by dividing each attribute into 
sub-attributes and writing an additional differential equation for each one. 
This may increase the number of effective attributes than originally given,
but the formalism is not modified.

DOUBT 2: Conventional wisdom suggests that the mean attribute lifetime is
significantly shorter than the mean PK lifetime.
REPLY: This is irrelevant for the derivation of equation (1),  which 
represents certificate lifetime.

DOUBT 3: There is no conventional wisdom about the distribution of
attribute lifetimes, but one would venture that it is a discrete, not a
continuous distribution.  Therefore, one cannot say that  "with
probability 1, attribute 2 doesn't expire at t1".
REPLY: There are no such assumptions for equation (1).

DOUBT 4: Possibly, attributes within a single certificate will not have 
pairwise mutually independent lifetimes, so their lifetimes are more than 
likely correlated.
REPLY: There is no such assumption for equation (1). Each effective 
attribute's lifetime is estimated or measured a priori, implictly with any 
interdependency or correlation that may exist or one wishes to represent, 
and then inputted to equation (1) as a number that wholly represents such 
interactions.  The mathematical basis for this procedure is that any 
attribute will always have a monotonically decreasing validity function 
over time, which can be well-approximated by the solution of a linear 
first-degree differential equation with an adequate rate.

DOUBT 5: The question whether pairwise mutual independence is sufficient 
for Bob's formula to hold, or whether the stronger joint independence is 
required. 
REPLY: Since Bob's formula is formally equal to equation (1), and 
equation (1) actually holds for a model where attribute independence is
not an issue, this doubt does not apply.

DOUBT 6: The preconditions for Bob's formula to be correct cannot be
demonstrated.
REPPLY: This is true. However, Bob's preconditions as given by (i), (ii) 
and (iii) are not necessary and can be entirely abandoned [1], leading 
however to the same formula. 

;-) DOUBT 7: Therefore one may prefer Steve's formula "The effective 
lifetime of a certificate is inversely proportional to the square of the 
number of attributes", simply because it rolls trippingly off the tongue.
REPLY:  Try equation (1) : "The inverse of the certificate lifetime is equal
to the sum of the inverses of each effective attribute lifetime".

Next, I will use Bob's example but now with equation (1):

        key-lifetime = 1 quarter

which yields a certificate lifetime of

1/T = 1/(72*4)  + 1/1 + 1/(2*4) + 1/1 + 1/1

so that T = 0.32 quarters or, 28.8 days. In other words, the certificate 
will be valid for less time (0.32 quarters) than what might be expected 
(and, controlled) by its key validity (1 quarter). 

This means that Bob's assertion:

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

is indeed correct, as shown by this example. However, Bob's assertion is 
correct also for any other lifetime ratios and examples. Such can be 
easily understood from equation (1).  Since all lifetimes play an equal 
role, I can affirm in the general case that: 

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

as can be seen from equation (1) by inspection.  Thus, if I want to control 
certificate lifetime by challenge-response with its key then indeed I have 
to make key-lifetime VERY short compared to the shortest attribute 
lifetime in the certificate. Then, certificate lifetime will still be 
shorter than key-lifetime but their difference will be closer to zero.

As a practical rule, key-lifetime Tk should be at most 1/3 the shortest 
attribute lifetime Ta, since for Tk = Ta/3 one has:

1/T = 1/Tk + 1/Ta + ...+ 1/TN =~ 1/Tk + 1/Ta => T =~ 0.75 * Tk

As a final remark, I note that two attributes with lifetime equal to the
key will reduce certificate lifetime to only 30% of the key lifetime. And, 
that three attributes that each have a lifetime equal to twice the key 
lifetime will nonetheless reduce certificate lifetime to 40% of the key 
lifetime. Thus, long-lived public-key certificates should have a least 
number of attributes -- a fact which denies the usefulness of overloading 
public-key certificates with data in an attempt to increase reliance (e.g.,
e-mail addresses fax numbers, phone numbers, etc.) unless the key lifetime
is properly much reduced or there is no key.  But, even for no key the least
number of attributes will again result in a much longer-lived certificate. 

Comments are welcome.

Cheers,

Ed Gerck

[1] Consider an ensemble of certificates, each with a given number M of 
attributes, with each attribute defined by a lifetime -- including
the key. This ensemble can include certificates that are issued at the
same time for different keyholders and certificates that are issued at
different times for the same keyholder. The ensemble is an analysis tool,
to be used in order to allow the calculation of average statistics based
on time averages, but note that the M attributes are not supposed to be 
independent from one another.

Note also that lifetime a priori distributions for each attribute are 
unknown but their time evolution is all that is required, which can be 
approximated by a linear first-degree differential equation for each 
attribute. This yields an exponential decay law for each attribute,  
which can be made as accurate as desired by dividing each attribute 
into sub-attributes and writing a linear first-order differential 
equation for each one. 

The justifications for the attribute certificate lifetime model 
considered here are thus:

(a) empirical: any observed lifetime for an attribute will necessarily
 subsume any dependencies from other attributes. If the observed time
 variation fits well an exponential decay law then the lifetime is 
 defined as the inverse of this exponential rate (as usual). Otherwise,
 the attribute will be divided into as many sub-attributes as needed to
 fit well different exponential rates (i.e., lifetimes). This is an 
 empirical/heuristic/theoretical modeling process that is a function
 of cost and risk. Leaving out sub-attributes that have fast dependencies
 can be risky since they can quickly decay to zero and yet be considered
 valid within a larger lifetime, but identifying them all can be costly 
 --  so, a compromise solution is necessary in the modeling phase
 (engineering specification of that particular certificate). This will
 lead to N effective attributes for the original M attributes, N >= M,
 each effective attribute with an effective lifetime -- these values
 are called "a priori lifetimes".

(b) mathematical: any attribute will always present a monotonically 
 decreasing validity function over time, which can be well-approximated
 by a linear first-degree differential equation with an adequate rate.

The above procedure will define a system of N attributes (including
the key) and the N a priori lifetimes. The original number M of 
certificate attributes may be smaller but this is irrelevant.

Loosely speaking, the ensemble represents the average experience for 
each effective attribute's lifetime when all attributes are considered 
together. Thus, the ensemble may combine empirical data, heuristics and 
also theoretical data in order to allow the observer to rely upon an 
effective lifetime value to each attribute -- the "a priori lifetimes". 
Note again that the M attributes are not supposed to be independent.

To build the system of N equations that will represent the time validity
function for each effective attribute, I write one normalized linear
first-order differential equation for each effective attribute n 
(including the key):

dAn/dt = - An/Tn , for n =1, ...N              (2)

where d/dt is time derivative (in continuous or discrete form), Tn is the 
effective attribute's a priori lifetime, and An is the attribute validity 
function at time t:

An = fraction of valid attributes n at time t, normalized to the ensemble.

The solution to equation (2) is:

An(t) = 1.0 * exp(-t/Tn)  , for n =1, ...N 

Now, define C to be the certificate validity function represented by the 
product of each individual validity solutions to equation (2), all 
with equal weights:

C = A1 * A2 * ... * AN = 1.0 * exp (-t/T1 - t/T2 - ... - t/TN)

and verify that C obeys equation (2) whith the standard solution:

C(t) = 1.0 * exp (-t/T)

if and only if the certificate lifetime T is given by

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

This result is given in equation (1).

______________________________________________________________________
Dr.rer.nat. E. Gerck                                 [email-masked]
  ---  Meta-Certificate Group member -- http://www.mcg.org.br  ---