Paper 2023/1266

Automatic Preimage Attack Framework on \ascon Using a Linearize-and-Guess Approach

Huina Li, Shanghai Jiao Tong University
Le He, Nanyang Technological University
Shiyao Chen, Nanyang Technological University
Jian Guo, Nanyang Technological University
Weidong Qiu, Shanghai Jiao Tong University

\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 \textit{et al.} at ASIACRYPT 2016 and subsequently improved by Li \textit{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 $2^{39}$ guesses to $2^{27.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.

Available format(s)
Attacks and cryptanalysis
Publication info
Ascon; Preimage Attack; SAT
Contact author(s)
lihuina @ sjtu edu cn
le he @ ntu edu sg
shiyao chen @ ntu edu sg
guojian @ ntu edu sg
qiuwd @ sjtu edu cn
2023-08-24: approved
2023-08-22: received
See all versions
Short URL
Creative Commons Attribution


      author = {Huina Li and Le He and Shiyao Chen and Jian Guo and Weidong Qiu},
      title = {Automatic Preimage Attack Framework on \ascon Using a Linearize-and-Guess Approach},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1266},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.