Does Encryption with Redundancy Provide Authenticity?
- 1.7k Downloads
A popular paradigm for achieving privacy plus authenticity is to append some “redundancy” to the data before encrypting. We investigate the security of this paradigm at both a general and a specific level. We consider various possible notions of privacy for the base encryption scheme, and for each such notion we provide a condition on the redundancy function that is necessary and sufficient to ensure authenticity of the encryption-with-redundancy scheme. We then consider the case where the base encryption scheme is a variant of CBC called NCBC, and find sufficient conditions on the redundancy functions for NCBC encryption-with-redundancy to provide authenticity. Our results highlight an important distinction between public redundancy functions, meaning those that the adversary can compute, and secret ones, meaning those that depend on the shared key between the legitimate parties.
- 1.J. An AND M. Bellare, “Does encryption with redundancy provide authenticity?” Full version of this paper, available via http://www-cse.ucsd.edu/users/mihir.
- 2.M. Atici AND D. Stinson, “Universal Hashing and Multiple Authentication,” Advances in Cryptology-CRYPTO '96, Lecture Notes in Computer Science Vol. 1109, N. Koblitz ed., Springer-Verlag, 1996.Google Scholar
- 3.M. Bellare, R. Canetti AND H. Krawczyk, “Keying hash functions for message authentication,” Advances in Cryptology — CRYPTO '96, Lecture Notes in Computer Science Vol. 1109, N. Koblitz ed., Springer-Verlag, 1996.Google Scholar
- 4.M. Bellare, A. Desai, E. Jokipii and P. Rogaway, “A concrete security treatment of symmetric encryption: Analysis of the DES modes of operation,” Proc. of the 38th IEEE FOCS, IEEE, 1997.Google Scholar
- 5.M. Bellare, A. Desai, D. Pointcheval AND P. Rogaway, “Relations among notions of security for public-key encryption schemes,” Advances in Cryptology — CRYPTO '98, Lecture Notes in Computer Science Vol. 1462, H. Krawczyk ed., Springer-Verlag, 1998.Google Scholar
- 7.M. Bellare AND C. Namprempre, “Authenticated Encryption: Relations among notions and analysis of the generic composition paradigm,” Advances in Cryptology — ASIACRYPT '00, Lecture Notes in Computer Science Vol. 1976, T. Okamoto ed., Springer-Verlag, 2000.Google Scholar
- 8.M. Bellare AND P. Rogaway, “Encode-then-encipher encryption: How to exploit nonces or redundancy in plaintexts for efficient cryptography,” Advances in Cryptology — ASIACRYPT '00, Lecture Notes in Computer Science Vol. 1976, T. Okamoto ed., Springer-Verlag, 2000.Google Scholar
- 9.M. Bellare AND A. Sahai, “Non-Malleable Encryption: Equivalence between Two Notions, and an Indistinguishability-Based Characterization,” Advances in Cryptology — CRYPTO '99, Lecture Notes in Computer Science Vol. 1666, M. Wiener ed., Springer-Verlag, 1999.Google Scholar
- 12.D. Dolev, C. Dwork AND M. Naor, “Non-malleable cryptography,” Proc. of the 23rd ACM STOC, ACM, 1991.Google Scholar
- 14.S. Halevi AND H. Krawczyk, “MMH: Software Message Authentication in the Gbit/Second Rates,” Fast Software Encryption — 4th International Workshop, FSE'97 Proceedings, Lecture Notes in Computer Science, vol. 1267, E. Biham ed., Springer, 1997.Google Scholar
- 15.R. Jueneman, “A high speed manipulation detection code,” Advances in Cryptology — CRYPTO '86, Lecture Notes in Computer Science Vol. 263, A. Odlyzko ed., Springer-Verlag, 1986.Google Scholar
- 16.R. Jueneman, C. Meyer AND S. Matyas, “Message Authentication with Manipulation Detection Codes,” in Proceedings of the 1983 IEEE Symposium on Security and Privacy, IEEE Computer Society Press, 1984, pp.33–54.Google Scholar
- 17.C. Jutla, “Encryption modes with almost free message integrity,” Report 2000/039, Cryptology ePrint Archive, http://eprint.iacr.org/, August 2000.
- 18.J. Katz AND M. Yung, “Complete characterization of security notions for probabilistic private-key encryption,” Proc. of the 32nd ACM STOC, ACM, 2000.Google Scholar
- 19.J. Katz AND M. Yung, “Unforgeable Encryption and Adaptively Secure Modes of Operation,” Fast Software Encryption '00, Lecture Notes in Computer Science, B. Schneier ed., Springer-Verlag, 2000.Google Scholar
- 20.H. Krawczyk, “LFSR-based Hashing and Authentication,” Advances in Cryptology — CRYPTO '94, Lecture Notes in Computer Science Vol. 839, Y. Desmedt ed., Springer-Verlag, 1994.Google Scholar
- 21.H. Krawczyk, “The order of encryption and authentication for protecting communications (Or: how secure is SSL?),” Manuscript, 2001.Google Scholar
- 23.A. Menezes, P. VAN Oorshot AND S. Vanstone, “Handbook of applied cryptography,” CRC Press LLC, 1997.Google Scholar
- 24.B. Preneel, “Cryptographic Primitives for Information Authentication — State of the Art,” State of the Art in Applied Cryptography, COSIC'97, LNCS 1528, B. Preneel and V. Rijmen eds., Springer-Verlag, pp. 49–104, 1998.Google Scholar
- 26.P. Rogaway, “OCB mode: Parallelizable authenticated encryption,” Presented in NIST’s workshop on modes ofop erations, October, 2000. See http://csrc.nist.gov/encryption/modes/workshop1/