×

Almost universal forgery attacks on AES-based MAC’s. (English) Zbl 1359.94589

Summary: A message authentication code (MAC) computes for each (arbitrarily long) message \(m\) and key \(k\) a short authentication tag which is hard to forge when \(k\) is unknown. One of the most popular ways to process \(m\) in such a scheme is to use some variant of AES in CBC mode, and to derive the tag from the final ciphertext block. In this paper, we analyze the security of several proposals of this type, and show that they are vulnerable to a new type of attack which we call almost universal forgery, in which it is easy to generate the correct tag of any given message if the attacker is allowed to change a single block in it.

MSC:

94A60 Cryptography
68P25 Data encryption (aspects in computer science)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bahrak B., Reza Aref M.: A novel impossible differential cryptanalysis of AES. In: Proceedings of the Western European Workshop on Research in Cryptology 2007, Bochum, Germany (2007).
[2] Biham E., Keller N.: Cryptanalysis of reduced variants of Rijndael. Unpublished manuscript (1999).
[3] Bogdanov A., Mendel F., Regazzoni F., Rijmen V., Tischhauser E.: ALE: AES-based lightweight authenticated encryption. Presented at Fast Software Encryption. To appear in Lecture Notes in Computer Science. Springer, Berlin (2013). · Zbl 1321.94042
[4] Bouillaguet C., Dunkelman O., Leurent G., Fouque P.-A.: Another look at complementation properties. In: Proceedings of Fast Software Encryption 2010. Lecture Notes in Computer Science, vol. 6147. Springer, Berlin, pp. 347-364 (2010). · Zbl 1279.94055
[5] Bouillaguet C., Derbez P., Fouque P.-A.: Automatic search of attacks on round-reduced AES and applications, advances in cryptography. In: Proceedings of CRYPTO 2011. Lecture Notes in Computer Science, vol. 6841. Springer, Berlin, pp. 169-187 (2011). · Zbl 1287.94056
[6] Coppersmith D., Knudsen L.R., Mitchell C.J.: Key recovery and forgery attacks on the MacDES MAC algorithm, advances in cryptography. In: Proceedings of CRYPTO 2000. Lecture Notes in Computer Science, vol. 1880. Springer, Berlin, pp. 184-196 (2000). · Zbl 0995.94546
[7] Daemen J.: Limitations of the even-mansour construction In: Proceedings of Asiacrypt 1991. Lecture Notes in Computer Science, vol. 739. Springer, Berlin, pp. 495-498 (1991). · Zbl 0825.94187
[8] Daemen J., Rijmen V.: The Design of Rijndael: AES-the Advanced Encryption Standard. Springer, Berlin (2002). · Zbl 1065.94005
[9] Daemen J., Rijmen V.: A new MAC construction ALRED and a specific instance, ALPHA-MAC. In: Proceedings of Fast Software Encryption 2005. Lecture Notes in Computer Science, vol. 3557. Springer, Berlin, pp. 1-17 (2005). · Zbl 1140.68385
[10] Daemen J., Rijmen V.: The Pelican MAC Function, IACR ePrint report (2005/088). · Zbl 1140.68385
[11] Daemen J., Rijmen V.: Refinements of the ALRED construction and MAC security claims. IET Inf. Secur. 4(3), 149-157 (2010).
[12] Dodis Y., Steinberger J.P.: Domain extension for MACs beyond the birthday barrier, advances in cryptography. In: Proceedings of EUROCRYPT 2012. Lecture Notes in Computer Science, vol. 7237. Springer, Berlin, pp. 323-342 (2012). · Zbl 1281.94022
[13] Dunkelman O., Keller N., Shamir A.: ALRED Blues: New Attacks on AES-Based MAC’s. IACR ePrint report (2011/095).
[14] Even S., Mansour Y.: A construction of a pseudorandom cipher from single pseudorandom permutation. J. Cryptol. 10(3), 151-162 (1997). · Zbl 1053.94552
[15] Guo J., Matusiewicz K., Knudsen L.R., Ling S., Wang H.: Practical pseudo-collisions for hash functions ARIRANG-224/384. In: Proceedings of Selected Areas in Crytpology 2009. Lecture Notes in Computer Science, vol. 5867. Springer, Berlin, pp. 141-156 (2009). · Zbl 1267.94063
[16] Guo J., Nikolić I., Peyrin T., Wang L.: Cryptanalysis of Zorro. IACR ePrint report (2013/713).
[17] Indesteege S., Mendel F., Preneel B., Schläffer M.: Practical collisions for SHAMATA-256. In: Proceedings of Selected Areas in Crytpology 2009. Lecture Notes in Computer Science, vol. 5867. Springer, Berlin, pp. 1-15 (2009). · Zbl 1267.94066
[18] Knuth D.: The Art of Computer Programming, 2nd edn, vol. 2, p. 7. Addison-Wesley, Reading (1981). · Zbl 0477.65002
[19] Landecker W., Shrimpton T., Seth Terashima R.: Tweakable blockciphers with beyond birthday-bound security, advances in cryptology. In: Proceedings of CRYPTO 2012. Lecture Notes in Computer Science, vol. 7417. Springer, Berlin, pp. 14-30 (2012). · Zbl 1294.94058
[20] Lu J., Dunkelman O., Keller N., Kim J.: New impossible differential attacks on AES. In: Proceedings of INDOCRYPT 2008. Lecture Notes in Computer Science, vol. 5365. Springer, Berlin, pp. 279-293 (2008). · Zbl 1203.94113
[21] Mala H., Dakhilalian M., Rijmen V., Modarres-Hashemi M.: Improved impossible differential cryptanalysis of 7-round AES-128. In: Proceedings of Indocrypt 2010. Lecture Notes in Computer Science, vol. 6498. Springer, Berlin, pp. 282-291 (2010). · Zbl 1253.94060
[22] Minematsu K., Tsunoo Y.: Provably secure MACs from differentially-uniform permutations and AES-based implementations. In: Proceedings of Fast Software Encryption 2006. Lecture Notes in Computer Science, vol. 4047. Springer, Berlin, pp. 226-241 (2006). · Zbl 1234.94058
[23] Peyrin T.: Chosen-salt, chosen-counter, pseudo-collision on SHAvite-3 compression function, SHA-3 mailing list, January (2009).
[24] Peyrin T., Sasaki Y., Wang L.: Generic related-key attacks for HMAC, advances in cryptology. In: Proceedings of ASIACRYPT 2012. Lecture Notes in Computer Science, vol. 7658. Springer, Berlin, pp. 580-597 (2012). · Zbl 1292.94128
[25] Sasaki Y.: Cryptanalyses on a merkle-damgrd based MAC—almost universal forgery and distinguishing-H attacks, advances in cryptography. In: Proceedings of EUROCRYPT 2012. Lecture Notes in Computer Science, vol. 7237. Springer, Berlin, pp. 411-427 (2012). · Zbl 1297.94099
[26] Simplício M.A., Jr., Barbuda P.F.F.S., Barreto P.S.L.M., Carvalho T.C.M.B., Margi C.B.: The MARVIN message authentication code and the LETTERSOUP authenticated encryption scheme. Secur. Commun. Netw. 2(2), 165-180 (2009).
[27] Simplício M.A., Jr., Barreto P.S.L.M., Carvalho T.C.M.B.: Revisiting the security of the alred design. In: Proceedings of Information Security Conference (ISC) 2010. Lecture Notes in Computer Science, vol. 6531. Springer, Berlin, pp. 69-83 (2011).
[28] Van Le T., Sparr R., Wernsdorf R., Desmedt Y.: Complementation-like and cyclic properties of AES round functions. In: Proceedings of 4-th AES conference. Lecture Notes in Computer Science, vol. 3373. Springer, Berlin, pp. 128-141 (2004). · Zbl 1117.94325
[29] Yasuda K.: A new variant of PMAC: beyond the birthday Bound, advances in cryptology. In: Proceedings of CRYPTO 2011. Lecture Notes in Computer Science, vol. 6841. Springer, Berlin, pp. 596-609 (2011). · Zbl 1290.94139
[30] Yuan Z., Wang W., Jia K., Xu G., Wang X.: New birthday attacks on some MACs based on block ciphers, advances in cryptology. In: Proceedings of CRYPTO 2009. Lecture Notes in Computer Science, vol. 5677. Springer, Berlin, pp. 209-230 (2009). · Zbl 1252.94102
[31] Zhang L., Wu W., Sui H., Wang P.: 3kf9: enhancing 3GPP-MAC beyond the birthday bound, advances in cryptology. In: Proceedings of ASIACRYPT 2012. Lecture Notes in Computer Science, vol. 7658. Springer, Berlin, pp. 296-312 (2012). · Zbl 1292.94162
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.