Why is sharing the seed and using SecureRandom "deterministically" so bad?

Question

I've recently been reading an article about "using cryptography to store credentials", and I would love it someone explained this in more detail…

Up until Android 4.1, Android used a SecureRandom provider, that, given the same seed, after using setSeed(seed), it would generate the exact same stream of bytes. Because of this, people used this fact to generate AES keys for encrypting, only sharing the seed between users.

Google found out about this and introduced a new SecureRandom provider in 4.2 (based on OpenSSL's PRNG), which, for the same setSeed(seed) generates different outputs. They also recommend using PBE (PBKDF2 etc) for doing key generation, which is a fair recommendation (due to bruteforcing protection).

Why is sharing the seed and using SecureRandom "deterministically" so bad? Is it a bug?

This technique is even mentioned in the RFC1750

It should be noted that if your technique for generating a sequence of key values is fast enough, it can trivially be used as the basis for a confidentiality system. If two parties use the same sequence generating technique and start with the same seed material, they will generate identical sequences. These could, for example, be xor'ed at one end with data being send, encrypting it, and xor'ed with this data as received, decrypting it due to the reversible properties of the xor operation.

Answer 1

Both determinism and non-determinism are useful. The question is which one you use for which purpose.

Determinism is generally useful for expanding a short secret to a long one. For example, you may keep a short random secret and use it to generate a long keystream that you can XOR against messages for encryption and decryption (such as described in the RFC quote). When one string is generated deterministically from another, then the derived string is considered no more secure than the original since knowing the original allows the derived one to be calculated.

Non-determinism is generally used to generate a random value that no one else knows (yet). If you need to generate a key and don't want someone else to guess it, you need a non-deterministic (or at least something that we feel is close enough to non-deterministic) process. If you instead used a deterministic one, then the output no stronger than input and the problem hasn't been solved since you need an strong input. Somewhere in the derivation chain you need something strongly non-deterministic so that the output can't be guessed.

Generally, cryptographic keys are derived non-deterministically and then the cryptographic operation (such as encryption or signing) performed by them is deterministic. (At least, you can think of it as being deterministic, technically it's still supposed to be randomized in some way.)

One last piece of the puzzle: In practice, non-deterministic random number generators accumulate non-deterministic entropy and use that to seed a deterministic process that generates output. This is because non-deterministic entropy is relatively hard to come by and it generally needs to be compressed/whitened before being output. The output was generated deterministically from a non-deterministic source, so it is considered non-deterministic itself.

All of that is a very high overview and is light on details, but the concepts are necessary to understand recent issues on SecureRandom.

So what happened with SecureRandom?

• SecureRandom provides random output for things like key generation, so it needs to be non-deterministic. SecureRandom keeps an internal random state that it deterministically generates output from, and that internal state is supposed to be non-deterministic. So although the output is deterministically derived from an internal seed, when the seed is non-determinstic we consider the SecureRandom output to be non-deterministic. SecureRandom also allows the user to provide their own input seed as well.

  SecureRandom had a bug where the internal state, if not seed was provided by a user, was automatically filled from a random source like /dev/urandom, but it was done improperly. The amount of random data actually used was much smaller than it should have been. Not having enough random input lead to cryptographic problems.

• Another problem was that when a seed was provided by the user to SecureRandom, that seed would override the existing internal state. This meant that if the user called SecureRandom without seeding it they got deterministic output from a non-deterministic source, but if they provided a seed then they got deterministic output from their own input and their input (very likely) wasn't strong enough to be cryptographically strong itself. I don't think this behavior was a bug, but it was changed anyway to prevent innocent misuse. The fix was to add the seed to the internal state, rather than to use it to replacing the state.

Summary: When SecureRandom was used without a seed, the output was supposed to be non-deterministic, but it was based on too few non-deterministic bytes to be secure. When a seed was provided, the output only depended on the seed which was behavior that might confuse developers who thought a custom seed would add to the internal state rather than replace it.

Answer 2

Amongst others there are these things possibly going wrong:

• If people enter initial seeds, they usually do not use proper independent and identically distributes random variables, but code words, phrases, passwords etc. PBKDF2 is lot better way to construct the shared secret(s) from the input. RNG (random number generator) is not intended to do well as key derivation function.
• If the SecureRandom is used for some other tasks, it can be fatal if it has been initialized deterministically, for instance, if signing using DSA or ECDSA uses flawed RNG, it'll allow compromising the private key.

NIST's SP 800-90 definition of RNG (or as they call it DRBG, deterministic random bit generator) contains the idea that when you ask to "reseed", you do not "set" the seed, but you add material to the RNG. You may look up that standard for details. Overall, anyway this idea is very good and work well together with the intended uses of RNG: to generate as unpredictable output as possible. If the target is not unpredictable output, some other like key derivation, then it is better to use a function designed for this purpose. Long story short, many modern RNGs have this same idea implemented.

---

The recommendation from RFC 1750 is bit dated. Please, read some of latests questions on OTP or Vernam cipher to see why this may be ill-adviced. Long story short: few modern RNG's offer key stream good enough for this purpose. Rather than using RNG+xor, just pick a modern stream cipher instead.