Commonly Used and Standardized CRCs
Numerous varieties of cyclic redundancy checks have been incorporated into technical standards. By no means does one algorithm, or one of each degree, suit every purpose; Koopman and Chakravarty recommend selecting a polynomial according to the application requirements and the expected distribution of message lengths. The number of distinct CRCs in use has confused developers, a situation which authors have sought to address. There are three polynomials reported for CRC-12, sixteen conflicting definitions of CRC-16, and six of CRC-32.
The polynomials commonly applied are not the most efficient ones possible. Between 1993 and 2004, Koopman, Castagnoli and others surveyed the space of polynomials up to 16 bits, and of 24 and 32 bits, finding examples that have much better performance (in terms of Hamming distance for a given message size) than the polynomials of earlier protocols, and publishing the best of these with the aim of improving the error detection capacity of future standards. In particular, iSCSI and SCTP have adopted one of the findings of this research, the CRC-32C (Castagnoli) polynomial.
The design of the 32-bit polynomial most commonly used by standards bodies, CRC-32-IEEE, was the result of a joint effort for the Rome Laboratory and the Air Force Electronic Systems Division by Joseph Hammond, James Brown and Shyan-Shiang Liu of the Georgia Institute of Technology and Kenneth Brayer of the MITRE Corporation. The earliest known appearances of the 32-bit polynomial were in their 1975 publications: Technical Report 2956 by Brayer for MITRE, published in January and released for public dissemination through DTIC in August, and Hammond, Brown and Liu's report for the Rome Laboratory, published in May. Both reports contained contributions from the other team. During December 1975, Brayer and Hammond presented their work in a paper at the IEEE National Telecommunications Conference: the IEEE CRC-32 polynomial is the generating polynomial of a Hamming code and was selected for its error detection performance. Even so, the Castagnoli CRC-32C polynomial used in iSCSI or SCTP matches its performance on messages from 58 bits to 131 kbits, and outperforms it in several size ranges including the two most common sizes of Internet packet. The ITU-T G.hn standard also uses CRC-32C to detect errors in the payload (although it uses CRC-16-CCITT for PHY headers).
The table below lists only the polynomials of the various algorithms in use. Variations of a particular protocol can impose pre-inversion, post-inversion and reversed bit ordering as described above. For example, the CRC32 used in both Gzip and Bzip2 use the same polynomial, but Bzip2 employs reversed bit ordering, while Gzip does not.
CRCs in proprietary protocols might use a non-trivial initial value and final XOR for obfuscation but this does not add cryptographic strength to the algorithm. An unknown error-detecting code can be characterized as a CRC, and as such fully reverse engineered, from its output codewords.
Name | Uses | Representations | ||
---|---|---|---|---|
Normal | Reversed | Reversed reciprocal | ||
CRC-1 | most hardware; also known as parity bit | 0x1 | 0x1 | 0x1 |
CRC-4-ITU | G.704 | 0x3 | 0xC | 0x9 |
CRC-5-EPC | Gen 2 RFID | 0x09 | 0x12 | 0x14 |
CRC-5-ITU | G.704 | 0x15 | 0x15 | 0x1A |
CRC-5-USB | USB token packets | 0x05 | 0x14 | 0x12 |
CRC-6-ITU | G.704 | 0x03 | 0x30 | 0x21 |
CRC-7 | telecom systems, G.707, G.832, MMC, SD | 0x09 | 0x48 | 0x44 |
CRC-8-CCITT | I.432.1; ATM HEC, ISDN HEC and cell delineation | 0x07 | 0xE0 | 0x83 |
CRC-8-Dallas/Maxim | 1-Wire bus | 0x31 | 0x8C | 0x98 |
CRC-8 | 0xD5 | 0xAB | 0xEA | |
CRC-8-SAE J1850 | AES3 | 0x1D | 0xB8 | 0x8E |
CRC-8-WCDMA | 0x9B | 0xD9 | 0xCD | |
CRC-10 | ATM; I.610 | 0x233 | 0x331 | 0x319 |
CRC-11 | FlexRay | 0x385 | 0x50E | 0x5C2 |
CRC-12 | telecom systems | 0x80F | 0xF01 | 0xC07 |
CRC-15-CAN | 0x4599 | 0x4CD1 | 0x62CC | |
CRC-15-MPT1327 | 0x6815 | 0x540B | 0x740A | |
CRC-16-IBM | Bisync, Modbus, USB, ANSI X3.28, SIA DC-07, many others; also known as CRC-16 and CRC-16-ANSI | 0x8005 | 0xA001 | 0xC002 |
CRC-16-CCITT | X.25, V.41, HDLC FCS, XMODEM, Bluetooth, PACTOR, SD, many others; known as CRC-CCITT | 0x1021 | 0x8408 | 0x8810 |
CRC-16-T10-DIF | SCSI DIF | 0x8BB7 | 0xEDD1 | 0xC5DB |
CRC-16-DNP | DNP, IEC 870, M-Bus | 0x3D65 | 0xA6BC | 0x9EB2 |
CRC-16-DECT | cordless telephones | 0x0589 | 0x91A0 | 0x82C4 |
CRC-16-ARINC | ACARS applications | 0xA02B | 0xD405 | 0xD015 |
CRC-16-Fletcher | Used in Adler-32 A & B CRCs | Not a CRC; see Fletcher's checksum | ||
CRC-24 | FlexRay | 0x5D6DCB | 0xD3B6BA | 0xAEB6E5 |
CRC-24-Radix-64 | OpenPGP | 0x864CFB | 0xDF3261 | 0xC3267D |
CRC-30 | CDMA | 0x2030B9C7 | 0x38E74301 | 0x30185CE3 |
CRC-32-Adler | Zlib | Not a CRC; see Adler-32 | ||
CRC-32 | HDLC, ANSI X3.66, ITU-T V.42, Ethernet, Serial ATA, MPEG-2, PKZIP, Gzip, Bzip2, PNG, many others) | 0x04C11DB7 | 0xEDB88320 | 0x82608EDB |
CRC-32C (Castagnoli) | iSCSI, SCTP, G.hn payload, SSE4.2, Btrfs, ext4 | 0x1EDC6F41 | 0x82F63B78 | 0x8F6E37A0 |
CRC-32K (Koopman) | 0x741B8CD7 | 0xEB31D82E | 0xBA0DC66B | |
CRC-32Q | aviation; AIXM | 0x814141AB | 0xD5828281 | 0xC0A0A0D5 |
CRC-40-GSM | GSM control channel | 0x0004820009 | 0x9000412000 | 0x8002410004 |
CRC-64-ISO | HDLC, Swiss-Prot/TrEMBL; considered weak for hashing | 0x000000000000001B | 0xD800000000000000 | 0x800000000000000D |
CRC-64-ECMA-182 | ECMA-182, XZ Utils | 0x42F0E1EBA9EA3693 | 0xC96C5795D7870F42 | 0xA17870F5D4F51B49 |
Read more about this topic: Cyclic Redundancy Check
Famous quotes containing the words commonly and/or standardized:
“The humblest observer who goes to the mines sees and says that gold-digging is of the character of a lottery; the gold thus obtained is not the same thing with the wages of honest toil. But, practically, he forgets what he has seen, for he has seen only the fact, not the principle, and goes into trade there, that is, buys a ticket in what commonly proves another lottery, where the fact is not so obvious.”
—Henry David Thoreau (18171862)
“Twenty or thirty years ago, in the army, we had a lot of obscure adventures, and years later we tell them at parties, and suddenly we realize that those two very difficult years of our lives have become lumped together into a few episodes that have lodged in our memory in a standardized form, and are always told in a standardized way, in the same words. But in fact that lump of memories has nothing whatsoever to do with our experience of those two years in the army and what it has made of us.”
—Václav Havel (b. 1936)