How does this compare to murmurhash3?
SeaHash: Explained
41–50 of 57 posts
Re: SeaHash: Explained
#42> there is a major difference between cryptographic and non-cryptographic hash functions. SeaHash is not cryptographic
Is this in reference to most used hash functions not leaving any way to trace the contents of what was hashed, or not being able to reliably reconstruct contents to generate a certain hash? Or something else entirely?
Re: SeaHash: Explained
#43Earlier quoted context omitted.
For a content-addressable database, you absolutely want a cryptographic hash. (And please, don't make the mistake Git did: please include the name of the hash function in the "address", to make it possible to change the hash function.)
It seems like Git could change the disk format eventually with backwards compatibility for current SHA1 addresses. You don't even need to rewrite old objects. You just need to know which hash method a given tree/commit object is using to verify history or perform checkout. That could be a flag or tag in the object.
Git has some work in progress in that direction, starting by changing all the internal data structures to use a struct rather than a hardcoded array of bytes the size of a SHA1.
Re: SeaHash: Explained
#44> there is a major difference between cryptographic and non-cryptographic hash functions. SeaHash is not cryptographic Is this in reference to most used hash functions not leaving any way to trace the contents of what was hashed, or not being able to reliably reconstruct contents to generate a certain hash? Or something else entirely?
A cryptographic hash makes it hard for an active attacker to cause the hash function to do something unwanted (generate collisions, generate a pre-determined output for a chosen input, etc.). "Hard" here is defined as it usually is for crypto: it should not be any easier to break the algorithm by knowing the algorithm's details, than to find one by brute-forcing 2^128 (or however many) possible inputs and treating the algorithm as a black box.
A non-cryptographic hash is generally not worried about active attackers; it wants to give a pretty good, even distribution of outputs for an arbitrary set of inputs, but it's not worried about inputs that are specifically designed to abuse the hash function. If you want to, say, create a random-looking but deterministic and stateless color for each user in an chat room, or something, a non-cryptographic hash function is fine. It's possible that an attacker can create a bunch of users with names constructed to all have the same color, but that's not going to break your website.
However, if you're putting each user in a hash table, a large number of collisions in a hash table can easily get you O(n^2) performance, despite the hash table being O(n) for a randomly-selected set of n inputs. That's the usual reason for using cryptographic hash functions even in places you wouldn't usually expect to see crypto. For instance, SipHash is a fast cryptographic hash function with output too small for use in actual cryptosystems, but it's perfect for hash tables.
(Strictly speaking, a cryptographic hash function doesn't promise anything about the privacy of its input; H(x) = x[0] + SHA-256(x) satisfies the theoretical constraints on cryptographic hash functions for preimage resistance and collision resistance.)
Re: SeaHash: Explained
#45How does this compare to murmurhash3?
Seahash is about 3x faster then murmur3
Re: SeaHash: Explained
#46Could someone explain what the point is? Is there a use-case for this for "general hashing" and such, where sha256 is _genuinely_ insufficient?
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.
Re: SeaHash: Explained
#47Earlier quoted context omitted.
SeaHash is obviously not cryptographic (nor is SipHash), but I hope it is a secure PRF (i.e. the keys cannot be extracted), and this was the best attack I was able to construct. Still, it isn't a practical attack, but I suppose it is possible to improve. Note that I am not a cryptographer, and my only piece of advice is: For the sake of god, don't use hash functions not designed for cryptographic security, if you nee…
SipHash is a cryptographic hash with a pretty good pedigree. The distinction between SipHash and Blake2 is more subtle than "cryptographic vs not".
No, it's not a cryptographic hash function. It's a MAC function.
The paper clearly states that it is not collision resistant.
Re: SeaHash: Explained
#48Earlier quoted context omitted.
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?
> 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.
Re: SeaHash: Explained
#49> there is a major difference between cryptographic and non-cryptographic hash functions. SeaHash is not cryptographic Is this in reference to most used hash functions not leaving any way to trace the contents of what was hashed, or not being able to reliably reconstruct contents to generate a certain hash? Or something else entirely?
The latter. Even a very simple hash algorithm will almost always make it impossible to get the original contents back. You'd have to write an intentionally pathological algorithm to achieve that.
Re: SeaHash: Explained
#50Earlier quoted context omitted.
SipHash is a cryptographic hash with a pretty good pedigree. The distinction between SipHash and Blake2 is more subtle than "cryptographic vs not".
No, it's not a cryptographic hash function. It's a MAC function. The paper clearly states that it is not collision resistant.
I believe that you and tptacek may be using differing definitions of "cryptographic", because he tends to knows what he's talking about when it comes to cryptography (e.g. https://gist.github.com/tqbf/be58d2d39690c3b366ad).