-----BEGIN PGP SIGNED MESSAGE----- [ To: sci.crypt, sci.crypt.research, cypherpunks ## Date: 01/25/96 10:08 am ## Subject: CAs and Digital Timestamping ] At the RSA conference last week, it occurred to me that there's a really neat application for digital timestamps (as done by Surety). Whenever a CA (Certification Authority) issues a public key certificate, it should also digitally timestamp it. This provides a relatively clean way to recover from top-level CA key compromises. First of all, let's talk about hash trees. A hash tree (I think the idea was originated by Merkle, but I could be wrong) is a binary tree. Each node in the tree eventually winds up with a hash value associated with it. The bottom nodes on the tree are hashes of individual messages. The other nodes are made up of the hash of all their children. This looks like this: (pardon the ASCII art) : H_0 = hash(H_1,H_2) : / \ : H_1 = hash(H_3, H_4) H_2 = hash(H_5,0) : / \ / \ : H_3 = hash(M_0) H_4 = hash(M_1) H_5= hash(M_2) 0 : : The neat thing about this is that, if I know H_0, then when someone wants to verify that M_0 appears in the hash, they only have to tell me H_4 and H_2, and the position of M_0 in the tree. I can then find H_3 = hash(M_0), H_1 = hash(H_3,H_4), and verify that the final H_0 = hash(H_1, H_2) gives the right output value. (Compare this with a hashing chain, and you can see that, for large trees, there's a big advantage here. The number of values needed to authenticate a given message in this tree is log_2(number of messages in the tree), while the number of values to verify a chain is is the whole number of messages in the chain. In the digital timestamping service offered by Surety, they use hash trees of this kind, because this allows efficient verification of a digital timestamp. The idea behind this is that a message is hashed into the hash tree, and that the final value of the hash tree each day or week is widely published, including in the New York Times. So long as it's not feasible to go back and change that value, and it's not possible to find collisions for the hash function, any hash value that appears in that tree must have been presented to the timestamping people at some point before that tree's final hash was calculated. Here's how we use this in having a CA sign certificates. CA Signs a Key: 1. At the beginning of the day, the CA generates a random value, R_0, and has it digitally timestamped. The resulting timestamp is used as one of the entries in today's hash tree. (If the CA is their own digital timestamp service, then they'll have to use the previous day's ending value, which is reasonable enough. They'll also have to work a lot harder to publish this value each day or week.) 2. For each certificate to be generated: a. The CA verifies the information in Certificate_u, then signs it with SK_{CA}. Certificate_u contains some indication of the time and date. b. The CA hashes Certificate_u into its daily hash tree. c. The CA sends Certificate_u to user u. 3. At the end of the day, the CA publishes its own final hash tree value, and gets this value digitally timestamped. (This amounts to having the CA act as its own "node." for the timestamping service.) Now, imagine that the CA's key has been compromised. (We have to assume that the CA's daily operations were OK--if not, there doesn't seem to be a clean way to recover cleanly.) The person who has the CA's key can issue false certificates. After a while, one of these false certificates are noticed. How do we recover? We use the hash trees and the digital timestamps which we've made in the past to verify each certificate presented for recertification. The digital timestamps allow us to immediately verify that this certificate was issued by this CA at this time. And we can be certain that this hash tree is correct because it's been digitally timestamped. What this does, essentially, is to allow us to quickly recover from key compromises. We still have problems if someone can take over the operations of our CA for a few days or weeks, though in that case, we probably know the likely dates. No compromise at the CA can put a different date's timestamp on a certificate. Now, I should note that I think Merkle talks about using hash trees to do public key certificates, in his thesis, and the idea may be patented. (It's been a couple of years since I looked at his thesis, so this is a little hazy.) However, we're not using them here to provide certificates--we're using them to authenticate the certificates in the event of a catastrophic key compromise. I don't think Merkle talked about this, but I could be mistaken. (At any rate, I've never seen any mention of it since then, though it's an obviously useful idea.) If the tree structure is patented, then we could still do this by using chains or some other structure. Does anyone know if this basic idea has been proposed before? I am pretty sure I haven't seen it, but it seems pretty obvious now that I think about it. We could even recover using this method from a break of the hash function supported (so long as the timestamps are done with multiple hash functions, and at least one isn't broken), or the public key algorithm used. --John Kelsey, jmkelsey@delphi.com / kelsey@counterpane.com PGP 2.6 fingerprint = 4FE2 F421 100F BB0A 03D1 FE06 A435 7E36 -----BEGIN PGP SIGNATURE----- Version: 2.6.2 iQCVAwUBMQfn70Hx57Ag8goBAQETUQQA3S7k8rrYDud5N3uVdUqSVHC3VH+Tpmuu wcRisf8PrYX/I9Q4vBTN7SS0H30Xl1bRTQyS1mQP+CuyBlESi1qn0OMKbgAYPndd 1qYOvrX/29fMbhrO7VQjAcSAHpCZOvoVfsq0fWwv4zzUIhJBZNFnMxdSm4eNrmEv U3/oo5CiM2o= =7TIl -----END PGP SIGNATURE-----