International Association for Cryptologic Research

International Association
for Cryptologic Research


Bounds for the Security of Ascon against Differential and Linear Cryptanalysis

Johannes Erlacher , Graz University of Technology, Graz, Austria
Florian Mendel , Infineon Technologies AG, Munich, Germany
Maria Eichlseder , Graz University of Technology, Graz, Austria
DOI: 10.46586/tosc.v2022.i1.64-87
Search ePrint
Search Google
Abstract: The NIST Lightweight Cryptography project aims to standardize symmetric cryptographic designs, including authenticated encryption and hashing, suitable for constrained devices. One essential criterion for the evaluation of the 10 finalists is the evidence for their security against attacks like linear and differential cryptanalysis. For Ascon, one of the finalists and previous winner of the CAESAR competition in the ‘lightweight’ category, there is a large gap between the proven bounds and the best known characteristics found with heuristic tools: The bounds only cover up to 3 rounds with 15 differentially and 13 linearly active S-boxes, insufficient for proving a level of security for the full constructions.In this paper, we propose a new modeling strategy for SAT solvers and derive strong bounds for the round-reduced Ascon permutation. We prove that 4 rounds already ensure that any single characteristic has a differential probability or squared correlation of at most 2−72, and 6 rounds at most 2−108. This is significantly below the bound that could be exploited within the query limit for keyed Ascon modes. These bounds are probably not tight. To achieve this result, we propose a new search strategy of dividing the search space into a large number of subproblems based on ‘girdle patterns’, and show how to exploit the rotational symmetry of Ascon using necklace theory. Additionally, we evaluate and optimize several aspects of the pure SAT model, including the counter implementation and parallelizability, which we expect to be useful for future applications to other models.
Video from TOSC 2022
  title={Bounds for the Security of Ascon against Differential and Linear Cryptanalysis},
  journal={IACR Transactions on Symmetric Cryptology},
  publisher={Ruhr-Universität Bochum},
  volume={2022, Issue 1},
  author={Johannes Erlacher and Florian Mendel and Maria Eichlseder},