Cryptology ePrint Archive: Report 2013/338

Security Analysis of Pseudo-Random Number Generators with Input: /dev/random is not Robust

Yevgeniy Dodis and David Pointcheval and Sylvain Ruhault and Damien Vergnaud and Daniel Wichs

Abstract: A pseudo-random number generator (PRNG) is a deterministic algorithm that produces numbers whose distribution is indistinguishable from uniform. A formal security model for PRNGs with input was proposed in 2005 by Barak and Halevi (BH). This model involves an internal state that is refreshed with a (potentially biased) external random source, and a cryptographic function that outputs random numbers from the continually internal state. In this work we extend the BH model to also include a new security property capturing how it should accumulate the entropy of the input data into the internal state after state compromise. This property states that a good PRNG should be able to eventually recover from compromise even if the entropy is injected into the system at a very slow pace, and expresses the real-life expected behavior of existing PRNG designs.

Unfortunately, we show that neither the model nor the specific PRNG construction proposed by Barak and Halevi meet this new property, despite meeting a weaker robustness notion introduced by BH. From a practical side, we also give a precise assessment of the security of the two Linux PRNGs, /dev/random and /dev/urandom. In particular, we show several attacks proving that these PRNGs are not robust according to our definition, and do not accumulate entropy properly. These attacks are due to the vulnerabilities of the entropy estimator and the internal mixing function of the Linux PRNGs. These attacks against the Linux PRNG show that it does not satisfy the "robustness" notion of security, but it remains unclear if these attacks lead to actual exploitable vulnerabilities in practice. Finally, we propose a simple and very efficient PRNG construction that is provably robust in our new and stronger adversarial model. We therefore recommend to use this construction whenever a PRNG with input is used for cryptography.

Category / Keywords: Randomness; Entropy; Security models; dev/random

Original Publication (with minor differences): ACM Conference on Computer and Communication Security (CCS), November 2013
DOI:
10.1145/2508859.2516653

Date: received 3 Jun 2013, last revised 20 Oct 2013

Contact author: ruhault at di ens fr

Available format(s): PDF | BibTeX Citation

Note: Paper updated with a new attack on the PRNG.

Version: 20131020:193616 (All versions of this report)

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]