Efficient integrity checking of untrusted network storage

ABSTRACT

Outsourced storage has become more and more practical in recent years. Users can now store large amounts of data in multiple servers at a relatively low price. An important issue for outsourced storage systems is to design an efficient scheme to assure users that their data stored at remote servers has not been tampered with. This paper presents a general method and a practical prototype application for verifying the integrity of files in an untrusted network storage service. The verification process is managed by an application running in a trusted environment (typically on the client) that stores just one cryptographic hash value of constant size, corresponding to the "digest" of an authenticated data structure. The proposed integrity verification service can work with any storage service since it is transparent to the storage technology used. Experimental results show that our integrity verification method is efficient and practical for network storage systems.

REFERENCES

• 1: Amazon S3 (simple storage service). http://aws.amazon.com/s3.
• 2: JetS3t, an open source java toolkit for Amazon S3. http://jets3t.s3.amazonaws.com/index.html.
• 3: Giuseppe Ateniese , Randal Burns , Reza Curtmola , Joseph Herring , Lea Kissner , Zachary Peterson , Dawn Song, Provable data possession at untrusted stores, Proceedings of the 14th ACM conference on Computer and communications security, October 28-31, 2007, Alexandria, Virginia, USA [doi>10.1145/1315245.1315318]
• 4: Premkumar Devanbu , Michael Gertz , April Kwong , Charles Martel , Glen Nuckolls , Stuart G. Stubblebine, Flexible authentication of XML documents, Journal of Computer Security, v.12 n.6, p.841-864, December 2004
• 5: G. Di Battista and B. Palazzi. Authenticated relational tables and authenticated skip lists. In Proc. IFIP Working Conference on Data and Applications Security, pp. 31--46, 2007.
• 6: Kevin Fu , M. Frans Kaashoek , David Mazières, Fast and secure distributed read-only file system, ACM Transactions on Computer Systems (TOCS), v.20 n.1, p.1-24, February 2002 [doi>10.1145/505452.505453]
• 7: E.-J. Goh, H. Shacham, N. Modadugu, and D. Boneh. SiRiUS: Securing remote untrusted storage. In Proc. Network and Distributed System Security, pp. 131--145, 2003.
• 8: M. T. Goodrich, M. Shin, R. Tamassia, and W. H. Winsborough. Authenticated dictionaries for fresh attribute credentials. In Proc. Trust Management Conference, pp. 332--347, 2003.
• 9: Michael T. Goodrich , Charalampos Papamanthou , Roberto Tamassia , Nikos Triandopoulos, Athos: Efficient Authentication of Outsourced File Systems, Proceedings of the 11th international conference on Information Security, September 15-18, 2008, Taipei, Taiwan [doi>10.1007/978-3-540-85886-7_6]
• 10: M. T. Goodrich, R. Tamassia, and A. Schwerin. Implementation of an authenticated dictionary with skip lists and commutative hashing. In DARPA Information Survivability Conference and Exposition II, pp. 68--82, 2001.
• 11: R. C. Jammalamadaka, R. Gamboni, S. Mehrotra, K. E. Seamons, and N. Venkatasubramanian. gVault: A gmail based cryptographic network file system. In Proc. Working Conference on Data and Applications Security, pp. 161--176, 2007.
• 12: Vishal Kher , Yongdae Kim, Securing distributed storage: challenges, techniques, and systems, Proceedings of the 2005 ACM workshop on Storage security and survivability, November 11-11, 2005, Fairfax, VA, USA [doi>10.1145/1103780.1103783]
• 13: 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
• 14: Feifei Li , Marios Hadjieleftheriou , George Kollios , Leonid Reyzin, Dynamic authenticated index structures for outsourced databases, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142488]
• 15: 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
• 16: Umesh Maheshwari , Radek Vingralek , William Shapiro, How to build a trusted database system on untrusted storage, Proceedings of the 4th conference on Symposium on Operating System Design & Implementation, p.10-10, October 22-25, 2000, San Diego, California
• 17: J. Manger. Response on Jungle Disk Blog. http://blog.jungledisk.com/2006/06/06/ encryption/#comment-26.
• 18: Petros Maniatis , Mary Baker, Enabling the Archival Storage of Signed Documents, Proceedings of the Conference on File and Storage Technologies, p.31-45, January 28-30, 2002
• 19: Ralph C. Merkle, A Certified Digital Signature, Proceedings of the 9th Annual International Cryptology Conference on Advances in Cryptology, p.218-238, August 20-24, 1989
• 20: G. Miklau and D. Suciu. Implementing a tamper-evident database system. In Proc. Asian Computing Science Conference, pp. 28--48, 2005.
• 21: Einar Mykletun , Maithili Narasimha , Gene Tsudik, Authentication and integrity in outsourced databases, ACM Transactions on Storage (TOS), v.2 n.2, p.107-138, May 2006 [doi>10.1145/1149976.1149977]
• 22: M. Narasimha and G. Tsudik. Authentication of Outsourced Databases Using Signature Aggregation and Chaining. In Proc. In. Conf. on Database Systems for Advanced Applications, pp. 420--436, 2006.
• 23: Alina Oprea , Michael K. Reiter, Integrity checking in cryptographic file systems with constant trusted storage, Proceedings of 16th USENIX Security Symposium on USENIX Security Symposium, p.1-16, August 06-10, 2007, Boston, MA
• 24: C. Papamanthou and R. Tamassia. Time and Space Efficient Algorithms for Two-Party Authenticated Data Structures. In Proc. Information and Communications Security, pp. 1--15, 2007.
• 25: William Pugh, Skip lists: a probabilistic alternative to balanced trees, Communications of the ACM, v.33 n.6, p.668-676, June 1990 [doi>10.1145/78973.78977]
• 26: 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]
• 27: H. Shacham and B. Waters. Compact proofs of retrievability. Crypto. ePrint Arch., 08/073, 2008.
• 28: R. Tamassia. Authenticated data structures. In Proc. European Symposium on Algorithms, pp. 2--5, 2003.
• 29: R. Tamassia and N. Triandopoulos. Computational bounds on hierarchical data processing with applications to information security. In Proc. Int. Colloquium on Automata, Languages and Programming, pp. 153--165, 2005.
• 30: Aydan R. Yumerefendi , Jeffrey S. Chase, Strong accountability for network storage, Proceedings of the 5th USENIX conference on File and Storage Technologies, p.6-6, February 13-16, 2007, San Jose, CA

INDEX TERMS

Primary Classification:
  E. Data
  E.2 DATA STORAGE REPRESENTATIONS

General Terms:
Algorithms, Experimentation, Security, Verification

Keywords:
authenticated data structures, data integrity, security, untrusted outsourced storage