Abstract
This paper develops several new techniques of cryptanalyzing MACs based on block ciphers, and is divided into two parts.
The first part presents new distinguishers of the MAC construction Alred and its specific instance Alpha-MAC based on AES. For the Alred construction, we first describe a general distinguishing attack which leads to a forgery attack directly with the complexity of the birthday attack. A 2-round collision differential path of Alpha-MAC is adopted to construct a new distinguisher with about 265.5 chosen messages and 265.5 queries. One of the most important results is to use this new distinguisher to recover the internal state, which is an equivalent subkey of Alpha-MAC. Moreover, our distinguisher on Alred construction can be applied to the MACs based on CBC and CFB encryption modes.
The second part describes the first impossible differential attack on MACs-Pelican, MT-MAC-AES and PC-MAC-AES. Using the birthday attack, enough message pairs that produce the inner near-collision with some specific differences are detected, then the impossible differential attack on 4-round AES to the above mentioned MACs is performed. For Pelican, our attack recovers its internal state, which is an equivalent subkey. For MT-MAC-AES, the attack turns out to be a subkey recovery attack directly. The complexity of the two attacks is 285.5 chosen messages and 285.5 queries. For PC-MAC-AES, we recover its 256-bit key with 285.5 chosen messages and 2128 queries.
Supported by the National Natural Science Foundation of China (NSFC Grant No. 60525201 and No.90604036) and 973 Project (No.2007CB807902).
Chapter PDF
Similar content being viewed by others
Keywords
References
Bahrak, B., Aref, M.R.: Impossible Differential Attack on Seven-Round AES-128. IET Information Security 2(2), 28–32 (2008)
Bellare, M., Canetti, R., Krawczyk, H.: Keying Hash Functions for Message Authentication. In: Koblitz, N. (ed.) CRYPTO 1996. LNCS, vol. 1109, pp. 1–15. Springer, Heidelberg (1996)
Biham, E., Biryukov, A., Shamir, A.: Cryptanalysis of Skipjack Reduced to 31 Rounds Using Impossible Differentials. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 12–23. Springer, Heidelberg (1999)
Biham, E., Keller, N.: Cryptanalysis of Reduced Variants of Rijndael. In: 3rd AES Conference (2000)
Biryukov, A., Bogdanov, A., Khovratovich, D., Kasper, T.: Collision Attacks on AES-Based MAC: Alpha-MAC. In: Paillier, P., Verbauwhede, I. (eds.) CHES 2007. LNCS, vol. 4727, pp. 166–180. Springer, Heidelberg (2007)
Boesgaard, M., Christensen, T., Zenner, E.: Badger - A Fast and Provably Secure MAC. In: Ioannidis, J., Keromytis, A.D., Yung, M. (eds.) ACNS 2005. LNCS, vol. 3531, pp. 176–191. Springer, Heidelberg (2005)
Daemen, J., Rijmen, V.: AES Proposal: Rijndael. In: The First Advanced Encryption Standard Candidate Conference. NIST AES Proposal (1998)
Daemen, J., Rijmen, V.: A New MAC Construction Alred and A Specific Instance Alpha-MAC. In: Gilber, H., Handschuh, H. (eds.) FSE 2005. LNCS, vol. 3557, pp. 1–17. Springer, Heidelberg (2005)
Daemen, J., Rijmen, V.: The PELICAN MAC Function. IACR ePrint Archive (2005), http://eprint.iacr.org/2005/088
Huang, J., Seberry, J., Susilo, W.: On the Internal Structure of Alpha-MAC. In: Nguyen, P.Q. (ed.) VIETCRYPT 2006. LNCS, vol. 4341, pp. 271–285. Springer, Heidelberg (2006)
ISO/IEC 9797-1, Information technology - Security Techniques - Message Authentication Codes (MACs) - Part 1: Mechanisms using A Block Cipher, ISO (1999)
Iwata, T., Kurosawa, K.: OMAC: One-Key CBC MAC. In: Johansson, T. (ed.) FSE 2003. LNCS, vol. 2887, pp. 129–153. Springer, Heidelberg (2003)
Kim, J., Biryukov, A., Preneel, B., Hong, S.: On the Security of HMAC and NMAC Based on HAVAL, MD4, MD5, SHA-0, and SHA-1. In: Prisco, R.D., Yung, M. (eds.) SCN 2006. LNCS, vol. 4116, pp. 242–256. Springer, Heidelberg (2006)
Kurosawa, K., Iwata, T.: TMAC: Two-Key CBC-MAC. In: Joye, M. (ed.) CT-RSA 2003. LNCS, vol. 2612, pp. 33–49. Springer, Heidelberg (2003)
Minematsu, K., Tsunoom, Y.: Provably Secure MACs from Differentially-Uniform Permutations and AES-Based Implementations. In: Robshaw, M.J.B. (ed.) FSE 2006. LNCS, vol. 4047, pp. 226–241. Springer, Heidelberg (2006)
Phan, R.C.-W.: Impossible Differential Cryptanalysis of 7-round Advanced Encryption Standard (AES). Information Processing Letters 91(1), 33–38 (2004)
Preneel, B., van Oorschot, P.: MDx-MAC and Building Fast MACs from Hash Functions. In: Coppersmith, D. (ed.) CRYPTO 1995. LNCS, vol. 963, pp. 1–14. Springer, Heidelberg (1995)
Wang, W., Wang, X., Xu, G.: Impossible Differential Cryptanalysis of Pelican, MT-MAC-AES and PC-MAC-AES, Cryptology ePrint Archive, Report 2009/005 (2009), http://eprint.iacr.org/2009/005
Wang, X., Wang, W., Jia, K., Wang, M.: New Distinguishing Attack on MAC using Secret-Prefix Method. In: FSE 2009 (to appear, 2009)
Wang, X., Yu, H., Wang, W., Zhang, H., Zhan, T.: Cryptanalysis on HMAC/NMAC-MD5 and MD5-MAC. In: Joux, A. (ed.) EUROCRYPT 2009. LNCS, vol. 5479, pp. 121–133. Springer, Heidelberg (2009)
Yuan, Z., Jia, K., Wang, W., Wang, X.: Distinguishing and Forgery Attacks on Alred and Its AES-based Instance Alpha-MAC. Cryptology ePrint Archive, Report 2008/516 (2008), http://eprint.iacr.org/2008/516
Yuval, G.: How to Swindle Rabin. Cryptologia 3, 187–189 (1979)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Yuan, Z., Wang, W., Jia, K., Xu, G., Wang, X. (2009). New Birthday Attacks on Some MACs Based on Block Ciphers. In: Halevi, S. (eds) Advances in Cryptology - CRYPTO 2009. CRYPTO 2009. Lecture Notes in Computer Science, vol 5677. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-03356-8_13
Download citation
DOI: https://doi.org/10.1007/978-3-642-03356-8_13
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-03355-1
Online ISBN: 978-3-642-03356-8
eBook Packages: Computer ScienceComputer Science (R0)