Paper 2019/960

Another Look at Key Randomisation Hypotheses

Subhabrata Samajder and Palash Sarkar

Abstract

In the context of linear cryptanalysis of block ciphers, let $p_0$ (resp. $p_1$) be the probability that a particular linear approximation holds for the right (resp. a wrong) key choice. The standard right key randomisation hypothesis states that $p_0$ is a constant $p\ne 1/2$ and the standard wrong key randomisation hypothesis states that $p_1=1/2$. Using these hypotheses, the success probability $P_S$ of the attack can be expressed in terms of the data complexity $N$. The resulting expression for $P_S$ is a monotone increasing function of $N$. Building on earlier work by Daemen and Rijmen (2007), Bogdanov and Tischhauser (2014) argued that $$ should be considered to be a random variable. They postulated the adjusted wrong key randomisation hypothesis which states that $$ follows a normal distribution. A non-intuitive consequence was that the resulting expression for $$ is no longer a monotone increasing function of $$. A later work by Blondeau and Nyberg (2017) argued that $$ should also be considered to be a random variable and they postulated the adjusted right key randomisation hypothesis which states that $$ follows a normal distribution. In this work, we revisit the key randomisation hypotheses. While the argument that $$ and $$ should be considered to be random variables is indeed valid, we consider the modelling of their distributions by normal to be inappropriate. Being probabilities, the support of the distributions of $$ and $$ should be subsets of $$ which does not hold for normal distributions. We show that if $$ and $$ follow any distributions with supports which are subsets of $$, and $$ and $$, then the expression for $$ that is obtained is exactly the same as the one obtained using the standard key randomisation hypotheses. Consequently, $$ is a monotone increasing function of $$ even when $$ and $$ are considered to be random variables.