The Efficient Randomness Testing using Boolean Functions

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F17%3A00095141" target="_blank" >RIV/00216224:14330/17:00095141 - isvavai.cz</a>

Výsledek na webu

<a href="https://crocs.fi.muni.cz/public/papers/secrypt2017" target="_blank" >https://crocs.fi.muni.cz/public/papers/secrypt2017</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.5220/0006425100920103" target="_blank" >10.5220/0006425100920103</a>

Jazyk výsledku

angličtina

Název v původním jazyce

The Efficient Randomness Testing using Boolean Functions

Popis výsledku v původním jazyce

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ázev v anglickém jazyce

The Efficient Randomness Testing using Boolean Functions

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/GA16-08565S" target="_blank" >GA16-08565S: Rozvoj kryptoanalytických metod prostřednictvím evolučních výpočtů</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2017

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

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

ISBN

9789897582592

ISSN

—

e-ISSN

—

Počet stran výsledku

12

Strana od-do

92-103

Název nakladatele

SCITEPRESS

Místo vydání

Madrid, Spain

Místo konání akce

Madrid, Spain

Datum konání akce

24. 7. 2017

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—