4 ms·

> There also should never be a rule about maximum length What about hash collisions? Is there a good way to handle that?

• drostie 15y ago
  Collisions can be handled with two different approaches. The first problem with collisions is when two people have the same password. This is one of the reasons you should salt a password before hashing. If you choose a random m-bit salt then due to the "birthday phenomenon", you can go to around 2^{m/2} users before there is a significant risk that some pair of them shares the same password. This actually isn't too hard to understand. If you have N people who want to high-five each other (e.g. N ~= 18 at the end of an Ultimate frisbee match, everyone from both teams generally high-fives everyone on their own team as well as everyone on the other team), then there are N * (N - 1) / 2 high-fives, or roughly N^2 / 2 for very large N. To see this, enumerate all of the pairs (1, 1), (1, 2), ..., (N, N -1), (N, N), N^2 of them in total, then cross out the ones of the form (k, k), N of them in total, because nobody high-fives themselves, and then cross out the half (a, b) for which a > b, because 3 high-fiving 2 is the same as 2 high-fiving 3. Then (N^2 - N) / 2 = N (N - 1) / 2. But if each of these comparisons has a roughly independent chance p of sharing the same salt, like 1/2^72, then the number you need before you get towards a 50/50 chance is approximately p * N^2/2 = 1/2, or N = sqrt(1/p). If p = 1/2^72, sqrt(1/p) = 2^36 = 68.7 billion. So a 72-bit random salt will make sure that everyone shares a salt with less than a billionth of your users or so. If you want even better, you might want to know that a salt doesn't have to be random, and you could generate them incrementally to get even more security. For example in Node.js: var new_salt = (function () { var counter = 0, buf = new Buffer(8); return function () { counter = (counter + 1) % 1e6; buf.writeDoubleLE(new Date().getTime() * 1e6 + counter, 1); return buf.toString('base64') }; }); Now as long as I have fewer than one million new passwords per millisecond, there is no chance at all of two people having the same salt. (I'm sure Windows has timing issues so that this has to be much more than once per millisecond, but the point stands.) You asked about hash collisions in particular, and in the context of not having a maximum length. That's a little trickier of a problem. Yes, there exist attacks, particularly on MD5, which use a bunch of arbitrary output blocks to steer a hash to a particular value. But that usually requires a hash to be well-broken. In the case of SHA-256, you would need something like 2^128 user accounts before you'd map different inputs to different outputs. So you're protected from both: you ensure different inputs to the hash function and then you choose a hash function which requires too much work to generate collisions.
  • tomg 15y ago
    Thanks for this post, it's very informative!