Hacker News Reader

Comment by gnabgib | Hacker News Reader

None of these hashes are cryptographic. They're designed to be /fast/ and so therefore easier to break. They're mostly only used in developer-controlled situations (hash maps etc) where you probably control the keys (if you don't.. well you're at risk). The risk/cost of a collision (the break) is decreased performance, not a security failure.

Crypto hashes don't have a problem of being slow.. they are designed to be slow.

The conclusion tries to tie weak/fast hashes to crypto/secure hashes (the https mention), but they're worlds apart.

View on HN

Cryptographic hashes are not designed to be slow. They are designed to be as fast as possible while still adhering to their security requirements (first and second preimage resistance, collision resistance).

Password hashes are designed to be slow, but those are a very distinct category of hash.

The point of this post is to demonstrate how easy it is to generate collisions for HashDoS attacks.

Cryptographic hash functions are usually designed to be fast since they are on the hot path for cryptographic signatures and for hash-based message authentication codes.

Password hashes are designed to be slow, but they are an entirely different beast.

The point about https in the conclusion is that the author’s PolyMur hash uses a polynomial construction related to GCM and poly1305, which makes it much harder to invert.

Slowness isn't always a desireable property of cryptographic hashing. Generally you only want that property when you are trying to do some kind of key derivation from a human-generated password. In plenty of circumstances you want them to be fast, but hashes that have the desired security properties are all slower than the hashes designed to be fast and work well enough with non-adversarial input.

> They're mostly only used in developer-controlled situations (hash maps etc) where you probably control the keys (if you don't.. well you're at risk).

It's very common for keys to contain user input.

> None of these hashes are cryptographic.

I never said they were.

> Crypto hashes don't have a problem of being slow.. they are designed to be slow.

No they're not. Only password-based key derivation functions are designed to be slow, every other hash tries to be as fast as possible within their security budget.

> The conclusion tries to tie weak/fast hashes to crypto/secure hashes (the https mention), but they're worlds apart.

Actually, the specific link I made between cryptographic strength universal hashing and maximum-speed universal hashing is precisely because they're not worlds apart. They use the same techniques, and stand on the same mathematical background.

Depending on the length of what you're hashing, either one of the cut down Siphashes or Blake3 are reasonably fast.

The Siphashes are too short I think for general use, but when cut down and keyed they're okay for a hashmap.

Siphash and Blake3 or NOT reasonably fast, they are dirt slow. They should not be used in hash tables at all. Fighting DOS attacks can only be done with detecting DOS attacks, which is much cheaper than using a slow, better hash function. Count the collisions. And then either stop the attack, or fallback to a tree.

1) they're not that slow, and 2) I'm talking about the cut down versions of Siphash

They are. See https://rurban.github.io/smhasher/

Fast hashes are around 20.000 MiB/sec, blake2 around 350, siphash13 1800. That's insanely slow, for no benefits.

Crypto hashes are not designed to be slow.

It's relative. They are about 1000x slower than fast, good enough hash functions. Dirt slow.

Nobody is talking about password hashes here.

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/blak...

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.

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?

> 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/.

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).

Yes, polymur is probably the very best right now

Reply on news.ycombinator.com