Another look at normal approximations in cryptanalysis

Journal of mathematical cryptology

article

Subhabrata Samajder¹  Palash Sarkar¹ 

[1] Applied Statistics Unit, Indian Statistical Institute

关键词: Block cipher;    linear/differential cryptanalysis;    order statistics;    normal distribution;    Berry–Essén theorem;   

DOI  :  10.1515/jmc-2016-0006

学科分类：社会科学、人文和艺术（综合）

来源: De Gruyter

【 摘 要 】

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.

【 授权许可】

CC BY|CC BY-NC-ND