Paper 2016/404

A New Test Statistic for Key Recovery Attacks Using Multiple Linear Approximations

Subhabrata Samajder and Palash Sarkar

Abstract

The log-likelihood ratio (LLR) and the chi-squared distribution based test statistics have been proposed in the literature for performing statistical analysis of key recovery attacks on block ciphers. A limitation of the LLR test statistic is that its application requires the full knowledge of the corresponding distribution. Previous work using the chi-squared approach required {\em approximating} the distribution of the relevant test statistic by chi-squared and normal distributions. Problematic issues regarding such approximations have been reported in the literature. Perhaps more importantly, both the LLR and the chi-squared based methods are applicable only if the success probability $P_S$ is greater than 0.5. On the other hand, an attack with success probability less than $0.5$ is also of considerable interest. This work proposes a new test statistic for key recovery attacks which has the following features. Its application does not require the full knowledge of the underlying distribution; it is possible to carry out an analysis using this test statistic without using any approximations; the method applies for all values of the success probability. The statistical analysis of the new test statistic follows the hypothesis testing framework and uses Hoeffding's inequalities to bound the probabilities of Type-I and Type-II errors.

Metadata
Available format(s)
PDF
Publication info
Preprint.
Keywords
multiple linear cryptanalyisLLR statisticchi-squared statisticHoeffding inequality.
Contact author(s)
subhabrata samajder @ gmail com
palash sarkar @ gmail com
History
2017-01-19: last of 2 revisions
2016-04-25: received
See all versions
Short URL
https://ia.cr/2016/404
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/404,
      author = {Subhabrata Samajder and Palash Sarkar},
      title = {A New Test Statistic for Key Recovery Attacks Using Multiple Linear Approximations},
      howpublished = {Cryptology ePrint Archive, Paper 2016/404},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/404}},
      url = {https://eprint.iacr.org/2016/404}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.