Another look at normal approximations in cryptanalysis
Statistical analysis of attacks on symmetric ciphers often requires 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 literatur...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
De Gruyter
2016-06-01
|
| Series: | Journal of Mathematical Cryptology |
| Subjects: | |
| Online Access: | https://doi.org/10.1515/jmc-2016-0006 |
| Summary: | Statistical analysis of attacks on symmetric ciphers often requires 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. A basic mathematical requirement is that such approximation errors
should be within reasonable bounds, a point which appears to have been overlooked in many of the earlier works on statistical
aspects of cryptanalysis. Interpreting the error bounds in the cryptanalytic context yields 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.
This, however, necessitates using normal approximations for the χ2${\chi ^2}$ and the LLR test statistics considered in earlier works.
These approximations themselves have issues which seem to be difficult to resolve satisfactorily. 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. |
|---|---|
| ISSN: | 1862-2976 1862-2984 |