Advertisement

The Security of Cipher Block Chaining

  • Mihir Bellare
  • Joe Kilian
  • Phillip Rogaway
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 839)

Abstract

The Cipher Block Chaining — Message Authentication Code (CBC MAC) specifies that a message x = x 1 . . . x m be authenticated among parties who share a secret key a by tagging x with a prefix of
$$ f_a^{(m)} (x)\mathop = \limits^{def} f_a (f_a ( \ldots f_a (f_a (x_1 ) \oplus x_2 ) \oplus \ldots \oplus x_{m - 1} ) \oplus x_m ) $$
where f is some underlying block cipher (eg. f = DES). This method is a pervasively used international and U.S. standard. We provide its first formal justification, showing the following general lemma: that cipher block chaining a pseudorandom function gives a pseudorandom function. Underlying our results is a technical lemma of independent interest, bounding the success probability of a computationally unbounded adversary in distinguishing between a random ml-bit to l-bit function and the CBC MAC of a random l-bit to l-bit function.

Keywords

Query Sequence Block Cipher Function Family Message Authentication Code Pseudorandom Function 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

References

  1. 1.
    ANSI X9.9, “American National Standard for Financial Institution Message Authentication (Wholesale),” American Bankers Association, 1981. Revised 1986.Google Scholar
  2. 2.
    M. Bellare, R. Guérin and P. Rogaway, “Fully parallelizable message authentication,” Manuscript, April 1994.Google Scholar
  3. 3.
    M. Bellare and P. Rogaway, “Entity authentication and key distribution,” Advances in Cryptology — Crypto 93 Proceedings, Lecture Notes in Computer Science Vol. 773, Springer-Verlag, D. Stinson, ed., 1994.CrossRefGoogle Scholar
  4. 4.
    M. Bellare and P. Rogaway, “Optimal asymmetric encryption,” Advances in Cryptology — Eurocrypt 94 Proceedings, 1994.Google Scholar
  5. 5.
    R. Bird, I. Gopal, A. Herzberg, P. Janson, S. Kutten, R. Molva and M. Yung, “Systematic design of two-party authentication protocols,” Advances in Cryptology — Crypto 91 Proceedings, Lecture Notes in Computer Science Vol. 576, Springer-Verlag, J. Feigenbaum, ed., 1991.Google Scholar
  6. 6.
    S. Even, O. Goldreich and S. Micali, “On-line/Off line digital signatures,” Manuscript, March 1994. Preliminary version in Crypto 89.Google Scholar
  7. 7.
    U. Feige and M. Naor, Private communication, April 1994.Google Scholar
  8. 8.
    O. Goldreich and L. Levin, “A hard predicate for all one-way functions,” Proceedings of the Twenty First Annual Symposium on the Theory of Computing, ACM, 1989.Google Scholar
  9. 9.
    O. Goldreich, S. Goldwasser and S. Micali, “How to construct random functions,” Journal of the ACM, Vol. 33, No. 4, 210–217, (1986).CrossRefMathSciNetGoogle Scholar
  10. 10.
    O. Goldreich, S. Goldwasser and S. Micali, “On the cryptographic applications of random functions,” Advances in Cryptology — Crypto 84 Proceedings, Lecture Notes in Computer Science Vol. 196, Springer-Verlag, B. Blakley, ed., 1985.Google Scholar
  11. 11.
    S. Goldwasser, S. Micali and R. Rivest, “A digital signature scheme secure against adaptive chosen-message attacks,” SIAM Journal of Computing, 17(2):281–308, April 1988.zbMATHCrossRefMathSciNetGoogle Scholar
  12. 12.
    R. Impagliazzo, L. Levin and M. Luby, “Pseudo-random generation from one-way functions,” Proceedings of the Twenty First Annual Symposium on the Theory of Computing, ACM, 1989.Google Scholar
  13. 13.
    ISO/IEC 9797, “Data cryptographic techniques — Data integrity mechanism using a cryptographic check function employing a block cipher algorithm,” 1989.Google Scholar
  14. 14.
    T. Leighton and S. Micali, “Provably fast and secure digital signature algorithms based on secure hash functions,” Manuscript, March 1993.Google Scholar
  15. 15.
    M. Luby and C. Rackoff, “How to construct pseudorandom permutations from pseudorandom functions,” SIAM J. Computation, Vol. 17, No. 2, April 1988.Google Scholar
  16. 16.
    M. Luby and C. Rackoff, “A study of password security,” Advances in Cryptology — Crypto 87 Proceedings, Lecture Notes in Computer Science Vol. 293, Springer-Verlag, C. Pomerance, ed., 1987.Google Scholar
  17. 17.
    K. Ohta and M. Matsui, “Differential attack on message authentication codes,” Advances in Cryptology — Crypto 93 Proceedings, Lecture Notes in Computer Science Vol. 773, Springer-Verlag, D. Stinson, ed., 1994.CrossRefGoogle Scholar
  18. 18.
    R. Rivest, “The MD5 message-digest algorithm,” IETF Network Working Group, RFC 1321, April 1992.Google Scholar
  19. 19.
    C. Schnorr, “Efficient identification and signatures for smart cards,” Advances in Cryptology — Crypto 89 Proceedings, Lecture Notes in Computer Science Vol. 435, Springer-Verlag, G. Brassard, ed., 1989.Google Scholar
  20. 20.
    S. Stubblebine and V. Gligor, “On message integrity in cryptographic protocols,” Proceedings of the 1992 IEEE Computer Society Symposium on Research in Security and Privacy. May 1992.Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 1994

Authors and Affiliations

  • Mihir Bellare
    • 1
  • Joe Kilian
    • 2
  • Phillip Rogaway
    • 3
  1. 1.Advanced Networking LaboratoryIBM T.J. Watson Research CenterYorktown HeightsUSA
  2. 2.NEC Research InstitutePrincetonUSA
  3. 3.Department of Computer ScienceUniversity of California at DavisDavisUSA

Personalised recommendations