Paper 2020/1152

An Automatic Search Tool for Iterative Trails and its Application to estimation of differentials and linear hulls

Tianyou Ding, Wentao Zhang, Chunning Zhou, and Fulei Ji

Abstract

The design and cryptanalysis are the both sides from which we look at symmetric-key primitives. If a symmetric-key primitive is broken by a kind of cryptanalysis, it's definitely insecure. If a designer claims a symmetric-key primitive to be secure, one should demonstrate that the primitive resists against all known attacks. Differential and linear cryptanalysis are two of the most important kinds of cryptanalysis. To conduct a successful differential (linear) cryptanalysis, a differential (linear) distinguisher with significant differential probability (linear correlation) is needed. We observe that, for some lightweight symmetric-key primitives, their significant trails usually contain iterative trails. In this work, We propose an automatic tool for searching iterative trails. We model the problem of searching itrative trails as a problem of finding elementry ciucuits in a graph. Based on the iterative trails found, we further propose a method to estimate the probability (correlation) of a differential (linear hull). We apply our methods to the 256-bit KNOT permutation, PRESENT, GIFT-64 and RECTANGLE. Iterative trails are found and visualized. If iterative trails are found, we show our method can efficiently find good differentials and linear hulls. What's more, the results imply that for the primitives we test with bit permutations as their linear layers, the good differentials and linear hulls are dominated by iterative trails.

Note: The writing and experiments are still in progress. More experiment results will be added on.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Differential CryptanalysisLinear CryptanalysisAutomatic Search ToolsIterative TrailsLightweight Cryptography
Contact author(s)
dingtianyou @ iie ac cn
zhangwentao @ iie ac cn
History
2020-09-25: received
Short URL
https://ia.cr/2020/1152
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/1152,
      author = {Tianyou Ding and Wentao Zhang and Chunning Zhou and Fulei Ji},
      title = {An Automatic Search Tool for Iterative Trails and its Application to estimation of differentials and linear hulls},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1152},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/1152}},
      url = {https://eprint.iacr.org/2020/1152}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.