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
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.
Chapter PDF
Similar content being viewed by others
Keywords
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
ANSI X9.9, “American National Standard for Financial Institution Message Authentication (Wholesale),” American Bankers Association, 1981. Revised 1986.
M. Bellare, R. Guérin and P. Rogaway, “Fully parallelizable message authentication,” Manuscript, April 1994.
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.
M. Bellare and P. Rogaway, “Optimal asymmetric encryption,” Advances in Cryptology — Eurocrypt 94 Proceedings, 1994.
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.
S. Even, O. Goldreich and S. Micali, “On-line/Off line digital signatures,” Manuscript, March 1994. Preliminary version in Crypto 89.
U. Feige and M. Naor, Private communication, April 1994.
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.
O. Goldreich, S. Goldwasser and S. Micali, “How to construct random functions,” Journal of the ACM, Vol. 33, No. 4, 210–217, (1986).
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.
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.
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.
ISO/IEC 9797, “Data cryptographic techniques — Data integrity mechanism using a cryptographic check function employing a block cipher algorithm,” 1989.
T. Leighton and S. Micali, “Provably fast and secure digital signature algorithms based on secure hash functions,” Manuscript, March 1993.
M. Luby and C. Rackoff, “How to construct pseudorandom permutations from pseudorandom functions,” SIAM J. Computation, Vol. 17, No. 2, April 1988.
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.
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.
R. Rivest, “The MD5 message-digest algorithm,” IETF Network Working Group, RFC 1321, April 1992.
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.
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.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1994 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bellare, M., Kilian, J., Rogaway, P. (1994). The Security of Cipher Block Chaining. In: Desmedt, Y.G. (eds) Advances in Cryptology — CRYPTO ’94. CRYPTO 1994. Lecture Notes in Computer Science, vol 839. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48658-5_32
Download citation
DOI: https://doi.org/10.1007/3-540-48658-5_32
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-58333-2
Online ISBN: 978-3-540-48658-9
eBook Packages: Springer Book Archive