15

I'm trying to calculate the Frame Check Sequence (FCS) of an Ethernet packet byte by byte. The polynomial is 0x104C11DB7. I did follow the XOR-SHIFT algorithm seen here http://en.wikipedia.org/wiki/Cyclic_redundancy_check or here http://www.woodmann.com/fravia/crctut1.htm

Assume the information that is supposed have a CRC is only one byte. Let's say it is 0x03.

  1. step: pad with 32 bits to the right

    0x0300000000

  2. align the polynomial and the data at the left hand side with their first bit that is not zero and xor them

    0x300000000 xor 0x209823B6E = 0x109823b6e

  3. take remainder align and xor again

    0x109823b6e xor 0x104C11DB7 = 0x0d4326d9

Since there are no more bit left the CRC32 of 0x03 should be 0x0d4326d9

Unfortunately all the software implementations tell me I'm wrong, but what did I do wrong or what are they doing differently?

Python tells me:

 "0x%08x" % binascii.crc32(chr(0x03))
 0x4b0bbe37

The online tool here http://www.lammertbies.nl/comm/info/crc-calculation.html#intr gets the same result. What is the difference between my hand calculation and the algorithm the mentioned software uses?

UPDATE:

Turns out there was a similar question already on stack overflow:

You find an answer here Python CRC-32 woes

Although this is not very intuitive. If you want a more formal description on how it is done for Ethernet frames you can look at the Ethernet Standard document 802.3 Part 3 - Chapter 3.2.9 Frame Check Sequence Field

Lets continue the example from above:

  1. Reverse the bit order of your message. That represents the way they would come into the receiver bit by bit.

    0x03 therefore is 0xC0

  2. Complement the first 32 bit of your message. Notice we pad the single byte with 32 bit again.

    0xC000000000 xor 0xFFFFFFFF = 0x3FFFFFFF00

  3. Complete the Xor and shift method from above again. After about 6 step you get:

    0x13822f2d

  4. The above bit sequense is then complemented.

    0x13822f2d xor 0xFFFFFFFF = 0xec7dd0d2

  5. Remember that we reversed the bit order to get the representation on the Ethernet wire in step one. Now we have to reverse this step and we finally fulfill our quest.

    0x4b0bbe37

Whoever came up with this way of doing it should be ...

A lot of times you actually want to know it the message you received is correct. In order to achieve this you take your received message including the FCS and do the same step 1 through 5 as above. The result should be what they call residue. Which is a constant for a given polynomial. In this case it is 0xC704DD7B.

As mcdowella mentions you have to play around with your bits until you get it right, depending on the Application you are using.

Community
  • 1
  • 1
sebs
  • 4,566
  • 3
  • 19
  • 28
  • 1
    Where does 0x209823B6E come from? – grieve Feb 15 '12 at 05:31
  • Also did you set your initial remainder to 0xFFFFFFFF – grieve Feb 15 '12 at 05:48
  • the 0x209823B6E is a shifted version of the polynomial to align it with the data – sebs Feb 15 '12 at 20:56
  • @sebs, shifted how? – cp.engr Jan 24 '17 at 19:29
  • 1
    @cp.engr shifted by one bit left. `(0x104C11DB7 << 1)` – sebs Nov 27 '18 at 17:38
  • The "residue" depends on hardware implementation. If following the standard, the bytes would have to be buffered, in order to calculate the standard's left shifting CRC. Instead, a right shifting CRC can be used to calculate the CRC on the fly. A hardware implementation could use either a right or left shifting LFSR like register to calculate the CRC, so the "residue" may be bit reversed, resulting in 0xDEBB20E3 (right shifting) or 0xC704DD7B (left shifting). – rcgldr Jan 31 '20 at 20:54
  • Compounding the issue is that data is transmitted lsb (bit 0) first, while the FCS is transmitted msb (bit 31) first. – rcgldr Jan 31 '20 at 20:57

4 Answers4

9

This snippet writes the correct CRC for Ethernet.

Python 3

# write payload
for byte in data:
    f.write(f'{byte:02X}\n')
# write FCS
crc = zlib.crc32(data)
for i in range(4):
    byte = (crc >> (8*i)) & 0xFF
    f.write(f'{byte:02X}\n')

Python 2

# write payload
for byte in data:
    f.write('%02X\n' % ord(byte))
# write FCS
crc = zlib.crc32(data) & 0xFFFFFFFF
for i in range(4):
    byte = (crc >> (8*i)) & 0xFF
    f.write('%02X\n' % byte)

Would have saved me some time if I found this here.

