Automatic Preimage Attack Framework on Ascon Using a Linearize-and-Guess Approach
Ascon is the final winner of the lightweight cryptography standardization competition (2018 − 2023). In this paper, we focus on preimage attacks against round-reduced Ascon. The preimage attack framework, utilizing the linear structure with the allocating model, was initially proposed by Guo et al. at ASIACRYPT 2016 and subsequently improved by Li et al. at EUROCRYPT 2019, demonstrating high effectiveness in breaking the preimage resistance of Keccak. In this paper, we extend this preimage attack framework to Ascon from two aspects. Firstly, we propose a linearize-and-guess approach by analyzing the algebraic properties of the Ascon permutation. As a result, the complexity of finding a preimage for 2-round Ascon-Xof with a 64-bit hash value can be significantly reduced from 239 guesses to 227.56 guesses. To support the effectiveness of our approach, we find an actual preimage of all ‘0’ hash in practical time. Secondly, we develop a SAT-based automatic preimage attack framework using the linearize-and-guess approach, which is efficient to search for the optimal structures exhaustively. Consequently, we present the best theoretical preimage attacks on 3-round and 4-round Ascon-Xof so far.
New Techniques for Searching Differential Trails in Keccak 📺
Keccak-f is the permutation used in the NIST SHA-3 hash function standard. Inspired by the previous exhaustive differential trail search methods by Mella et al. at ToSC 2017, we introduce in this paper new algorithms to cover 3-round trail cores with propagation weight at least 53, up from the previous best weight 45. To achieve the goal, the concept of ideal improvement assumption is proposed to construct theoretical representative of subspaces so as to efficiently cover the search space of 3-round trail cores with at least one out-Kernel α state. Of particular note is that the exhaustiveness in 3-round trail core search of at least one out-Kernel α is only experimentally verified. With the knowledge of all 3-round trail cores of weight up to 53, lower bounds on 4/5/6-round trails are tightened to 56/58/108, from the previous 48/50/92, respectively.