Towards cryptographic function distinguishers with evolutionary circuits
Petr Svenda and Martin Ukrop and Vashek Matyas
{svenda,xukrop,matyas}@fi.muni.cz
Masaryk University, Faculty of Informatics, Czech Republic
Abstract: Cryptanalysis of a cryptographic function usually requires advanced cryptanalytical skills and extensive
amount of human labour. However, some automation is possible, e.g., by using randomness testing suites
like STS NIST or Dieharder. These can be applied to test statistical properties
of cryptographic function outputs. Yet such testing suites are limited only to predefined patterns testing
particular statistical defects. We propose more open approach based on a combination of software circuits
and evolutionary algorithms to search for unwanted statistical properties like next bit predictability, random
data nondistinguishability or strict avalanche criterion. Software circuit that acts as a testing function is automatically
evolved by a stochastic optimization algorithm and uses information leaked during cryptographic
function evaluation. We tested this general approach on problem of finding a distinguisher of outputs produced by several candidate algorithms for eStream competition from truly random sequences.
We obtained similar results (with some exceptions) as those produced by STS NIST and Dieharder
tests w.r.t. the number of rounds of the inspected algorithm. This paper focuses on providing solid assessment
of the proposed approach w.r.t. STS NIST and Dieharder when applied over multiple different algorithms
rather than obtaining best possible result for a particular one. Additionally, proposed approach is able to
provide random distinguisher even when presented with very short sequence like 16 bytes only
Paper download: Svenda_EACirc_SeCrypt2013.pdf
Slides download: SeCrypt2013_EACirc_20130728_final.pdf
@inproceedings{Svenda13_secrypt,
title={Towards cryptographic function distinguishers with evolutionary circuits},
author={\v{S}}venda and Ukrop, M. and Maty{\'a}{\v{s}}, V.},
booktitle={Proceedings of the 10th International Conference on Security and Cryptography, SeCrypt 2013},
pages={135146},
year={2013},
organization={SCITEPRESS},
isbn={9789898565730}
}
Details for all experiments performed: https://is.muni.cz/th/374297/fi_b/thesis.pdf
Software circuit emulator  EACirc, source codes: https://github.com/petrs/EACirc
