International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Huina Li , School of Cyber Science and Engineering, Shanghai Jiao Tong University, Shanghai, China; School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore, Singapore
Le He , School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore, Singapore
Shiyao Chen , Strategic Centre for Research in Privacy-Preserving Technologies and Systems, Nanyang Technological University, Singapore, Singapore; School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore, Singapore
Jian Guo , School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore, Singapore
Weidong Qiu , School of Cyber Science and Engineering, Shanghai Jiao Tong University, Shanghai, China
Download:
DOI: 10.46586/tosc.v2023.i3.74-100
URL: https://tosc.iacr.org/index.php/ToSC/article/view/11185
Search ePrint
Search Google
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 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.
BibTeX
@article{tosc-2023-33495,
  title={Automatic Preimage Attack Framework on Ascon Using a Linearize-and-Guess Approach},
  journal={IACR Transactions on Symmetric Cryptology},
  publisher={Ruhr-Universität Bochum},
  volume={2023, Issue 3},
  pages={74-100},
  url={https://tosc.iacr.org/index.php/ToSC/article/view/11185},
  doi={10.46586/tosc.v2023.i3.74-100},
  author={Huina Li and Le He and Shiyao Chen and Jian Guo and Weidong Qiu},
  year=2023
}