The Efficient Randomness Testing using Boolean Functions

D 2017

The Efficient Randomness Testing using Boolean Functions

SÝS, Marek, Dušan KLINEC a Petr ŠVENDA

Základní údaje

Originální název

The Efficient Randomness Testing using Boolean Functions

Autoři

SÝS, Marek (703 Slovensko, garant, domácí), Dušan KLINEC (703 Slovensko, domácí) a Petr ŠVENDA (203 Česká republika, domácí)

Vydání

Madrid, Spain, Proceedings of the 14th International Joint Conference on e-Business and Telecommunications (ICETE 2017) - Volume 4: SECRYPT, Madrid, Spain, July 24-26, 2017, od s. 92-103, 12 s. 2017

Nakladatel

SCITEPRESS

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Portugalsko

Utajení

není předmětem státního či obchodního tajemství

Forma vydání

tištěná verze "print"

Odkazy

URL

Kód RIV

RIV/00216224:14330/17:00095141

Organizační jednotka

Fakulta informatiky

ISBN

978-989-758-259-2

DOI

http://dx.doi.org/10.5220/0006425100920103

Klíčová slova anglicky

booltest; randomness; randomness testing; polynomials; NIST STS; Dieharder; boolean functions; statistical randomness test

Štítky

core_B, firank_B

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 27. 4. 2018 11:02, RNDr. Pavel Šmerk, Ph.D.

Anotace

V originále

The wide range of security applications requires data either truly random or indistinguishable from the random. The statistical tests included in batteries like NIST STS or Dieharder are frequently used to assess this randomness property. We designed principally simple, yet powerful statistical randomness test working on the bit level and based on a search for boolean function(s) exhibiting bias not expected for truly random data when applied to the tested stream. The deviances are detected in seconds rather than tens of minutes required by the common batteries. Importantly, the boolean function exhibiting the bias directly describes the pattern responsible for this bias - allowing for construction of bit predictor or fixing the cause of bias in tested function design. The present bias is frequently detected in at least order of magnitude less data than required for NIST STS or Dieharder showing that the tests included in these batteries are either too simple to spot the common biases (like Monobit test) or overly complex (like Fourier Transform test) which requires an extensive amount of data. The proposed approach called BoolTest fills this gap. The performance was verified on more than 20 real world cryptographic functions – block and stream ciphers, hash functions and pseudorandom generators. Among others, the previously unknown bias in output of C rand() and Java Random generators which can be utilized as practical distinguisher was found.

Návaznosti

GA16-08565S, projekt VaV

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

Investor: Grantová agentura ČR, Advancing cryptanalytic methods through evolutionary computing

Citovat

SÝS, Marek, Dušan KLINEC a Petr ŠVENDA. The Efficient Randomness Testing using Boolean Functions. In Proceedings of the 14th International Joint Conference on e-Business and Telecommunications (ICETE 2017) - Volume 4: SECRYPT, Madrid, Spain, July 24-26, 2017. Madrid, Spain: SCITEPRESS, 2017, s. 92-103. ISBN 978-989-758-259-2. Dostupné z: https://dx.doi.org/10.5220/0006425100920103.

@inproceedings{1394875,
   author = {Sýs, Marek and Klinec, Dušan and Švenda, Petr},
   address = {Madrid, Spain},
   booktitle = {Proceedings of the 14th International Joint Conference on e-Business and Telecommunications (ICETE 2017) - Volume 4: SECRYPT, Madrid, Spain, July 24-26, 2017},
   doi = {http://dx.doi.org/10.5220/0006425100920103},
   keywords = {booltest; randomness; randomness testing; polynomials; NIST STS; Dieharder; boolean functions; statistical randomness test},
   howpublished = {tištěná verze "print"},
   language = {eng},
   location = {Madrid, Spain},
   isbn = {978-989-758-259-2},
   pages = {92-103},
   publisher = {SCITEPRESS},
   title = {The Efficient Randomness Testing using Boolean Functions},
   url = {https://crocs.fi.muni.cz/public/papers/secrypt2017},
   year = {2017}
}

TY  - JOUR
ID  - 1394875
AU  - Sýs, Marek - Klinec, Dušan - Švenda, Petr
PY  - 2017
TI  - The Efficient Randomness Testing using Boolean Functions
PB  - SCITEPRESS
CY  - Madrid, Spain
SN  - 9789897582592
KW  - booltest
KW  - randomness
KW  - randomness testing
KW  - polynomials
KW  - NIST STS
KW  - Dieharder
KW  - boolean functions
KW  - statistical randomness test
UR  - https://crocs.fi.muni.cz/public/papers/secrypt2017
L2  - https://crocs.fi.muni.cz/public/papers/secrypt2017
N2  - The wide range of security applications requires data either truly random or indistinguishable from the random. The statistical tests included in batteries like NIST STS or Dieharder are frequently used to assess this randomness property. We designed principally simple, yet powerful statistical randomness test working on the bit level and based on a search for boolean function(s) exhibiting bias not expected for truly random data when applied to the tested stream. The deviances are detected in seconds rather than tens of minutes required by the common batteries. Importantly, the boolean function exhibiting the bias directly describes the pattern responsible for this bias - allowing for construction of bit predictor or fixing the cause of bias in tested function design. The present bias is frequently detected in at least order of magnitude less data than required for NIST STS or Dieharder showing that the tests included in these batteries are either too simple to spot the common biases (like Monobit test) or overly complex (like Fourier Transform test) which requires an extensive amount of data. The proposed approach called BoolTest fills this gap. The performance was verified on more than 20 real world cryptographic functions – block and stream ciphers, hash functions and pseudorandom generators. Among others, the previously unknown bias in output of C rand() and Java Random generators which can be utilized as practical distinguisher was found.
ER  -

SÝS, Marek, Dušan KLINEC a Petr ŠVENDA. The Efficient Randomness Testing using Boolean Functions. In \textit{Proceedings of the 14th International Joint Conference on e-Business and Telecommunications (ICETE 2017) - Volume 4: SECRYPT, Madrid, Spain, July 24-26, 2017}. Madrid, Spain: SCITEPRESS, 2017, s.~92-103. ISBN~978-989-758-259-2. Dostupné z: https://dx.doi.org/10.5220/0006425100920103.

Podrobný výpis o publikaci