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
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
In a 15,000 entry password file, a space of 241 salts ensures with high probability that every salt will be unique. For 212 possible salts, on the other hand, we can only expect about 3,991 different salts. At 224 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.