4 ms·
For perfectly uniform random-errors, it doesn't matter how you hash / error check. But if there's a certain class of errors you expect, you can do far better th
by dragontamer 5y ago
For perfectly uniform random-errors, it doesn't matter how you hash / error check. But if there's a certain class of errors you expect, you can do far better than just random.
In particular: CRC are theoretically perfect/ideal for burst errors. A CRC32 can detect all burst errors of size 32 (aka: if the error is within 32-bits, the CRC32 will always catch it). A CRC extended out to 256-bits would catch all 256-bit bursts, which SHA1 cannot do.
EDIT: "Burst errors" are incredibly common in communications. If there's some kind of electrical noise (static shock or the like) would destroy maybe 20-bits all in a row. Aka: a 20-bit burst error.
Similarly, CD-ROMs were designed to primarily protect against burst errors, because people assumed that CDs would get scratched. I forget exactly how the calculations were done, but some number of "millimeters of damage" were the assumed damage (maybe 4mm or 5mm) as typical, and then CD-ROMs were designed to be resilient even in the face of scratches of that size (or less).
- adrian_b 5y agoYou are right, but I have not seen any published data about the properties of some concrete 128-bit or 256-bit CRC's that could be chosen. For 32-bit or smaller CRC's there are a large number of publications analyzing various useful polynomials and there is also some published data about a few 64-bit polynomials. So if you want to use a CRC larger than 64-bit, you must first spend some time to learn and understand very well the theory of CRCs, then search for some suitable polynomials and test them. It is unlikely that this would be worthwhile in most cases. In practice, CRCs of up to 64-bit are very useful to detect errors in data packets of limited length, like in the data packets sent and received through some communication protocol, or in the headers or other components of limited size of some structured kind of data file. CRCs of the available lengths are usually not suitable to check the integrity of entire data files, because in modern computers the files have become too large and too many. Therefore a file utility like the traditional UNIX cksum has become obsolete when used to compute CRC values for files. (The latest GNU cksum has become a generic utility, where you can specify other hash algorithms instead of the default CRC-32) While this is expected due to the short length of CRC-32, I have actually verified that when computing the CRC-32 values for all the files on my 2 TB SSD I have obtained about seven hundreds of CRC collisions, i.e. pairs of completely different files that had identical CRC-32 values. Even with the obsolete 128-bit MD5 hash there were no collisions, but as another poster mentioned, on modern CPUs with hardware support MD5 is slower than SHA-1 or SHA-256, so there is no reason to ever use it. While SHA-1 is insecure for digital signatures and other applications for which an opponent must not be able to find collisions, because SHA-1 remains faster than SHA-256, it remains useful for error detection in many cases, e.g. for detecting whole file corruption.
- dragontamer 5y ago> You are right, but I have not seen any published data about the properties of some concrete 128-bit or 256-bit CRC's that could be chosen. I mean, sure. But what published data do you have about SHA1's error detection properties? SHA1 doesn't have a hamming distance analysis associated with it, not at all... nor is there any kind of "burst error" analysis (or the like) associated with it. The only analysis you got on SHA1 is differential cryptography, and other such maths that have little or no relevance with regards to the kinds of errors we expect to see in data. Its not too hard to pick a 128-bit burst error CRC-128. In fact, all CRC-128 would detect 128-bit burst errors. The "high quality CRC" is about the difficult question of hamming distances and other such properties. ----- IMO: picking SHA1 is basically saying you don't care about those details. Which is a fine choice to make. But it seems odd that you'd criticize CRC for "not having enough analysis" when SHA1 barely has any at all.
- CorrectHorseBat 5y agoIt's been a while, but is it not the other way around? CRCs can detect (or correct for y smaller than x) up to x bits in a w bit message. If there are more errors in a burst CRC will not catch it. SHA will detect any error of any size, but you can't correct it so for many applications such as cd's it's not very useful. IIRC in CDs they solved this by simply spreading the RS correction codes and data around so bursts aren't bursts anymore.
- dragontamer 5y ago> If there are more errors in a burst CRC will not catch it. *Might* not catch it. Just like how SHA1 might not catch a 3-bit error if you find a collision in just the right spots. Consider a 1024-bit message, and 1023-bits are in error. The CRC would trivially, and obviously, catch the error (because this would be "obviously" a 1-bit parity error, and the CRC's bottom bit is always a simple 1-bit parity) In fact, there's all sorts of errors CRC are guaranteed to catch. The "burst error" is the one that most people care about, but "odd errors" (ex: 511-bit or 4095-bit errors, thanks to the bottom parity bit) are guaranteed to be caught as well. --------- CRC is "so regular", it is very easy to prove the specific kinds of errors that can, or cannot, be caught. According to classical theory of communications, there are really only two errors to care about: 1. Random errors -- your methodology doesn't matter. Simple checksum or even XOR is provably optimal vs random errors (!!), and indistinguishable from a SHA1. 2. Burst errors -- Your connection goes dead for a time: this leads to 10 bits all in a row in error (lets say some electrical storm or static-shock, or other such phenomenon causes the antenna / line / whatever to be dead for 10-microseconds, on a 1MHz baud rate connection. That's 10-bits that disappear, aka a 10-bit burst error). Because #1 doesn't care "which methodology" you use, its all about optimizing against #2.
- 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.