3 ms·
> A CRC extended out to 256-bits would catch all 256-bit bursts, which SHA1 cannot do. This is technically true, but misses the practical point. The chance of
by jiggawatts 5y ago
> A CRC extended out to 256-bits would catch all 256-bit bursts, which SHA1 cannot do.
This is technically true, but misses the practical point. The chance of a contiguous 256-bit burst causing a SHA1 hash collision with the original unmodified byte string is 1 in 2^160, which is about 1 per 10^48 for a given input value. This is 1 in ( 1 trillion )^4. Or one per a trillion-trillion-trillion-trillion.
(Remember that the "birthday paradox" doesn't apply: we're not comparing a large set of values against all of the others, we're comparing a value with its may-be-corrupted copy only.)
For reference, typical computer hardware has 1 bit error per hour for each 10^11 to 10^30 bits stored or processed.[1] Just cosmic rays or background radiation alone will cause bit flips in all hardware at a rate comparable to this. While ECC memory and ECC processor caches reduce the error rate, they don't eliminate it. Typical improvements for contiguous errors in ECC DRAM are a factor of 256 (8-bit parity).
This means that even if you had a perfect checksum, the boolean returned by the "crc256()" function itself is a physical bit in memory subject to this corruption! Hence, there's a "noise floor" that no checksum can improve upon, because the output storage is also noisy. It might correctly detect the error, but then its output will be flipped back to "no error" by an errant relativistic particle!
The SHA1 hash collision rate is 10^16 times better than even the optimistic 10^30 error rate for reliable components even with an 8-bit ECC thrown on top! In other words, even on really, really good hardware, you'll get a thousand trillion times more false detections caused by bit flips than missed detections caused by the choice of hash algorithm. That's with SHA1. If you're paranoid, SHA512 is in the league of "not if every atom in the universe was a computer" levels of assurance.
As long as the hash is significantly better than this "system-wide" bit error rate, it is effectively perfect when implemented by practical, physical computers. Further software improvements are pointless without accompanying improvements to the hardware.
[1] https://en.wikipedia.org/wiki/ECC_memory#Research https://en.wikipedia.org/wiki/ECC_memory#Research
PS: This kind of "analog" thinking related to digital computer reliability becomes important at large scales. For example, filesystems like ZFS are sensitive to bit flips. It has a known failure mode where a corruption of certain regions of its Merkle tree will corrupt the whole disk array. Similarly, I've heard of algorithms being redesigned to be tolerant of bit flips, returning at least partially valid data. E.g.: instead of maintaining a count and incrementing/decrementing it over time, prefer to measure the count from scratch every time. That way it'll be correct most of the time, instead of becoming permanently corrupt and staying that way.
- dragontamer 5y agoAnd my point: assuming a random error, your SHA1 is no better than a simple checksum. So what's your error model? You make a big post about the nature of errors but you fail to specify the distribution of errors. If your distribution of errors is uniformly random, then a 128-bit checksum is optimal. The reason why checksum isn't used, is because in practice, there are long-strings of "0" in data and "0" for errors / communications. Checksum fails to distinguish between 20x 0s in a row and 200x 0s in a row. Is that a problem you expect to find in files? If your distribution of errors is bursty, then 128-bit CRC is optimal. What distribution of errors are you assuming for SHA1? What kind of file errors are you expecting that makes SHA1 better than other methodologies? --------- If all errors are random, and you want to distinguish from the "multiple 0s" problem, then the Adler32-like checks are sufficient at fixing both those problems, and the Adler32 methodology obviously extends out to 128-bits (just have two 64-bit sums) CRC, specifically, is designed to optimally check for burst errors of its full length. (32-bit CRC finds all 32-bit burst errors. 128-bit CRC would find all 128-bit burst errors). That all CRC is, and that's all CRC is designed / math'd out to do.
- jiggawatts 5y agoThe key thing about cryptographic hashes (not mere checksums) like SHA1 is that the distribution of the errors doesn't matter. Effectively, they're all the same. That's the point. If mere "runs" of bits were sufficient to trigger a collision, then the hash wouldn't be strong enough for cryptography! This means that you can simply throw out any such modelling, as it is no longer relevant. You "care" only about bit-error-rates and hash collision rates, but even mere SHA1 is so thoroughly past the BER that it is essentially perfect. That is, it is indistinguishable from perfect on all pratical computers for all intents and purposes. CRC codes have their uses, but if you just need to detect any corruption of a large-ish file (over 10KB), then cryptographic hashes are both fast and "perfect" in this physical sense. You will never get a collision with SHA256 or SHA512, even including adversarial, crafted inputs. The same "strength" attribute is not valid for CRC codes, they're vulnerable to deliberate corruption by an attacker. So in that sense, SHA hashes are stronger that CRC checksums.
- 5y ago