# Birthday-attack calculation in planning password salting strategy

The book Cryptography Engineering by Fergusun, Schneier, Kohno section 2.7.1 explains Birthday Attacks: "In general, if an element can take on N different values, then you can expect the first collision after choosing about sqrt(N) random elements." This is an approximation.

We are planning to upgrade the way we store password hashes and salts in our database. We need to allow for something on the order of 100 million salts, which is between 26 and 27 bits (two to the 26 or 27 power; I don't know how to format superscripts here). Taking the square that gets me to about 54 bits.

Seven bytes is 56 bits. Assuming that /dev/urandom is sufficiently random (evenly distributed and not predictable), do seven bytes of random salt meet the Birthday Attack criteria?

I realize this is not the only consideration in picking the salt. I'm trying to find out if I'm correctly applying the Birthday Attack theory.

EDIT: The final exercise at the end of the named book chapter asks the same question, which I can now answer confidently!

• Hmm, I'm wondering, you are actually only interested in the salt / PW combination regarding possible dupes, right? That would lower the limit somewhat. 8-16 bytes is the sensible default though, do you really need that additional byte? Sep 18, 2015 at 16:17
• Never underestimate the number of users whose password is "password". Sep 18, 2015 at 20:53
• The actual number of such users in our database is appalling. But a difficult topic to satisfactorily address in practice! Sep 18, 2015 at 21:03
• May not be applicable to you, but other organizations using the same scheme increase the probability of a global collision, which may be exploitable in the case of database leaks (org doxing). Having a second fixed salt for all users can mitigate this. Sep 19, 2015 at 0:36
• In the same vein, 100 million should approximate the number of total salts over the lifetime of your database, rather than a particular, even maximal snapshot. (Using a new salt when password changes may be a good idea.)
– otus
Sep 19, 2015 at 7:41

Yes! I'd recommend at least 64 bits, but that's only because powers of two are convenient and space is cheap. Furthermore, usually a salt of the block size of the hash you're using is usually best, because salting at all will almost always involve an extra block, so why not fill it up given that there will be no performance impact?

But once again, yes, you're correct in your analysis of the Birthday Problem.

• Furthermore, sqrt(N) is only an approximation in that you're dealing with randomness. Statistically speaking, it is the exact point at which it becomes more likely than not to have a collision. Sep 18, 2015 at 15:48