When cryptography meets storage

ABSTRACT

Confidential data storage through encryption is becoming increasingly important. Designers and implementers of encryption methods of storage media must be aware that storage has different usage patterns and properties compared to securing other information media such as networks. In this paper, we empirically demonstrate two-time pad vulnerabilities in storage that are exposed via shifting file contents, in-place file updates, storage mechanisms hidden by layers of abstractions, inconsistencies between memory and disk content, and backups. We also demonstrate how a simple application of Bloom filters can automatically extract plaintexts from two-time pads. Further, our experience sheds light on system research directions to better support cryptographic assumptions and guarantees.

REFERENCES

• 1: Baddeley A.D., Conrad R., Thompson W.E. Letter structure in the English language. Nature, 186, pp. 414--416, 1960.
• 2: P. F. Bennison , P. J. Lasher, Data security issues relating to end of life equipment, Proceedings of the International Symposium on Electronics and the Environment, p.317-320, May 10-13, 2004
• 3: Burton H. Bloom, Space/time trade-offs in hash coding with allowable errors, Communications of the ACM, v.13 n.7, p.422-426, July 1970 [doi>10.1145/362686.362692]
• 4: Nikita Borisov , Ian Goldberg , David Wagner, Intercepting mobile communications: the insecurity of 802.11, Proceedings of the 7th annual international conference on Mobile computing and networking, p.180-189, July 2001, Rome, Italy [doi>10.1145/381677.381695]
• 5: Victor Boyko, On the Security Properties of OAEP as an All-or-Nothing Transform, Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology, p.503-518, August 15-19, 1999
• 6: Li-Pin Chang, On efficient wear leveling for large-scale flash-memory storage systems, Proceedings of the 2007 ACM symposium on Applied computing, March 11-15, 2007, Seoul, Korea [doi>10.1145/1244002.1244248]
• 7: Jim Chow , Ben Pfaff , Tal Garfinkel , Kevin Christopher , Mendel Rosenblum, Understanding data lifetime via whole system simulation, Proceedings of the 13th conference on USENIX Security Symposium, p.22-22, August 09-13, 2004, San Diego, CA
• 8: Jim Chow , Ben Pfaff , Tal Garfinkel , Mendel Rosenblum, Shredding your garbage: reducing data lifetime through secure deallocation, Proceedings of the 14th conference on USENIX Security Symposium, p.22-22, July 31-August 05, 2005, Baltimore, MD
• 9: Dawson E., Nielsen L. Automated cryptanalysis of XOR plaintext strings, Cryptologia, 20(2):165--181,April 1996.
• 10: Debian Source Repository, http://ftp.de.debian.org/debian, 2008.
• 11: Ferguson, N. AES-CBC + Elephant diffuser: A Disk Encryption Algorithm for Windows Vista. Technical Report, August 2006. Available online at http://www.microsoft.com/downloads/details.aspx?FamilyID=131dae03-39ae-48be-a8d6-8b0034c92555&DisplayLang=en.
• 12: H. F. Gaines, Cryptanalysis a Study of Ciphers and Their Solutions, Dover Publications, Incorporated, 1989
• 13: Eran Gal , Sivan Toledo, Mapping Structures for Flash Memories: Techniques and Open Problems, Proceedings of the IEEE International Conference on Software - Science, Technology & Engineering, p.83-92, February 22-23, 2005 [doi>10.1109/SWSTE.2005.14]
• 14: Gregory R. Ganger , Yale N. Patt, Metadata update performance in file systems, Proceedings of the 1st USENIX conference on Operating Systems Design and Implementation, p.5-es, November 14-17, 1994, Monterey, California
• 15: Simson L. Garfinkel , Abhi Shelat, Remembrance of Data Passed: A Study of Disk Sanitization Practices, IEEE Security and Privacy, v.1 n.1, p.17-27, January 2003 [doi>10.1109/MSECP.2003.1176992]
• 16: Tal Garfinkel , Ben Pfaff , Jim Chow , Mendel Rosenblum, Data lifetime is a systems problem, Proceedings of the 11th workshop on ACM SIGOPS European workshop, September 19-22, 2004, Leuven, Belgium [doi>10.1145/1133572.1133599]
• 17: The GNU Privacy Guard, http://gnupg.org, 2008.
• 18: Griffing A. Solving XOR Plaintext Strings with the Viterbi Algorithm. Cryptologia, 30(3), pp. 258--265, 2006.
• 19: Mike Halcrow, eCryptfs: a stacked cryptographic filesystem, Linux Journal, v.2007 n.156, p.2, April 2007
• 20: Hohmann C. CryptoFS. http://reboot.animeirc.de/cryptofs/. August 2007.
• 21: Jones M.N., Mewhort D.J.K. Case-sensitive letter and bigram frequency counts from large-scale English corpora. Behavior Research Methods, Instruments, & Computers, 36, pp. 388--396, 2004.
• 22: Atsuo Kawaguchi , Shingo Nishioka , Hiroshi Motoda, A flash-memory based file system, Proceedings of the USENIX 1995 Technical Conference Proceedings on USENIX 1995 Technical Conference Proceedings, p.13-13, January 16-20, 1995, New Orleans, Louisiana
• 23: L. M. S. C. of the IEEE Computer Society. Wireless LAN medium access control (MAC) and physical layer (PHY) specifications. IEEE Standard 802.11, 1999 Edition, 1999.
• 24: Large Text Compression Benchmark, http://www.cs.fit.edu/~mmahoney/compression/text.html, 2008.
• 25: Moses Liskov , Ronald L. Rivest , David Wagner, Tweakable Block Ciphers, Proceedings of the 22nd Annual International Cryptology Conference on Advances in Cryptology, p.31-46, August 18-22, 2002
• 26: Malita F. LUFS Userland Filesystem - Default branch. http://freshmeat.net/projects/lufs/. October 2003.
• 27: Joshua Mason , Kathryn Watkins , Jason Eisner , Adam Stubblefield, A natural language approach to automated cryptanalysis of two-time pads, Proceedings of the 13th ACM conference on Computer and communications security, October 30-November 03, 2006, Alexandria, Virginia, USA [doi>10.1145/1180405.1180435]
• 28: Mayzner MS, Tresselt ME. Tables of single-letter and digram frequency counts for various word-length and letter-position combinations. Psychonomic Monograph Supplements, 1(2), pp, 13--32, 1965.
• 29: Nettle - A Low-Level Cryptographic Library, http://www.lysator.liu.se/~nisse/nettle/, 2008.
• 30: David A. Patterson , Garth Gibson , Randy H. Katz, A case for redundant arrays of inexpensive disks (RAID), Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.109-116, June 01-03, 1988, Chicago, Illinois, United States
• 31: Zachary Peterson , Randal Burns, Ext3cow: a time-shifting file system for regulatory compliance, ACM Transactions on Storage (TOS), v.1 n.2, p.190-212, May 2005 [doi>10.1145/1063786.1063789]
• 32: Zachary N. J. Peterson , Randal Burns , Joe Herring , Adam Stubblefield , Aviel D. Rubin, Secure deletion for a versioning file system, Proceedings of the 4th conference on USENIX Conference on File and Storage Technologies, p.11-11, December 13-16, 2005, San Francisco, CA
• 33: Richardson, R. 2007. CSI Survey 2007: The 12th Annual Computer Crime and Security Survey. Computer Security Institute. http://www.gocsi.com/forms/csi_survey.jhtml.
• 34: Rivest RL. The RC4 Encryption Algorithm. RSA Data Security, Inc., March 1992.
• 35: Ronald L. Rivest, All-or-Nothing Encryption and the Package Transform, Proceedings of the 4th International Workshop on Fast Software Encryption, p.210-218, January 20-22, 1997
• 36: Mendel Rosenblum , John K. Ousterhout, The design and implementation of a log-structured file system, Proceedings of the thirteenth ACM symposium on Operating systems principles, p.1-15, October 13-16, 1991, Pacific Grove, California, United States
• 37: Douglas J. Santry , Michael J. Feeley , Norman C. Hutchinson , Alistair C. Veitch, Elephant: The File System that Never Forgets, Proceedings of the The Seventh Workshop on Hot Topics in Operating Systems, p.2, March 28-30, 1999
• 38: Seagate Momentus Hard Drive Family, http://www.seagate.com/www/en--us/products/laptops/momentus/, 2008.
• 39: Solso R.L., King J.F. Frequency and versatility of letters in the English language. Behavior Research Methods & Instrumentation, 8, 283--286, 1976.
• 40: Tutte W. FISH and I, A transcript of Tutte's lecture at the University of Waterloo, June 1998.
• 41: Valli C. Throwing out the Enterprise with the Hard Disk, Proceedings of the 2nd Australian Computer, Networks & Information Forensics Conference, 2004.
• 42: Viterbi A.J. Error Bounds for Convolutional Codes and Asymptotically Optimal Decoding Algorithm. IEEE Transactions on Information Theory, 13(2), pp. 260--267, 1967.
• 43: Walker J. Ent - A Pseudorandom Number Sequence Test Program, http://www.fourmilab.ch/random/, 2008.
• 44: Woodhouse D. JFFS: The Journaling Flash File System. Proceedings of the Ottawa Linux Symposium. RedHat Inc., 2001.
• 45: Woodhouse D. JFFS2: The Journalling Flash File System, version 2. http://sourceware.org/jffs2/, 2008.

INDEX TERMS

Primary Classification:
  E. Data
  E.3 DATA ENCRYPTION
      Subjects: Code breaking

Additional Classification:
  E. Data
  E.3 DATA ENCRYPTION
      Subjects: Standards (e.g., DES, PGP, RSA)

  K. Computing Milieux
  K.4 COMPUTERS AND SOCIETY
      K.4.1 Public Policy Issues
          Subjects: Privacy
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.5 Security and Protection (D.4.6, K.4.2)

General Terms:
Security

Keywords:
block ciphers, bloom filters, modes of encryption, storage, two-time pads