maxy
  • 4,971
  • 1
  • 23
  • 25
  • This saved me hours of strife. Thank you, thank you. – dinkelk Nov 06 '19 at 16:50
  • Thanks for this code. Helped out a lot. What's the purpose of and-ing the zlib.crc(data) with f's? crc is already going to be a 32-bit int, so and-ing with 32 bits of '1' will just return the same thing whether zlib.crc32(data) returns 1 or 2^32-1. Not a big deal because everything works either way, but it confused me a tiny bit. Thanks. – Michael Grover Aug 04 '22 at 05:36
  • It's not needed for Python3, thanks for pointing it out. (I've edited the answer.) In Python2 the result can be negative: https://docs.python.org/3/library/zlib.html#zlib.crc32 – maxy Aug 04 '22 at 18:06
4

There is generally a bit of trial and error required to get CRC calculations to match, because you never end up reading exactly what has to be done. Sometimes you have to bit-reverse the input bytes or the polynomial, sometimes you have to start off with a non-zero value, and so on.

One way to bypass this is to look at the source of a program getting it right, such as http://sourceforge.net/projects/crcmod/files/ (at least it claims to match, and comes with a unit test for this).

Another is to play around with an implementation. For instance, if I use the calculator at http://www.lammertbies.nl/comm/info/crc-calculation.html#intr I can see that giving it 00000000 produces a CRC of 0x2144DF1C, but giving it FFFFFFFF produces FFFFFFFF - so it's not exactly the polynomial division you describe, for which 0 would have checksum 0

From a quick glance at the source code and these results I think you need to start with an CRC of 0xFFFFFFFF - but I could be wrong and you might end up debugging your code side by side with the implementation, using corresponding printfs to find out where the first differ, and fixing the differences one by one.

mcdowella
  • 19,301
  • 2
  • 19
  • 25
3

There are a number of places on the Internet where you will read that the bit order must be reversed before calculating the FCS, but the 802.3 spec is not one of them. Quoting from the 2008 version of the spec: 

3.2.9 Frame Check Sequence (FCS) field

A cyclic redundancy check (CRC) is used by the transmit and receive algorithms to
generate a CRC value for the FCS field. The FCS field contains a 4-octet (32-bit)
CRC value. This value is computed as a function of the contents of the protected
fields of the MAC frame: the Destination Address, Source Address, Length/ Type 
field, MAC Client Data, and Pad (that is, all fields except FCS). The encoding is
defined by the following generating polynomial.

  G(x) = x32 + x26 + x23 + x22 + x16 + x12 + x11 
             + x10 + x8 + x7 + x5 + x4 + x2 + x + 1

Mathematically, the CRC value corresponding to a given MAC frame is defined by 
the following procedure:

a) The first 32 bits of the frame are complemented.
b) The n bits of the protected fields are then considered to be the coefficients
   of a polynomial M(x) of degree n – 1. (The first bit of the Destination Address
   field corresponds to the x(n–1) term and the last bit of the MAC Client Data 
   field (or Pad field if present) corresponds to the x0 term.)
c) M(x) is multiplied by x32 and divided by G(x), producing a remainder R(x) of
   degree ≤ 31.
d) The coefficients of R(x) are considered to be a 32-bit sequence.
e) The bit sequence is complemented and the result is the CRC.

The 32 bits of the CRC value are placed in the FCS field so that the x31 term is
the left-most bit of the first octet, and the x0 term is the right most bit of the
last octet. (The bits of the CRC are thus transmitted in the order x31, x30,..., 
x1, x0.) See Hammond, et al. [B37].

Certainly the rest of the bits in the frame are transmitted in reverse order, but that does not include the FCS. Again, from the spec:

3.3 Order of bit transmission

Each octet of the MAC frame, with the exception of the FCS, is transmitted least
significant bit first.
Burkart
  • 462
  • 4
  • 9
Daniel Wisehart
  • 1,489
  • 12
  • 31
  • It's just implicit that "first bit" and "last bit" refer to transmission order ­— they *don't* say "most significant bit" or "least significant bit" for that reason :) – hobbs Mar 06 '15 at 17:37
  • The standard describes CRC32 BZIP2, which is a left shifting CRC, then transmitting data lsb first, but the FCS msb (bit 31) first. An alternative is to use the right shifting CRC32, which results in a CRC that is the bit reversal of the FCS, after which both the data and CRC can be sent least significant bit first, resulting in identical transmission. The standard also mentions that the receiver should compare it's calculated FCS with the received FCS, but an alternative is to generate CRC on data + FCS, resulting in a fixed non-zero value that depends on the implementation. – rcgldr Jan 31 '20 at 20:49
2

http://en.wikipedia.org/wiki/Cyclic_redundancy_check

has all the data for ethernet and wealth of important details, for example there are (at least) 2 conventions to encode polynomial into a 32-bit value, largest term first or smallest term first.

Dima Tisnek
  • 11,241
  • 4
  • 68
  • 120