New Attacks on the Concatenation and XOR Hash Combiners

详细信息    查看全文

• 关键词：Hash function ; Cryptanalysis ; Concatenation combiner ; XOR combiner
• 刊名：Lecture Notes in Computer Science
• 出版年：2016
• 出版时间：2016
• 年：2016
• 卷：9665
• 期：1
• 页码：484-508
• 全文大小：538 KB
• 参考文献：1.Andreeva, E., Bouillaguet, C., Dunkelman, O., Fouque, P.-A., Hoch, J., Kelsey, J., Shamir, A., Zimmer, S.: New second-preimage attacks on hash functions. J. Cryptol. 1–40. (to appear) (2015)
  2.Andreeva, E., Bouillaguet, C., Dunkelman, O., Kelsey, J.: Herding, second preimage and trojan message attacks beyond Merkle-Damgård. In: Jacobson Jr., M.J., Rijmen, V., Safavi-Naini, R. (eds.) SAC 2009. LNCS, vol. 5867, pp. 393–414. Springer, Heidelberg (2009)CrossRef
  3.Andreeva, E., Bouillaguet, C., Fouque, P.-A., Hoch, J.J., Kelsey, J., Shamir, A., Zimmer, S.: Second preimage attacks on dithered hash functions. In: Smart, N.P. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 270–288. Springer, Heidelberg (2008)CrossRef
  4.Biham, E., Dunkelman, O.: A framework for iterative hash functions- HAIFA. In: IACR Cryptology ePrint Archive (2007). http://​eprint.​iacr.​org/​2007/​278
  5.Boneh, D., Boyen, X.: On the impossibility of efficiently combining collision resistant hash functions. In: Dwork, C. (ed.) CRYPTO 2006. LNCS, vol. 4117, pp. 570–583. Springer, Heidelberg (2006)CrossRef
  6.Brassard, G. (ed.): CRYPTO 1989. LNCS, vol. 435. Springer, Heidelberg (1990)MATH
  7.Cramer, R. (ed.): EUROCRYPT 2005. LNCS, vol. 3494. Springer, Heidelberg (2005)MATH
  8.Damgård, I.: A design principle for hash functions. In: Brassard [6], pp. 416–427
  9.Dean, R.D.: Formal Aspects of Mobile Code Security. Ph.D. thesis, Princeton University (1999)
  10.Dierks, T., Rescorla, E.: The Transport Layer Security (TLS) Protocol Version 1.2. RFC 5246 (2008). https://​www.​ietf.​org/​rfc/​rfc5246.​txt
  11.Dinur, I., Leurent, G.: Improved generic attacks against hash-based MACs and HAIFA. In: Garay, J.A., Gennaro, R. (eds.) [16], pp. 149–168
  12.Dunkelman, O., Preneel, B.: Generalizing the herding attack to concatenated hashing schemes. In: ECRYPT Hash Workshopp (2007)
  13.Fischlin, M., Lehmann, A.: Multi-property preserving combiners for hash functions. In: Canetti, R. (ed.) TCC 2008. LNCS, vol. 4948, pp. 375–392. Springer, Heidelberg (2008)CrossRef
  14.Fischlin, M., Lehmann, A., Pietrzak, K.: Robust multi-property combiners for hash functions. J. Cryptol. 27(3), 397–428 (2014)MathSciNet CrossRef MATH
  15.Freier, A.O., Karlton, P., Kocher, P.C.: The Secure Sockets Layer (SSL) Protocol Version 3.0.RFC 6101 (2011). http://​www.​ietf.​org/​rfc/​rfc6101.​txt
  16.Garay, J.A., Gennaro, R. (eds.): CRYPTO 2014, Part I. LNCS, vol. 8616. Springer, Heidelberg (2014)MATH
  17.Guo, J., Peyrin, T., Sasaki, Y., Wang, L.: Updates on generic attacks against HMAC and NMAC. In: Garay, J.A., Gennaro, R. (eds.) [16], pp. 131–148
  18.Hellman, M.E.: A cryptanalytic time-memory trade-off. IEEE Trans. Inf. Theory 26(4), 401–406 (1980)MathSciNet CrossRef MATH
  19.Hoch, J.J., Shamir, A.: Breaking the ICE - finding multicollisions in iterated concatenated and expanded (ICE) hash functions. In: Robshaw, M. (ed.) FSE 2006. LNCS, vol. 4047, pp. 179–194. Springer, Heidelberg (2006)CrossRef
  20.Hoch, J.J., Shamir, A.: On the strength of the concatenated hash combiner when all the hash functions are weak. In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds.) Automata, Languages and Programming. LNCS, vol. 5126, pp. 616–630. Springer, Heidelberg (2008)CrossRef
  21.Jha, A., Nandi, M.: Some Cryptanalytic Results on Zipper Hash and Concatenated Hash. IACR Cryptology ePrint Archive 2015:973 (2015)
  22.Joux, A.: Multicollisions in iterated hash functions. Application to cascaded constructions. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 306–316. Springer, Heidelberg (2004)CrossRef
  23.Kelsey, J., Schneier, B.: Second preimages on n-Bit hash functions for much less than \(2^n\) work. In: Cramer [7], pp. 474–490
  24.Leurent, G., Peyrin, T., Wang, L.: New generic attacks against hash-based MACs. In: Sako, K., Sarkar, P. (eds.) ASIACRYPT 2013, Part II. LNCS, vol. 8270, pp. 1–20. Springer, Heidelberg (2013)CrossRef
  25.Leurent, G., Wang, L.: The sum can be weaker than each part. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9056, pp. 345–367. Springer, Heidelberg (2015)
  26.Mendel, F., Rechberger, C., Schläffer, M.: MD5 is weaker than weak: attacks on concatenated combiners. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 144–161. Springer, Heidelberg (2009)CrossRef
  27.Mennink, B., Preneel, B.: Breaking and fixing cryptophia’s short combiner. In: Gritzalis, D., Kiayias, A., Askoxylakis, I. (eds.) CANS 2014. LNCS, vol. 8813, pp. 50–63. Springer, Heidelberg (2014)
  28.Merkle, R.C.: One way hash functions and DES. In: Brassard [6], pp. 428–446
  29.Mittelbach, A.: Hash combiners for second pre-image resistance, target collision resistance and pre-image resistance have long output. In: Visconti, I., De Prisco, R. (eds.) SCN 2012. LNCS, vol. 7485, pp. 522–539. Springer, Heidelberg (2012)CrossRef
  30.Nandi, M., Stinson, D.R.: Multicollision attacks on some generalized sequential hash functions. IEEE Trans. Inf. Theory 53(2), 759–767 (2007)MathSciNet CrossRef MATH
  31.Perrin, L., Khovratovich, D.: Collision spectrum, entropy loss, T-Sponges, and cryptanalysis of GLUON-64. In: Cid, C., Rechberger, C. (eds.) FSE 2014. LNCS, vol. 8540, pp. 82–103. Springer, Heidelberg (2015)
  32.Peyrin, T., Wang, L.: Generic universal forgery attack on iterative hash-based MACs. In: Nguyen, P.Q., Oswald, E. (eds.) EUROCRYPT 2014. LNCS, vol. 8441, pp. 147–164. Springer, Heidelberg (2014)CrossRef
  33.Pietrzak, K.: Non-trivial black-box combiners for collision-resistant hash-functions don’t exist. In: Naor, M. (ed.) EUROCRYPT 2007. LNCS, vol. 4515, pp. 23–33. Springer, Heidelberg (2007)CrossRef
  34.Preneel, B.: Analysis and design of cryptographic hash functions. Ph.D. thesis, KU Leuven (1993)
  35.Rjasko, M.: On existence of robust combiners for cryptographic hash functions. In: Vojtás, P. (ed.) Proceedings of the Conference onTheory and Practice of Information Technologies, ITAT 2009, Horskýhotel Kralova studna, Slovakia, September 25-29, 2009, volume 584 of CEUR Workshop Proceedings, pp. 71–76. CEUR-WS.org 2009
  36.van Oorschot, P.C., Wiener, M.J.: Parallel collision search with cryptanalytic applications. J. Cryptol. 12(1), 1–28 (1999)MathSciNet CrossRef MATH
  37.Wang, X., Yin, Y.L., Yu, H.: Finding collisions in the full SHA-1. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 17–36. Springer, Heidelberg (2005)CrossRef
  38.Wang, X., Yu, H.: How to break MD5 and other hash functions. In: Cramer [7], pp. 19–35
  
• 作者单位：Itai Dinur (15)
  
  15. Department of Computer Science, Ben-Gurion University, Beersheba, Israel
  
• 丛书名：Advances in Cryptology ¨C EUROCRYPT 2016
• ISBN：978-3-662-49890-3
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349
• 卷排序：9665

文摘

We study the security of the concatenation combiner \(H_1(M) \Vert H_2(M)\) for two independent iterated hash functions with n-bit outputs that are built using the Merkle-Damgård construction. In 2004 Joux showed that the concatenation combiner of hash functions with an n-bit internal state does not offer better collision and preimage resistance compared to a single strong n-bit hash function. On the other hand, the problem of devising second preimage attacks faster than \(2^n\) against this combiner has remained open since 2005 when Kelsey and Schneier showed that a single Merkle-Damgård hash function does not offer optimal second preimage resistance for long messages.