Hypothesis testing and advanced distiguishers in differential cryptanalysis of block ciphers

Mourouzis, Theodosis ; Courtois, Nicolas

Tatra Mountains Mathematical Publications, Tome 62 (2015), / Harvested from Mathematical Institute

Résumé

Distinguishing distributions is a major part duringcryptanalysis of symmetric block ciphers. Essentially, the goalis to distinguish two distributions; one that characterizes thenumber of certain events which occur totally at random andanother one that characterizes same type of events but dueto progagation inside the cipher. This can be realized as ahypothesis testing problem using as the reference distributionthe one corresponding to a random permutation. Suppose that asource is used to generate independent random samples in somegiven 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 mostlikely 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 ageneral hypothesis-testing based approach to construct statisticaldistinguishers using truncated differential properties [5], as firstlydiscussed in [13], [6]. The observed variable in our case is theexpected number of pairs which follow a certain differentialproperty of the form $\delta X  \to \delta Y$  after some number of rounds R. As a proof of concept, we apply this methodology to GOSTand SIMON64/128 block ciphers and present distinguishers on20 and 22 rounds respectively, that allow us to distinguish thedistribution corresponding due to encryption with the correctkey from a random permutation with a very low false-positiverate.

Détail

Publié le : 2015-01-01
DOI : https://doi.org/10.2478/tatra.v64i0.393