Cyclic Redundancy Check - Commonly Used and Standardized CRCs

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 (1817–1862)

    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)