Why is sharing the seed and using SecureRandom "deterministically" so bad? 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.
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.