Advertisement

Does Encryption with Redundancy Provide Authenticity?

  • Jee Hea An
  • Mihir Bellare
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 2045)

Abstract

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.

References

  1. 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. 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. 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. 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. 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
  6. 6.
    M. Bellare, J. Kilian AND P. Rogaway, “The Security of the Cipher Block Chaining Message Authentication Code,” Journal of Computer and System Sciences, Vol. 61, No. 3, December 2000, pp. 362–399.zbMATHCrossRefMathSciNetGoogle Scholar
  7. 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. 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. 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
  10. 10.
    J. Black, S. Halevi, H. Krawczyk, T. Krovetz AND P. Rogaway, “UMAC: Fast and secure message authentication,” Advances in Cryptology — CRYPTO '99, Lecture Notes in Computer Science Vol. 1666, M. Wiener ed., Springer-Verlag, 1999.CrossRefGoogle Scholar
  11. 11.
    L. Carter AND M. Wegman, “Universal Classes of Hash Functions,” Journal of Computer and System Sciences, Vol. 18, 1979, pp. 143–154.zbMATHCrossRefMathSciNetGoogle Scholar
  12. 12.
    D. Dolev, C. Dwork AND M. Naor, “Non-malleable cryptography,” Proc. of the 23rd ACM STOC, ACM, 1991.Google Scholar
  13. 13.
    S. Goldwasser AND S. Micali, “Probabilistic encryption,” Journal of Computer and System Sciences, Vol. 28, 1984, pp. 270–299.zbMATHCrossRefMathSciNetGoogle Scholar
  14. 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. 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. 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. 17.
    C. Jutla, “Encryption modes with almost free message integrity,” Report 2000/039, Cryptology ePrint Archive, http://eprint.iacr.org/, August 2000.
  18. 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. 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. 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. 21.
    H. Krawczyk, “The order of encryption and authentication for protecting communications (Or: how secure is SSL?),” Manuscript, 2001.Google Scholar
  22. 22.
    M. Luby AND C. Rackoff, “How to Construct Pseudorandom Permutations from Pseudorandom Functions,” SIAM Journal of Computing, Vol. 17, No. 2, pp. 373–386, April 1988.zbMATHCrossRefMathSciNetGoogle Scholar
  23. 23.
    A. Menezes, P. VAN Oorshot AND S. Vanstone, “Handbook of applied cryptography,” CRC Press LLC, 1997.Google Scholar
  24. 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
  25. 25.
    P. Rogaway, “Bucket Hashing and its Application to Fast Message Authentication,” Advances in Cryptology — CRYPTO '95, Lecture Notes in Computer Science Vol. 963, D. Coppersmith ed., Springer-Verlag, 1995.CrossRefGoogle Scholar
  26. 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/
  27. 27.
    M. Wegman AND L. Carter, “New hash functions and their use in authentication and set equality,” Journal of Computer and System Sciences, Vol. 22, 1981, pp. 265–279.zbMATHCrossRefMathSciNetGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2001

Authors and Affiliations

  • Jee Hea An
    • 1
  • Mihir Bellare
    • 1
  1. 1.Dept. of Computer Science & EngineeringUniversity of California at San DiegoLa JollaUSA

Personalised recommendations