POTSHARDS—a secure, recoverable, long-term archival storage system

ABSTRACT

Users are storing ever-increasing amounts of information digitally, driven by many factors including government regulations and the public's desire to digitally record their personal histories. Unfortunately, many of the security mechanisms that modern systems rely upon, such as encryption, are poorly suited for storing data for indefinitely long periods of time; it is very difficult to manage keys and update cryptosystems to provide secrecy through encryption over periods of decades. Worse, an adversary who can compromise an archive need only wait for cryptanalysis techniques to catch up to the encryption algorithm used at the time of the compromise in order to obtain “secure” data. To address these concerns, we have developed POTSHARDS, an archival storage system that provides long-term security for data with very long lifetimes without using encryption. Secrecy is achieved by using unconditionally secure secret splitting and spreading the resulting shares across separately managed archives. Providing availability and data recovery in such a system can be difficult; thus, we use a new technique, approximate pointers, in conjunction with secure distributed RAID techniques to provide availability and reliability across independent archives. To validate our design, we developed a prototype POTSHARDS implementation. In addition to providing us with an experimental testbed, this prototype helped us to understand the design issues that must be addressed in order to maximize security.

REFERENCES

• 1: 104th Congress. 1996. Health Information Portability and Accountability Act. http://www.hhs.gov/ocr/hipaa/.
• 2: 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]
• 3: Mary Baker , Mehul Shah , David S. H. Rosenthal , Mema Roussopoulos , Petros Maniatis , TJ Giuli , Prashanth Bungale, A fresh look at the reliability of long-term digital storage, Proceedings of the 1st ACM SIGOPS/EuroSys European Conference on Computer Systems 2006, April 18-21, 2006, Leuven, Belgium
• 4: Mihir Bellare , Alexandra Boldyreva, The Security of Chaffing and Winnowing, Proceedings of the 6th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.517-530, December 03-07, 2000
• 5: Sandeep Bhatkar , Daniel C. DuVarney , R. Sekar, Address obfuscation: an efficient approach to combat a board range of memory error exploits, Proceedings of the 12th conference on USENIX Security Symposium, p.8-8, August 04-08, 2003, Washington, DC
• 6: Fay W. Chang , Minwen Ji , Shun-Tak A. Leung , John MacCormick , Sharon E. Perl , Li Zhang, Myriad: Cost-Effective Disaster Tolerance, Proceedings of the Conference on File and Storage Technologies, p.103-116, January 28-30, 2002
• 7: Choi, S. J., Youn, H. Y., and Lee, B. K. 2003. An efficient dispersal and encryption scheme for secure distributed information storage. Lecture Notes in Computer Science, vol. 2660, 958--967.
• 8: 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
• 9: CleverSafe. 2006. Highly secure, highly reliable, open source storage solution. http://www. cleversafe.org/.
• 10: S. Forrest , A. Somayaji , D. Ackley, Building Diverse Computer Systems, Proceedings of the 6th Workshop on Hot Topics in Operating Systems (HotOS-VI), p.67, May 05-06, 1997
• 11: H. M. Gladney , R. A. Lorie, Trustworthy 100-year digital objects: durable encoding for when it's too late to ask, ACM Transactions on Information Systems (TOIS), v.23 n.3, p.299-324, July 2005 [doi>10.1145/1080343.1080346]
• 12: A. V. Goldberg , P. N. Yianilos, Towards an Archival Intermemory, Proceedings of the Advances in Digital Libraries Conference, p.147, April 22-24, 1998
• 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: Andreas Haeberlen , Alan Mislove , Peter Druschel, Glacier: highly durable, decentralized storage despite massive correlated failures, Proceedings of the 2nd conference on Symposium on Networked Systems Design & Implementation, p.143-158, May 02-04, 2005
• 16: 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
• 17: Iyengar, A., Cahn, R., Garay, J. A., and Jutla, C. 1998. Design and implementation of a secure distributed data repository. In Proceedings of the 14th IFIP International Information Security Conference (SEC'98), 123--135.
• 18: 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
• 19: Kimberley Keeton , Cipriano Santos , Dirk Beyer , Jeffrey Chase , John Wilkes, Designing for Disasters, Proceedings of the 3rd USENIX Conference on File and Storage Technologies, March 31-31, 2004, San Francisco, CA
• 20: Samuel T. King , Peter M. Chen, Backtracking intrusions, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
• 21: Ramakrishna Kotla , Lorenzo Alvisi , Mike Dahlin, SafeStore: a durable and practical storage system, 2007 USENIX Annual Technical Conference on Proceedings of the USENIX Annual Technical Conference, p.1-14, June 17-22, 2007, Santa Clara, CA
• 22: Petros Maniatis , Mema Roussopoulos , T. J. Giuli , David S. H. Rosenthal , Mary Baker, The LOCKSS peer-to-peer digital preservation system, ACM Transactions on Computer Systems (TOCS), v.23 n.1, p.2-50, February 2005 [doi>10.1145/1047915.1047917]
• 23: 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
• 24: Oxley, M. G. 2002. (H.R.3763) Sarbanes-Oxley Act of 2002.
• 25: James S. Plank, A tutorial on Reed-Solomon coding for fault-tolerance in RAID-like systems, Software—Practice & Experience, v.27 n.9, p.995-1012, Sept. 1997 [doi>10.1002/(SICI)1097-024X(199709)27:9<995::AID-SPE111>3.3.CO;2-Y]
• 26: 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
• 27: Michael O. Rabin, Efficient dispersal of information for security, load balancing, and fault tolerance, Journal of the ACM (JACM), v.36 n.2, p.335-348, April 1989 [doi>10.1145/62044.62050]
• 28: 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
• 29: Rivest, R. L. 1998. Chaffing and winnowing: Confidentiality without encryption. CryptoBytes, 4, 1, 12--17.
• 30: Douglas S. Santry , Michael J. Feeley , Norman C. Hutchinson , Alistair C. Veitch , Ross W. Carton , Jacob Ofir, Deciding when to forget in the Elephant file system, Proceedings of the seventeenth ACM symposium on Operating systems principles, p.110-123, December 12-15, 1999, Charleston, South Carolina, United States
• 31: Thomas S. J. Schwarz , Ethan L. Miller, Store, Forget, and Check: Using Algebraic Signatures to Check Remotely Administered Storage, Proceedings of the 26th IEEE International Conference on Distributed Computing Systems, p.12, July 04-07, 2006 [doi>10.1109/ICDCS.2006.80]
• 32: 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]
• 33: Douglas Stinson, Cryptography: Theory and Practice,Second Edition, CRC/C&H, 2002
• 34: Michael Stonebraker , Gerhard A. Schloss, Distributed RAID - A New Multiple Copy Algorithm, Proceedings of the Sixth International Conference on Data Engineering, p.430-437, February 05-09, 1990
• 35: Kevin Greenan , Mark Storer , Ethan L. Miller , Carlos Maltzahn, POTSHARDS: Storing Data for the Long-term Without Encryption, Proceedings of the Third IEEE International Security in Storage Workshop, p.12-20, December 13-13, 2005 [doi>10.1109/SISW.2005.10]
• 36: 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]
• 37: 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
• 38: Arun Subbiah , Douglas M. Blough, An approach for fault tolerant and secure data storage in collaborative work environments, Proceedings of the 2005 ACM workshop on Storage security and survivability, November 11-11, 2005, Fairfax, VA, USA [doi>10.1145/1103780.1103793]
• 39: Carmela Troncoso , Danny De Cock , Bart Preneel, Improving secure long-term archival of digitally signed documents, Proceedings of the 4th ACM international workshop on Storage security and survivability, October 31-31, 2008, Alexandria, Virginia, USA [doi>10.1145/1456469.1456476]
• 40: 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
• 41: XiaoFeng Wang , Zhuowei Li , Jun Xu , Michael K. Reiter , Chongkyung Kil , Jong Youl Choi, Packet vaccine: black-box exploit detection and signature generation, Proceedings of the 13th ACM conference on Computer and communications security, October 30-November 03, 2006, Alexandria, Virginia, USA [doi>10.1145/1180405.1180412]
• 42: Wong, T. M., Wang, C., and Wing, J. M. 2002. Verifiable secret redistribution for threshold sharing schemes. Tech. rep. CMU-CS-02-114-R, Carnegie Mellon University. October.
• 43: Jay J. Wylie , Michael W. Bigrigg , John D. Strunk , Gregory R. Ganger , Han Kiliççöte , Pradeep K. Khosla, Survivable Information Storage Systems, Computer, v.33 n.8, p.61-68, August 2000 [doi>10.1109/2.863969]
• 44: Jun Xu , Peng Ning , Chongkyung Kil , Yan Zhai , Chris Bookholt, Automatic diagnosis and response to memory corruption vulnerabilities, Proceedings of the 12th ACM conference on Computer and communications security, November 07-11, 2005, Alexandria, VA, USA [doi>10.1145/1102120.1102151]
• 45: 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]
• 46: Zheng Zhang , Qiao Lian , Shiding Lin , Wei Chen , Yu Chen , Chao Jin, BitVault: a highly reliable distributed data retention platform, ACM SIGOPS Operating Systems Review, v.41 n.2, p.27-36, April 2007 [doi>10.1145/1243418.1243423]

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.3 File Systems Management
          Subjects: Distributed file systems

General Terms:
Design, Experimentation, Performance, Reliability, Security

Keywords:
Archival storage, approximate pointers, secret splitting