nach oben

Designs, Codes and Cryptography

Erschienen in:

01.09.2015

Almost universal forgery attacks on AES-based MAC’s

verfasst von: Orr Dunkelman, Nathan Keller, Adi Shamir

Erschienen in: Designs, Codes and Cryptography | Ausgabe 3/2015

Einloggen, um Zugang zu erhalten

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

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.

Vorheriger Artikel Bentness and nonlinearity of functions on finite groups

Nächster Artikel An investigation of the tangent splash of a subplane of

In a practical scenario, giving the adversary continued access to the authentication oracle when a challenge message is given would enable her to trivially create the tag by using her oracle access. Any attempt to disallow only the challenge query is therefore artificial.

One can easily extend this definition by allowing other types of small modifications.

Clearly, such attacks do not violate the security claims nor the security proofs made by the designers.

In an earlier version of this paper [13], we have shown how to reduce the time complexity of the attack on the 4-round version of Pelican to \(2^{65}\) time. A few months later, another attack with the same time complexity was also developed independently in [5]. Hence, we do not describe our improved attack on 4-round Pelican in this paper, and refer the reader to [5, 13].

If the length of the tag is \(\ell _w\) bits then a collision in the tag value results from an internal collision with high probability. If the tag is shorter, there can be many false alarms, but the adversary can verify that a collision is internal by appending to the two messages the same block \(m_3\) and checking whether the new tags also collide. For the sake of simplicity, we assume in the sequel that the tag length is \(\ell _w\) bits.

Note that if \(f\) contains an AddRoundKey operation at the beginning, with a whitening key \(k_{0}\), then the adversary should guess an equivalent key \(E_k(0) \oplus k_{0}\) instead of \(E_k(0)\). In this case, the attack makes it possible to retrieve only the value \(E_k(0) \oplus k_{0}\), rather than \(E_k(0)\). However, this value is still sufficient for mounting the almost universal forgery attacks on the MAC described in Sect. 2. For sake of simplicity, we assume in the sequel that \(f\) does not contain a whitening key.

We alert the reader that the introduction of round constants into Pelican is sufficient to thwart the attack presented in this section.

Note that the first blocks in the two structures must differ, since otherwise there will be no collision between the structures as keyless AES is a permutation.

We note that this attack does not violate the security claims of Marvin, as these ensure security only as long as the number of queries is below the birthday bound.

Given less than \(2^{\ell _w/2+1}\) messages, one can still hope for an internal collision. Given \(2^{\ell _w/2+1-t}\) messages, we expect an internal collision with probability \(2^{-2t}\). Once this internal collision occurs, one can apply the suggested attack.

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).

Biham E., Keller N.: Cryptanalysis of reduced variants of Rijndael. Unpublished manuscript (1999).

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).

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).

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).

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).

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).

Daemen J., Rijmen V.: The Design of Rijndael: AES-the Advanced Encryption Standard. Springer, Berlin (2002).

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).

10.

Daemen J., Rijmen V.: The Pelican MAC Function, IACR ePrint report (2005/088).

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).

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).

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).

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).

18.

Knuth D.: The Art of Computer Programming, 2nd edn, vol. 2, p. 7. Addison-Wesley, Reading (1981).

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).

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).

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).

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).

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).

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).

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).

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).

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).

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).

Titel: Almost universal forgery attacks on AES-based MAC’s
verfasst von: Orr Dunkelman
Nathan Keller
Adi Shamir
Publikationsdatum: 01.09.2015
Verlag: Springer US
Erschienen in: Designs, Codes and Cryptography / Ausgabe 3/2015
Print ISSN: 0925-1022
Elektronische ISSN: 1573-7586
DOI: https://doi.org/10.1007/s10623-014-9969-x

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Weitere Artikel der Ausgabe 3/2015

Strongly secure authenticated key exchange from factoring, codes, and lattices

On the automorphisms of designs constructed from finite simple groups

Differential cryptanalysis of PRESENT-like cipher

Practical-time attacks against reduced variants of MISTY1

Diagonally cyclic equitable rectangles

Completely reducible super-simple designs with block size five and index two