# 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? – Maarten Bodewes Sep 18 '15 at 16:17
• Never underestimate the number of users whose password is "password". – Reid Rankin Sep 18 '15 at 20:53
• The actual number of such users in our database is appalling. But a difficult topic to satisfactorily address in practice! – Edward Barnard Sep 18 '15 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. – Richie Frame Sep 19 '15 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 '15 at 7:41