Hacker News Reader

Comment by libeclipse | Hacker News Reader

Could someone explain what the point is? Is there a use-case for this for "general hashing" and such, where sha256 is _genuinely_ insufficient?

View on HN

A good example is for a bloom filter: using sha256 is much too slow for good filter performance, you want something like siphash or some other non-cryptographic hash.

Here's a good story of the performance benefits of switching from cryptographic to non-crypto hashes: https://github.com/bitly/dablooms/pull/19

(But I don't recommend you use murmur anymore: https://emboss.github.io/blog/2012/12/14/breaking-murmur-has... (although tbh I could be wrong on this one, not an expert))

(Shameless plug for my bloom filter tutorial https://llimllib.github.io/bloomfilter-tutorial/ )

> But I don't recommend you use murmur anymore

I think xxHash was/is the fastest good non-crypto hash, and now SeaHash may be best. Although I'd like to see a bit more data on that (small keys? large keys? benchmarking methodology) than SeaHash's author is providing.

yeah I should look into that more. aapleby seems to have given some pretty good arguments against SeaHash in the previous discussion: https://news.ycombinator.com/item?id=13058652

That argument depends on the initial values being the same, you can easily make sure they are not.

This isn't a cryptographic hash. SHA-256 and other cryptographic hashes are much slower, but give certain guarantees about difficulty of doing things like finding hash collisions. The advantage of SeaHash is that it's even faster than other commonly used non-cryptographic hashes, and has attractive statistical properties that will result in fewer collisions than other hash functions.

A lot of stuff.

SHA256 is very slow, and that's no surprise. It's cryptographic after all.

Here's a small list of usecases for non-cryptographic hash functions:

- Checksums and error correction codes, as long as there is no way to maliciously use this.

- Hash tables. These always use non-cryptographic hash functions.

- Bloom filters.

- Heuristic fingerprinting. They're not strong enough to be used for normal data fingerprints, but they can be used as a way to decide if two buffers are "probably equal" or "certainly not equal".

Hash tables are the main one. Cryptographic hash functions are almost never used in them. SipHash is a popular choice, but it is not cryptographic. That is a misunderstanding: It's a MAC function.

I may be totally off-base here, but can't the SHA256 CPU instructions be used for this? Then it'd just be 1 (? Or is it more) instruction to perform?

Hi,

I recently used a hash function like this as part of a React-style delta calculation engine but for Swift / iOS.

I needed a hash function that was fast but collision-resistant, and I did not need a cryptographic hash, as all data is trusted (and a hash collision would not actually matter that much).

I chose SpookyHash V2 based on the advice of some peers and http://aras-p.info/blog/2016/08/09/More-Hash-Function-Tests/

Hope that helps, Chad

Even when I've not needed a cryptographic hash, I've still used one, because why not? I've never not needed one so bad as to resort to some barely studied, homemade hashing algorithm.

> A hash collision wouldn't matter that much.

Interesting. What was the use for the hash function then?

In hash tables, you never use cryptographic hash functions. Why? Because they're slower.

Take SHA3, which is around 50x slower than SeaHash. That is really really bad for hash tables.

When hash collisions happen in hash tables, they're resolved through collision-resolution strategy, such a linear proping.

Fingerprints are one very narrow usecase for hash functions, and there are tousands of other uses.

> Even when I've not needed a cryptographic hash, I've still used one, because why not?

To avoid wasting cpu cycles preserving a property you don't need. Seahash should be 50x faster than sha3

Caching often relies on hash functions. If you run the Cloudflare cache, you'll start caring, considering hashing is usually >50% of the CPU workload and an optimized non-cryptographic hash function can be 20x faster.

A trade off between collision potential vs. speed. Sometimes you need speed more than you need cryptographic levels of collision avoidance.

For example, finding unique files on the file system. After looking at size, first and last bytes, it would be better to filter quickly on an imperfect hash (with, say, a 1 in 1^56 chance of collision) than slowly on a perfect hash (with a 1 in 1^256 chance).

I hope you mean 2^56 and 2^256 :)

We can increase that by one to the fourth power!

http://aperiodical.com/2013/05/the-maths-of-star-trek-the-or...

> Even when I've not needed a cryptographic hash, I've still used one, because why not?

Performance. Take a look at djb's (non-cryptographic) hash, with a constant multiplier chosen to be implemented with a shift and an add — that's the level of performance a non-cryptographic hash (e.g. for hash tables & similar purposes) needs.

https://gist.github.com/hmic/1676398

Please don't. DJB2 is a poor hash function. It's similar to FNV: Entropy only moves upwards, so flipping higher bits doesn't affect lower bits.

In other words, you risk mapping `n` and `-n` to the same value under some modulus.

> Is there a use-case for this for "general hashing" and such, where sha256 is _genuinely_ insufficient?

Yeah. There are often times when you want to hash data but don't want to waste sha256-levels of cycles doing so. Applications are pretty much everything except cryptographic signing. Load-balancing, higher-quality checksuming, etc.

Reply on news.ycombinator.com