Another look at key randomisation hypotheses

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 O’Connor (In: Preneel B (ed) Fast Software Encryption: Second International Workshop. Leuven, Belgium, 14–16 December 1994, Proceedings, volume 1008 of Lecture Notes in Computer Science, pp. 131–136. Springer, 1994) and Daemen and Rijmen (J Math Cryptol 1(3):221–242, 2007), Bogdanov and Tischhauser (In: Moriai S (ed) Fast Software Encryption—20th International Workshop, FSE 2013, Singapore, March 11–13, 2013. Revised Selected Papers, volume 8424 of Lecture Notes in Computer Science, pp. 19–38. Springer, 2013) argued that \(p_1\) should be considered to be a random variable. They postulated the adjusted wrong key randomisation hypothesis which states that \(p_1\) follows a normal distribution. A non-intuitive consequence is that the resulting expression for \(P_S\) is no longer a monotone increasing function of N. A later work by Blondeau and Nyberg (Des Codes Cryptogr 82(1–2):319–349, 2017) argued that \(p_0\) should also be considered to be a random variable and they postulated the adjusted right key randomisation hypothesis which states that \(p_0\) follows a normal distribution. In this work, we revisit the key randomisation hypotheses. While the argument that \(p_0\) and \(p_1\) should be considered to be random variables is indeed valid, we show that if \(p_0\) and \(p_1\) follow any distributions with supports which are subsets of [0, 1], and \({\textbf{E}}[p_0]=p\) and \({\textbf{E}}[p_1]=1/2\), then the expression for \(P_S\) that is obtained is exactly the same as the one obtained using the standard key randomisation hypotheses. Consequently, \(P_S\) is a monotone increasing function of N even when \(p_0\) and \(p_1\) are considered to be random variables.