Title:
The Hunt for High Probability Statistical Impurities in Cryptographic Primitives

Abstract:
Computer security relies on cryptographic primitives such as block ciphers and hash functions. The security of these primitives is usually not proved in a reduction-style proof, but rather argued based on claims of the form - this block cipher has no statistical property of some type (e.g., differential) with high enough probability. However, how do we know that there are no such statistical properties in a given n-bit cryptographic primitive?

When n is small (e.g., an 8-bit S-box), this is easy to do. However, for large values of 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 work 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 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 by differentiating f in a single randomly 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 larger than 2^{-32} and all their linear approximations with bias larger than 2^{-16}; previous algorithms for these problems required at least 2^{96}  time.

This is a joint work with Itai Dinur, Nathan Keller, Eyal Ronen, and Adi Shamir.

Bio:
Prof. Orr Dunkelman is a full professor of computer science at the Computer Science Department at the University of Haifa in Israel. He graduated from the Technion, Israel Institute of Technology, in 2006. He did his post-doctoral studies with the COSIC research group at KU Leuven in
Belgium, with the Crypto team at Ecole Normale Superieure in Paris, France, and in the Weizmann Institute of Science in Israel.

Prof. Dunkelman co-invented numerous cryptanalytic attacks and suggested attacks on many symmetric-key cryptosystems. He won several awards and distinctions such as the Krill Prize for 2014 and the best paper award of CRYPTO 2012. He also served as the program chair of several cryptographic conferences, including EUROCRYPT 2022. In addition, he served as a director on the board of the International Association for Cryptologic Research (IACR) in the years 2017-2018. He is currently the chair of the FSE steering committee, and was for many years a member of the SAC workshop board.
Orr is a co-director of the Center for Cyber, Law and Policy (CCLP) at the University of Haifa, and the head of the Center for research of biometrics and its applications that operates as part of the CCLP.