5 ms·
Generally, given the CPU acceleration available, one should generally prefer SHA1 or SHA256. CRC/MD5 is really only advisable if you're being forced into it for
by vlovich123 5y ago
Generally, given the CPU acceleration available, one should generally prefer SHA1 or SHA256. CRC/MD5 is really only advisable if you're being forced into it for some legit backward compatibility reason. Most embedded CPUs these days can handle SHA variants just fine (I've used SHA256 on an M3 and even more crazily on the Kalimba of a CSR8605 which is a 48-bit DSP with a char size of 24 bits as well as its coprocessor which is a 32-bit CPU which a char size of 16 bits).
- zbjornson 5y agoCRCs have the awesome ability to be composed, and are many times faster to compute than SHAs with the best hardware acceleration.
- nullc 5y agoAnd can also give guaranteed distance properties-- so you can e.g. guarantee all corruption of hamming distance <D within a message size of <W will be detected, -- which is a massive improvement in performance when that's what you need to catch.
- CorrectHorseBat 5y agoSHA will detect corruption of any size, but it can't be used for correction.
- nullc 5y agoIt (and particularly truncated hashes made from it) is not _guaranteed_ to detect small corruptions. It will falsely admit 1 in 2^bits. A well matched CRC is can give guaranteed detection even with a very short hash.
- adrian_b 5y agoTrue, but one must not forget that the good error detection properties of CRCs are guaranteed only for limited data lengths. The CRCs of usual sizes, up to 32 bits, are perfectly fine for data sizes in the kilobyte range, but they become poor at megabyte sizes and completely useless at gigabyte sizes. The CRCs have their domain of application for which they are excellent, but some times they are misused, e.g. in various archive file formats, where the archive integrity is checked with a too short CRC instead of using a hash of appropriate length, e.g. SHA-1 or SHA-256. The longer hashes may be truncated, e.g. to 128 bit, which is likely enough for the current sizes of files and file systems, but 64-bit or less is not enough for the kind of files that are typically encountered now.
- nullc 5y ago> only for limited data lengths. That's true-- and it's why my message up thread said so explicitly. Though you can design CRC-like codes which work over extremely long cycle lengths pretty easily, if that is your objective.
- CorrectHorseBat 5y agoIs 64 bit really not enough? 2^64 is a very big number.
- adrian_b 5y agoThe size needed for an error detection code depends on the size of the data from which it was computed, on the error rate and on the time that passes since the error detection code is generated until it is verified. With data sent through communication channels, the error rate may be high, but the data reaches its destination after a few seconds. On an archival storage medium, the error rate may be very low, but you might check for corruption only some years later. If you want to decide which is the acceptable error detection length, the best way would be to make a simulation, with random data of the expected length to which various random errors having the expected number should be applied. Then you can test the alternative error detection codes to see whether they detect the errors or not. I expect that for data sizes of a few megabytes a 64-bit CRC should be OK. From my experiments with gigabyte-sized files, 32-bit CRCs were completely inadequate, 128-bit hashes were OK and 64-bit CRCs were inconclusive. (By OK and inconclusive, I mean that 128-bit hashes detected all the errors generated, but I have seen 2 cases not detected by CRC-64 in several tens of millions of tests at a 5 GB file size, which was more than expected but statistically insignificant.) Because the speed of 128-bit to 256-bit non-CRC hashes, e.g. Poly1305, SHA-1, SHA-256 or BLAKE3 is very high on modern CPUs, i.e. much faster than any CRC implementation that does not use PCLMUL or equivalent instructions, and of similar speed to a 64-bit CRC with PCLMUL after the overhead for data movement is accounted for, and because there is very little published information about the properties of the few 64-bit CRCs known, I have not made any extra experiments to confirm whether a 64-bit CRC might be adequate, because using any 128-bit hash was more certain to give good results without any disadvantages. On the other hand, for a hardware implementation it would make sense to determine whether a 64-bit CRC is good enough for a certain application.
- adrian_b 5y agoAlso, it must be kept in mind that CRCs, i.e. the remainders of polynomial division, are not the only simple way to obtain predictable error properties. A simple alternative is to evaluate the polynomial corresponding to the data at a certain point and use the value as the error detection code. The properties about short bursts are identical. Polynomial evaluation is advantageous at large hash sizes instead of CRC, because it matters very little at which point you choose to evaluate the polynomial, as long as it is non-null and non-unit. With CRCs, the choice of the primitive polynomial to be used as divisor is critical and you cannot choose just a random 128-bit sequence and hope that it happens to correspond to a primitive polynomial and also to one with good error detection properties. For example, if you want guaranteed error-burst detection for a data size where the known 32-bit or 64-bit CRCs are inadequate, you may use the Poly1305 evaluation functions available in most cryptographic libraries for data authentication. When used in cryptography, the point chosen for the polynomial evaluation must be secret, but for error detection it may be fixed and public and you get error detection properties equivalent with an 128-bit CRC. An optimized 128-bit CRC might be a little better, but good luck to finding the right 128-bit primitive polynomial.
- adrian_b 5y agoCRC's are many times faster when implemented in hardware, e.g. in a network interface card that checks the CRC of Ethernet data packets. When computing a CRC in software, in a CPU that has instructions for both CRC and for SHA-1/SHA-256, e.g. a modern Intel/AMD CPU or a 64-bit ARM CPU, there remains a speed difference, but in most cases reading the data from the memory or from a SSD/HDD takes so much time that the difference in speed is negligible. Moreover, until very recently most utilities that compute CRC's over files, e.g. UNIX cksum, did not use the special instructions for polynomial multiplication, but they used generic algorithms with precomputed tables. The consequence was that for example most versions of cksum are much slower than the corresponding versions of sha1sum.
- dragontamer 5y agoFor 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.