5 ms·
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
by tptacek 2y 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 2y agoChecksums 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.
- loeg 2y agoIf 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.
- nepthar 2y agoThat’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.
- cstrahan 2y agoNote 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 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-enough-almost-universal-fingerprinting/ https://engineering.backtrace.io/2020-08-24-umash-fast-enoug...
- loeg 2y agoWell, 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.
- jnwatson 2y agoHash tables and related data structures.
- loeg 2y agoIf 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.)
- zamalek 2y agoContent 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).
- loeg 2y agoWhat operations would be faster in Git from using an insecure hash instead of SHA256? Commit is already reasonably fast.
- iainmerrick 2y agoI 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?
- keepamovin 2y agoThanks 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.
- deleted 2y ago[deleted]
- keepamovin 2y agoThat'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.
- tptacek 2y agoWhat does "vetted" mean to you here?
- keepamovin 2y agoJust 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?