Hacker News Reader

I am afraid the terminology you use is not canonical.

A hash (function) is any function that maps a big variable-length data structure to a smaller (fixed-length) data structure.

A checksum is a special hash (function) which has the purpose of detecting accidental errors during transmission or storage. (This makes them different from hash functions used for example in hash tables. For example relevant question: minimum how many badly transmitted bits are needed to break the error detection in the case of a specific checksum?)

A cryptographic hash function is another kind of special hash function which also has a very good definition on wikipedia.

(Basically these are the definitions on Wikipedia, and I think they are fine. If the terminology you use would be canonical we would use the name 'checksum table' instead of 'hash table', and it would be quite illogical also, because the term 'checksum' really includes purpose in its name 'checking something').

I have hash functions that work on less bytes than the length of the hash they produce.

Won't that be fairly common? Java's hashCode and the .Net GetHashCode both return 4 byte ints and there are presumably a lot of HashMap and Dictionary objects out there using short strings as keys.

It's very common; the norm even. My point was that "A hash (function) is any function that maps a big variable-length data structure to a smaller (fixed-length) data structure." is incorrect; the source size isn't relevant.

The source size is extremely relevant, in the property that the function is able to work with variable sized input including large input. This definition has obviously embedded its purpose unto itself. The reason we have such cryptographically secure hash functions corresponds to the need to digest large data.

Secure hashes need to be fast. If you look at the ongoing SHA-3 competition, you will see an enormous focus on speed, on both software and hardware.

Why do they need to be fast? They're used everywhere. Opening up notepad.exe, you'll verify a handful of digital signatures, each of which will compute a hash of the binary as first order of business. HMAC is used in virtually every secure network protocol worth using --- it uses an underlying hash as building block. Need a fast (determistic) pseudorandom generator? Hashes it is.

Password hashing (and key derivation) is about the single use of hashes that requires computational hardness. It should be treated separately.

I guess what I don't fully understand is just how computationally intensive (slow) a hash needs to be to produce a reliable fingerprint, that is, one that is as collision free as possible and extremely sensitive to any tiny change in the source data.

I do understand that password related hashes may have arbitrary computational delays added just to make them tougher to brute force, which would be bad in many other (all other?) situations?

Strongly collision-free hash functions are generally in the range of 5-20 clock cycles per byte of data on modern hardware. It's significantly slower than memcpy, but probably significantly faster than your network.

Correct me if I'm wrong, but my understanding is that cryptographic and non-cryptographic hash functions have similar avalanche properties (and therefore similar probability of accidental collision); the difference is just that cryptographic hash functions make it difficult to intentionally create a collision.

Is that right?

Good non-cryptographic hash functions have "good" avalanching behaviour, but the definition of "good" depends on how randomly you expect your inputs to behave and how much a collision costs you. In hash tables, for instance, people often use quite weak -- i.e., poorly avalanching -- hashes since the cost of a collision is quite low.

Probably the best way to phrase it is that non-cryptographic hash functions cover a continuum with checksums at one extreme and cryptographic hash functions at the opposite extreme.

Maybe the question is asked from the wrong perspective - it's not that designers of cryptographic hash functions ask themselves "Hmm, so how fast/slow do we want this thing to be?".

They go the other way round and set a "security parameter" that should hold for a particular instance (all the parameters fixed) of their algorithm. That "security parameter" determines how hard it should be for an arbitrary adversary to break the scheme by brute force, and in addition the scheme is only thought to be secure if there is no polynomial time algorithm that can break it in time significantly less than the brute force algorithm would take.

Given such a security parameter, the art is then typically to design the fastest primitive that upholds this same security margin. For example, if two (unbroken) algorithms would take O(2^80) for a brute force Birthday Attack, then you'd conceive the faster of the two as the "better" algorithm. ("Fast" of course can be subjective, e.g. fast in HW or fast in SW etc.)

For one thing, that's simply just because making an algorithm slower is always possible (PBKDF2), but in practice there are a lot of applications (probably more) where a hash should be as fast as possible rather than as slow as possible, as in digital signatures for example.

The first question is an open one. Not even theoretical cryptography people understand collision resistance very well. From a practical standpoint, though, we know that it can be pulled off reasonably fast; SHA-256 is still standing, for example, and it "only" takes 14 cycles per byte hashed. Not great, but not bad either.

The first written mention of artificially slowing down key derivation was (AFAIK) here: https://www.schneier.com/paper-low-entropy.html The rationale was that, given a key (resp. password) that gives you s bits of security, you apply some function that gives you extra t bits of security, by making bruteforcing it 2^t times more expensive.

Also note that some applications of hash functions don't care about collisions. MD5 is still OK-ish for e.g. HMAC, where what matters is second-preimage resistance.

Morris and Thompson beat Schneier et al. by about two decades; see Password security: a case history, CACM 1979.

> Well, I'd say a hash that has no need whatsoever to be tamper-proof (no attackers, ever) and cares only about speed is a checksum -- so maybe a terminology issue.

Imagine someone trying to attack a BitTorrent tracker by injecting false data packets with "true" hashes. This is a case where you do want the properties of a hash, not a checksum (changing a single bit greatly changes the output; it's hard to figure out an input that will create a matching output) but you don't want the properties of a cryptographically-secure hash (slow to calculate.)

> Well, I'd say a hash that has no need whatsoever to be tamper-proof (no attackers, ever) and cares only about speed is a checksum -- so maybe a terminology issue.

Cityhash, spookyhash, and murmurhash are three modern non-cryptographic hash functions which explicitly don't call themselves "checksums".

Indeed, we say "hashtable", not "checksumtable".

Hash tables have no correlation to cryptography, and the "hash" function in most languages are more closely related to checksums---in fact, the `hash` function in python for ints is the identity. I would never assume that a hash is intended to be secure in any sense, just a function that produces an integer from an arbitrary data source.

I would not call "a hash that has no need whatsoever to be tamper-proof and cares only about speed" a checksum. You don't use checksums to create a hash table. Now some checksum would be suitable for that use, but not all. So let's continue to call a hash a hash.