Salt Collisions

A salt collision occurs when two password encodings use the same salt. Ideally, there should be no salt collisions--the salts of different password encodings should be different even across password files. Because traditional crypt uses only 4,096 different salts, it leads to many collisions, as illustrated in Figure 4. To optimize dictionary attacks, an attacker can group encrypted passwords by salt, and hash each candidate password from a dictionary only once per salt. The resulting speedup can roughly be determined as

$$\frac{\mbox{number of passwords}}{\mbox{number of different salts}}.$$

If salts are generated with a good random number generator, the expected number of different salts for n password entries with s possible salts is

$$EV(n,s) = \sum^{n-1}_{i=0} \Bigl(\frac{s-1}{s}\Bigr)^i = s - (s-1)^n s^{1-n}.$$

In a 15,000 entry password file, a space of 2⁴¹ salts ensures with high probability that every salt will be unique. For 2¹² possible salts, on the other hand, we can only expect about 3,991 different salts. At 2²⁴ possible salts, the number becomes 14,994. In practice, however, we find that the number of salt collisions is generally higher than expected. The reason is that many operating systems generate poor random numbers.

  

Figure 4: Distribution of expected different salts depending on the salt space against the number of entries in a password file.