Introduction

Key regression [3,4,5,6] coalesces many versions of a shared, symmetric key into one short key. A client can easily unwind one version of the key to derive past versions of the key. Only the group manager can wind a key forward to produce new versions of the key. Key regression is helpful when key distribution is not possible because a group manager is offline or has nearly zero throughput.

Prototype

The Chefs file system [3] uses key regression to generate the shared, symmetric keys protecting the confidentiality of content in a publishing system. Chefs protects an entire directory tree with a single shared, symmetric key. Chefs also uses lazy revocation [2,6] to make group member eviction fast. Following an eviction, new content is encrypted with a new version of the shared key. Yet old content remains encrypted in past versions of the shared key. Key regression helps coalesce the many versions of a shared key used in cryptographic storage.

Key regression enables publishers on low-bandwidth connections to control access to private content replicated by untrusted servers. In the Chefs file system, a publisher encrypts file system data and metadata at the block level with a symmetric key for confidentiality. A client that downloads encrypted blocks from an untrusted server can access content by decrypting with the symmetric key.

Contributions

The contributions of this project include:

• Key regression constructions based on hash functions, block ciphers, and trapdoor permutations
• The Chefs file system to demonstrate the utility and performance of key regression
• A concrete definition of security and proofs of security for key regression

Related Work

The Plutus file system [5] introduced the notion of key regression, but did not implement or measure the performance of key regression. Our contribution serves to precisely define the necessary properties key regression, construct several secure key regression protocols, and offer the first performance measurements of key regression under workloads of dynamic content and dynamic group membership.

Key regression provides the opposite semantics of forward-secure encryption [1]. Forward-secure encryption aims to prevent an adversary who breaks into a machine from decrypting past communication protected with past versions of a key. Yet the adversary may be able to derive keys for future communication. Key regression ensures that a client can derive past versions of a key, but not immediately compute future versions. This makes sense because key regression is helpful for protecting stored data. We desire permanency. Forward-secure encryption is about protecting ephemeral communication.

Research Support

Partial support came from Project Oxygen and an Intel Fellowship. This research is in collaboration with the Johns Hopkins University Information Security Institute and the University of California at San Diego.

References

[1] Mihir Bellare and Bennet Yee. Forward-Security in Private-Key In Cryptography Topics in Cryptology, CT-RSA 2003, Lecture Notes in Computer Science, Volume 2612 , M. Joye ed., Springer-Verlag, 2003.

[2] Kevin Fu. Group sharing and random access in cryptographic storage file systems. Masters thesis. MIT. June 1999.

[3] Kevin Fu. Integrity and access control in untrusted content distribution networks. PhD thesis. Manuscript, April 2005.

[4] Kevin Fu, Mahesh Kallahalla, Sivaramakrishnan Rajagopalan, and Ram Swaminathan. Secure rotation on key sequences. Manuscript, 2002.

[5] Kevin Fu, Seny Kamara, and Tadayoshi Kohno. Key regression for fast and secure content distribution using untrusted servers. Manuscript, April 2005.

[6] Mahesh Kallahalla, Erik Riedel, Ram Swaminathan, Qian Wang, and Kevin Fu. Plutus: Scalable secure file sharing on untrusted storage. In Proceedings of FAST 2003: 2nd USENIX Conference on File and Storage Technologies, San Francisco, CA, USA, March 2003.