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
So what happened with
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.
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.