4 ms·

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 issu

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. I agree there are certainly other uses for hashes, just trying to distinguish between hashes and checksums. Re-reading what I wrote, I open with "Hashes are a bit like fingerprints for data. A given hash uniquely represents a file, or any arbitrary collection of data" so the context of this article is hash functions that are able to uniquely identify something in a reliable, trustworthy way -- either checksums (fast, no need for security) or hashing (slower, more reliable, possibly "secure" for some definition of secure), but always in the context of "can I trust this value to tell me that the data is really what I think it is?" Of course there is a tradeoff with speed; a person's name can be good enough identifier (checksum) in some circumstances, but maybe other circumstances require more reliability like DNA or fingerprints (secure-ish hash), at the cost of being far slower to collect and validate and way more onerous.

nadam 14y ago
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').
- ralph 14y ago
  I have hash functions that work on less bytes than the length of the hash they produce.
  - arethuza 14y ago
    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.
    - ralph 14y ago
      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.
      - dekz 14y ago
        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.
pbsd 14y ago
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.
- codinghorror 14y ago
  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?
  - pbsd 14y ago
    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 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.
    - cperciva 14y ago
nooop 14y ago
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.
duaneb 14y ago
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.
derefr 14y ago
> 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.)
jlebar 14y ago
> 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".

nadam 14y ago

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

ralph 14y ago
I have hash functions that work on less bytes than the length of the hash they produce.
- arethuza 14y ago
  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.
  - ralph 14y ago
    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.
    - dekz 14y ago
      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.

pbsd 14y ago

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.

codinghorror 14y ago
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?
- pbsd 14y ago
  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 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.
  - cperciva 14y ago

nooop 14y ago

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.

duaneb 14y ago

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.

derefr 14y ago

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

jlebar 14y ago

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