BoolTest: The Fast Randomness Testing Strategy Based on Boolean
Functions with Application to DES, 3-DES, MD5, MD6 and SHA-256

D 2019

BoolTest: The Fast Randomness Testing Strategy Based on Boolean Functions with Application to DES, 3-DES, MD5, MD6 and SHA-256

SÝS, Marek; Dušan KLINEC; Karel KUBÍČEK and Petr ŠVENDA

Basic information

Original name

BoolTest: The Fast Randomness Testing Strategy Based on Boolean Functions with Application to DES, 3-DES, MD5, MD6 and SHA-256

Name in Czech

BoolTest: rychlé testovanie náhodnosti na bázy boolovských funkcií DES, 3-DES, MD5, MD6 and SHA-256

Authors

SÝS, Marek (703 Slovakia, guarantor, belonging to the institution); Dušan KLINEC (703 Slovakia, belonging to the institution); Karel KUBÍČEK (203 Czech Republic, belonging to the institution) and Petr ŠVENDA (203 Czech Republic, belonging to the institution)

Edition

Madrid, E-Business and Telecommunications 14th International Joint Conference, ICETE 2017, p. 123-149, 27 pp. 2019

Publisher

Springer

Other information

Language

English

Type of outcome

Proceedings paper

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

Germany

Confidentiality degree

is not subject to a state or trade secret

Publication form

printed version "print"

References:

Webpage with paper supplementary materials

RIV identification code

RIV/00216224:14330/19:00107243

Organization unit

Faculty of Informatics

ISBN

978-3-030-11038-3

ISSN

DOI

http://dx.doi.org/10.1007/978-3-030-11039-0_7

EID Scopus

2-s2.0-85061124830

Keywords in English

Statistical randomness testing; hypothesis testing; boolean function

Abstract

V originále

The output of modern cryptographic primitives like pseudorandom generators and block or stream ciphers is frequently required to be indistinguishable from a truly random data. The existence of any distinguisher provides a hint about the insufficient confusion and diffusion property of an analyzed function. In addition to targeted cryptoanalysis, statistical tests included in batteries such as NIST STS, Dieharder or TestU01 are frequently used to assess the indistinguishability property. However, the tests included in these batteries are either too simple to spot the common biases (like the Monobit test) or overly complex (like the Fourier Transform test) requiring an extensive amount of data. We propose a simple, yet surprisingly powerful method called BoolTest for the construction of distinguishers based on an exhaustive search for boolean function(s). The BoolTest typically constructs distinguisher with fewer input data required and directly identifies the function’s biased output bits. We analyze the performance on four input generation strategies: counter-based, low hamming weight, plaintextciphertext block combination and bit-flips to test strict avalanche criterion. The BoolTest detects bias and thus constructs distinguisher in a significantly higher number of rounds in the round-reduced versions of DES, 3-DES, MD5, MD6 and SHA-256 functions than the state-of-the-art batteries. Finally, we provide a precise interpretation of BoolTest verdict (provided in the form of Z-score) about the confidence of a distinguisher found. The BoolTest clear interpretation is a significant advantage over standard batteries consisting of multiple tests, where not only a statistical significance of a single test but also aggregated decision over multiple, potentially correlated tests, needs to be correctly performed.

Links

GA16-08565S, research and development project

Name: Rozvoj kryptoanalytických metod prostřednictvím evolučních výpočtů

Investor: Czech Science Foundation

Cite

SÝS, Marek; Dušan KLINEC; Karel KUBÍČEK and Petr ŠVENDA. BoolTest: The Fast Randomness Testing Strategy Based on Boolean Functions with Application to DES, 3-DES, MD5, MD6 and SHA-256. In E-Business and Telecommunications 14th International Joint Conference, ICETE 2017. Madrid: Springer, 2019, p. 123-149. ISBN 978-3-030-11038-3. Available from: https://dx.doi.org/10.1007/978-3-030-11039-0_7.

@inproceedings{1490410,
   author = {Sýs, Marek and Klinec, Dušan and Kubíček, Karel and Švenda, Petr},
   address = {Madrid},
   booktitle = {E-Business and Telecommunications 14th International Joint Conference, ICETE 2017},
   doi = {http://dx.doi.org/10.1007/978-3-030-11039-0_7},
   keywords = {Statistical randomness testing; hypothesis testing; boolean function},
   howpublished = {tištěná verze "print"},
   language = {eng},
   location = {Madrid},
   isbn = {978-3-030-11038-3},
   pages = {123-149},
   publisher = {Springer},
   title = {BoolTest: The Fast Randomness Testing Strategy Based on Boolean Functions with Application to DES, 3-DES, MD5, MD6 and SHA-256},
   url = {https://crocs.fi.muni.cz/public/papers/Secrypt2017selected},
   year = {2019}
}

TY  - CONF
ID  - 1490410
AU  - Sýs, Marek - Klinec, Dušan - Kubíček, Karel - Švenda, Petr
PY  - 2019
TI  - BoolTest: The Fast Randomness Testing Strategy Based on Boolean Functions with Application to DES, 3-DES, MD5, MD6 and SHA-256
PB  - Springer
CY  - Madrid
SN  - 9783030110383
KW  - Statistical randomness testing
KW  - hypothesis testing
KW  - boolean function
UR  - https://crocs.fi.muni.cz/public/papers/Secrypt2017selected
L2  - https://crocs.fi.muni.cz/public/papers/Secrypt2017selected
N2  - The output of modern cryptographic primitives like pseudorandom generators and block or stream ciphers is frequently required to be indistinguishable from a truly random data. The existence of any distinguisher provides a hint about the insufficient confusion and diffusion property of an analyzed function. In addition to targeted cryptoanalysis, statistical tests included in batteries such as NIST STS, Dieharder or TestU01 are frequently used to assess the indistinguishability property. However, the tests included in these batteries are either too simple to spot the common biases (like the Monobit test) or overly complex (like the Fourier Transform test) requiring an extensive amount of data. We propose a simple, yet surprisingly powerful method called BoolTest for the construction of distinguishers based on an exhaustive search for boolean function(s). The BoolTest typically constructs distinguisher with fewer input data required and directly identifies the function’s biased output bits. We analyze the performance on four input generation strategies: counter-based, low hamming weight, plaintextciphertext block combination and bit-flips to test strict avalanche criterion. The BoolTest detects bias and thus constructs distinguisher in a significantly higher number of rounds in the round-reduced versions of DES, 3-DES, MD5, MD6 and SHA-256 functions than the state-of-the-art batteries. Finally, we provide a precise interpretation of BoolTest verdict (provided in the form of Z-score) about the confidence of a distinguisher found. The BoolTest clear interpretation is a significant advantage over standard batteries consisting of multiple tests, where not only a statistical significance of a single test but also aggregated decision over multiple, potentially correlated tests, needs to be correctly performed.
ER  -

SÝS, Marek; Dušan KLINEC; Karel KUBÍČEK and Petr ŠVENDA. BoolTest: The Fast Randomness Testing Strategy Based on Boolean Functions with Application to DES, 3-DES, MD5, MD6 and SHA-256. In \textit{E-Business and Telecommunications 14th International Joint Conference, ICETE 2017}. Madrid: Springer, 2019, p.~123-149. ISBN~978-3-030-11038-3. Available from: https://dx.doi.org/10.1007/978-3-030-11039-0\_{}7.

Přehled o publikaci