Hacker News Reader

Comment by tptacek | Hacker News Reader

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?

View on HN

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?

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.

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.

What does "vetted" mean to you here?

Just held to the same standards of cryptanalysis that the community decides imbues a cryptohash with trust for use.

Pretty standard, and consistent with the rest of the text.

What did you think it meant?

Nothing in particular, but, like, there was just a NIST competition that produced SHA3, and "vetted" Blake2, and this wasn't submitted to it. It's not like there's a test suite to which you can just submit a cryptographic hash to validate it. You actually have to convince a bunch of mathematicians to do studies of your hash, right?

I'm not trying to pick on you, it's just that this keeps coming up with constructions like PCG. There's a cryptographic literature, and then a side-hustle of people building stuff like this. We used to have a sci.crypt discourse about it, but now I worry that HN has lost the antibodies.

There's 2 hashes here. Rainbow is non-crypto, rainstorm is proposed as a crypto-hash, requiring cryptanalysis. It's not claiming to be validated as a cryptohash by SMHasher3, which tests statistical properties. You need (crypt)analysis to say it's a secure and trusted crypto-hash. This was developed a couple months past the NIST submission deadline for SHA3.

Maybe your immune response was wrongly triggered? It happens. But what we really need antibodies against is excessive negativity and vague criticism, combined with attempts to justify the same with "you're not someone who is supposed to do that" gatekeeping.

Could some of this be motivated by the fact that you want to do stuff like this yourself, but instead of doing so, or analyzing it, you just criticize it, inappropriately? I don't think you're trying to pick on me, just confused and powered by righteous protective instinct that is better were it more informed and discerning. Reflect some?

No immune response! Making new things and posting them is an absolute good thing. I'm literally asking, straight up: what's the use case for a hash that is "more secure" than an insecure hash, but "less vetted" than an actual cryptographic hash. That's all.

Alright - if you want a strict use case for rainstorm in 2024 before public cryptanalysis: as a subject of cryptanalysis and experiment; as a way to make your name as a junior cryptographer attacking it.

What other ideas can you think of? How about in a construct for password hashing? You can add more rounds to the loop to increase the cost like pbkdf1/2.

For rainbow you can use it in place of whatever other non-crypto hash you have, especially if you want fast 128 or 256 bit widths.

Yep. Dunno. A question! It's the Internet, I get it, I'd bucket responses into "this is amazing" and "this is the worst" too. I have a more philosophical question here. :)

You would? That’s not what I’m doing: "bucketing". I always assume good, but look at everything closely, and call it out if I see it. I respond to what’s there individually.

If you're trying to be friendly you got a funny way about it. What’s your philosophical question?

The one at the root of the thread: "why would I ever use a hash that's slower than the fast, 'insecure' hashes, and isn't a serious cryptographically secure hash". This comes up a bunch!

Rainstorm is serious, but not yet publicly vetted. Anyway, I thought that might be your question. You don't have any answers?

If not...Oh well, you might have to wait until it gets analyzed a lot. Use Rainbow now without fear: fast, statistically great, and unlikely collisions - which makes most uses better. As someone else put it: "fastest 128-bit and 256-bit non-crypto hash, passes all tests, and under 140 source lines of code."

Why do you expect cryptography researchers to analyze your hash? That's maybe the question I should have started with.

Probably is. Why do you not expect them to?

I'm sure they will eventually, not too long. What's your big concern / lack of confidence here?

In the meantime you can take care of it and nurture it by encouraging people to analyze it, using your influential voice for good.

I'd be happy to if I understood better why someone would want to undertake that project, which is why I asked. There is an enormous literature on cryptographic hashing; where does your hash fit into it?

Nice question! Rainstorm pulls from a rich history of ciphers and cryptohashes. It’s based on ARX-like mixing (though it swaps addition for subtraction—hence XSR: XOR, Subtract, Rotate) to create non-linearity, while borrowing structural ideas from Feistel networks, sponge constructions, and Merkle–Damgård iteration. It fits into the “experimental hybrid” category, exploring whether combining paradigms can offer fresh resilience or reveal new weaknesses. Definitely more to expand on, and you can read more, here: https://dosaygo-research.github.io/rain/paper/crypto-note.pd...

Hopefulyl this gives an overview of some of the historical influences and inspirations.

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.

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.

That’s a good question. A cryptographic hash must not leak any information other than “yes” or “no”. A checksum-type hash might have an additional property where data that only has a single bit flipped might hash to something close to the original hash, allowing you to refine your collision attack by knowing if you’re hot or cold.

For a checksum, this isnt a bad thing and actually could be good.

Note that you said “likely” and not “equally likely”. Therein lies your answer.

There are applications where hashes are used as identifiers, where it would be impossible to use the original data to resolve possible collisions. One example would be in RTTI (Run Time Type Information), when you want to check if two objects (of unknown-at-compile-time type) are instances of the same type. The only performant way to achieve this is if the compiler emits each type’s RTTI with a unique integer key to efficiently compare against, and this key must be unique across all object files and shared objects. In practice, this is done using hashing. If there is a collision, then the program behavior is undefined, so it is ideal to minimize probability of collision. You can see this issue in the Rust compiler project where there is ongoing discussion about how to handle this hashing, trying to balance compiler speed and collision likeliness:

https://github.com/rust-lang/rust/issues/129014

Another scenario would be like what Backtrace does: a hash is used to identify certain classes of errors in application code. The cost of analyzing each error is quite high (you have to load objects into memory, source maps (if available), perform symbolification, etc), so comparing any two errors every time you want to perform any metrics or retrieve associated data (like issue tracker identifiers) would reduce the performance to a point that any such application would be too slow to be useful. So a lot of thought was given to producing fast, non-cryptographic hashes (these hashes aren’t shared across tenants, and no customer is going to go out of their way to work out initialization parameters so they can be their own adversary) with a known likely hood of collision. You can read about the hash (UMASH) here:

https://engineering.backtrace.io/2020-08-24-umash-fast-enoug...

Well, also notice that I said "bit-flipped input." I.e., the use case I believed to be talking about and responding to was data corruption detection (which is also associated with "checksum" as a term of art, as opposed to a generic "hash"). I agree that hashing for identity is a different use case than checksumming for data integrity.

FWIW I think commonly used checksums are basically ideal ("equally likely" to come to a different value) on single-bit flipped inputs, but don't quote me on that.

Hash tables and related data structures.

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.)

For adversarial inputs, even a cryptographic hash won't save you, the cost of brute force searching for pathological keys is based the number of buckets not the cost of finding full collisions.

There's a whole literature of cryptographic hashes designed for this problem.

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).

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

Where in my comment do I say it should be used? I merely used Git as an example of a production CAS.

> For example, the Git DAG would be one place to use it

I read that as you thinking Git is a motivating use case for this hash.

Reply on news.ycombinator.com