A Collision Attack on a Double-Block-Length Compression Function Instantiated with Round-Reduced AES-256

详细信息    查看全文

• 作者：Jiageng Chen (15)
  Shoichi Hirose (16)
  Hidenori Kuwakado (17)
  Atsuko Miyaji (15)
  
  15. School of Information Science ; Japan Advanced Institute of Science and Technology ; Nomi ; Japan
  16. Graduate School of Engineering ; University of Fukui ; Fukui ; Japan
  17. Faculty of Informatics ; Kansai University ; Suita ; Japan
  
• 关键词：Double ; block ; length compression function ; Free ; start collision attack ; Rebound attack ; AES ; 256
• 刊名：Lecture Notes in Computer Science
• 出版年：2015
• 出版时间：2015
• 年：2015
• 卷：8949
• 期：1
• 页码：271-285
• 全文大小：373 KB
• 参考文献：1. Armknecht, F, Fleischmann, E, Krause, M, Lee, J, Stam, M, Steinberger, J The preimage security of double-block-length compression functions. In: Lee, DH, Wang, X eds. (2011) Advances in Cryptology 鈥?ASIACRYPT 2011. Springer, Heidelberg, pp. 233-251 CrossRef
  2. Bertoni, G., Daemen, J., Peeters, M., Van Assche, G.: The Keccak sponge function family (2008). http://keccak.noekeon.org
  3. Biryukov, A, Khovratovich, D, Nikoli膰, I Distinguisher and related-key attack on the full AES-256. In: Halevi, S eds. (2009) Advances in Cryptology - CRYPTO 2009. Springer, Heidelberg, pp. 231-249 CrossRef
  4. Black, J, Rogaway, P, Shrimpton, T, Stam, M (2010) An analysis of the blockcipher-based hash functions from PGV. J. Cryptol. 23: pp. 519-545 CrossRef
  5. Bogdanov, A, Leander, G, Paar, C, Poschmann, A, Robshaw, MJB, Seurin, Y Hash functions and RFID tags: mind the gap. In: Oswald, E, Rohatgi, P eds. (2008) Cryptographic Hardware and Embedded Systems 鈥?CHES 2008. Springer, Heidelberg, pp. 283-299 CrossRef
  6. Brachtl, B.O., Coppersmith, D., Hyden, M.M., Matyas Jr., S.M., Meyer, C.H.W., Oseas, J., Pilpel, S., Schilling, M.: Data authentication using modification detection codes based on a public one-way encryption function, March 1990. US Patent # 4,908,861
  Canteaut, A eds. (2012) Fast Software Encryption. Springer, Heidelberg
  7. Daemen, J, Rijmen, V (2002) The Design of Rijndael. Springer, Heidelberg CrossRef
  8. Duc, A., Guo, J., Peyrin, T., Wei, L.: Unaligned rebound attack: application to Keccak. In: Canteaut [7], pp. 402鈥?21
  9. Ferguson, N.: Observations on H-PRESENT-128. CRYPTO 2011 Rump Session (2011). http://www.iacr.org/cryptodb/archive/2011/CRYPTO/video/rump/
  10. FIPS PUB 180鈥?. Secure hash standard (SHS), March 2012
  11. FIPS PUB 197. Advanced encryption standard (AES) (2001)
  12. Fleischmann, E., Gorski, M., Lucks, S.: Security of cyclic double block length hash functions. In: Parker [28], pp. 153鈥?75
  13. Hirose, S Provably secure double-block-length hash functions in a black-box model. In: Park, C, Chee, S eds. (2005) Information Security and Cryptology 鈥?ICISC 2004. Springer, Heidelberg, pp. 330-342 CrossRef
  14. Hirose, S Some plausible constructions of double-block-length hash functions. In: Robshaw, M eds. (2006) Fast Software Encryption. Springer, Heidelberg, pp. 210-225 CrossRef
  15. Jean, J, Naya-Plasencia, M, Peyrin, T Multiple limited-birthday distinguishers and applications. In: Lange, T, Lauter, K, Lison臎k, P eds. (2014) Selected Areas in Cryptography 鈥?SAC 2013. Springer, Heidelberg, pp. 533-550 CrossRef
  16. Khovratovich, D, Nikoli膰, I, Rechberger, C Rotational rebound attacks on reduced skein. In: Abe, M eds. (2010) Advances in Cryptology - ASIACRYPT 2010. Springer, Heidelberg, pp. 1-19 CrossRef
  17. Knudsen, L.R., Gauravaram, P., Matusiewicz, K., Mendel, F., Rechberger, C., Schl盲ffer, M., Thomsen, S.S.: Gr酶stl - a SHA-3 candidate (2008). http://www.groestl.info
  18. Lai, X, Massey, JL A proposal for a new block encryption standard. In: Damg氓rd, IB eds. (1991) Advances in Cryptology - EUROCRYPT 1990. Springer, Heidelberg, pp. 389-404
  19. Lai, X, Massey, JL Hash functions based on block ciphers. In: Rueppel, RA eds. (1993) Advances in Cryptology - EUROCRYPT 1992. Springer, Heidelberg, pp. 55-70
  20. Lamberger, M., Mendel, F., Rechberger, C., Rijmen, V., Schl盲ffer, M.: The rebound attack and subspace distinguishers: application to Whirlpool. Cryptology ePrint Archive, Report 2010/198 (2010). http://eprint.iacr.org/
  21. Lee, J, Kwon, D (2011) The security of Abreast-DM in the ideal cipher model. IEICE Trans. 94鈥揂: pp. 104-109 CrossRef
  22. Lee, J, Stam, M MJH: a faster alternative to MDC-2. In: Kiayias, A eds. (2011) Topics in Cryptology 鈥?CT-RSA 2011. Springer, Heidelberg, pp. 213-236 CrossRef
  23. Lee, J, Stam, M, Steinberger, J The collision security of Tandem-DM in the ideal cipher model. In: Rogaway, P eds. (2011) Advances in Cryptology 鈥?CRYPTO 2011. Springer, Heidelberg, pp. 561-577 CrossRef
  24. Mendel, F, Peyrin, T, Rechberger, C, Schl盲ffer, M Improved cryptanalysis of the reduced Gr酶stl compression function, ECHO permutation and AES block cipher. In: Jacobson, MJ, Rijmen, V, Safavi-Naini, R eds. (2009) Selected Areas in Cryptography. Springer, Heidelberg, pp. 16-35 CrossRef
  25. Mendel, F, Rechberger, C, Schl盲ffer, M, Thomsen, SS The rebound attack: cryptanalysis of reduced Whirlpool and Gr酶stl. In: Dunkelman, O eds. (2009) Fast Software Encryption. Springer, Heidelberg, pp. 260-276 CrossRef
  26. 脰zen, O., Stam, M.: Another glance at double-length hashing. In: Parker [28], pp. 176鈥?01
  Parker, MG eds. (2009) Cryptography and Coding. Springer, Heidelberg
  27. Peyrin, T, Gilbert, H, Muller, F, Robshaw, MJB Combining compression functions and block cipher-based hash functions. In: Lai, X, Chen, K eds. (2006) Advances in Cryptology 鈥?ASIACRYPT 2006. Springer, Heidelberg, pp. 315-331 CrossRef
  28. Preneel, B, Govaerts, R, Vandewalle, J Hash functions based on block ciphers: a synthetic approach. In: Stinson, DR eds. (1994) Advances in Cryptology - CRYPTO 1993. Springer, Heidelberg, pp. 368-378
  29. Rijmen, V., Barreto, P.S.L.M.: The Whirlpool hash function (2000). http://www.larc.usp.br/pbarreto/WhirlpoolPage.html
  30. Rijmen, V, Toz, D, Var谋c谋, K Rebound attack on reduced-round versions of JH. In: Hong, S, Iwata, T eds. (2010) Fast Software Encryption. Springer, Heidelberg, pp. 286-303 CrossRef
  31. Rivest, R.: The MD5 message-digest algorithm. Request for Comments 1321 (RFC 1321), The Internet Engineering Task Force (1992)
  32. Sasaki, Y (2013) Meet-in-the-middle preimage attacks on AES hashing modes and an application to Whirlpool. IEICE Trans. Fundam. E96鈥揂: pp. 121-130 CrossRef
  33. Wei, L., Peyrin, T., Soko艂owski, P., Ling, S., Pieprzyk, J., Wang, H.: On the (in)security of IDEA in various hashing modes. In: Canteaut [7], pp. 163鈥?79. The full version is 鈥淐ryptology ePrint Archive: Report 2012/264鈥?at http://eprint.iacr.org/
  
