More Details on the Android JCA PRNG Flaw

I've spent a couple days reading the source code for the Pseudo Random number generators in Android mostly because there aren't many breakdowns of the vulnerability around, none that walk through the code explicitly anyway. After some discussion with some people from the Android Security Discussion Google Group I realized that the issue goes a little deeper than  just the super calls and constructor definition as I previously thought.

I was also mislead by grepcode---the site I was using to read the code---since it it wasn't directing me to the Android SecureRandom Implementation but rather OpenJDK!

So I thought I'd correct myself re-post about the issue and study the code directly from the Android repo namely ( https://android.googlesource.com/platform/libcore/+/jb-release/luni/src/main/java/java/security/SecureRandom.java )



Anyway Here's the official Android Secure Random constructor from the implementation in the Jelly Bean Release:

  89 public SecureRandom() {
  90    super(0);
  91    Services.refresh();
  92   Provider.Service service = Services.getSecureRandomService();
  93    if (service == null) {
  94        this.provider = null;
  95        this.secureRandomSpi = new SHA1PRNG_SecureRandomImpl();
  96        this.algorithm = "SHA1PRNG";
  97    } else {
  98        try {
  99            this.provider = service.getProvider();
  100           this.secureRandomSpi = (SecureRandomSpi)service.newInstance(null);
  101           this.algorithm = service.getAlgorithm();
  102       } catch (Exception e) {
  103           throw new RuntimeException(e);
  104       }
  105   }
  106}

extract from https://android.googlesource.com/platform/libcore/+/jb-release/luni/src/main/java/java/security/SecureRandom.java

The code from this constructor is important, specifically because the flaw in the implementation comes directly from how the PRNG is seeded implicitly, namely when the developer does not provide a seed via the constructor, and uses the default constructor's mechanism to seed it. This constructor could branch off into one of three directions each potentially seeding it differently (as far as we know from the source code quoted above). To start off with lets explore what happens when, lines 91 and 92 are executed, namely when the provider is sourced from the

Services.getSecureRandomService();

call. Well this method called getSecureRandomService is actually pretty simple it literally has 3 lines of code to it namely:

     * Returns the default SecureRandom service description.
     * Call refresh() before.
     */
    public static Provider.Service getSecureRandomService() {
        return secureRandom;
    }

All it does is return some class field called SecureRandom which is set up using the call in line 91 of SecureRandom's constructor, which is Services.refresh(), and this actually sets up a "cached" version of the SecureRandom provider. The Android folks probably wanted to void searching the list of available Providers by making sure one was cached ready to be returned when this method is invoked. As far as I know this call defaults to the Apache Harmony Secure Random Provider, we can see is being invoked explicitly in the true clause of the if statement after line 93. Back to the line 92 now, if everything worked fine in lines 92 and 91 we should have returned the Apache Harmony implementation of the SecureRandom provider, and the field called services would not be null.

This would drop us into line 97, the else class of the if statement, where the Providers metadata is set up and a call to

(SecureRandomSpi)service.newInstance(null);

which returns the Service Provider Interface (Spi) that allows us to make the important calls with regards to generating seeds and grabbing some secure pseudo random numbers. This call works as follows:

