Automatic Search of Linear Structure: Applications to Keccak and Ascon

The linear structure technique was developed by Guo et al. at ASIACRYPT 2016, notably boosting the preimage attacks on Keccak. This technique transforming the preimage attack into solving algebraic systems allows entire linearization of the underlying permutation of Keccak for up to 2.5 rounds with significant degrees of freedom left. A linear structure with a larger degree of freedom left refers to a more powerful preimage attack, as it can substantially reduce the complexity of solving algebraic systems. However, previous linear structures on Keccak relied solely on manual design. They impose restrictions on specific lanes, requiring each of them to have exactly 64 variables, which may lead to some better linear structures without this restriction being ignored. In this paper, we remove such restrictions, formulate the essential ideas of designing linear structures for preimage attacks in well-defined ways, and translate the problem of finding the best preimage attacks into searching for optimal linear structure problems. We propose a new bit-level SAT-based automatic tool to search for optimal linear structures. The SAT model captures a large solution space of linear structures. Based on our tool, we find Guo et al. ’s structures on Keccak-224/-256/-384/-512, which proves the correctness of our model. Furthermore, we improve Guo et al. ’s preimage attacks on 2-/3-round Keccak-512 from \(2^{384}/2^{482} \) to \(2^{365}/2^{478}\) by identifying a new 1.5-round linear structure on Keccak-512 with 147 \(^\circ \) C of freedom left. Since a similar nonlinear layer exists in the final winner of the lightweight cryptography standardization competition Ascon, we make a study of linear structures on Ascon as an independent interest. As a result, we discover a 2-round linear structure with 102 \(^\circ \) C of freedom left. Based on this 2-round structure, we construct a full-round zero-sum distinguisher with a time complexity of \(2^{82}\) .