1
$\begingroup$

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!

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ 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? $\endgroup$
    – Maarten Bodewes ♦
    Sep 18 '15 at 16:17
  • 1
    $\begingroup$ Never underestimate the number of users whose password is "password". $\endgroup$
    – Reid Rankin
    Sep 18 '15 at 20:53
  • $\begingroup$ The actual number of such users in our database is appalling. But a difficult topic to satisfactorily address in practice! $\endgroup$
    – Edward Barnard
    Sep 18 '15 at 21:03
  • 2
    $\begingroup$ 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. $\endgroup$
    – Richie Frame
    Sep 19 '15 at 0:36
  • 1
    $\begingroup$ 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.) $\endgroup$
    – otus
    Sep 19 '15 at 7:41
4
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 5
    $\begingroup$ 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. $\endgroup$
    – Reid Rankin
    Sep 18 '15 at 15:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.