public Object newInstance(Object constructorParameter) throws NoSuchAlgorithmException {
            if (implementation == null || !className.equals(lastClassName)) {
                ClassLoader cl = provider.getClass().getClassLoader();
                if (cl == null) {
                    cl = ClassLoader.getSystemClassLoader();
                }
                try {
                    implementation = Class.forName(className, true, cl);
                    lastClassName = className;
                } catch (Exception e) {
                    throw new NoSuchAlgorithmException(type + " " + 

algorithm + " implementation not found: " + e);
                }
            }
            if (constructorParameter == null) {
                try {
                    return implementation.newInstance();
                } catch (Exception e) {
                    throw new NoSuchAlgorithmException(
                            type + " " + algorithm + " implementation not found", e);
                }
            }

What this means for the Android PRNG is that because of the way the constructor of Secure Random is set up, namely it makes a call to newInstance will a null argument, which will mean the constructor for

SHA1PRNG_SecureRandomImpl  

and return a Service Provider Instance wrapping an instance of this class, which is the actual provider. So then what happens when SHA1PRNG_SecureRandomImpl is invoked via the default construcutor? Here's the code for that:

 public SHA1PRNG_SecureRandomImpl() {

        seed = new int[HASH_OFFSET + EXTRAFRAME_OFFSET];
        seed[HASH_OFFSET] = H0;
        seed[HASH_OFFSET + 1] = H1;
        seed[HASH_OFFSET + 2] = H2;
        seed[HASH_OFFSET + 3] = H3;
        seed[HASH_OFFSET + 4] = H4;

        seedLength = 0;
        copies = new int[2 * FRAME_LENGTH + EXTRAFRAME_OFFSET];
        nextBytes = new byte[DIGEST_LENGTH];
        nextBIndex = HASHBYTES_TO_USE;
        counter = COUNTER_BASE;
        state = UNDEFINED;
    }

extract from  https://android.googlesource.com/platform/libcore/+/jb-release/luni/src/main/java/org/apache/harmony/security/provider/crypto/SHA1PRNG_SecureRandomImpl.java

All this does is set up some pointers that de-reference offsets inside the seed buffer and fills the buffer with some initialzation data, specific to the SHA1 algorithm, no problems here so far. Also the seed array would have the SHA1 initialization data in the last couple of addressed of the array, this data will be used as an internal state with which to generate Pseudo Random Data. How Pseudo Random the output of the PRNG is depends completely on how it is seeded initially.

Now according to how you would use SecureRandom, once you've setup an instance of SecureRandom via the default constructor you would then call SecureRandom.nextBytes(), which in turn would call the SHA1PRNG_SecureRandomImple.engineNextBytes(byte[]) method, which in essence handles seeding the PRNG if it was not explicitly seeded, here's how it does that:

 protected synchronized void engineNextBytes(byte[] bytes) {

        int i, n;

        long bits; // number of bits required by Secure Hash Standard
        int nextByteToReturn; // index of ready bytes in "bytes" array
        int lastWord; // index of last word in frame containing bytes
        final int extrabytes = 7;// # of bytes to add in order to computer # of 8 byte words

        if (bytes == null) {
            throw new NullPointerException("bytes == null");
        }

        lastWord = seed[BYTES_OFFSET] == 0 ? 0
                : (seed[BYTES_OFFSET] + extrabytes) >> 3 - 1;

        if (state == UNDEFINED) {

            // no seed supplied by user, hence it is generated thus randomizing internal state
            updateSeed(RandomBitsSupplier.getRandomBits(DIGEST_LENGTH));
            nextBIndex = HASHBYTES_TO_USE;

extract from https://android.googlesource.com/platform/libcore/+/jb-release/luni/src/main/java/org/apache/harmony/security/provider/crypto/SHA1PRNG_SecureRandomImpl.java

We can see that if the state of the engine is UNDEFINED it will proceed to seed the PRNG using RandomBitsSupplier.getRandomBits(DIGEST_LENGTH) where DIGEST_LENGTH is defined as 20, which is the block length of SHA1 in bytes. Here's how the seeding works; the getRandomBits calls a method called getUnixDeviceRandom(int) which looks like this:

  private static synchronized byte[] getUnixDeviceRandom(int numBytes) {

        byte[] bytes = new byte[numBytes];

        int total = 0;
        int bytesRead;
        int offset = 0;
        try {
            for ( ; ; ) {

                bytesRead = fis.read(bytes, offset, numBytes-total);


                // the below case should not occur because /dev/random or /dev/urandom is a special file
                // hence, if it is happened there is some internal problem
                if ( bytesRead == -1 ) {
                    throw new ProviderException("bytesRead == -1");
                }

                total  += bytesRead;
                offset += bytesRead;

                if ( total >= numBytes ) {
                    break;
                }
            }
        } catch (IOException e) {

            // actually there should be no IOException because device is a special file;
            // hence, there is either some internal problem or, for instance,
            // device was removed in runtime, or something else
            throw new ProviderException("ATTENTION: IOException in RandomBitsSupplier.getLinuxRandomBits(): " + e);
        }
        return bytes;
    }

extract from  https://android.googlesource.com/platform/libcore/+/jb-release/luni/src/main/java/org/apache/harmony/security/provider/crypto/RandomBitsSupplier.java

This byte array---as the previously quoted code indicates---is passed to updateSeed, which does the following:

 private void updateSeed(byte[] bytes) {

        // on call:   "seed" contains current bytes and current hash;
        // on return: "seed" contains new current bytes and possibly new current hash
        //            if after adding, seed bytes overfill its buffer
        SHA1Impl.updateHash(seed, bytes, 0, bytes.length - 1);

        seedLength += bytes.length;
    }

In summary SHA1Impl.updateHash the bytes pooled from /dev/urandom are fed into a hashing operation and saved in the seed[] array as the input to the next round of pseudo random byte generation.

This next part is where I believe the Android PRNG goes wrong, it involves how the counter is updated. The counter is stored in the seed array and serves to help insure the deterministic nature of a hashing algorithm like SHA1 does not negatively influence the pseudo random nature of the output. Ironically the way it writes the counter into the seed array actually destroys some of the psuedo random data pulled from /dev/urandom. The first 5 bytes of the seed array hold the hash of the /dev/urandom sampled data, but when the counter is updated it calculates the position in the seed array using a value in the seed array called seed[BYTES_OFFSET] which will be calculated as 0 after the initial sampling from /dev/uranom which means the counter data overwrites some of the actual seed used in proceeding hashing operations. Here's some of the problem code:

 lastWord = seed[BYTES_OFFSET] == 0 ? 0
                : (seed[BYTES_OFFSET] + extrabytes) >> 3 - 1;

As we can see lastWord will be calculated as 0 meaning that the following code, further down in SHA1PRNG_SecureRandomImpl:

        n = seed[BYTES_OFFSET] & 0x03;
        for (;;) {
            if (n == 0) {

                seed[lastWord] = (int) (counter >>> 32);
                seed[lastWord + 1] = (int) (counter & 0xFFFFFFFF);
                seed[lastWord + 2] = END_FLAGS[0];

            } else {

                seed[lastWord] |= (int) ((counter >>> RIGHT1[n]) & MASK[n]);
                seed[lastWord + 1] = (int) ((counter >>> RIGHT2[n]) & 0xFFFFFFFF);
                seed[lastWord + 2] = (int) ((counter << LEFT[n]) | END_FLAGS[n]);

extract from https://android.googlesource.com/platform/libcore/+/jb-release/luni/src/main/java/org/apache/harmony/security/provider/crypto/SHA1PRNG_SecureRandomImpl.java lines 349-361

will overwrite some of the /dev/urandom sampled data, which will cause consequtive calls to SecureRandom.nextBytes to generate pseudo random data from a deterministic internal state! Here's a screen shot of how the seed value or internal state converges, you should see that after just 3 calls, the seed converges to only having 64 bits of true pseudo random data:

 Each column is a separate run of the SHA1PRNG implementation currently on Android, the tests were done on an Ubuntu 12.04 machine, though this has little or no effect on the affect of the flaw. This printout shows the first 8 bytes of the seed array in SHA1PRNG_SecureRandomImpl.