ticki 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.
SeaHash: Explained
11–20 of 57 posts
Re: SeaHash: Explained
#12> `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.
A (translated) Dirac delta function might be a better example [1].
Re: SeaHash: Explained
#13> `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.
It'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.)
I 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.
Re: SeaHash: Explained
#14> `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.
It'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.)
[deleted]
Re: SeaHash: Explained
#15Could someone explain what the point is? Is there a use-case for this for "general hashing" and such, where sha256 is _genuinely_ insufficient?
Re: SeaHash: Explained
#16Could someone explain what the point is? Is there a use-case for this for "general hashing" and such, where sha256 is _genuinely_ insufficient?
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
Re: SeaHash: Explained
#17Could someone explain what the point is? Is there a use-case for this for "general hashing" and such, where sha256 is _genuinely_ insufficient?
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-T…
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?
Re: SeaHash: Explained
#18Could someone explain what the point is? Is there a use-case for this for "general hashing" and such, where sha256 is _genuinely_ insufficient?
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.
Re: SeaHash: Explained
#19I'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.
And on that note, has anyone seen any benches for blake2 vs Seahash/Metrohash? I'm not finding anything so far
BLAKE(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.
Re: SeaHash: Explained
#20Earlier quoted context omitted.
The 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…
https://github.com/ticki/tfs/issues/5#issuecomment-266031657
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 need cryptographic security. It's that simple.