Building secure file systems out of byzantine storage

ABSTRACT

This paper shows how to implement a trusted network file system on an untrusted server. While cryptographic storage techniques exist that allow users to keep data secret from untrusted servers, this work concentrates on the detection of tampering attacks and stale data. Ideally, users of an untrusted storage server would immediately and unconditionally notice any misbehavior on the part of the server. This ideal is unfortunately not achievable. However, we define a notion of data integrity called fork consistency in which, if the server delays just one user from seeing even a single change by another, the two users will never again see one another's changes---a failure easily detectable with on-line communication. We give a practical protocol for a multi-user network file system called SUNDR, and prove that SUNDR offers fork consistency whether or not the server obeys the protocol.

REFERENCES

• 1: Thomas E. Anderson , Michael D. Dahlin , Jeanna M. Neefe , David A. Patterson , Drew S. Roselli , Randolph Y. Wang, Serverless network file systems, ACM Transactions on Computer Systems (TOCS), v.14 n.1, p.41-79, Feb. 1996 [doi>10.1145/225535.225537]
• 2: David Bindel, Yan Chen, Patrick Eaton, Dennis Geels, Ramakrishna Gummadi, Sean Rhea, Hakim Weatherspoon, Westley Weimer, Westley Weimer, Christopher Wells, Ben Zhao, and John Kubiatowicz. Oceanstore: An exteremely wide-area storage system. In Proceedings of the 9th International Conference on Architectural Support for Programming Languages and Operating Systems, pages 190-201, 2000.
• 3: Matt Blaze, A cryptographic file system for UNIX, Proceedings of the 1st ACM conference on Computer and communications security, p.9-16, November 03-05, 1993, Fairfax, Virginia, United States [doi>10.1145/168588.168590]
• 4: William J. Bolosky , John R. Douceur , David Ely , Marvin Theimer, Feasibility of a serverless distributed file system deployed on an existing set of desktop PCs, Proceedings of the 2000 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.34-43, June 18-21, 2000, Santa Clara, California, United States
• 5: Miguel Castro , Barbara Liskov, Practical Byzantine fault tolerance, Proceedings of the third symposium on Operating systems design and implementation, p.173-186, February 1999, New Orleans, Louisiana, United States
• 6: Frank Dabek , M. Frans Kaashoek , David Karger , Robert Morris , Ion Stoica, Wide-area cooperative storage with CFS, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 7: Dan Duchamp. A toolkit approach to partially disconnected operation. In Proceedings of the 1997 USENIX, pages 305-318. USENIX, January 1997.
• 8: Kevin Fu. Group sharing and random access in cryptographic storage file systems. Master's thesis, Massachusetts Institute of Technology, May 1999.
• 9: Kevin Fu, M. Frans Kaashoek, and David Mazières. Fast and secure distributed read-only file system. In Proceedings of the 4th Symposium on Operating Systems Design and Implementation, 2000.
• 10: Umesh Maheshwari and Radek Vingralek. How to build a trusted database system on untrusted storage. In Proceedings of the 4th Symposium on Operating Systems Design and Implementation, San Diego, October 2000.
• 11: David Mazières , Michael Kaminsky , M. Frans Kaashoek , Emmett Witchel, Separating key management from file system security, Proceedings of the seventeenth ACM symposium on Operating systems principles, p.124-139, December 12-15, 1999, Charleston, South Carolina, United States
• 12: David Mazières and Dennis Shasha. Building secure file systems out of byzantine storage. Technical Report TR2002-826, NYU Department of Computer Science, May 2002.
• 13: Ralph C. Merkle, A Digital Signature Based on a Conventional Encryption Function, A Conference on the Theory and Applications of Cryptographic Techniques on Advances in Cryptology, p.369-378, August 16-20, 1987
• 14: Ethan Miller, Darrell Long, William Freeman, and Benjamin Reed. Strong security for distributed file systems. In Proceedings of the 20th IEEE International Performance, Computing, and Communications Conference, pages 34-40, Phoenix, AZ, April 2001.
• 15: David Reed and Liba Svobodova. Swallow: A distributed data storage system for a local network. In A. West and P. Janson, editors, Local Networks for Computer Communications, pages 355-373. North-Holland Publ., Amsterdam, 1981.
• 16: Antony I. T. Rowstron , Peter Druschel, Pastry: Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer Systems, Proceedings of the IFIP/ACM International Conference on Distributed Systems Platforms Heidelberg, p.329-350, November 12-16, 2001
• 17: Christopher A. Stein , John H. Howard , Margo I. Seltzer, Unifying File System Protection, Proceedings of the General Track: 2002 USENIX Annual Technical Conference, p.79-90, June 25-30, 2001
• 18: Ion Stoica , Robert Morris , David Karger , M. Frans Kaashoek , Hari Balakrishnan, Chord: A scalable peer-to-peer lookup service for internet applications, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.149-160, August 2001, San Diego, California, United States