10

There was a lot of news in the past year about exploitable weaknesses in cryptography which originated from weak random number generators. In some cases it was negligence on side of the developers, in others it was intelligence organisations intentionally sabotaging standards for secure RNG generation.

What about the implementation of the SecureRandom random number generator used in Oracle's JavaVM? What algorithm is it using when you don't specify one? And is that algorithm and its implementation secure enough for use in cryptography?

Philipp
  • 49,017
  • 8
  • 127
  • 158

1 Answers1

14

The JDK complete source code (not only the standard classes, but also the Sun-specific classes and the C++ native code) used to be available under a "research license", and I have a copy on my disk, for JDK 1.6 (I suppose that nowadays you would go to OpenJDK).

We see that creating a java.security.SecureRandom instance implies invoking the default PRNG which happens to be the Sun-specific class sun.security.provider.SecureRandom.

The PRNG is seeded from sun.security.provider.SeedGenerator which in turn will try to rely on what the OS provides, i.e. /dev/urandom or /dev/random on Unix-like systems (such as Linux), CryptoAPI's CryptGenRandom() on Windows. If such things are not available (or deactivated from JVM's config), then the seed will be extracted by timing the speed at which the OS can switch contexts between threads; this is a fallback mechanism which is very rarely, if ever, triggered.

The seed is expanded with what appears to be a custom, home-made PRNG based on SHA-1. It works like this:

  • There is a 160-bit state s, which is 20 bytes, and is also interpreted as an integer modulo 2160 by applying the little-endian convention.
  • Output is produced by 20-byte chunks.
  • To produce the next chunk c:
    • c = SHA-1(s)
    • s = s + c + 1 mod 2160

There is a mechanism which ensures that s is indeed changed at some point; if s appears to be unchanged by the update, then its first byte is incremented forcefully. This is never invoked; probability of such an occurrence is 2-160 and forcing it with a special seed would require breaking SHA-1's preimage resistance, which we don't know how to do.

Cryptographically speaking, this is not atrocious; it should reach a cycle, on average, only after about 280 chunks, and the cycle should have the same average length; that's a lot (about 24 millions of billions of gigabytes), so that's good. If SHA-1 is a random oracle then the PRNG is "obviously" secure as long as attackers cannot enumerate a 160-bit space (they realistically cannot) and a given seed is not used to produce more than 24 millions of billions of gigabytes (and it won't, not in any reasonable or even unreasonable time). We know that SHA-1 is not a random oracle, but it still looks randomish enough.

Personally, I would not deem this PRNG a problem for cryptographic usage; it has no "magic constant" and thus very unlikely to be backdoored. The one bad part of it is that it is non-standard, thus understudied.

If (when) I need to have, in Java, randomness which is good enough for formal cryptography (i.e. good, and also demonstrably good for regulatory purposes), then I use java.security.SecureRandom to generate an initial seed (at least 16 bytes), that I then run through HMAC_DRBG (specified in NIST SP800-90A)(the same publication contains the Dual_EC_DRBG of sinister fame, but HMAC_DRBG is nonetheless considered to be fine and clean by cryptographers).

Community
  • 1
Tom Leek
  • 170,038
  • 29
  • 342
  • 480