Method and apparatus for using secret keys to make data permanently unreadable

This application hereby claims priority under 35 U.S.C. §119 to U.S. Provisional Patent Application No. 60/514,400, filed on 24 Oct., 2003, entitled “Ephemerizer: Making Data Disappear,” by inventor Radia J. Perlman.

1. Field of the Invention

The present invention relates to techniques for encrypting and decrypting data. More specifically, the present invention relates to a method and an apparatus that manages secret keys in a manner that facilitates making data permanently unreadable.

2. Related Art

Making data robustly available is an important and difficult problem, but sometimes it is equally important for the data to become reliably unrecoverable. One example is email. One might want a certain class of emails to be readable for only some finite amount of time, say two weeks. Even if the data is explicitly deleted, copies may remain on backup media, or may have been captured and stored in transit (e.g., at a router or mail transfer agent) or even be forensically recovered from disk.

There are some email systems that have a “self-destruct” feature. This is implemented purely in the mail reading client, and involves no cryptography. It just means that the copy of the email at the client is automatically deleted after reading (or perhaps merely marked as deleted). There are also commercial systems that allow setting policies, which state that email should be deleted automatically after some time. Again, this involves no cryptography, and copies on backup media would of course not go away.

Another approach is to only store the data in encrypted form, and then destroying it is a somewhat easier problem because we just need to delete the key. However, long-term user keys can, over time, be made available through compromise or coercion. It is possible for keys to be kept in tamper-resistant smart cards, in which case it would not be feasible to covertly discover the key. To delete the data, the user need only destroy the smart card. But it is expensive to require every user to have a smart card and every computer to have a smart card reader.

A more sophisticated system for managing secret keys was designed by a company called Disappearing, Inc. This system uses a special server whose job it is to create and destroy keys. We will refer to this server as an “ephemerizer”. Conceptually, the Disappearing, Inc. system worked as follows:

1. If Alice wishes to create an encrypted message for Bob, she contacts the ephemerizer, requesting a key and an expiration time. 2. The ephemerizer chooses a random secret key K, assigns a key identifier, ID K , tells Alice: (K, ID K ), and remembers: (expiration time, K, ID K ). 3. Alice encrypts the message M with K to obtain {M}K and sends to Bob: ({M} K, ID K ) 4. When Bob wishes to decrypt the message, he sends the ephemerizer: ID K . 5. The ephemerizer replies with K, and then Bob can decrypt the message. 6. When the expiration time is reached, the ephemerizer forgets K.

To be secure, Alice and Bob communicate with the ephemerizer via some protected channel such as Secure Sockets Layer (SSL), in which they authenticate that they are indeed talking to the ephemerizer, and such that the messages between the ephemerizer and a client are encrypted.

A nice property of the Disappearing, Inc. system is that the ephemerizer could be built so it does not see messages. However, the ephemerizer must create and store a key for every ephemerally created message. This can involve storing a large amount of data if the system is used for encryption of many messages.

Hence, what is needed is a method and an apparatus that manages secret keys in a manner that facilitates making data disappear without the above-described problems.

One embodiment of the present invention provides a system that manages secret keys for messages. During operation, the system receives a desired expiration time T from an encrypter, and possibly a nonce N, at a server that manages keys. If N is not sent by the encrypter, it is generated by a key managing server. Next, the system chooses a secret S T , with an expiration time close to T, and an identifier ID S from a database for which secret S T can be retrieved using the identifier ID S . If such an S T is not already in the database, the server generates a new S T and ID S . The system then calculates a hash H=h(N,S T ), and sends H and ID S from the server to the encrypter. The encrypter then encrypts M with H to form {M}H, and communicates ({M} H, N, ID S ) to a message reader. The message reader then sends N and ID S to the server. The server then uses ID S to lookup S T , recalculates H=h(N,S T ), and sends H to the message reader, thereby enabling the message reader to decrypt {M}H to obtain M. Note that by using the secret S T associated with the expiration time T and the nonce N, the server is able to reconstruct the secret key H for the message M without having to maintain per-message state information.

In a variation on this embodiment, the server forgets both N and H.

In a variation on this embodiment, while ensuring that the secret S T is stored on the server, the system first determines if the secret S T is already stored on the server for the expiration time T. If not, the system generates secret S T for the expiration time T, and stores S T on the server.

