Hypothesis testing and advanced distiguishers in differential cryptanalysis of block ciphers

Abstract

Distinguishing distributions is a major part during
cryptanalysis of symmetric block ciphers. Essentially, the goal
is to distinguish two distributions; one that characterizes the
number of certain events which occur totally at random and
another one that characterizes same type of events but due
to progagation inside the cipher. This can be realized as a
hypothesis testing problem using as the reference distribution
the one corresponding to a random permutation. Suppose that a
source is used to generate independent random samples in some
given finite set with some distribution P, which is either $P = P_0$
or $P = P_1$. Distinguisher’s goal is to determine which one is most
likely the one which was used to generate the sample. Discovery of such distinguishers can be potentially exploited to attack a certain number of rounds, and sometimes but more rarely, could lead to attacks against the full number of rounds. A good example of this,
is the differential attack described in [?]. In this paper, we study a
general hypothesis-testing based approach to construct statistical
distinguishers using truncated differential properties [5], as firstly
discussed in [13], [6]. The observed variable in our case is the
expected number of pairs which follow a certain differential

property of the form $\delta X  \to \delta Y$  after some number of rounds R. As a proof of concept, we apply this methodology to GOST
and SIMON64/128 block ciphers and present distinguishers on
20 and 22 rounds respectively, that allow us to distinguish the
distribution corresponding due to encryption with the correct
key from a random permutation with a very low false-positive
rate.