Secure data deduplication

ABSTRACT

As the world moves to digital storage for archival purposes, there is an increasing demand for systems that can provide secure data storage in a cost-effective manner. By identifying common chunks of data both within and between files and storing them only once, deduplication can yield cost savings by increasing the utility of a given amount of storage. Unfortunately, deduplication exploits identical content, while encryption attempts to make all content appear random; the same content encrypted with two different keys results in very different ciphertext. Thus, combining the space efficiency of deduplication with the secrecy aspects of encryption is problematic.

We have developed a solution that provides both data security and space efficiency in single-server storage and distributed storage systems. Encryption keys are generated in a consistent manner from the chunk data; thus, identical chunks will always encrypt to the same ciphertext. Furthermore, the keys cannot be deduced from the encrypted chunk data. Since the information each user needs to access and decrypt the chunks that make up a file is encrypted using a key known only to the user, even a full compromise of the system cannot reveal which chunks are used by which users.

REFERENCES

• 1: Atul Adya , William J. Bolosky , Miguel Castro , Gerald Cermak , Ronnie Chaiken , John R. Douceur , Jon Howell , Jacob R. Lorch , Marvin Theimer , Roger P. Wattenhofer, Farsite: federated, available, and reliable storage for an incompletely trusted environment, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060291]
• 2: N. Agrawal, W. J. Bolosky, J. R. Douceur, and J. R. Lorch. A five-year study of file-system metadata. In Proceedings of the steganographic storage. Lecture Notes in Computer Science, 2429:130--140, Mar. 2002.
• 3: Ross J. Anderson , Roger M. Needham , Adi Shamir, The Steganographic File System, Proceedings of the Second International Workshop on Information Hiding, p.73-82, April 14-17, 1998
• 4: Siddhartha Annapureddy , Michael J. Freedman , David Mazières, Shark: scaling file servers via cooperative caching, Proceedings of the 2nd conference on Symposium on Networked Systems Design & Implementation, p.129-142, May 02-04, 2005
• 5: Deepavali Bhagwat , Kristal Pollack , Darrell D. E. Long , Thomas Schwarz , Ethan L. Miller , Jehan-Francois Paris, Providing High Reliability in a Minimum Redundancy Archival Storage System, Proceedings of the 14th IEEE International Symposium on Modeling, Analysis, and Simulation, p.413-421, September 11-14, 2006 [doi>10.1109/MASCOTS.2006.42]
• 6: William J. Bolosky , Scott Corbin , David Goebel , John R. Douceur, Single instance storage in Windows® 2000, Proceedings of the 4th conference on USENIX Windows Systems Symposium, p.2-2, August 03-04, 2000, Seattle, Washington
• 7: P. J. Braam. The Lustre storage architecture. http://www.lustre.org/documentation.html, Cluster File Systems, Inc., Aug. 2004.
• 8: A. Brinkmann , S. Effert , F. Meyer auf der Heide, Dynamic and Redundant Data Placement, Proceedings of the 27th International Conference on Distributed Computing Systems, p.29, June 25-27, 2007 [doi>10.1109/ICDCS.2007.103]
• 9: Ian Clarke , Oskar Sandberg , Brandon Wiley , Theodore W. Hong, Freenet: a distributed anonymous information storage and retrieval system, International workshop on Designing privacy enhancing technologies: design issues in anonymity and unobservability, p.46-66, January 2001, Berkeley, California, United States
• 10: John R. Douceur , Atul Adya , William J. Bolosky , Dan Simon , Marvin Theimer, Reclaiming Space from Duplicate Files in a Serverless Distributed File System, Proceedings of the 22 nd International Conference on Distributed Computing Systems (ICDCS'02), p.617, July 02-05, 2002
• 11: F. Douglis and A. Iyengar. Application-specific delta-encoding via resemblance detection. In Proceedings of the 2003 USENIX Annual Technical Conference, pages 113--126. USENIX, June 2003.
• 12: David Goldschlag , Michael Reed , Paul Syverson, Onion routing, Communications of the ACM, v.42 n.2, p.39-41, Feb. 1999 [doi>10.1145/293411.293443]
• 13: Garth R. Goodson , Jay J. Wylie , Gregory R. Ganger , Michael K. Reiter, Efficient Byzantine-Tolerant Erasure-Coded Storage, Proceedings of the 2004 International Conference on Dependable Systems and Networks, p.135, June 28-July 01, 2004
• 14: Haryadi S. Gunawi , Nitin Agrawal , Andrea C. Arpaci-Dusseau , Remzi H. Arpaci-Dusseau , Jiri Schindler, Deconstructing Commodity Storage Clusters, Proceedings of the 32nd annual international symposium on Computer Architecture, p.60-71, June 04-08, 2005
• 15: Steven Hand , Timothy Roscoe, Mnemosyne: Peer-to-Peer Steganographic Storage, Revised Papers from the First International Workshop on Peer-to-Peer Systems, p.130-140, March 07-08, 2002
• 16: Health Information Portability and Accountability Act, Oct. 1996.
• 17: Dave Hitz , James Lau , Michael Malcolm, File system design for an NFS file server appliance, Proceedings of the USENIX Winter 1994 Technical Conference on USENIX Winter 1994 Technical Conference, p.19-19, January 17-21, 1994, San Francisco, California
• 18: R. J. Honicky and E. L. Miller. Replication under scalable hashing: A family of algorithms for scalable decentralized data distribution. In Proceedings of the 18th International Parallel & Distributed Processing Symposium (IPDPS 2004), Santa Fe, NM, Apr. 2004. IEEE.
• 19: A. Iyengar, R. Cahn, J. A. Garay, and C. Jutla. Design and implementation of a secure distributed data repository. In Proceedings of the 14th IFIP International Information Security Conference (SEC'98), pages 123--135, Sept. 1998.
• 20: Mahesh Kallahalla , Erik Riedel , Ram Swaminathan , Qian Wang , Kevin Fu, Plutus: Scalable Secure File Sharing on Untrusted Storage, Proceedings of the 2nd USENIX Conference on File and Storage Technologies, March 31-31, 2003, San Francisco, CA
• 21: Andrew W. Leung , Ethan L. Miller , Stephanie Jones, Scalable security for petascale parallel file systems, Proceedings of the 2007 ACM/IEEE conference on Supercomputing, November 10-16, 2007, Reno, Nevada [doi>10.1145/1362622.1362644]
• 22: Andrew W. Leung , Shankar Pasupathy , Garth Goodson , Ethan L. Miller, Measurement and analysis of large-scale network file system workloads, USENIX 2008 Annual Technical Conference on Annual Technical Conference, p.213-226, June 22-27, 2008, Boston, Massachusetts
• 23: Jinyuan Li , Maxwell Krohn , David Mazières , Dennis Shasha, Secure untrusted data repository (SUNDR), Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation, p.9-9, December 06-08, 2004, San Francisco, CA
• 24: Ethan L. Miller , Darrell D. E. Long , William E. Freeman , Benjamin Reed, Strong Security for Network-Attached Storage, Proceedings of the Conference on File and Storage Technologies, p.1-13, January 28-30, 2002
• 25: Athicha Muthitacharoen , Benjie Chen , David Mazières, A low-bandwidth network file system, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 26: M. G. Oxley. (H.R.3763) Sarbanes-Oxley Act of 2002, Feb. 2002.
• 27: Sean Quinlan , Sean Dorward, Venti: A New Approach to Archival Storage, Proceedings of the Conference on File and Storage Technologies, p.89-101, January 28-30, 2002
• 28: M. O. Rabin. Fingerprinting by random polynomials. Technical Report TR--15--81, Center for Research in Computing Technology, Harvard University, 1981.
• 29: Sean Rhea , Patrick Eaton , Dennis Geels , Hakim Weatherspoon , Ben Zhao , John Kubiatowicz, Awarded Best Student Paper! - Pond: The OceanStore Prototype, Proceedings of the 2nd USENIX Conference on File and Storage Technologies, March 31-31, 2003, San Francisco, CA
• 30: Drew Roselli , Jacob R. Lorch , Thomas E. Anderson, A comparison of file system workloads, Proceedings of the annual conference on USENIX Annual Technical Conference, p.4-4, June 18-23, 2000, San Diego, California
• 31: Adi Shamir, How to share a secret, Communications of the ACM, v.22 n.11, p.612-613, Nov. 1979 [doi>10.1145/359168.359176]
• 32: Mark W. Storer , Kevin Greenan , Ethan L. Miller, Long-term threats to secure archives, Proceedings of the second ACM workshop on Storage security and survivability, October 30-30, 2006, Alexandria, Virginia, USA [doi>10.1145/1179559.1179562]
• 33: Mark W. Storer , Kevin M. Greenan , Ethan L. Miller , Kaladhar Voruganti, POTSHARDS: secure long-term storage without encryption, 2007 USENIX Annual Technical Conference on Proceedings of the USENIX Annual Technical Conference, p.1-14, June 17-22, 2007, Santa Clara, CA
• 34: Marc Waldman , Aviel D. Rubin , Lorrie Faith Cranor, Publius: a robust, tamper-evident, censorship-resistant web publishing system, Proceedings of the 9th conference on USENIX Security Symposium, p.5-5, August 14-17, 2000, Denver, Colorado
• 35: Sage A. Weil , Scott A. Brandt , Ethan L. Miller , Darrell D. E. Long , Carlos Maltzahn, Ceph: a scalable, high-performance distributed file system, Proceedings of the 7th USENIX Symposium on Operating Systems Design and Implementation, p.22-22, November 06-08, 2006, Seattle, WA
• 36: Sage A. Weil , Scott A. Brandt , Ethan L. Miller , Carlos Maltzahn, CRUSH: controlled, scalable, decentralized placement of replicated data, Proceedings of the 2006 ACM/IEEE conference on Supercomputing, November 11-17, 2006, Tampa, Florida [doi>10.1145/1188455.1188582]
• 37: Brent Welch , Marc Unangst , Zainul Abbasi , Garth Gibson , Brian Mueller , Jason Small , Jim Zelenka , Bin Zhou, Scalable performance of the Panasas parallel file system, Proceedings of the 6th USENIX Conference on File and Storage Technologies, p.1-17, February 26-29, 2008, San Jose, California
• 38: Lawrence L. You , Kristal T. Pollack , Darrell D. E. Long, Deep Store: An Archival Storage System Architecture, Proceedings of the 21st International Conference on Data Engineering, p.804-8015, April 05-08, 2005 [doi>10.1109/ICDE.2005.47]

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.6 Security and Protection
          Subjects: Access controls

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL

General Terms:
Design, Security

Keywords:
capacity, cryptography, deduplication, encryption, optimization, secure storage, single-instance storage