7 ms·
SeaHash: Explained
- eutectic 10y agoPrevious discussion: https://news.ycombinator.com/item?id=13057797 https://news.ycombinator.com/item?id=13057797
- wyldfire 10y ago> SeaHash has mathematically provable statistical guarantees I'm all for proofs but would love to see an empirical head-to-head against metroHash. Is it as good or better output distribution?
- ComputerGuru 10y agoShould be easy to plug it into smhasher.
- eutectic 10y agoAccording to the author, it passes.
- ticki_ 10y agoMetroHash's main transformation actually loses entropy, so that's, well, pretty bad. It still passes Smhasher, though.
- notheguyouthink 10y agoI've been using blake2(b) for file hashing in some content addressable db stuff. What might be a scenario where i would choose Seahash over Blake2? My main concern was speed and assurance that i would not see collisions. Beyond that, i am clearly naive on the subject.
- notheguyouthink 10y agoAnd on that note, has anyone seen any benches for blake2 vs Seahash/Metrohash? I'm not finding anything so far
- ticki_ 10y agoBLAKE(2) is a cryptographic hash function, SeaHash is not. Even the fastest implementations of BLAKE only gets around 7.8 cycles/byte (hardware might do it twice as fast). SeaHash gets 0.24 cycles/byte. That's a wide difference, around 32x faster.
- dom0 10y agoThe main question, aside from performance, is... - Is there an (abstract) attack model? (Assuming that you have one if you ought to) - Then: Can an attacker insert collisions into the DB, and is that problematic? - Then: A non-cryptographic hash might be much easier to "reverse", especially for short inputs. Is that problematic? If none of these are problematic you probably don't need a cryptographic hash. Regarding performance: BLAKE2b on a Haswell gives you, in a "naive", pure C implementation (compiled to pure, non-vectorized AMD64 assembly), about 230 MB/s / GHz. (Referring to https://github.com/borgbackup/borg/issues/45#issuecomment-221234832 https://github.com/borgbackup/borg/issues/45#issuecomment-22... ), ie. something like 850-1000 MB/s on a desktop SKU. There are implementations that are around 10-30 % faster than that. AFAIK all these newer n-c hash functions that popped up in the last couple years perform (on desktop SKUs) in the area of beyond ~10 GB/s.
- leeoniya 10y agohttps://github.com/ticki/tfs/issues/5#issuecomment-266031657 https://github.com/ticki/tfs/issues/5#issuecomment-266031657
- ticki_ 10y agoSeaHash 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 need cryptographic security. It's that simple.
- ticki_ 10y agoThere's a huge difference between cryptographic and non-cryptographic. Note that blake2 has various length, whereas SeaHash is fixed to 64-bit (although I suppose it's not to hard to make a version with bigger length), and thus naturally collisions will happen. If you need fingerprints, don't use SeaHash, but if you are looking to insert into e.g. a hash table, you shouldn't use BLAKE2. It's awfully slow for that.
- JoshTriplett 10y agoFor 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.)
- loeg 10y agoIt 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.
- JoshTriplett 10y agoGit 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.
- gbrown_ 10y agoDiscussion that came up the other week for those that missed it. https://news.ycombinator.com/item?id=13057797 https://news.ycombinator.com/item?id=13057797
- thomasahle 10y ago> `f : {0,1}^n → {0,1}^n` is a perfect PRF if and only if given a distribution `d : {0,1}^n → [0,1]`, `f` maps inputs following the distribution `d` to the uniform distribution. Is this even possible? If the distribution `d` always returns 0, how can a function make it uniform? It would be nice, if the article would go into more details on how SeaHash obtains this property, and how it related to collision avoidance.
- petters 10y agoIt's not clear what the author means here. This is not a very mathematical article. (Nit: d is a distribution so it can not always return 0 -- it has to sum to 1. But your point stands.)
- pdpi 10y agoI believe the point is that you get a uniform distirbution of 1s and 0s after going through the PRF irrespectively of the distribution of 1s and 0s in the input. This is certainly a desirable property for a hash function.
- deleted 10y ago[deleted]
- jamessb 10y agoA (translated) Dirac delta function might be a better example [1]. [1]: https://en.wikipedia.org/wiki/Dirac_delta_function https://en.wikipedia.org/wiki/Dirac_delta_function
- johnnycarcin 10y agoticki and the rest of the crew working on Redox (jackpot51) are really doing some neat stuff. a lot of it is over my head but it is cool to see something being built from the ground up using some new techniques and ideas.
- libeclipse 10y agoCould someone explain what the point is? Is there a use-case for this for "general hashing" and such, where sha256 is _genuinely_ insufficient?
- chadaustin 10y agoHi, 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/ http://aras-p.info/blog/2016/08/09/More-Hash-Function-Tests/ Hope that helps, Chad
- libeclipse 10y agoEven 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?
- ticki_ 10y agoIn 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.
- jjaredsimpson 10y ago> 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
- 10y ago
- _RPM 10y agoHow does this compare to murmurhash3?
- valarauca1 10y agoSeahash is about 3x faster then murmur3 https://docs.rs/seahash/3.0.3/seahash/ https://docs.rs/seahash/3.0.3/seahash/
- 0x6c6f6c 10y ago> 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?
- geofft 10y agoA 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.)
- rudolf0 10y agoThe 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.