×

A collision attack on a double-block-length compression function instantiated with round-reduced AES-256. (English) Zbl 1344.94038

Lee, Jooyoung (ed.) et al., Information security and cryptology – ICISC 2014. 17th international conference, Seoul, Korea, December 3–5, 2014. Revised selected papers. Cham: Springer (ISBN 978-3-319-15942-3/pbk; 978-3-319-15943-0/ebook). Lecture Notes in Computer Science 8949, 271-285 (2015).
Summary: This paper presents the first non-trivial collision attack on the double-block-length compression function presented at FSE 2006 [S. Hirose, Lect. Notes Comput. Sci. 4047, 210–225 (2006; Zbl 1234.94046)] instantiated with round-reduced AES-256:
\(f_0(h_0\| h_1,M)\| f_1(h_0\| h_1,M)\) such that \[ \begin{aligned} f_0(h_0 \| h_1,M)&=E_{h_1\| M}(h_0)\oplus h_0,\\ f_1(h_0 \| h_1,M)&=E_{h_1\| M}(h_0\oplus c)\oplus h_0\oplus c, \end{aligned} \] where \(\| \) 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 F. Mendel et al. [FSE 2009, Lect. Notes Comput. Sci. 5665, 260–276 (2009; Zbl 1291.94130)]. 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.
For the entire collection see [Zbl 1318.68031].

MSC:

94A60 Cryptography
PDFBibTeX XMLCite
Full Text: DOI