Efficient random number generator to produce the salt for PBKDF2

Question

I have been looking for an algorithm that generates random numbers and this algorithm has to be secure.

I am going to use this algorithm to generate a salt that will be used in PBKDF2.

Through my reading, I found that ISAAC is a fast algorithm and better than RC4, but it is not good in terms of the security. Also, I thought about the Blum-Blum-Shub algorithm, but some articles said it is not efficient.

Which algorithm is both secure and reasonably efficient for PBKDF2 salt generation?

Answer 1

Since the goal is to generate the salt for PBKDF2, there is no need for an efficient (as in fast) random generator: PBKDF2 is (purposely) compute-intensive. Further, in many uses of PBKDF2 (e.g. storing a password), the salt is generated once, stored, and reused many times, further lowering the concern over efficiency of the salt generation. As the saying goes: premature optimization is the root of all evil.

In this usage, you also do not need a precisely uniform distribution (as would be the case for a random generator used e.g. in a casino machine). The (extremely slight) bias of RC4 is not a concern in the context of salt generation.

In that context, by far the most important criteria is that the generator should have low odds of generating twice the same value. As shown by recent anecdote in the context of RSA key generation (also here updated), that's difficult to implement correctly, especially on network appliances. The essential problem is that different runs of any deterministic RNG (such as RC4 or ISAAC) will generate the same result if fed the same input. Thus what matters is the seed material of the generator, and if/how its state is preserved across runs.

Two simple implementations of a generator that does not repeat are

1. Increment a persistent integer (stored e.g. in a data base), then output it. The integer should be wide enough to never overflow, or the number of runs limited.

2. Obtain the UTC time to some granularity, wait at least as long as that granularity, plus twice the maximum absolute value of the uncertainty of the source of time, plus one second (to account for leap second), then output the result.

Notice that both methods assume a single instance runs, and can be broken if the attacker can influence the system (reset the persistent integer, alter the clock setting...). And of course, these generators are predictable, not random generators. But assuming the availability of a single secret randomly-seeded Key, this is easy to fix: given the output N of a generator that does not repeat, output HMAC(Key,N).

Practical designs of good software RNGs combine seed material gathered using several techniques, including the above, CPU clock since boot, process time, RAM content at boot, hard disk and network latency, mouse position, keyboard presses and their timing, hardware serial numbers such as in hard disk and network cards...

For more in-depth discussion on the desirable properties and design of software RNGs, see yarrow. For physical design and testing, see e.g. Design of Testable Random Bit Generators.

Answer 2

If you're generating the salt for PBKDF2, well, you really don't care about efficiency (because the evaluation of PKBKD2 is itself quite expensive by design).

In addition, password salts do not have very high security requirements. We really don't care if someone is able to distinguish a valid salt value from a random value. All we really care about is that it is unlikely that two people get the same salt, and that it is nontrivial to predict the salt value in advance. Both RC4 and ISAAC meets those requirements.

On the other hand, if you are generating random numbers for anything security related, I would personally suggest you look at the random number generators found in NIST SP 800-90 (except for the Dual_EC_DRBG); they're designed by people who know what they're doing, and they're plenty fast for what you need. The only thing you need to worry about is entropy collection (and you have to worry about that for any random number generator). Yes, they're overkill for what you need; however, overkill isn't necessarily a bad thing.

Answer 3

The number one mistake people do when they need random numbers, is not that they use a half-decent prf such as RC4, but that they don't seed it with sufficient entropy. If you get to choose using RC4 with a 128 bit seed packed with fresh entropy, and a state of the art implementation of NIST SP 800-90 seeded with a few calls to a build in rand function, you are better of with a properly seeded RC4.

Answer 4

Randomness is not a strict requirement for the salt of PBKDF2. What PBKDF2 needs is that you do not reuse any salt value. Random salts with a good random generator are just an easy way to achieve that, without keeping a global state somewhere. But you could use a simple counter value (utterly non-random) and it would still be secure. So don't sweat it on the randomness.

If you need a very fast and good RNG (i.e. not for PBKDF2, which has only very indirect needs for randomness, and also can accomodate a slow RNG since PBKDF2 is very slow, and that's a deliberate feature), then:

• Get a really good seed value from the operating system (/dev/urandom, CryptGenRandom()...); don't try to gather randomness yourself, the OS is much better at it.
• Use that seed as key in a cryptographically secure stream cipher. Stream ciphers are not to be improvised; rather, rely on algorithms which have been thoroughly looked at by cryptographers, such as the ones from the eSTREAM project.

Yet you would need a rather specific situation for the OS RNG to be a performance bottleneck (and salt generation for PBKDF2 is certainly not such a situation).