On the Security of NMAC and Its Variants

Fanbao Liu, Changxiang Shen, Tao Xie, Dengguo Feng

Abstract


Based on the three earlier MAC (Message Authentication Code) construction approaches, we propose and analyze some variants of NMAC. We propose  some key recovery attacks to  these  NMAC  variants, for  example, we can  recover  the  equivalent  inner  key  of NMAC  in  about O(2n/2) MAC  operations, in  a related key  setting. We  propose  NMAC-E, a  variant of NMAC  with  secret  envelop,  to  achieve  more  process  efficiency  and  no  loss  of security, which needs only one call to the  underlying hash  function, instead of two invocations in HMAC.


Full Text:

PDF

References


Bellare M, Canetti R, Krawczyk H. Pseudorandom functions revisited: the cascade construction and its concrete security. Foundations of Computer Science. Annual IEEE Symposium on 0. 1996; 514.

Bellare M. New Proofs for NMAC and HMAC: Security without Collision-Resistance. In: Dwork C (ed.) Advances in Cryptology - CRYPTO 2006, Lecture Notes in Computer Science, vol. 4117. Heidelberg: Springer Berlin. 2006: 602–619.

Bellare M. Canetti R, Krawczyk H. Keying Hash Functions for Message Authentication. In: Koblitz N (ed.) Advances in Cryptology CRYPTO’ 96, Lecture Notes in Computer Science, vol. 1109. Heidelberg: Springer Berlin. 1996: 1–15.

Contini S, Yin Y. Forgery and Partial Key-Recovery Attacks on HMAC and NMAC Using Hash Collisions. In: Lai X, Chen K (eds.) Advances in Cryptology ASIACRYPT 2006, Lecture Notes in Computer Science, vol. 4284. Heidelberg: Springer Berlin. 2006: 37–53.

Damg˚ard I. A Design Principle for Hash Functions. In: Brassard, G. (ed.) Advances in Cryptology CRYPTO’ 89 Proceedings, Lecture Notes in Computer Science, vol. 435. Heidelberg: Springer Berlin. 1990: 416–427.

Eastlake DE, Jones P. US secure hash algorithm 1 (SHA1). RFC 3174, Internet Engineering Task Force (Sep 2001), http://www.rfc-editor.org/rfc/rfc3174.txt.

Fouque, Pierre-Alain, Leurent, Gatan, Nguyen, Phong. Full key-recovery attacks on hmac/nmac- md4 and nmac-md5. In: Menezes, A. (ed.) Advances in Cryptology - CRYPTO 2007, Lecture Notes in Computer Science, vol. 4622. Heidelberg: Springer Berlin. 2007: 13–30.

Girault M, Cohen R, Campana M. A Generalized Birthday Attack. In: Barstow D, Brauer W, Brinch Hansen P, Gries D, Luckham D, Moler C, Pnueli A, Seegmller G, Stoer J, Wirth N, Gnther C (eds.) Advances in Cryptology EUROCRYPT 88, Lecture Notes in Computer Science, vol. 330. Heidelberg: Springer Berlin. 1988: 129–156.

Hirose S, Park J, Yun A. A simple variant of the merkle-damg˚ard scheme with a permutation. In: Kurosawa K. (ed.) Advances in Cryptology ASIACRYPT 2007, Lecture Notes in Computer Science, vol. 4833. Heidelberg: Springer Berlin. 2007: 113–129.

Leurent G. MD4 is not One-Way. In: Nyberg K (ed.) Fast Software Encryption, Lecture Notes in Computer Science, vol. 5086. Heidelberg: Springer Berlin. 2008: 412–428.

Liu F, Liu Y, Xie T, Feng D, Feng Y. Fast Password Recovery Attack: Application to apop. Journal Intelligent Manufacturing. 2012: 1–11.

Liu F, Xie T, Shen C. Breaking H2-MAC Using Birthday Paradoc. Cryptology eprint Archive, Report 2011/647 (2011), http://eprint.iacr.org/

Menezes AJ, Vanstone SA, Oorschot PCV. Handbook of Applied Cryptography. CRC Press, Inc., Boca Raton, FL, USA, 1st edn. 1996.

Merkle R. One Way Hash Functions and DES. In: Brassard, G. (ed.) Advances in Cryptology CRYPTO 89 Proceedings, Lecture Notes in Computer Science, vol. 435.Heidelberg: Springer Berlin. 1990: 428–446.

Patel S. An efficient mac for short messages. In: Nyberg K., Heys H. (eds.) Selected Areas in Cryptography, Lecture Notes in Computer Science, vol. 2595. Heidelberg: Springer Berlin. 2003: 353–368.

Preneel B, Van Oorschot P. On the security of iterated message authentication codes. IEEE Transactions on Information Theory. 1999; 45(1): 188 – 199.

