How important is the randomness of the salt for Bcrypt?

Question

I need to generate salts for Bcrypt and I am trying to understand how random my PRNG needs to be for the salt not to be so weak as to make using Bcrypt pointless. I have five general classes of sources of randomness:

1. the PRNG that comes with Perl 5 seeded with the default seed (this seems to be the current fractions of the second, the address of the thing holding the fractions of the current second, the pid of the process, and the address of the Perl stack pointer all mixed together with some primes)
2. the PRNG that comes with Perl 5 seeded with some other seed
3. Some other Perl 5 based PRNG like Math::Random::Secure
4. Just reading bytes from /dev/urandom
5. Just reading bytes from /dev/random

The machines this code will run on already hit /dev/random too hard in my opinion (when the machine is busy, /proc/sys/kernel/random/entropy_avail dips below 500), otherwise this would be a non-issue and I would just use /dev/random. That said, if it is important enough, I will use /dev/random/ anyway (people don't setup new passwords that often).

Answer 1

Salt is only used to make output of hashing function different when run several times on same input and prevent rainbow table attacks. Cryptographic strength is provided by implementation of function itself. Any reasonably distributed RNG will do fine for salt, there's no need for true entropy.

Answer 2

Password salt need not be random or even secret. What’s important is that each password’s salt be unique. See the excerpt below from pages 52 and 53 in the second edition of Schneier’s Applied Cryptography.

Choosing bits randomly is an implementation that generates unique salt with some small probability of collision. This is generally regarded as a decent trade because such a salt generator does not require elevated privilege to read the list of salt values currently in use in the system.

With bcrypt, salt is stored in plaintext for later authentication attempts. This means your system’s entire list of hashed passwords could be compromised. At that point, random salt does not help. Note the punchline in the last paragraph the excerpt below. Salt confounds dictionary attacks, but only to a point.

The conservative approach is to use a cryptographically secure RNG to select salt values “just in case,” but depending on the value of what you’re trying to protect and thus how much effort an adversary would be willing to invest, that may be overkill.

Dictionary Attacks and Salt

A file of passwords encrypted with a one-way function is still vulnerable. In his spare time, Mallory compiles a list of the 1,000,000 most common passwords. He operates on all 1,000,000 of them with the one-way function and stores the results. If each password is about 8 bytes, the resulting file will be no more than 8 megabytes; it will fit on a few floppy disks. Now, Mallory steals an encrypted password file. He compares the file with his file of encrypted possible passwords and sees what matches.

This is a dictionary attack, and it’s surprisingly successful (see Section 8.1 [“Generating Keys”]). Salt is a way to make it more difficult. Salt is a random string that is concatenated with passwords before being operated on by the one-way function. Then, both the salt value and the result of the one-way function are stored in a database on the host. If the number of possible salt values is large enough, this practically eliminates a dictionary attack against commonly used passwords because Mallory has to generate the one-way hash for each possible salt value. This is a simple attempt at an initialization vector (see Section 9.3 [“Cipher Block Chaining Mode”]).

The point here is to make sure Mallory has to do a trial encryption of each password in his dictionary every time he tries to break another person’s password, rather than just doing one massive precomputation for all possible passwords.

A lot of salt is needed. Most UNIX systems only use 12 bits of salt. Even with that, Daniel Klein developed a password-guessing program that often cracks 40 percent of the passwords on a given host system within a week [847,848] (see Section 8.1). David Feldmeier and Philip Karn compiled a list of about 732,000 common passwords concatenated with each of 4096 possible salt values. They estimate that 30 percent of passwords on any given host can be broken with this list [561].

Salt isn’t a panacea; increasing the number of salt bits won’t solve everything. Salt only protects against general dictionary attacks on a password file, not against a concerted attack on a single password. It protects people who have the same password on multiple machines, but it doesn’t make poorly chosen passwords any better.

561. D.C. Feldmeier and P.R. Karn, “UNIX Password Security—Ten Years Later,” Advances in Cryptology—CRYPTO ’89 Proceedings, Springer-Verlag, 1990, pp. 44–63.
847. D.V. Klein, “ ‘Foiling the Cracker’: A Survey of, and Implications to, Password Security,” Proceedings of the USENIX UNIX Security Workshop, Aug 1990, pp. 5–14.
848. D.V. Klein, personal communication, 1994.