Working with CRCs - jonelo/jacksum GitHub Wiki

Table of Contents

• What is a CRC?
• Standard CRCs
• Customized CRCs
  • CRCs with 6 parameters (the Rocksoft™ Model)
  • CRCs with 7 parameters
  • CRCs with 8 parameters
• Investigate CRC parameters
• Find the CRC algorithm that had generated a certain check value
  • Knowing both a byte sequence and the CRC value
  • Knowing both a file and the CRC value
• Links

A cyclic redundancy check (CRC) is an error-detecting code commonly used in digital networks and storage devices to detect accidental changes to digital data. Blocks of data entering these systems get a short check value attached, based on the remainder of a polynomial division of their contents.

CRCs are so called because the check (data verification) value is a redundancy (it expands the message without adding information and the algorithm is based on cyclic codes.

Because the check value has a fixed length, the function that generates it is also actually a simple, non-cryptographic hash function.

See also https://en.wikipedia.org/wiki/Cyclic_redundancy_check

Jacksum supports a wide range of well known CRCs.

Example: get the Castagnoli CRC-32 from the crc_v3.txt

    $ jacksum -a crc32 crc_v3.txt
    3848729387 89127 crc_v3.txt

The first value of the output is the CRC in decimal. The 2nd value of the output is the file size. The 3rd value of the output is the file name.

There is a popular paper on CRC algorithms written by Ross Williams that was posted to some Internet newsgroups on 19 August 1993. See also http://www.ross.net/crc/crcpaper.html

Jacksum supports the quasi standard called "Rocksoft (tm) Model CRC Algorithm" to specify CRCs by setting the 6 parameters.

Example 1: get the Castagnoli CRC-32 in lower hex

    $ jacksum -a crc:32,1EDC6F41,FFFFFFFF,true,true,FFFFFFFF -x -q txt:123456789
    e3069283 9

Example 2: as above by using an alias

    $ jacksum -a crc32c -x -q txt:123456789
    e3069283 9

An extended model with 7 CRC parameters is also supported in order to define CRCs that incorporate the length of the message. If the 7th parameter is set to true, the most significant octet of the length will be processed first to the update method of the CRC. If it is set to false, the least significant octet of the length will be processed first to the update method of the CRC.

Example 1: get the POSIX 1003.2 CRC algorithm

    $ jacksum -a crc:32,04C11DB7,0,false,false,FFFFFFFF,false -x -q txt:123456789
    377a6011 9

Example 2: as above by using an alias

    $ jacksum -a cksum -x -q txt:123456789
    377a6011 9

An extended model with 8 CRC parameters is also supported in order to define CRCs that incorporate the length of the message, and to XOR the length of the value before it gets included to the CRC.

Example 1: get the output of the sum command from Plan 9:

    $ jacksum -a crc:32,04C11DB7,0,true,true,0,true,CC55CC55 -x -q txt:123456789
    afcbb09a 9

Example 2: as above by using an alias

    $ jacksum -a sum_plan9 -x -q txt:123456789
    afcbb09a 9

CRC parameters can be investigated by the CRC algorithm, and setting the --info option. It returns the polynomial value as a polynomial in math expression, normal, reversed, and Koopman representation, and the reciprocal poly. Example for the Castagnoli CRC-32:

    $ jacksum -a crc32c --info

or by specifying all of the CRC's parameters explicitly:

    $ jacksum -a crc:32,1EDC6F41,FFFFFFFF,true,true,FFFFFFFF --info

  algorithm:
    name:                                 crc32c

  hash length:
    bits:                                 32
    bytes:                                4
    nibbles:                              8

  CRC parameters:
    width (in bits):                      32
    polynomial [hex]:                     1edc6f41
    init [hex]:                           ffffffff
    refIn:                                true
    refOut:                               true
    xorOut [hex]:                         ffffffff

  Polynomial representations:
    mathematical:                         x^32 + x^28 + x^27 + x^26 + x^25 + x^23 + x^22 + x^20 + x^19 + x^18 + x^14 + x^13 + x^11 + x^10 + x^9 + x^8 + x^6 + 1
    normal/MSB first [binary]:            00011110110111000110111101000001
    normal/MSB first [hex]:               1edc6f41
    reversed/LSB first [binary]:          10000010111101100011101101111000
    reversed/LSB first [hex]:             82f63b78
    Koopman [binary]:                     10001111011011100011011110100000
    Koopman [hex]:                        8f6e37a0

  Reciprocal poly (similar error detection strength):
    mathematical:                         x^32 + x^26 + x^24 + x^23 + x^22 + x^21 + x^19 + x^18 + x^14 + x^13 + x^12 + x^10 + x^9 + x^7 + x^6 + x^5 + x^4 + 1
    normal [binary]:                      00000101111011000111011011110001
    normal [hex]:                         5ec76f1

  speed:
    relative rank:                        11/477

  alternative/secondary implementation:
    has been requested:                   false
    is available and would be used:       false

Since Jacksum supports customized algorithms, Jacksum also helps you to find the CRC algorithm to a CRC check value by calling a fast and smart brute force algorithm if the hash is unknown, but the data is known.

If it is a well known CRC definition, Jacksum will find the CRC algorithm within seconds. If the CRC is not-well known, Jacksum will use brute force which is very fast for CRCs having a width of 1 to 16 bits on a normal computer. If it has more than 16 bits, it can take a very long time to print all CRCs that produce the output for the input given.

If you know both a byte sequence and the corresponding CRC value, you can query Jacksum with that information on the command line by specifying -a unknown:<bit width>, -quick <sequence>, and --expect.

In the following example we know one 16 bit CRC value and its hexadecimal representation (--encoding hex --expect d893 or in short -E hex -e d893), and the input bytes in hex that have generated it (-q hex:050000). What we do not know is the 16 bit algorithm that generated the value (-a unknown:16):

    $ jacksum -a unknown:16 -q hex:050000 -E hex -e d893

Trying 13 algorithms with a width of 16 bits that are supported by Jacksum 3.0.0 ...

Trying 30 CRC algorithms with a width of 16 bits by testing against well known CRCs ...
crc:16,1021,FFFF,false,false,FFFF
    --> CRC-16/GENIBUS

Trying all CRC algorithms with a width of 16 bits by brute force (be patient!) ...
crc:16,1021,FFFF,false,false,FFFF
crc:16,37D2,FFFF,true,false,FFFF
crc:16,3E2D,0000,true,false,FFFF
crc:16,4175,FFFF,true,false,FFFF
crc:16,4A5B,FFFF,true,true,0000
crc:16,5A41,FFFF,true,false,FFFF
crc:16,5C63,FFFF,true,true,0000
crc:16,6287,FFFF,true,true,0000
crc:16,649C,0000,false,true,FFFF
crc:16,6D55,FFFF,true,true,0000
crc:16,75AC,FFFF,true,false,FFFF
crc:16,7D64,FFFF,false,false,FFFF
crc:16,81A6,FFFF,true,false,FFFF
crc:16,B9F9,FFFF,true,true,0000
crc:16,C3D6,FFFF,false,false,FFFF
crc:16,D436,0000,true,false,FFFF
crc:16,D6D2,0000,false,true,FFFF
crc:16,DA9C,FFFF,true,false,FFFF
crc:16,E03E,FFFF,false,false,FFFF
crc:16,F701,FFFF,true,false,FFFF


Jacksum: algorithms tested: 1048620
Jacksum: algorithms found: 21

Jacksum: elapsed time: 6 s, 460 ms

    $ jacksum -a crc:16,1021,FFFF,false,false,FFFF -E hex -q txt:"Hello World"

If you do not know the byte sequence, but the content of a file that generated the CRC value you can specify -q file:<file> for the input. Note that the file will be read entirely into memory once in order to avoid repeated read operations that the brute force algorithm would trigger. Therefore the size of <file> is limited to 128 MiB.

    $ jacksum -a unknown:16 -q file:input01.dat -E hex -e 42ff

• Cyclic Redundancy Check by the Wikipedia Community
• A Painless Guide to CRC Error Detection Algorithms by Ross N. Williams, Australia
• Catalogue of parametrised CRC algorithms by Gregory Cook

• Best CRC Polynomials by Professor Philip Koopman, Carnegie Mellon University, USA
• Understanding and implementing CRC (Cyclic Redundancy Check) calculation by Bastian Molkenthin, Germany