Paper 2017/729

Success Probability of Multiple/Multidimensional Linear Cryptanalysis Under General Key Randomisation Hypotheses

Subhabrata Samajder and Palash Sarkar

Abstract

This work considers statistical analysis of attacks on block ciphers using several linear approximations. A general and unified approach is adopted. To this end, the general key randomisation hypotheses for multidimensional and multiple linear cryptanalysis are introduced. Expressions for the success probability in terms of the data complexity and the advantage are obtained using the general key randomisation hypotheses for both multidimensional and multiple linear cryptanalysis and under the settings where the plaintexts are sampled with or without replacement. Particularising to standard/adjusted key randomisation hypotheses gives rise to success probabilities in 16 different cases out of which in only five cases expressions for success probabilities have been previously reported. Even in these five cases, the expressions for success probabilities that we obtain are more general than what was previously obtained. A crucial step in the analysis is the derivation of the distributions of the underlying test statistics. While we carry out the analysis formally to the extent possible, there are certain inherently heuristic assumptions that need to be made. In contrast to previous works which have implicitly made such assumptions, we carefully highlight these and discuss why they are unavoidable. Finally, we provide a complete characterisation of the dependence of the success probability on the data complexity.