## Another look at normal approximations in cryptanalysis

Subhabrata Samajder and Palash Sarkar

*Journal of Mathematical Cryptology*, 10 (2016), 69-99.

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 χ^{2} and the
log-likelihood ratio (LLR) based test statistics. The normal approximation
of the χ^{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 χ^{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.

Journal paper
Eprint paper