Characterization of Real-Life PRNGs under Partial State Corruption

International audiencePseudo-random number generators (PRNGs) are widely used as a randomness source in cryptographic applications. It is essential for their security that the internal state, in which the entropy is accumulated, is kept secret. However, this assumption is unrealistic for PRNGs that are implemented in software, as the internal state can be partially corrupted through memory corruption bugs such as buffer overflows or through faults attacks. The recent Heartbleed bug gives us a concrete illustration of this vulnerability. In this work we study several widely used PRNGs from different popular providers, including OpenSSL, OpenJDK, Android, IBM and Bouncy Castle and we characterize how they handle their internal states. We formalize a framework based on the most recent and strongest security model called robustness of PRNGs to analyze these PRNGs and their implementations. With this framework we capture the notion of how much of the internal state must be corrupted in order to generate a predictable output. Using this framework, we determine the number of bits of the internal state that an attacker needs to corrupt in order to produce a predictable output. We also show that two of the PRNGs do not require state compromise to generate a non-random output. To the best of our knowledge, we present the first thorough characterization of an IBM implementation of a PRNG