Paper 2023/288

Efficient Detection of High Probability Statistical Properties of Cryptosystems via Surrogate Differentiation

Itai Dinur, Ben-Gurion University of the Negev
Orr Dunkelman, University of Haifa
Nathan Keller, Bar-Ilan University
Eyal Ronen, Tel Aviv University
Adi Shamir, Weizmann Institute of Science

A central problem in cryptanalysis is to find all the significant deviations from randomness in a given $n$-bit cryptographic primitive. When $n$ is small (e.g., an $8$-bit S-box), this is easy to do, but for large $n$, the only practical way to find such statistical properties was to exploit the internal structure of the primitive and to speed up the search with a variety of heuristic rules of thumb. However, such bottom-up techniques can miss many properties, especially in cryptosystems which are designed to have hidden trapdoors. In this paper we consider the top-down version of the problem in which the cryptographic primitive is given as a structureless black box, and reduce the complexity of the best known techniques for finding all its significant differential and linear properties by a large factor of $2^{n/2}$. Our main new tool is the idea of using {\it surrogate differentiation}. In the context of finding differential properties, it enables us to simultaneously find information about all the differentials of the form $f(x) \oplus f(x \oplus \alpha)$ in all possible directions $\alpha$ by differentiating $f$ in a single arbitrarily chosen direction $\gamma$ (which is unrelated to the $\alpha$'s). In the context of finding linear properties, surrogate differentiation can be combined in a highly effective way with the Fast Fourier Transform. For $64$-bit cryptographic primitives, this technique makes it possible to automatically find in about $2^{64}$ time all their differentials with probability $p \geq 2^{-32}$ and all their linear approximations with bias $|p| \geq 2^{-16}$; previous algorithms for these problems required at least $2^{96}$ time. Similar techniques can be used to significantly improve the best known time complexities of finding related key differentials, second-order differentials, and boomerangs. In addition, we show how to run variants of these algorithms which require no memory, and how to detect such statistical properties even in trapdoored cryptosystems whose designers specifically try to evade our techniques.

Available format(s)
Secret-key cryptography
Publication info
A major revision of an IACR publication in EUROCRYPT 2023
Cryptanalysissurrogate differentiationDifferential CryptanalysisLinear Cryptanalysis
Contact author(s)
dinuri @ cs bgu ac il
orrd @ cs haifa ac il
Nathan Keller @ biu ac il
eyal ronen @ cs tau ac il
Adi Shamir @ weizmann ac il
2023-02-27: approved
2023-02-26: received
See all versions
Short URL
Creative Commons Attribution-NonCommercial-ShareAlike


      author = {Itai Dinur and Orr Dunkelman and Nathan Keller and Eyal Ronen and Adi Shamir},
      title = {Efficient Detection of High Probability Statistical Properties of Cryptosystems via Surrogate Differentiation},
      howpublished = {Cryptology ePrint Archive, Paper 2023/288},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.