3 ms·

Crypto hashes are not designed to be slow.

rurban 2y ago
It's relative. They are about 1000x slower than fast, good enough hash functions. Dirt slow. Nobody is talking about password hashes here.
- Dylan16807 2y ago
  https://github.com/Cyan4973/xxHash/issues/450 https://github.com/Cyan4973/xxHash/issues/450 This person's testing has blake3 at 250 cycles for small hashes. It's not a thousand times slower. And for a lot of uses, 250 cycles is plenty fast. That's like one uncached memory access. That test does mention batching but I don't think it makes a particularly large difference, the paper shows 4 cycles per byte for 64 byte inputs and I don't think they're getting fancy: https://github.com/BLAKE3-team/BLAKE3-specs/blob/master/blake3.pdf https://github.com/BLAKE3-team/BLAKE3-specs/blob/master/blak...
  - rurban 2y ago
    The fastest realistic hash is o1hash with 11.629.440 MiB/sec. The typical crypto hash is 100—200 MiB/sec. Thats about 10.000x faster. A modern AES-NI hash is 30.000 MiB/s. That's about 50x faster than blake3 or siphash13. And also not reversible.
    - Dylan16807 2y ago
      o1hash is a gimmick. And that's way faster than a CPU can load or store data so you can't do anything with it. When we look at hashes mentioned in this discussion where people are trying to be fast, blake3 is at 3000MB/s when vectorized, and cityhash, murmurhash, and siphash range from 5x faster to 2x slower if I take the smhasher numbers. There's not that much difference. But also the number we need here is the latency of a small hash, not the max throughput. If blake3 takes 250 cycles for that, how much faster do you think you can go? You can't fit a reasonable hash into 10 cycles. You can't even fit o1hash into 10 cycles. And all of those numbers are pretty fast for most purposes. AES-NI is a great tool! But isn't that arguing in favor of a crypto hash?
      - orlp 2y ago
        > You can't fit a reasonable hash into 10 cycles. Not 10 cycles, but my polymur-hash can hash any value <= 49 bytes in 21 cycles on an Apple ARM machine: https://github.com/orlp/polymur-hash/ https://github.com/orlp/polymur-hash/. I think it's a "reasonable hash" too, considering against non-interactive attackers it's provably secure (collision probability bounded up to n * 2^-60.2 for n bytes).
        rurban 2y ago
        Yes, polymur is probably the very best right now

It's relative. They are about 1000x slower than fast, good enough hash functions. Dirt slow. Nobody is talking about password hashes here.

Dylan16807 2y ago
https://github.com/Cyan4973/xxHash/issues/450 https://github.com/Cyan4973/xxHash/issues/450 This person's testing has blake3 at 250 cycles for small hashes. It's not a thousand times slower. And for a lot of uses, 250 cycles is plenty fast. That's like one uncached memory access. That test does mention batching but I don't think it makes a particularly large difference, the paper shows 4 cycles per byte for 64 byte inputs and I don't think they're getting fancy: https://github.com/BLAKE3-team/BLAKE3-specs/blob/master/blake3.pdf https://github.com/BLAKE3-team/BLAKE3-specs/blob/master/blak...
- rurban 2y ago
  The fastest realistic hash is o1hash with 11.629.440 MiB/sec. The typical crypto hash is 100—200 MiB/sec. Thats about 10.000x faster. A modern AES-NI hash is 30.000 MiB/s. That's about 50x faster than blake3 or siphash13. And also not reversible.
  - Dylan16807 2y ago
    o1hash is a gimmick. And that's way faster than a CPU can load or store data so you can't do anything with it. When we look at hashes mentioned in this discussion where people are trying to be fast, blake3 is at 3000MB/s when vectorized, and cityhash, murmurhash, and siphash range from 5x faster to 2x slower if I take the smhasher numbers. There's not that much difference. But also the number we need here is the latency of a small hash, not the max throughput. If blake3 takes 250 cycles for that, how much faster do you think you can go? You can't fit a reasonable hash into 10 cycles. You can't even fit o1hash into 10 cycles. And all of those numbers are pretty fast for most purposes. AES-NI is a great tool! But isn't that arguing in favor of a crypto hash?
    - orlp 2y ago
      > You can't fit a reasonable hash into 10 cycles. Not 10 cycles, but my polymur-hash can hash any value <= 49 bytes in 21 cycles on an Apple ARM machine: https://github.com/orlp/polymur-hash/ https://github.com/orlp/polymur-hash/. I think it's a "reasonable hash" too, considering against non-interactive attackers it's provably secure (collision probability bounded up to n * 2^-60.2 for n bytes).
      - rurban 2y ago
        Yes, polymur is probably the very best right now