On the Unbearable Lightness of FIPS 140–2 Randomness Tests
Open Access
- 17 April 2020
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Forensics and Security
- Vol. 17 (15566013) , 3946-3958
Abstract
Random number generation is critical to many applications. Gaming, gambling, and particularly cryptography all require random numbers that are uniform and unpredictable. For testing whether supposedly random sources feature particular characteristics commonly found in random sequences, batteries of statistical tests are used. These are fundamental tools in the evaluation of random number generators and form part of the pathway to certification of secure systems implementing them. Although there have been previous studies into this subject becker2013stealthy, RNG manufacturers and vendors continue to use statistical tests known to be of dubious reliability, in their RNG verification processes. Our research shows that FIPS-140-2 cannot identify adversarial biases effectively, even very primitive ones. Concretely, this work illustrates the inability of the FIPS 140 family of tests to detect bias in three obviously flawed PRNGs. Deprecated by official standards, these tests are nevertheless still widely used, for example in hardware-level self-test schemes incorporated into the design of many True RNGs (TRNGs). They are also popular with engineers and cryptographers for quickly assessing the randomness characteristics of security primitives and protocols, and even with manufacturers aiming to market the randomness features of their products to potential customers. In the following, we present three biased-by-design RNGs to show in explicit detail how simple, glaringly obvious biases are not detected by any of the FIPS 140-2 tests. One of these RNGs is backdoored, leaking key material, while others suffer from significantly reduced unpredictability in their output sequences. To make our point even more straightforward, we show how files containing images can also fool the FIPS 140 family of tests. We end with a discussion on the security issues affecting an interesting and active project to create a randomness beacon. Their authors only tested the quality of their randomness with the FIPS 140 family of tests, and we will show how this has led them to produce predictable output that, albeit passing FIPS fails other randomness tests quite catastrophically.Keywords
Funding Information
- European Union’s Horizon 2020 research and innovation programme through the RAMSES Project (700326)
- CyberSec4Europe project (830929)
- LOCARD project (832735)
- EPSRC (EP/P011772/1)
- EconoMical, PsycHologicAl, and Societal Impact of RanSomware
- EPSRC’s Quantum Communications Hub (EP/T001011/1)
- Innovate UK Industrial Strategy Challenge Fund (106374–49229)
- AQuRand
This publication has 18 references indexed in Scilit:
- Backdoors in Pseudorandom Number Generators: Possibility and Impossibility Results2016
- Dual EC: A Standardized Back Door2016
- Built-in hardware pseudo-random test module for Physical Unclonable FunctionsNonlinear Theory and Its Applications, IEICE, 2014
- On-chip lightweight implementation of reduced NIST randomness test suite2013
- Stealthy Dopant-Level Hardware Trojans2013
- Objective assessment of the WebP image coding algorithmSignal Processing: Image Communication, 2012
- TestU01ACM Transactions on Mathematical Software, 2007
- A Generic Method for Secure SBox Implementation2007
- On the (Im)possibility of Cryptography with Imperfect Randomness2004
- A Threshold Cryptosystem without a Trusted Party2001