In a variation on this embodiment, when the expiration time T is reached, the server forgets the secret S 7′.

In a variation on this embodiment, if N is not received from the encrypter, but is instead generated by the server, sending H from the server to the encrypter additionally involves sending N from the server to the encrypter.

In a variation on this embodiment, the secret S T for expiration time T, is computed by applying a hash function h to a secret S T-1 for a preceding expiration time T−1, so that S T =h(S T-1 ). This allows space to be saved by storing fewer S T ′S, possibly only a single one, and by repeatedly applying the hash function h to S T to compute secrets for subsequent expiration times. (Note that this hash function h need not be the same hash function h that was used to hash N and S T to get the per-message encryption key H.)

In a variation on this embodiment, the server stores a different secret for each combination of expiration time and security property. In this way, the server can store multiple secrets with different security properties for each expiration time.

In a variation on this embodiment, the nonce N is a per-message nonce which is generated specifically for the message M.

In a variation on this embodiment, storing S T involves generating and storing S T on a tamper-resistant smart card, which receives ID S and N, calculates H, and does not reveal S T .

FIG. 1 illustrates a message encrypter, a message reader and an ephemerizer in accordance with an embodiment of the present invention.

FIG. 2 presents a flow chart illustrating the process of encrypting and decrypting a message using secret keys in accordance with an embodiment of the present invention.

The following description is presented to enable any person skilled in the art to make and use the invention, and is provided in the context of a particular application and its requirements. Various modifications to the disclosed embodiments will be readily apparent to those skilled in the art, and the general principles defined herein may be applied to other embodiments and applications without departing from the spirit and scope of the present invention. Thus, the present invention is not limited to the embodiments shown, but is to be accorded the widest scope consistent with the principles and features disclosed herein.

The data structures and code described in this detailed description are typically stored on a computer-readable storage medium, which may be any device or medium that can store code and/or data for use by a computer system. This includes, but is not limited to, magnetic and optical storage devices such as disk drives, magnetic tape, CDs (compact discs) and DVDs (digital versatile discs or digital video discs).

System

FIG. 1 illustrates a message encrypter 102 , a message reader 104 and an ephemerizer 106 in accordance with an embodiment of the present invention. Encrypter 102 , reader 104 and ephemerizer 106 can generally include any type of computer system or computing device, including, but not limited to, a computer system based on a microprocessor, a mainframe computer, a digital signal processor, a portable computing device, a personal organizer, a device controller, and a computational engine within an appliance. Encrypter 102 , reader 104 and ephemerizer 106 may also be computing processes or software modules within the same computer system or within different computer systems.

During operation of the system illustrated in FIG. 1 , encrypter 102 encrypts a message M and transmits the encrypted message to reader 104 . Upon receiving the encrypted message, reader 104 decrypts the encrypted message to restore the message M. These encryption and decryption operations are performed with help from ephemerizer 106 .

Ephemerizer 106 is configured to service requests from encrypter 102 and reader 104 to perform operations involving secret keys. These operations can involve creating, storing, and destroying secret keys, as well as using secret keys to encrypt and decrypt information. In one embodiment of the present invention, ephemerizer 106 is configured to generate and store secret keys in a tamper-resistant device 108 (such as a smart card).

The operations performed by encrypter 102 , reader 104 and ephemerizer 106 are described in more detail below with reference to FIG. 2 .

Encryption and Decryption Processes

FIG. 2 presents a flow chart illustrating the process of encrypting and decrypting a message M using secret keys in accordance with an embodiment of the present invention. First, encrypter 102 (or optionally ephemerizer 106 ) chooses a per-message nonce, N (step 202 ). (Note that a “nonce” is a non-repeating value.) Next, encrypter 102 communicates a desired expiration time T, and possibly a nonce N, to ephemerizer 106 (step A in FIG. 1 and step 204 in FIG. 2 ). If encrypter 102 does not send N to ephemerizer 106 , ephemerizer 106 chooses an N, and sends it to encrypter 102 .

Ephemerizer 106 stores a secret S T associated with expiration time T so that S T can be looked up using an identifier ID S (step 206 ). The system first determines if a secret S T is already stored on the server for the expiration time T. If not, the system generates secret S T , and stores S T on the server for the expiration time T.

