Details on the Android JCA PRNG Flaws

Recently some bitcoin wallets suffered an attack that made use of a critical flaw in the way Java's Cryptography Architecture is implemented in Android. The following post discusses some of the technical details of the flaw by interpreting the code that causes the issue.

UPDATE: A more up to scratch attempt at explaining the vulnerability can be found here http://blog.k3170makan.com/2013/08/more-details-on-android-jca-prng-flaw.html 



Android implements Java's Cryptography Architecture which has quite a simple structure to it namely, the API calls we use encrypt, MAC, Sign and hash plaintexts are facilitated by classes called Providers which interface with actual libraries that hold the implementations of the cryptographic operations. In summary whenever you need to hash something with SHA1 you would first need to grab an instance of the SHA1 provider. The Providers translate configurations and arguments down the line to the actual libraries facilitating the call.

This is all in concept works quite well, although Java has made some questionable calls in the way the designed the classes that make use of the providers, for instance SecureRandom inherents from java.util.Random which isn't a terrbile thing though, but when looking at the way some of the class constructors were developed in SecureRandom I noticed the following:

87  public class SecureRandom extends java.util.Random {

...

143      public SecureRandom() {
144          /*
145           * This call to our superclass constructor will result in a call
146           * to our own <code>setSeed</code> method, which will return
147           * immediately when it is passed zero.
148           */
149          super(0);
150          getDefaultPRNG(false, null);
151      }

The very ominously named method called getDefaultPRNG does the following:

176  public SecureRandom(byte seed[]) {
177      super(0);
178      getDefaultPRNG(true, seed);
179  }
181  private void getDefaultPRNG(boolean setSeed, byte[] seed) {
182      String prng = getPrngAlgorithm();
183      if (prng == null) {
184          // bummer, get the SUN implementation
185          prng = "SHA1PRNG";
186          this.secureRandomSpi = new sun.security.provider.SecureRandom();
187          this.provider = Providers.getSunProvider();
188          if (setSeed) {
189              this.secureRandomSpi.engineSetSeed(seed);
190          }
191      } else {
192          try {
193              SecureRandom random = SecureRandom.getInstance(prng);
194              this.secureRandomSpi = random.getSecureRandomSpi();
195              this.provider = random.getProvider();
196              if (setSeed) {
197                  this.secureRandomSpi.engineSetSeed(seed);
198              }
199          } catch (NoSuchAlgorithmException nsae) {
200              // never happens, because we made sure the algorithm exists
201              throw new RuntimeException(nsae);
202          }
203      }
204      // JDK 1.1 based implementations subclass SecureRandom instead of
205      // SecureRandomSpi. They will also go through this code path because
206      // they must call a SecureRandom constructor as it is their superclass.
207      // If we are dealing with such an implementation, do not set the
208      // algorithm value as it would be inaccurate.
209      if (getClass() == SecureRandom.class) {
210          this.algorithm = prng;
211      }
212  }

The first dangerous move here is that SecureRandom is super classed by java.util.Random, this means when you make a call to SecureRandom without explicitly initializing your seed, you are actually initializing your seed using util.Random which means the following happens, keep in mind the argument passed to the super call in line 149:

93  public Random(long seed) {
94      this.seed = new AtomicLong(0L);
95      setSeed(seed);
96  }

So SecureRandom passes and argument of "0" via a super call which means that this actually the value used to set the seed! For the sake of completeness I'll include the source for java.util.Random's setSeed:

117  synchronized public void setSeed(long seed) {
118      seed = (seed ^ multiplier) & mask;
119      this.seed.set(seed);
120      haveNextNextGaussian = false;
121  }

So the actual flaw here is the fact that SecureRandom's PRNG mechanism by default is just another instance of java.util.Random in fact its a lot worst than that, since it forces util.Random to seed using "0" if the default constructor of SecureRandom is used so it actually makes a PRNG implementation that is not designed to provide cryptographic security even more insecure and predictable, here's what java.util.Random does should you instantiate it using the default construcutor:

77  public Random() { this(++seedUniquifier + System.nanoTime()); }
78  private static volatile long seedUniquifier = 8682522807148012L;

Basically it does what no cryptographic secure PRNG should ever do, get entropy from a predictable source!

Anyway that's all I could find for now, I hope this clarifies the issue and gives some people insight into how to spot flaws in PRNG designs.