**Another Look at Normal Approximations in Cryptanalysis**

*Subhabrata Samajder and Palash Sarkar*

**Abstract: **Statistical analysis of attacks on symmetric ciphers often require assuming the normal behaviour of a test statistic.
Typically such an assumption is made in an asymptotic sense. In this work, we consider concrete versions of some important
normal approximations that have been made in the literature. To do this, we use the Berry-Esséen theorem to derive
explicit bounds on the approximation errors. Analysing these error bounds in the cryptanalytic context throws up several
surprising results. One important implication is that this puts in doubt the applicability of the order statistics
based approach for analysing key recovery attacks on block ciphers. This approach has been earlier used to obtain several
results on the data complexities of (multiple) linear and differential cryptanalysis. The non-applicability of the order
statistics based approach puts a question mark on the data complexities obtained using this approach. Fortunately, we
are able to recover all of these results by utilising the hypothesis testing framework. Detailed consideration of the
error in normal approximation also has implications for $\chi^2$ and the log-likelihood ratio (LLR) based test statistics.
The normal approximation of the $\chi^2$ test statistics has some serious and counter-intuitive restrictions. One such
restriction is that for multiple linear cryptanalysis as the number of linear approximations grows so does the requirement
on the number of plaintext-ciphertext pairs for the approximation to be proper. The issue of satisfactorily addressing the
problems with the application of the $\chi^2$ test statistics remains open. For the LLR test statistics, previous work
used a normal approximation followed by another approximation to simplify the parameters of the normal approximation. We
derive the error bound for the normal approximation which turns out to be difficult to interpret. We show that the approximation
required for simplifying the parameters restricts the applicability of the result. Further, we argue that this approximation
is actually not required. More generally, the message of our work is that all cryptanalytic attacks should properly derive and
interpret the error bounds for any normal approximation that is made.

**Category / Keywords: **secret-key cryptography / block cipher, linear cryptanalysis, differential cryptanalysis, $\chi^2$ test, log-likelihood test, order statistics, normal distribution

**Date: **received 6 Jul 2015, last revised 21 Sep 2015

**Contact author: **subhabrata samajder at gmail com; palash sarkar@gmail com;

**Available format(s): **PDF | BibTeX Citation

**Version: **20150921:080619 (All versions of this report)

**Short URL: **ia.cr/2015/679

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]