3 ms·

> bite the performance bullet, and use a provably secure hash algorithm Do these exist? (Genuine question; I’m not familiar with the state of the art.)

verandaguy 6y ago
Depends what you mean by "provably secure." Hashing algorithms are usually only practical because of what compromises they make to achieve "good enough." - At the most basic level, (practical) hashing cannot map all inputs to the same number of outputs, since consistent output length is usually highly desirable. This means that for sufficiently long inputs you will get collisions. What determines how good a hash is is often how hard that is to do. - If your inputs map 1:1 to outputs, rainbow tables become harder but you open yourself up to a number of other possible attacks starting with the obvious length analysis. - Hashing also often has to be very performant, which leads to its own compromises, but in many applications (like message digests) throughput performance is given a lot of weight. In the most formal way, I guess it's possible to have a provably secure hash for all possible attacks, but this would most likely require a 1:1 mapping between inputs and outputs. This would be impractical for a few reasons.
- Dylan16807 6y ago
  The output has to be indistinguishable from random, and colliding n bits needs to take an exponential amount of time. Output length can be anything. As long as it's indistinguishable from random, the chance of collision will be exponentially rare, and you can truncate or concatenate to get the length you want.
  - verandaguy 6y ago
    You're correct on all points, though this kind of implementation (with variable-length output) is fairly rare AFAIK. Having a fixed-length output lets you reliably define for example a database field length. I'd love to see a practical implementation of that though, if you know where to find that kind of project off-hand!
    - Dylan16807 6y ago
      I didn't mean "variable" when I said "anything". I was saying it didn't matter. Variable length would be valid, but so is a fixed 200 bit output. The main thing I wanted to express is that "provably secure" doesn't mean no collisions.

verandaguy 6y ago

Depends what you mean by "provably secure." Hashing algorithms are usually only practical because of what compromises they make to achieve "good enough." - At the most basic level, (practical) hashing cannot map all inputs to the same number of outputs, since consistent output length is usually highly desirable. This means that for sufficiently long inputs you will get collisions. What determines how good a hash is is often how hard that is to do. - If your inputs map 1:1 to outputs, rainbow tables become harder but you open yourself up to a number of other possible attacks starting with the obvious length analysis. - Hashing also often has to be very performant, which leads to its own compromises, but in many applications (like message digests) throughput performance is given a lot of weight. In the most formal way, I guess it's possible to have a provably secure hash for all possible attacks, but this would most likely require a 1:1 mapping between inputs and outputs. This would be impractical for a few reasons.

Dylan16807 6y ago
The output has to be indistinguishable from random, and colliding n bits needs to take an exponential amount of time. Output length can be anything. As long as it's indistinguishable from random, the chance of collision will be exponentially rare, and you can truncate or concatenate to get the length you want.
- verandaguy 6y ago
  You're correct on all points, though this kind of implementation (with variable-length output) is fairly rare AFAIK. Having a fixed-length output lets you reliably define for example a database field length. I'd love to see a practical implementation of that though, if you know where to find that kind of project off-hand!
  - Dylan16807 6y ago
    I didn't mean "variable" when I said "anything". I was saying it didn't matter. Variable length would be valid, but so is a fixed 200 bit output. The main thing I wanted to express is that "provably secure" doesn't mean no collisions.