Show HN: Rain hashes – well designed, simple and fast variable sized hashes

https://github.com/DOSAYGO-Research/rain

by keepamovin • 2 years ago

79 52 2 years ago

keepamovin18• 2 years ago

This is my hash included in the best hash testing library out there "SMHasher3" maintained by Frank T Wojcik: https://gitlab.com/fwojcik/smhasher3 This test lib has many improvements over SMHasher 1 & 2, listed on the previous link. Results are: https://gitlab.com/fwojcik/smhasher3/-/blob/main/results/REA...

Rainbow is the fastest 128-bit hash, and the fastest 256-bit hash (non-crypto). The 8th fastest 64-bit hash (by family, or 9th fastest overall, and 13-th fatest overall if you include 32-bit hashes). The advantage of rainbow is its easily scalable output size (64, 128 and 256), its high quality (passes all the tests), and its utter simplicity: it is under 140 source lines of code, easily readable

The random constants are primes that were selected based on their avalanche quality under a multiply modulo operation. This part of the development was interesting different primes had very distinctly different avalanche qualities. The highest quality primes caused good avalanche (~ 50% bit flip probability) across the widest possible set of bits, on average. These are quite rare. A lot of large primes only avalanche across a narrow range of bits, even in a 128-bit space. The search program took a couple of days to discover all these primes running on a 2020s era MBP. Primes are chosen because they give a complete residue set under the modulus, ensuring a long cycle length at least regarding the nominal test operation.

The rest of the hash was developed by trial and error using my intuition on developing hashes arising from long experience of doing so, and using SMHasher3 to evaluate the results, by iterating to improve and re-testing, over a period of a couple of weeks in the holidays a few years ago. I started making hash functions in my teens as a fun hobby.

There's also a fun little wasm powered dashboard you can play with, here: https://dosaygo-research.github.io/rain/

mulle_nat4• 2 years ago

I am using fnv-1a to hash Objective-C method selectors, which are generally just identifier characters and zero or multiple ':'. At the time of my research, fnv-1a had the least collisions over my set of "real life" selectors. I think, it could be worthwhile some time, to try out other constants for maybe even less collisions. Is your list of good primes available ? (And maybe also those that are not quite perfect)

keepamovin18• 2 years ago

Everything is in the source code. I highly doubt any of the good hash functions listed in smhasher3 (ie all tests passed) would collide over identifiers.

So they should all have zero collisions, meaning there’s no ‘least’ among the good quality ones - they’re all equally collissionless (they differ in other tests).

Sounds like an interesting project. What’s its purpose?

rurban3• 2 years ago

Spooky also has some good results on common identifiers.

But fnv-1a is in a completely different league. It's recommended for hash tables with other security measures than hash function security. This hash is a typical hybrid, but not universal. umash would be the perfect hybrid: insecure, pretty fast, passes all tests, universal

zokier• 2 years ago

The benchmarks are bogus at the least, you are essentially just measuring the startup time of the executable/runtime and not your hash function.

keepamovin18• 2 years ago

Right, how to improve that? That nodejs bench script is meant to compare between cpp and wasm.

For hash speed consult the smasher3 results.

tptacek9• 2 years ago

Broadly: I don't understand the design space of "cryptographic-ish" hashes. There's an intensely competitive design space of cryptographic hashes. What does it mean to be "more secure" than an insecure hash function? When would it ever be appropriate to use such a hash?

dan_manges• 2 years ago

Checksums are a good use case, where you’re not worried about any sort of forged collisions and you want to calculate the checksum as fast as possible. Although cryptographic hashes are fast enough that there likely aren’t too many use cases where the difference in speed is meaningful.

loeg5• 2 years ago

If you don't care about forged collisions, what makes a secure-ish checksum bette than a faster insecure checksum? Both are likely to result in a different value for bit-flipped input, which is the point.

jnwatson• 2 years ago

Hash tables and related data structures.

loeg5• 2 years ago

If the distribution of bits isn't better, you would prefer a faster hash for a table that doesn't care about adversarial inputs. (And if you do care about adversarial inputs, I think you need an actually secure hash? Medium confidence on that.)

zamalek2• 2 years ago

