3
$\begingroup$

I find that for every 100 password salts in our database, we only average 94.73 distinct salt values (averaged over a total of around 18 million). Is there a way to take that observation and calculate the amount of effective entropy (or whatever is the correct term) we have in our salts?

Clearly we need to improve how we generate salts. But, meanwhile, I'd like to better understand the theory behind the observation.

EDIT: I have asked this question aimed at correctly generating our password salts.

Improve this question
$\endgroup$
1
  • $\begingroup$ Sorry to stop you in your tracks people, but comments are not for extended discussion; this conversation has been moved to chat accordingly. Please feel free to continue your lively communication in the chat, while keeping the comments area open for stuff like minor or transient information… thanks. $\endgroup$
    – e-sushi
    Sep 19, 2015 at 4:27

1 Answer 1

Reset to default
4
$\begingroup$

It is possible to reverse the birthday bound calculation. You can get an easily computable approximation using the expected number of collisions:

If you had random $n$-bit salts, after $k$ values you would expect $2^{-n}\binom{k}{2}$ collisions. If the collisions are rare, they are mostly single collisions, so there are approximately $u = k-2^{1-n}\binom{k}{2}$ unique, non-colliding values. So your results $k = 1.8 \cdot 10^7$ and $u \approx 1.7 \cdot 10^7$ could be generated with $n \approx 28.3$. That is, they could be random numbers between zero and 340 million, give or take.

More exact formulas are found in the answers to this question Neil Slater linked in the comments. With your numbers they give an answer of around 27.3. This makes sense, because the approximation above ignored multi-collisions, which leave more unique values than estimated.

However, that does not imply they have 27-28 bits of entropy. They could have considerably less. For example, they could instead be the results of a counter that wraps around after ~17500000 items. There is no way to know with just the data you gave. They very likely do not have more than about 28 bits of entropy each, however.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Related question: stats.stackexchange.com/questions/9240/… . . . I have to say the maths there is beyond me though, I just found it when tryin to research an answer here. $\endgroup$
    – Neil Slater
    Sep 18, 2015 at 19:10
  • 1
    $\begingroup$ @NeilSlater, ok that's basically what I tried to approximate above. Now to check if my approximations holds... $\endgroup$
    – otus
    Sep 18, 2015 at 19:15
  • 1
    $\begingroup$ Ok, based on an answer there, a better guess would apparently be $n \approx 27.3$, but my floating point math may be underflowing so I'm not particularly confident in that one. The order of magnitude should be about right anyway. $\endgroup$
    – otus
    Sep 18, 2015 at 19:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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