Christopher Meyer

About Christopher Meyer

Chris works as a researcher and is eagerly looking for bugs in SSL/TLS, the Java platform and various applications. In addition, he is primarily interested in secure coding and exploiting coding mistakes.

Weaknesses in Java Pseudo Random Number Generators (PRNGs)

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.

Fast Mode

Slow Mode

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.

Related Whitepaper:

Web Application Security; How to Minimize Prevalent Risk of Attacks

Vulnerabilities in web applications are now the largest vector of enterprise security attacks.

Stories about exploits that compromise sensitive data frequently mention culprits such as cross-site scripting, SQL injection, and buffer overflow. Vulnerabilities like these fall often outside the traditional expertise of network security managers.

Get it Now!  

Leave a Reply


nine + 5 =



Java Code Geeks and all content copyright © 2010-2014, Exelixis Media Ltd | Terms of Use | Privacy Policy
All trademarks and registered trademarks appearing on Java Code Geeks are the property of their respective owners.
Java is a trademark or registered trademark of Oracle Corporation in the United States and other countries.
Java Code Geeks is not connected to Oracle Corporation and is not sponsored by Oracle Corporation.

Sign up for our Newsletter

20,709 insiders are already enjoying weekly updates and complimentary whitepapers! Join them now to gain exclusive access to the latest news in the Java world, as well as insights about Android, Scala, Groovy and other related technologies.

As an extra bonus, by joining you will get our brand new e-books, published by Java Code Geeks and their JCG partners for your reading pleasure! Enter your info and stay on top of things,

  • Fresh trends
  • Cases and examples
  • Research and insights
  • Two complimentary e-books