• 作者单位：Information Security and Cryptology - ICISC 2014
• 丛书名：978-3-319-15942-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

文摘

This paper presents the first non-trivial collision attack on the double-block-length compression function presented at FSE 2006 instantiated with round-reduced AES-256: \(f_0(h_0\Vert h_1,M)\Vert f_1(h_0\Vert h_1,M)\) such that $$\begin{aligned} f_0(h_0 \Vert h_1,M)&=E_{h_1\Vert M}(h_0)\oplus h_0 ,\\ f_1(h_0 \Vert h_1,M)&=E_{h_1\Vert M}(h_0\oplus c)\oplus h_0\oplus c , \end{aligned}$$ where \(\Vert \) represents concatenation, \(E\) is AES-256 and \(c\) is a non-zero constant. The proposed attack is a free-start collision attack. It uses the rebound attack proposed by Mendel et al. It finds a collision with time complexity \(2^{8}\) , \(2^{64}\) and \(2^{120}\) for the instantiation with 6-round, 8-round and 9-round AES-256, respectively. The space complexity is negligible. The attack is effective against the instantiation with 6-/8-round AES-256 if the \(16\) -byte constant \(c\) has a single non-zero byte. It is effective against the instantiation with 9-round AES-256 if the constant \(c\) has four non-zero bytes at some specific positions.