Preneel B. Cryptographic Primitives for Information Authentication State of the Art. In: State of the Art in Applied Cryptography, Lecture Notes in Computer Science, vol. 1528. Heidelberg: Springer Berlin. 1998: 49–104.

Preneel B, van Oorschot P. On the Security of Two MAC Algorithms. In: Maurer, U. (ed.) Advances in Cryptology EUROCRYPT 96. Lecture Notes in Computer Science, vol. 1070. Heidelberg: Springer Berlin. 1996: 19–32.

Rivest R. The MD5 Message-Digest algorithm. RFC 1321, Internet Engineering Task Force (Apr 1992), http://www.rfc-editor.org/rfc/rfc1321.txt.

Tsudik G. Message authentication with one-way hash functions. SIGCOMM Comput Commun Rev. 1992; 22: 29–38.

Wang L, Ohta K, Kunihiro N. New Key-Recovery Attacks on HMAC/NMAC-MD4 and NMAC-MD5. In: Smart N (ed.) Advances in Cryptology EUROCRYPT 2008, Lecture Notes in Computer Science, vol. 4965. Heidelberg: Springer Berlin. 2008: 237–253.

Wang W. Equivalent Key Recovery Attack on H2-MAC Instantiated with MD5. In: Kim Th, Adeli H, Robles RJ, Balitanas M (eds.) Information Security and Assurance, Communications in Computer and Information Science, vol. 200. Heidelberg: Springer Berlin. 2011: 11–20.

Wang X, Lai X, Feng D, Chen H, Yu X. Cryptanalysis of the Hash Functions MD4 and RIPEMD. In: Cramer R (ed.) Advances in Cryptology EUROCRYPT 2005, Lecture Notes in Computer Science, vol. 3494. Heidelberg: Springer Berlin. 2005: 551–551.

Wang X, Yin Y, Yu H. Finding Collisions in the Full SHA-1. In: Shoup, V. (ed.) Advances in Cryptology CRYPTO 2005, Lecture Notes in Computer Science, vol. 3621. Heidelberg: Springer Berlin. 2005: 17–36.

Wang X, Yu H. How to Break MD5 and Other Hash Functions. In: Cramer, R. (ed.) Advances in Cryptology EUROCRYPT 2005, Lecture Notes in Computer Science, vol. 3494. Heidelberg: Springer Berlin. 2005: 561–561.

Wang X, Yu H, Wang W, Zhang H, Zhan T. Cryptanalysis on HMAC/NMAC-MD5 and MD5-MAC. In: Joux, A. (ed.) Advances in Cryptology - EUROCRYPT 2009, Lecture Notes in Computer Science, vol. 5479. Heidelberg: Springer Berlin. 2009: 121–133.

Xie T, Liu F, Feng D. Could The 1-MSB Input Difference Be The Fastest Collision Attack For MD5? Eurocrypt 2009, Poster Session, Cryptology ePrint Archive, Report 2008/391 (2008), http://eprint.iacr.org/.

Yasuda K. Boosting merkle-damg˚ard hashing for message authentication. In: Kurosawa, K. (ed.) Advances in Cryptology ASIACRYPT 2007, Lecture Notes in Computer Science, vol. 4833. Heidelberg: Springer Berlin. 2007: 216–231.

Yasuda K. Multilane hmac-security beyond the birthday limit. In: Srinathan K, Rangan C, Yung M. (eds.) Progress in Cryptology INDOCRYPT 2007, Lecture Notes in Computer Science, vol. 4859. Heidelberg: Springer Berlin. 2007: 18–32.

Yasuda K. “sandwich” is indeed secure: How to authenticate a message with just one hashing. In: Pieprzyk J, Ghodosi H, Dawson E. (eds.) Information Security and Privacy, Lecture Notes in Computer Science, vol. 4586. Heidelberg: Springer Berlin. 2007: 355–369.

Yasuda, K. HMAC without the “Second” Key. In: Samarati P, Yung M, Martinelli F, Ardagna C (eds.) Information Security, Lecture Notes in Computer Science, vol. 5735. Heidelberg: Springer Berlin. 2009: 443–458.




DOI: http://doi.org/10.12928/telkomnika.v11i2.940

Refbacks

  • There are currently no refbacks.


Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

TELKOMNIKA Telecommunication, Computing, Electronics and Control
ISSN: 1693-6930, e-ISSN: 2302-9293
Universitas Ahmad Dahlan, 4th Campus
Jl. Ringroad Selatan, Kragilan, Tamanan, Banguntapan, Bantul, Yogyakarta, Indonesia 55191
Phone: +62 (274) 563515, 511830, 379418, 371120
Fax: +62 274 564604

View TELKOMNIKA Stats