[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: threshold subjects


At 10:08 AM 11/18/97 -0500, David Black wrote:
>> The more I look at real examples, the more valuable Tatu's threshold 
>> appears.  I know this was considered a complication of the current draft 
>> therefore something to eliminate, but AFAIK, this is the cleanest (only?) 
>> way to permit the on-line replacement of a root key which has been 
>> compromised.
>The more general problem is that all keys have to be replaced eventually.
>Do threshold subjects provide a route for replacing *all* keys (one at a
>time is ok) -- i.e., replacing all n keys in a k-of-n subject?  The line
>of thinking that bothers me is that to do this, one eventually has to
>use some of the n keys to sign a certificate establishing a new key --
>on the assumption that all n of the keys eventually go stale, assume the
>adversary gets them and can then do his/her own key replacement.  This
>is a problem for a verifier that hasn't been paying close attention --
>it may accept the adversary's key replacement.

This depends, as Michael Richardson pointed out, on whether a signature by a 
key remains valid after the key has been declared compromised (or otherwise 

What we're missing there is the notion of trusted time -- either global or 

Assume I start with 3 of 5 root keys for some authorization (have an ACL 
entry with a 3 of 5 subject).  Then tomorrow I receive certificates 
replacing 1 of the 5 keys.  In case (1) I then use that knowledge to make a 
new ACL entry, still 3 of 5.  In case (2), I keep the new certificates in my 
cache, recording when they arrived (by my clock).  In case (3), I keep the 
new certificates in my cache, not recording when they arrived.

SO: ACL says: (subject (threshold 3 5 A B C D E)).
A gets replaced with F by 4 certs, each with
(subject (threshold 3 5 F B C D E))
each signed by one of the keys B, C, D, and E.

The fact that A had been stolen 3 weeks earlier makes no difference.  The 
clock starts over on compromise of the new set of 5.  Eventually, through 
this process, the original 5 keys can all have been replaced.

In cases (1) and (2), this gets expressed correctly.
In case (3), by throwing out time information, we can't evaluate this 

So, we need to keep time information.  One way is with a secure time stamp 
service (although such a service might depend on public keys, unless it's a 
hash-only service (with hash trees and daily hashes published in the 
paper)).  Another is by keeping our own local time in trusted storage (as we 
keep ACLs in trusted storage).

Of course, we don't know exactly when a key gets compromised.  Sometimes we 
never know that a key was stolen.  So, instead we have to arrange to replace 
keys periodically even with no evidence of compromise and rely on our guess 
that the replacement rate exceeds the leakage rate.

 - Carl

Version: PGP for Personal Privacy 5.0
Charset: noconv


|Carl M. Ellison  cme@cybercash.com   http://www.clark.net/pub/cme |
|CyberCash, Inc.                      http://www.cybercash.com/    |
|207 Grindall Street  PGP 08FF BA05 599B 49D2  23C6 6FFD 36BA D342 |
|Baltimore MD 21230-4103  T:(410) 727-4288  F:(410)727-4293        |