Efficient and provably secure ciphers for storage device block level encryption

ABSTRACT

Block ciphers generally have fixed and relatively small input length. Thus they are often used in some mode of operations (e.g., ECB, CBC, CFB, and CTR) that enables the encryption of longer messages. Unfortunately, all these modes of operation reveal some information on their inputs or on relationships between different inputs. As an example, in the CBC mode, encrypting two messages with an identical prefix will result in identical initial blocks in the ciphertexts. Due to the well-known birthday attack and the small input length, the CBC mode becomes less secure as the number of data blocks to be encrypted increases. This leads to a challenging task, namely to design schemes for storage device block or sector level data encryption that are efficient and do not have the disadvantages mentioned above. In this paper, we propose an efficient cipher whose data/cipher blocks can be specified flexibly to match the length of a block unit for current and foreseeable future storage devices. We show that our encryption scheme is provably secure under the assumption that the underlying one-way hash function is a random function.

REFERENCES

• 1: Mihir Bellare , Anand Desai , Eron Jokipii , Phillip Rogaway, A Concrete Security Treatment of Symmetric Encryption, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.394, October 19-22, 1997
• 2: M. Bellare, T. Krovetz, and P. Rogaway. Luby-Rackoff backwards: increasing security by making block ciphers non-invertible. In: Proc. Eurocrypt 98, LNCS 1403. Springer-Verlag 1998.
• 3: Manuel Blum , Silvio Micali, How to generate cryptographically strong sequences of pseudo-random bits, SIAM Journal on Computing, v.13 n.4, p.850-864, Nov. 1984 [doi>10.1137/0213053]
• 4: S. Halevi and P. Rogaway. A tweakable enciphering mode. In: Crypto 03, LNCS 2729, pages 482--499, Springer-Verlag.
• 5: 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
• 6: Michael Luby , Charles Rackoff, How to construct pseudorandom permutations from pseudorandom functions, SIAM Journal on Computing, v.17 n.2, p.373-386, April 1988 [doi>10.1137/0217022]
• 7: U. Maurer. A simplified and generalized treatment of Luby-Rackoff pseudorandom permutation generators. In Proc. Eurocrypt 92, LNCS 658, pages 239--255, Springer-Verlag, 1992.
• 8: Moni Naor , Omer Reingold, On the construction of pseudo-random permutations: Luby-Rackoff revisited (extended abstract), Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.189-199, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258581]
• 9: M. Naor and O. Reingold. A pseudorandom encryption mode. Technical report submitted to IEEE Storage Device Standard Working Group.
• 10: NIST. Secure Hash Standards (SHS), FIPS 180-2. August, 2002.
• 11: A. Yao. Theory and applications of trapdoor functions. Proc. 23rd IEEE FOCS, pages 80--91, 1982.
• 12: Yuliang Zheng , Tsutomu Matsumoto , Hideki Imai, Impossibility and optimally results on constructing pseudorandom permutations (extended abstract), Proceedings of the workshop on the theory and application of cryptographic techniques on Advances in cryptology, p.412-422, November 1990, Houthalen, Belgium

INDEX TERMS

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

General Terms:
Algorithms, Performance, Security, Theory

Keywords:
hash function, storage device encryption, symmetric cipher