Content addressable storage. For example, the Git DAG would be one place to use it (depending on which camp you're in: should the DAG be cryptographically secure, or should the security be out-of-band e.g. signatures).

loeg5• 2 years ago

What operations would be faster in Git from using an insecure hash instead of SHA256? Commit is already reasonably fast.

iainmerrick• 2 years ago

I have the same question.

Might be useful to clarify for people replying with suggested use cases: this repo has two hash functions, describing them as “General-purpose, non-crypto hash” (OK) and “Experimental cryptographic-like hashing” (???)

The question is, what is that second one for? Do they just mean it could eventually become a cryptographic hash?

keepamovin18• 2 years ago

Thanks for adding that clarification that yes it includes two hashes: one not meant as a crypto hash; one proposed to be a cryptohash. The text in the README means it (the second one) is proposed as a crypto-hash. But the wording you used looks unclear, is that what we really have in there?

edit: AH, I see you mean in the comparison table. Yeah that wording could be improved. I'll change it now. The rest of the text is hopefully clearer:

"Consider it (rainstorm) experimental, but designed to be secure. Note on Cryptographic Intent: Rainstorm's design includes concepts from cryptographic hashing, but without formal analysis, it should not be considered secure. Feedback and analysis are welcome."

Although without a bunch of accepted analyses people shouldn't trust a secure cryptohash that merely claims to be a secure cryptohash - which this doesn't claim.

It is funny people get obsessed with wording when what's really needed is evidence.

I will take a look at the wording again now and if there's any wording that's insufficiently clear that rainstorm is proposed as a crypto-hash and requires analysis, I'll update such wording.

keepamovin18• 2 years ago

That's a clear distinction, thanks for bringing it up.

For clarity, this lib has 2 hashes: rainbow, and rainstorm. "rainbow" the faster, is not intended to be crypto secure. "rainstorm" the slower, designed with strength, is, but it has not been analyzed publicly.

My intent is that rainstorm is proposed as a cryptohash and eventually is analyzed properly in order to be trusted, and used - or improved! We probably can't remove the "ish" until then.

In terms of saying "more secure"? Without formal cryptanalysis it is hard to say, but if you have good statistical properties (as measured by these tests in SMHasher3) it's fair to say you're more secure as a lot of the attacks on (cryptographic) hashes are to do with finding dependencies between input and output ("differentials").

I wouldn't make sweeping recommendations unless a hash was vetted because that's how we end up trusting primitives, through the trust in the collective work of people trying to attack them. Right now we just have the speed results, the SMHasher3 results and the design, and some limited analysis. But more is coming, some people are doing good stuff on GitHub right now.

In terms of aptness, to use either of my hashes in rain as a cryptohash without having a deep understanding of potential attacks against it would be rolling the dice, but you could probably trust that at least potential attacks would seem to be difficult given the lack of statistical predictabilities. And they're both fine to use as regular non-cryptographic hashes.

Of course I want to recommend people use them, but I couldn't say use them in crypto applications without being irresponsible and I don't want to do that. Also, to be more lawyerly about it, heh, it's provided "as is".

I guess the main draw right now is if you want good statistical properties and hashes that can be 64, 128 or 256 (or even 512 in rainstorm) bits wide, and fairly fast for that.

tptacek9• 2 years ago

What does "vetted" mean to you here?

thadt• 2 years ago

So, questions for people that know more than I: What's up with the 'passing' and 'failing' hashes in SMHasher3?

Specifically, what happened to xxHash[1] to kick it down to the 'failing' category? I'm not certain about SMHasher's testing criteria, but comparing the benchmark numbers posed in Rain vs xxHash show xxH3 rather faster? Not that a have a personally vested intersted in xxHash, but it seems to be a rather widely used (e.g. RocksDB [2]) with a number of implementations - it would be useful to understand the criteria that make it no longer a passing SMHasher3 entry.

[1] https://github.com/Cyan4973/xxHash

[2] https://rocksdb.org/blog/2022/07/18/per-key-value-checksum.h...

zimpenfish• 2 years ago

Specifically, what happened to xxHash to kick it down to the 'failing' category?

Looking at [1], it seems to collisions (search for "!!!!!")

[1] https://gitlab.com/fwojcik/smhasher3/-/blob/main/results/raw...

mrbluecoat• 2 years ago

The fastest 128-bit and 256-bit non-crypto hash, passes all tests, and under 140 source lines of code

Nice!

keepamovin18• 2 years ago

Yes. Thank you :)

It’s pretty good

rurban3• 2 years ago

I failed to integrate it into my smhasher, the rain branch. Lots of collisions and wrong results all over. Pretty fragile for a workday

keepamovin18• 2 years ago

Hey Reini, I'm no C++ expert, but yes your SMHasher2 is pretty fragile. I don't know for a workday or not, but it's fragile. But what you said is a pretty nasty thing to say given there’s lots of bugs in your SMHasher2 that have already been fixed in SMHasher3. You can’t blame a hash for what’s your fault. You could always just do fixes instead of saying toxic nasty stuff.

If you want to put it in, take a look at the SMHasher3 library code, and the rain integrations there. I think you’ll have to port it as there’s some internal differences with your SMHasher2. Also, I'm sorry for the unclear and wrong default branch: it should be 'boss' branch. That's corrected now.

rurban3• 2 years ago

smhasher2 is not fragile at all. The rain test api functions are static in a .cpp. This will not work anywhere else than in smhasher3 with its special wrappers. You need to put them in headers if you want them static inline.

dgacmu• 2 years ago

Just to make sure I'm understanding correctly, I think that your intent is that rainbow is / should be treated as cryptographically weaker than SIPhash, right? (despite both of them not being something you would use in a high security context)

keepamovin18• 2 years ago

Right: rainbow has not been evaluated for HMAC or PRF (Sip's main security objectives), but it's not designed to be secure, just to have good stats and be fast af. I wouldn't be surprised if it was a good PRF, but also wouldn't be surprised if it was broken (by the standards of cryptohashes or HMAC or even PRF).

Some more about sip: https://docs.kernel.org/security/siphash.html

keepamovin18• 2 years ago

However there’s some chance it’s actually better and more secure than Rainstorm

Show HN: Rain hashes – well designed, simple and fast variable sized hashes

Related Stories