Paper 2021/965

Automatic Search for Bit-based Division Property

Shibam Ghosh and Orr Dunkelman

Abstract

Division properties, introduced by Todo at Eurocrypt 2015, are extremely useful in cryptanalysis, are an extension of square attack (also called saturation attack or integral cryptanalysis). Given their im- portance, a large number of works tried to offer automatic tools to find division properties, primarily based on MILP or SAT/SMT. This paper studies better modeling techniques for finding division properties using the Constraint Programming and SAT/SMT-based automatic tools. We use the fact that the Quine-McCluskey algorithm produces a concise CNF representation corresponding to the division trail table of an Sbox. As a result, we can offer significantly more compact models, which allow SAT and Constraint Programming tools to outperform previous results. To show the strength of our new approach, we look at the NIST lightweight candidate KNOT and Ascon. We show several new distinguishers with a lower data complexity for 17-round KNOT-256, KNOT-384 and 19- round KNOT-512. In addition, for the 5-round Ascon, we get a lower data distinguisher than the previous division-based results. Finally, we revisit the method to extend the integral distinguisher by composing linear layers at the input and output. We provide a formu- lation to find the optimal number of linear combinations that need to be considered. As a result of this new formulation, we prove that 18- round KNOT-256 and KNOT-384 have no integral distinguisher using conventional division property and we show this more efficiently than the previous methods.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. Minor revision. Latin Crypt 2021
Keywords
Constraint programmingdivision propertyintegral crypt- analysisKNOTAscon.
Contact author(s)
sghosh03 @ campus haifa ac il
orrd @ cs haifa ac il
History
2021-07-22: received
Short URL
https://ia.cr/2021/965
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/965,
      author = {Shibam Ghosh and Orr Dunkelman},
      title = {Automatic Search for Bit-based Division Property},
      howpublished = {Cryptology ePrint Archive, Paper 2021/965},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/965}},
      url = {https://eprint.iacr.org/2021/965}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.