International Association
for Cryptologic Research

The log-likelihood ratio (LLR) test statistic has been proposed in the literature for performing statistical analysis of attacks on block ciphers. A limitation of the LLR test statistic is that its application requires the full knowledge of the corresponding distribution. Another test statistic which has been proposed in the literature does not possess this limitation. The statistical analysis using this test statistic requires {\em approximating} its distribution by a chi-squared distribution. Problematic issues regarding such approximations have been reported in the literature. This work proposes a new test statistic which offers the following two features. Its application does not require knowledge of the underlying distribution and it is possible to carry out an analysis using this test statistic without using any approximation. This is made possible by applying the theory of martingales to build a Doob martingale satisfying an appropriate Lipschitz condition so that the Azuma-Hoeffding inequality can be applied. Experimental comparison of the data complexity obtained using the new method is made to the data complexity obtained using the chi-squared based method for both simulated distributions and the previously reported distribution for the block cipher SERPENT. In all cases, the data complexity obtained by the new method turns out to be greater. While this may appear to be a drawback of the new method, this is a rigorous bound while the data complexity obtained using the chi-squared method is an approximation where there is little knowledge about the error in the approximation. So, if rigorous bound is desired, then one will have to be satisfied with a more conservative estimate of the data complexity.