================================================================== Preventing digital book-burnings without using patented technology ================================================================== ------------------------------------------------------------------ Long-time archival storage without timestamping ------------------------------------------------------------------ :Author: Benja Fallenstein :Created: 2003-07-13 :Modified: $Date: 2003/07/16 15:13:19 $ (the beginning of a summary of the stuff I developed while thinking about Storm pointers; need to publish as a techreport to get protection from others patenting this) Introduction ============ - Documents on the Web transient - A long-term storage system where past versions remain accessible as long as someone wants to access them - Digital signatures for updateable documents - Keys expire and are revoked - The usual approach: Certificate Authorities (CAs) plus Time Stamping Services (TSSs) - For a complete system, also need a Key Archival Service (KAS), which stores the certificate associated with an identity at one time, in order to verify that key K was really the certified public key of entity E at time T - Together: KASTS design; non-centralized: Prokopius - Good TSS mechanisms patented; the need for something new - We present an alternative design which relies on non-patented technology - We show that attacks on our system have equivalents in a KASTS system An "A said that B said that C said..." approach =============================================== - Key intuition: each signer picks an *envoy*, a service provider. The signer has signed something if their envoy says they have signed it. - Each envoy again appoints another, "parent" envoy (except for one designated envoy, the *root envoy*). - An envoy has signed something if their parent envoy says they have signed it. - The signers and envoys thus form a tree: the signers are leaves, the envoys are interal nodes. - A full "signature" of a message M consists of the root saying: "My child envoy A said that A's child envoy B said that B's child signer C said that M is true". - What the root envoy says is established out-of-bounds, e.g. through common public-key cryptography - so far, not a very secure system: envoys completely trusted - similar to timestamping with a completely trusted TSS, i.e. where the timestamp consists of the TSS saying, "Document X seen at time T." Hash trees and catenate certificates ==================================== - Better system: A child envoy regularly submits the root of a hash tree of all its signed messages to its parent envoy; the parent envoy simply certifies that one hash - (the child envoy only submits the messages that are new since the last time it submitted a hash tree, of course) - The root envoy, instead of submitting the hash tree root to another entity, chains them together in a linear list-- i.e., in each "round," the root publishes a pair (hash tree root, last round's hash). - The public keeps an eye open that in each round, the root does indeed refer to the correct last round. - A full signature consists of all the verifying information necessary to get from one such root round to the signed message - Example: From the root hash through the hash tree to the statement "Envoy A has submitted hash HA;" from HA through the corresponding hash tree to the statement "Envoy B has submitted hash HB;" and from HB through the corresponding hash tree to the statement "Signer C has submitted message M." - All of the root's rounds are publicly remembered, so if the signature was in a past round, it can be verified against the present round's published hash value. - The present round's hash value is, again, signed with the root's public key and published widely. - Additionally, in regular intervals, the value can be "grounded" by publishing it in a widely witnessed, undeniable way, e.g. by widely distributing a notarized "real world" document stating the present round's value. - This, again, is reminiscent of timestamping-- this time, of the catenate certificate variety. - That technology is patented... **for timestamping**. We don't do timestamping at all here. No "method for time-stamping a digital document," as `the patent`_ says, so it doesn't trigger them!!! - The patent on Merkle hash trees has expired. (XXX check, but I'm pretty sure) - We'd assume that a benign envoy only signs a message after it has securely authenticated the signer somehow. - Trust in one's envoy is required because the envoy can sign messages in one's name. - However, if one notices that one's envoy wrongly signs messages in one's name, one can initiate legal action or similar against the envoy. - This will not remove the signatures from the system, but can be used to prevent further misbehavior. (Removal of the sigs is not possible, because it would endanger non-repudiability; i.e. if there was a technical way to invalidate a signature, it could be used to maliciously deny the validity of a correct signature.) - This is similar to the CA in a KASTS system; a malicious CA could also sign messages for their clients, after issuing a certificate associating the client with a public key whose corresponding private key is known to the CA. - It's also similar to a webspace provider; a provider can replace one's website - Cryptographically, the scheme only depends on the hash function; no keys are used in the archive, the use of public-key cryptography is limited to non-archived infrastructure stuff .. _the patent: http://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO1&Sect2=HITOFF&d=PALL&p=1&u=/netahtml/srchnum.htm&r=1&f=G&l=50&s1=5,136,646.WKU.&OS=PN/5,136,646&RS=PN/5,136,646 Scalability and trust ===================== - The hierarchy in the above system serves two purposes: Scalability and trust - Scalability because the root doesn't need to deal with all users on the system, only the first-level envoys - Trust because people can pick an envoy they really trust, instead of being stuck with the root provided by the network - Of course, the root can still cheat everybody, in theory. But since it does relatively few transactions, it is possible to keep an eye on it and ensure that it does not cheat. - For example, the root might do a new round only every day, or every week. - Generally, a first-level envoy will promise to its children to keep a close watch on what the root is doing; that way, if the child trusts the first-level envoy to do its job well, it can rest assured that the root will be forced to act correctly. - If the root misbehaves, remedy is sought out-of-bounds-- for example, through legal action. Promises ======== - If the root's rounds are as infrequent as postulated above, however, it will take a day or more to obtain a signature on a message. - While that may be fine for pure archiving, it is not acceptable for a day-to-day publishing system. - Therefore, the *promise* architecture. Key idea: Before a signer has acquired a certificate on a message from its envoy, it can use its public key to sign a *promise* that it will later submit the message to its parent envoy for certification. - Until the key has expired or been revoked, the signer can be held accountabe for their promise: If the signer fails to submit the message to its envoy, anybody can submit the promise to the envoy; the envoy will verify the promise and issue a certificate on the message. - If the envoy refuses to honor the promise (it may conspire with the signer), one can ask the parent envoy and so on, right up to the root. - Since everybody can validate the promise, the people that keep a watch on the root can verify that the root acted correctly if it honored a promise that was broken by its children. - An entity E can acquire a key simply by getting a certificate on the message, "E has public key K (expires at time T)." - An envoy maintains a certificate revocation list (CRL) containing, at any given time, every such certificate that has been revoked and that hasn't expired yet. The current CRL is published together with the root of the tree of messages currently certified by the envoy. - The CRL is submitted to the parent envoy together with the root of the message tree. The parent's CRL contains a pointer to each child's current CRL. - Each root round then consists of the pointer to the hash tree, the pointer to the previous root round, and the pointer to the root's current CRL. - A key remains valid until it either expires, or it appears on the parent envoy's CRL-- *as reachable from the root's CRL*. That is, a key remains valid until the CRL it is on has propagated up to the root. - This is to ensure that a promise signed by the key remains valid until the revocation has been published in a widely witnessed way, and until any party in possession of the promise has had the chance to force the promise to be honored through the root. - Thus, one can have confidence in a promise as long as one keeps an eye on it and approaches the appropriate higher-level envoys if the lower-level envoys cheat. - The above means that until the revocation has propagated up to the root, messages can still be signed by the revoked key. - Acceptable for digital publishing; the affected publisher can later publish a note that the key was compromised and it wasn't them who signed certain versions of a document. Readers can then draw their own conclusions. - Similar in KASTS design: If a signature and the revocation of a certificate are timestamped in the same globally accepted timestamping round, then the signature has to be accepted as valid (since the revocation may have happened after the signature, and we cannot allow publishers to sign something and later revoke their keys to pretend they didn't really give the signature). - If you want to be protected from this, guard your private key so that nobody can steal it before its expiration time! ;-) - It cannot be expected that every person validating a signature is online often and long enough to ensure that the promises it has received are kept. - Instead, they submit the promise to an always-online entity that they trust to perform this job in their stead, often their own envoy. - Once the promise has been fulfilled, that entity will send back to the original verifier all data necessary to verify the signature against a given root round value. This, then, is the "full" signature that the promise promised. - Of course, if the trusted entity collaborates with the signer of the promise, they can break the promise. Thus, trust in the promise-watching entity is really required. - This, again, has a parallel in KASTS/Prokopius; as long as a document hasn't been timestamped globally, to be sure that it will be globally timestamped one has to submit it to a trusted timestamping service. If the trusted TTS collaborates with the signer, it can prevent the signature from being timestamped at all. (If the key is revoked in the same round, the signature becomes worthless.) - Once a child's key has been revoked, an envoy shall assign a new key only after it has ascertained through out-of-bounds means that the key is really in the possession of the child entity. - Through which procedures the envoy obtains this information is a question of policy, and possibly of the contract between the envoy and the child, if any. - It should be noted that while the current operations depend on public key cryptosystems, the archive operates exactly as in the previous scheme and deepends only on hashes. This means that the whole promise architecture can be changed at a later time if a better system is invented, without invalidating the archive. A distributed system ==================== - Using a protocol analogous to Prokopius', we can allow the root values to be produced through a Byzantine agreement protocol by the first-level envoys, i.e. the children of the root. - There is only one function that should probably not be implemented this way: Assgning a new key to a first-level envoy after its old key has been revoked. - All the other functions can be authenticated cryptographically: A child envoy's hash tree root or CRL is accepted iff signed by the child envoy's current key; a child envoy's key is revoked iff there is a statement signed with that key that the key should be revoked; a promise given by somebody is accepted if it can be validated and the key wasn't revoked before. The root's behavior in all these respects can be checked by independent bystanders through purely cryptographical means. - (Actually, there's also introduction of a new first-level envoy, but that can be seen as a special case of assigning a new key... in a sense...) - But the assignment of a new hash is a social process; it involves verifying through out-of-bounds means that the new key is really in possession of that envoy. - Assigning new keys after revocation could be done through some agreed-upon, widely reviewed social process; one example would be the publication of an RFC. Off-line identity generation ============================ - Generating an identity that can sign messages through this system doesn't necessarily require an online registration with an envoy, though this is certainly the most obvious way. - Alternatively, one could create a document stating the signer's initial public key and its expiration date, the provider that the signer picks as its parent envoy, and personal identity information about the signer, for the envoy to verify the signer's identity when assigning a new key. - The hash of the above document would be the signer's identity in the system. - The signer could immediately start handing out promises, using the key specified in the above document. If they want permanent signatures authenticable from a root round value, or if they need their key revoked, or if they need a new key assigned, they can contact the envoy, present the above document, and ask the envoy to verify their identity and act on their behalf. - This would allow the signer to first use this system privately, yet with a global identity. - Of course, this presumes that the envoy's policy includes dealing with this kind of request. - There should be a way for an envoy to specify simply, "In the future, messages from my child A will authenticated by envoy E"-- allowing a signer to switch to a different envoy. - Then, there could be special envoys dedicated only to handle off-line-generated identities by assigning the corresponding entities to a different envoy of their choice. Naming ====== - The hierarchy of envoys could be used to form the basis of a secure, global naming scheme. - Each envoy would be able to assign names to its children; if the root calls a specific first-level envoy "A," and A calls one of its child envoys "B," and B has a child signer it calls "S," then S's globally unique name would be something like "A/B/S." - Each signer would then have their own namespace for documents it could publish, e.g. "A/B/S/doc1." - Every envoy would have to guarantee that it never assigns a name in its namespace to a different entity; this would, essentially, be a breach of implicit contract with the entity the name was assigned to at first. Once a name in a namespace has been assigned, it **must not** be reassigned. - Everything else is a breach of protocol and must be dealt with through legal or other social ways. Detecting envoy cheating ======================== - An alternative to CRLs is that every envoy (including the root) publishes an authenticated search tree [XXX ref], associating its children with (current key, current search tree hash) pairs. The "current search tree hash" field is omitted for children that aren't envoys, though. - A key is valid if there is a certificate for it starting at the current search tree of the root. - (During their lifetime, an envoy keeps their whole search trees available on the network.) - This is equivant to the CRL approach except in that there can only be one key associated with one entity at any given time; this makes it easier to detect when one's entity has cheated one by usurping one's key. - However, it's easier still for one's envoy to cheat by simply signing an arbitrary message in one's stead. - CAs can do this also... Comparison to the KASTS architecture ==================================== XXX Conclusions =========== - We have presented a system that can be used for permanent digital 'signature' certificates, without needing patented time-stamping algorithms. - Attacks in our system have equivalences in a CA/timestamping/key archiving system. - Our system is not implemented yet; we will start implementing it soon. - Our system is designed for digital publishing, not for creating legally binding signatures. If it were to be used for legal signatures, the envoys would have to be very trustworthy entities.