3 ms·

It is also worth noting that historically hash functions have had the implicit requirement of being "fast" and "small". Because hashes are used on both encrypt

by evgen 18y ago

It is also worth noting that historically hash functions have had the implicit requirement of being "fast" and "small". Because hashes are used on both encrypted and unencrypted data there is a pressure on hash designers and the people selecting from available hash options to factor speed and output hash size into the selection criteria. This inevitably leads to the selection of hash functions that compromise security for other (practical) considerations. We could have moved from MD5 to Whirlpool a long time ago, but I and everyone else looked at doubling storage requirements and chopping throughput to a trickle and selected SHA1...

gms 18y ago
It's not that. People just know so little about designing good crypto hash functions. Basically right now nobody knows what they're doing.
- cperciva 18y ago
  Basically right now nobody knows what they're doing. That's going a bit far. We know how to design hashes which are provably at least as strong as block ciphers (i.e., "if you can break this hash, you can break AES") -- but synthetic constructions like those always end up being much slower than constructions which are "native" hashes.
- tptacek 18y ago
  I don't know why someone would mod this comment down. It paraphrases pretty accurately points made by professional cryptographers. Percival's response is also accurate. He's saying, there's a baseline for secure hash functions: those that adapt block cipher constructions. But that's just the baseline. Nobody does that, because hash functions need to be fast. And making that tradeoff of speed versus proven constructions seems to put us into the weeds.
  - ars 18y ago
    So is that my answer to the question that started this thread? We know how to make good hashes, but they are slow. And all the fast hashes get broken eventually?
    - cperciva 18y ago
      And all the fast hashes get broken eventually? I'd phrase it as "because hashes have historically attracted less attention than ciphers, it took longer for us to figure out how much of a margin of error to design into hashes". For both block ciphers and hashes, the vast majority of designs rely on iterated mixing functions, and long before the complete designs are broken cryptographers figure out how to attack reduced-round versions. There's nothing inherently broken about the designs behind either MD5 or SHA1 -- if you created an MD5++ hash which exactly followed the design of MD5 but used twice as many mixing rounds, I don't think anyone would be able to find collisions for it.

by evgen 18y ago

gms 18y ago

It's not that. People just know so little about designing good crypto hash functions. Basically right now nobody knows what they're doing.

cperciva 18y ago
Basically right now nobody knows what they're doing. That's going a bit far. We know how to design hashes which are provably at least as strong as block ciphers (i.e., "if you can break this hash, you can break AES") -- but synthetic constructions like those always end up being much slower than constructions which are "native" hashes.
tptacek 18y ago
I don't know why someone would mod this comment down. It paraphrases pretty accurately points made by professional cryptographers. Percival's response is also accurate. He's saying, there's a baseline for secure hash functions: those that adapt block cipher constructions. But that's just the baseline. Nobody does that, because hash functions need to be fast. And making that tradeoff of speed versus proven constructions seems to put us into the weeds.
- ars 18y ago
  So is that my answer to the question that started this thread? We know how to make good hashes, but they are slow. And all the fast hashes get broken eventually?
  - cperciva 18y ago
    And all the fast hashes get broken eventually? I'd phrase it as "because hashes have historically attracted less attention than ciphers, it took longer for us to figure out how much of a margin of error to design into hashes". For both block ciphers and hashes, the vast majority of designs rely on iterated mixing functions, and long before the complete designs are broken cryptographers figure out how to attack reduced-round versions. There's nothing inherently broken about the designs behind either MD5 or SHA1 -- if you created an MD5++ hash which exactly followed the design of MD5 but used twice as many mixing rounds, I don't think anyone would be able to find collisions for it.