Next, ephemerizer 106 calculates a hash H=h(N,S T ), and sends H and ID S to encrypter 102 (step B in FIG. 1 and step 208 in FIG. 2 ). Ephemerizer 106 then forgets the per-message state information, H and N.

Upon receiving H and ID S , encrypter 102 encrypts a message with H and communicates ({M} H, N, ID S ) to reader 104 (step C in FIG. 1 and step 210 in FIG. 2 ).

To later decrypt {M}(H) (of the quantity ({M}H, N, ID S ) received from encrypter 102 ), reader 104 first needs to obtain H. To obtain H, reader 104 sends (N, ID S ) to ephemerizer 106 (step D in FIG. 1 and step 212 in FIG. 2 ).

Ephemerizer 106 then looks up S T using ID S (step 214 ). Ephemerizer 106 then calculates H=h(N,S T ), and communicates H to reader 104 (step E in FIG. 1 and step 216 in FIG. 2 ).

Reader 104 then uses H to decrypt {M}H to restore M (step 218 ).

Finally, when the expiration time T is reached, the system forgets the secret key S T (step 220 ). This makes any messages which have been encrypted with S r unreadable.

Unlike the Disappearing, Inc. system, the present invention avoids the necessity for the ephemerizer to keep per-message state information. It does mean that someone who compromises a single one of the ephemerizer's secret S′s compromises all messages encrypted with that secret. However, note that in the Disappearing, Inc. system anyone who compromises the ephemerizer's data would capture all the per-message keys anyway. The present invention is probably more secure in practice because it would be easier to adapt the present invention to store the secret keys on a tamper-resistant smart card, since the database is so much smaller.

One could save even more space by rolling over keys with a one-way hash function. Instead of generating a new secret for each expiration time, the secret for expiration time T might be S T , the secret for expiration time one time unit later would be h(S T ), and the secret for expiration time two time units later would be h(h(S r )), and so on. The current secret, S T , is the one about to expire. Every time unit, the current secret S r is forgotten and replaced by h(S r ). This saves storage if the ephemerizer is willing to compute h″(S r ) in order to encrypt or decrypt a message with a key n units from the current secret. Otherwise, the ephemerizer could pre-compute the next n secrets and store them, in which case it does not save any storage.

Either of the above enhancements might be able to be made on-the-wire compatible with Disappearing, Inc.'s system, and therefore could be implemented as an optimization at the server without modifying the clients. This might be done by having ephemerizer 106 , rather than Alice (who is equivalent to encrypter 102 ), choose the nonce, and have what appears to Alice to be the identifier of the per-message secret actually be the tuple (N, ID S ).

Furthermore, as mentioned above, in one embodiment of the present invention, the server stores a different secret for each combination of expiration time and security property. In this way, the server can store multiple secrets with different security properties for each expiration time.

Note that a similar ephemerizer, which maintains secret keys with expiration times, is disclosed in U.S. Pat. No. 6,363,480, entitled “Ephemeral Decryptability,” by inventor Radia J. Perlman. However, the encryption technique disclosed in this patent is based on public-key/private key pairs, which require the ephemerizer to perform many more computational operations than for the symmetric keys used by the present invention. This larger number of computational operations can place a significantly larger computational burden on the ephemerizer.

Unlike the ephemerizer disclosed in U.S. Pat. No. 6,363,480, the ephemerizer of the present application generates a per-message key H using a per-message nonce N. The ephemerizer then forgets the per-message nonce N (which is passed along with the encrypted message) and per-message key H. The ephemerizer is subsequently able to regenerate this per-message key H from the nonce N and a secret S T , which is associated with an expiration time T.

In this way, the present invention is able regenerate the per-message key without having to maintain per-message state information. This is a considerable advantage because the number of messages can be quite large, and storing per-message state information can require a large amount of storage space.

The foregoing descriptions of embodiments of the present invention have been presented only for purposes of illustration and description. They are not intended to be exhaustive or to limit the present invention to the forms disclosed. Accordingly, many modifications and variations will be apparent to practitioners skilled in the art. Additionally, the above disclosure is not intended to limit the present invention. The scope of the present invention is defined by the appended claims.