Paper 2023/1266
Automatic Preimage Attack Framework on \ascon Using a Linearize-and-Guess Approach
Abstract
\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.
Metadata
- Available format(s)
-
PDF
- Category
- Attacks and cryptanalysis
- Publication info
- Preprint.
- Keywords
- 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 - History
- 2023-08-24: approved
- 2023-08-22: received
- See all versions
- Short URL
- https://ia.cr/2023/1266
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2023/1266, 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}, url = {https://eprint.iacr.org/2023/1266} }