PRNG determinism?

Question

Looking at getDefaultPRNG() in java.security.SecureRandom makes me very unsure about how to use it. On my desktop, it uses sun.security.provider.NativePRNG, which reads from /dev/random and/or /dev/urandom which should be effectively unpredictable (non-deterministic) on Linux if you don't have direct access to the operating system. But on Windows, who knows? When I run this code on another machine or JVM, it could fall back to SHA1 or another deterministic algorithm.

If the output of SecureRandom is effectively unpredictable (dev/random), then it can be used by a web server to generate secure session tokens which are given to end users more-or-less raw. But if it is deterministic (digest), then exposing enough output to the end user effectively compromises all subsequent output.

For a deterministic PRNG, I should obscure each output with a few random bits (e.g. xor the low bits of the current time onto it). That would make it harder to guess where the deterministic RNG was in it's cycle. OTOH, If the PRNG uses /dev/random and the low bits of the time is already used as part of the seed, then using those same bits again is unnecessary or might even be counter-productive. The use models for the two kinds of "random" numbers are incompatible.

Unless I can be sure what kind of output SecureRandom is producing I can't use it properly. This seems like a design flaw to me. I think that the interface should guarantee either a deterministic, or effectively non-deterministic PRNG. I think this a necessary contract for users of all PRNGs (not just Java's SecureRandom).

Please tell me what I'm missing.

Answer 1

Assuming that nobody's screwed up the implementation, it should not matter what kind of RNG you get. This is because all java.security.SecureRandom implementations are supposed to be cryptographically strong, as defined in RFC 1750 §6.3 (emphasis mine):

6.3 Cryptographically Strong Sequences
In cases where a series of random quantities must be generated, an adversary may learn some values in the sequence. In general, they should not be able to predict other values from the ones that they know. […]

This includes the SHA1PRNG implementation, which is described as follows:

This algorithm uses SHA-1 as the foundation of the PRNG. It computes the SHA-1 hash over a true-random seed value concatenated with a 64-bit counter which is incremented by 1 for each operation. From the 160-bit SHA-1 output, only 64 bits are used.

Note two details here:

1. The internal state of the PRNG, which an attacker would need to learn in order to predict future output of the generator, consists of the random seed value and the counter. The output never contains these values, but only their SHA-1 hashes. In order to reconstruct the internal state from the output, an attacker would have to carry out a successful preimage attack on SHA-1, which is not currently believed to be feasible.

2. The output of the SHA-1 hash function is truncated to 64 bits, discarding a full 60% of it. Even if the internal state were propagated as in many non-cryptographic PRNGs, by repeatedly feeding the previous state through a mixing function (here, SHA-1), this truncation should be sufficient to prevent any reasonable attacker from reconstructing the full state, since they would effectively have to guess the remaining 96 bits of the state.

Thus, even though the output of SHA1PRNG is deterministic (given the initial seed, which the output never reveals), it should not be possible for any attacker, using currently known techniques and feasible computing resources, to predict its future output based on observed past outputs (or, indeed, even to distinguish its output from a truly random bitstream).

Now, for some caveats:

• The security of SHA1PRNG relies entirely on the seed value being secure (i.e. secretly and randomly chosen from a sufficiently large set of probabilities to withstand brute force guessing attacks). If the generator is seeded improperly, all the security properties may be lost.

  Normally, the first call to nextBytes() should automatically seed the generator from a system-provided source of randomness. However, this automatic seeding does not happen if setSeed() is called before the first call to nextBytes(). In this case, the internal PRNG state depends entirely on the user-provided seed, which, if poorly chosen, might not have much entropy. (This is particularly prone to cause confusion because calling setSeed() after the internal seeding just mixes the user-provided seed into the internal state, and so never reduces the randomness of the output.)

  Also, while the automatic seeding is supposed to be secure, this might not always be the case in practice. Notably, a flaw in the PRNG seeding on Android was used in 2013 to steal bitcoins from people running bitcoin software on Android devices.

• Even if the SecureRandom instance is used properly, the internal implementation of the PRNG might have bugs that compromise its security. Here's one paper I found that discusses weaknesses in various Java PRNG implementations.

If you don't trust the SHA1PRNG provided by your JRE, one option would be to explicitly request a NativePRNG implementation by using SecureRandom.getInstance("NativePRNG") instead of new SecureRandom(). Of course, this call may fail on systems that do not have such an implementation available, and in any case, still requires you to trust the OS native PRNG, and the Java interface to it provided by your Java crypto implementation.

The other alternative is to implement your own (deterministic) cryptographically secure pseudorandom number generator, such as HMAC_DRBG or CTR_DRBG from NIST SP 800-90A (note: do not use Dual_EC_DRBG!), and use it to generate your random numbers, possibly mixed (i.e. XORed) with the output of the OS native PRNG. The tricky part, here, is seeding the PRNG properly: if you have access to a secure OS RNG, you might as well use it directly; if not, you'd have to implement some ad hoc entropy collection scheme, which is difficult and easy to get wrong.

Answer 2

The key thing here is that even in the case that the final algorithm used is "SHA1PRNG", some entropy will be collected somehow for generating the seed that initializes the PRNG. So, it all depends on the seed. In this case, you can see in the code of sun.security.provider.SecureRandom that the seed is generated by the class sun.security.provider.SeedGenerator. What follows is a description from the documentation of this class:

This class generates seeds for the SHA1PRNG cryptographically strong random number generator. The seed is produced using one of two techniques, via a computation of current system activity or from an entropy gathering device. In the default technique the seed is produced by counting the number of times the VM manages to loop in a given period. This number roughly reflects the machine load at that point in time. The samples are translated using a permutation (s-box) and then XORed together. This process is non linear and should prevent the samples from "averaging out". The s-box was designed to have even statistical distribution; it's specific values are not crucial for the security of the seed. We also create a number of sleeper threads which add entropy to the system by keeping the scheduler busy. Twenty such samples should give us roughly 160 bits of randomness. These values are gathered in the background by a daemon thread thus allowing the system to continue performing it's different activites, which in turn add entropy to the random seed. The class also gathers miscellaneous system information, some machine dependent, some not. This information is then hashed together with the 20 seed bytes. The alternative to the above approach is to acquire seed material from an entropy gathering device, such as /dev/random. This can be accomplished by setting the value of the securerandom.source Security property to a URL specifying the location of the entropy gathering device, or by setting the java.security.egd System property. In the event the specified URL cannot be accessed the default threading mechanism is used.

Note that this procedure only happens if you don't seed the SecureRandom object yourself. If you provide your own seed, then the output of the PRNG will depend on that seed, obviously.

IMHO, I think that this procedure should be completely fine for your application, so you shouldn't be worried about the predictability of the source of randomness.

Other interesting references here:

• https://stackoverflow.com/questions/21254006/how-random-nextbytesbytes-generates-the-bytes-after-we-have-seed
• http://www.cigital.com/justice-league-blog/2009/08/14/proper-use-of-javas-securerandom/