Security under key-dependent inputs

ABSTRACT

In this work we re-visit the question of building cryptographic primitives that remain secure even when queried on inputs that depend on the secret key. This was investigated by Black, Rogaway, and Shrimpton in the context of randomized encryption schemes and in the random oracle model. We extend the investigation to deterministic symmetric schemes (such as PRFs and block ciphers) and to the standard model. We term this notion "security against key-dependent-input attack", or KDI-security for short. Our motivation for studying KDI security is the existence of significant real-world implementations of deterministic encryption (in the context of storage encryption) that actually rely on their building blocks to be KDI secure.

We consider many natural constructions for PRFs, ciphers, tweakable ciphers and randomized encryption, and examine them with respect to their KDI security. We exhibit inherent limitations of this notion and show many natural constructions that fail to be KDI secure in the standard model, including some schemes that have been proven in the random oracle model. On the positive side, we demonstrate examples where some measure of KDI security can be provably achieved (in particular, we show such examples in the standard model).

REFERENCES

• 1: P. Adão, G. Bana, J. Herzog, and A. Scedrov. Soundness of Formal Encryption in the Presence of Key-Cycles. In 10th European Symposium on Research in Computer Security - ESORICS 2005, volume 3679 of Lecture Notes in Computer Science, pages 374--396. Springer, 2005.
• 2: M. Bellare and T. Kohno. A theoretical treatment of related-key attacks: RKA-PRPs, RKA-PRFs, and applications. In Advances in Cryptology - EUROCRYPT '03, volume 2656 of LNCS, pages 491--506. Springer, 2003.
• 3: M. Bellare, T. Krovetz, and P. Rogaway. Luby-rackoff backwards: Increasing security by making block ciphers non-invertible. In Advances in Cryptology - EUROCRYPT'87, volume 1403 of Lecture Notes in Computer Science, pages 266--280. Springer, 1998.
• 4: John Black , Phillip Rogaway , Thomas Shrimpton, Encryption-Scheme Security in the Presence of Key-Dependent Messages, Revised Papers from the 9th Annual International Workshop on Selected Areas in Cryptography, p.62-75, August 15-16, 2002
• 5: Jan Camenisch , Anna Lysyanskaya, An Efficient System for Non-transferable Anonymous Credentials with Optional Anonymity Revocation, Proceedings of the International Conference on the Theory and Application of Cryptographic Techniques: Advances in Cryptology, p.93-118, May 06-10, 2001
• 6: Yevgeniy Dodis , Amit Sahai , Adam Smith, On Perfect and Adaptive Security in Exposure-Resilient Cryptography, Proceedings of the International Conference on the Theory and Application of Cryptographic Techniques: Advances in Cryptology, p.301-324, May 06-10, 2001
• 7: Oded Goldreich , Shafi Goldwasser , Silvio Micali, How to construct random functions, Journal of the ACM (JACM), v.33 n.4, p.792-807, Oct. 1986 [doi>10.1145/6490.6503]
• 8: S. Goldwasser and S. Micali. Probabilistic encryption. Journal of Computer and System Sciences, 28(2):270--299, April 1984.
• 9: Shai Halevi , Hugo Krawczyk, Security under key-dependent inputs, Proceedings of the 14th ACM conference on Computer and communications security, October 28-31, 2007, Alexandria, Virginia, USA [doi>10.1145/1315245.1315303]
• 10: Chris Hall , David Wagner , John Kelsey , Bruce Schneier, Building PRFs from PRPs, Proceedings of the 18th Annual International Cryptology Conference on Advances in Cryptology, p.370-389, August 23-27, 1998
• 11: Johan HÅstad , Russell Impagliazzo , Leonid A. Levin , Michael Luby, A Pseudorandom Generator from any One-way Function, SIAM Journal on Computing, v.28 n.4, p.1364-1396, Aug. 1999 [doi>10.1137/S0097539793244708]
• 12: IEEE P1619.* email archive. http://grouper.ieee.org/groups/1619/email/.
• 13: IEEE P1619. Standard for cryptographic protection of data on block-oriented storage devices. Draft standard, available temporarily from http://ieee-p1619.wetpaint.com/page/IEEE+Project+1619+Home, 2007.
• 14: Jonathan Katz , Moti Yung, Characterization of Security Notions for Probabilistic Private-Key Encryption, Journal of Cryptology, v.19 n.1, p.67-95, January 2006 [doi>10.1007/s00145-005-0310-8]
• 15: P. Laud and R. Corin. Sound Computational Interpretation of Formal Encryption with Composed Keys. In 6th International Conference on Information Security and Cryptology - ICISC 2003, volume 2971 of Lecture Notes in Computer Science, pages 55--66. Springer, 2003.
• 16: 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
• 17: 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]
• 18: S. Lucks. The sum of PRPs is a secure PRF. In Advances in Cryptology - EUROCRYPT '00, volume 1807, pages 470--484. Springer, 2000.
• 19: Noam Nisan , David Zuckerman, Randomness is linear in space, Journal of Computer and System Sciences, v.52 n.1, p.43-52, Feb. 1996 [doi>10.1006/jcss.1996.0004]
• 20: P. Rogaway. Efficient instantiations of tweakable blockciphers and refinements to modes OCB and PMAC. In Advances in Cryptology - ASIACRYPT '04, volume 3329 of Lecture Notes in Computer Science, pages 16--31. Springer, 2004.
• 21: L. Trevisan , S. Vadhan, Extracting randomness from samplable distributions, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.32, November 12-14, 2000

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.6 Security and Protection

General Terms:
Security

Keywords:
circular encryption, key-dependent input, self encryption