This will be a sum up of a Paper written by Kai Michaelis, Jörg Schwenk and me, which was presented at the Cryptographers’ Track at RSA Conference 2013. You can get the slides of my presentation here and our full Paper here. We performed an analysis on the random sequences generated by common Java libraries shipping with PRNGs (mostly SecureRandom) and found striking weaknesses under special conditions. To keep the post as short as possible the description of the algorithms used by the PRNGs, the detailed bug description and the results of the statistical tests are omitted, but available in the Paper. Our investigation covered the PRNGs itself, as well as their entropy collectors used for seeding (e.g., if no real number generator is available).
The bottom line: don’t use PRNGs when good randomness is needed!
The quality was graded with multiple means. At first, we performed a code analysis and (successfully) tried to find and identify coding mistakes leading to serious defects. Second, we performed statistical tests on the generated random sequences. Finally, we stressed the algorithms under special conditions (high system load, some components not available, etc.)
First library: Apache Harmony
Although retried, Apache Harmony survives as part of the Android Source Code (see here) and is thus part of million devices.
Weaknesses
One of the found bugs directly affects the Android platform. Th other bug is only present in Apache Harmony and NOT the Android Source Code.
FIRST – When creating a self seeding SecureRandom instance (by calling the constructor without arguments and subsequent setSeed() call), the code fails to adjust the byte offset (a pointer into the state buffer) after inserting a start value. This causes a counter and the beginning of a padding (a 32 bit word) to overwrite parts of the seed instead of appending.
SECOND – When running under a Unix-like OS a new SecureRandom instance is seeded with 20 bytes from the urandom or random device. If both are unaccessible the implementation provides a fall-back seeding facility. Once the seeding facility has gathered the requested amount of bytes, for unknown reasons the most significant bit is set to zero. As a consequence, the effective seed of a SecureRandom instance is only 7/8 for each requested byte, degrading security (of only 64 bits due to the first bug) by another 8 bits to 56 bits. Even worse, due to another invalid modulo reduction the entropy of a single call to the seeding facility is limited to only 31 bits. The problems of the entropy collector are obvious when having a look at the generated bytes. The following graph depicts two consecutive bytes a a single point.
A complete lack of values above 127 in each direction.
Second library: GNU Classpath
GNU Classpath is partly used by the famous IcedTea project and therefore mostly known for the 64-bit Java Browser-plugin on Linux systems.
Weaknesses
The library contains a significant weakness regarding internal states. The bug is related to identical Initialization Vectors (IVs) used for the hash function. This reduces the number of unknown bytes of the internal state from 32 to only 20. The Entropy Collector algorithm is hard to predict, which is good, but it relies on threads competing for CPU time which can easily be influenced (by putting the system under high load). The thread runtime checks are not strict enough to ensure good randomness. The following Figure shows difficulties concerning equal distribution of the output, leaving large patches. The Figure shows the Entropy Collector performing under high system load.
In contrast, the Entropy Collector performs as expected under normal conditions:
Third library: OpenJDK
The official free open-source implementation of Java SE is in most parts equal to the version provided by Oracle. Most Java users are very likely to rely on this code.
Weaknesses
The code review bared no obvious weaknesses. The Entropy Collector relies on threads incrementing counters, but in contrast to GNU Classpath enforces minimal requirements on runtime. The resulting graph is filled very balanced.
Fourth library: The Legion of Bouncy Castle
This library is somehow different to the other one’s, because it is only a very comprehensive library for all kinds of cryptographic algorithms. It ships with multiple replacements for SecureRandom.The Entropy Collector of BouncyCastle can run in two operation modes, a fast and a slow mode, where different amounts of bytes are used for random output.
Weaknesses
As in the OpenJDK case, Bouncy Castle’s SecureRandom replacement (DigestRandomGenerator) revealed no obvious bugs. On the contrary, the VMPCRandomGenerator is known to be vulnerable. The Entropy Collector was in both modes able to fill the graph very balanced.
Summary
Very interesting is the limited and not configurable internal state size of the inspected implementations. Nearly all implementations rely on SHA-1 as hash (compression) function. Hence, they seem to be useless for key generation > 160bit. Only Apache Harmony relies on an internal state of 512 bit, but suffers from coding mistakes. The blog post omits many details and statistics in order to provide only a quick and dirty review of the libraries – if you are interested in more details and further results you are invited to read the full paper.
Reference: Weaknesses in Java Pseudo Random Number Generators (PRNGs) from our JCG partner Christopher Meyer at the Java security and related topics blog.
