Jottings on CRCs

Over the years I’ve learnt a few interesting things about CRCs and I want to write them down for other people to use. The problem I’ve had is that I want the explanations to be understood without needing to understand all of the mathematics behind CRCs, but some of the interesting results come out of the mathematics.

I did consider trying to write a basic explanation of the mathematics starting from scratch emphasising the bits I needed, but that would mean writing a lot of text before I could get to the interesting results.

So, I’m going to try another approach. I’m going to assume that the bulk of the details of the mathematics don’t matter to the explanation and I’ll pull in specific bits only when needed1.

The minimum you need to know is that this mathematics is used because it’s well understood, and the operations can be implemented using just shift and exclusive-or operations, which makes it very easy to implement in digital circuitry.

Some notation

A full CRC encountered in the real world consists of the core-CRC algorithm, an initial seed and sometimes a final exclusive-or. Most of the mathematical properties apply to the core CRC algorithm with the initial seed and exclusive-or having no effect. To make it clearer, I’ll use the following notations:
CRC(seed, message, final_xor)
An arbitrary CRC algorithm run over a message of arbitrary length using the given seed and final exclusive-or.
CRCL(seed, message, final_xor)
An arbitrary CRC algorithm running over a message of length L. “L” may be specific number, such as 8, or a placeholder letter to show two invocations of a CRC algorithm are operating on messages of the same length.
CRCM(message)
An arbitrary CRC algorithm running over a message of arbitrary length using a seed and final exclusive-or of zero, that is, this is just the contribution to the CRC from the message.
CRC-NAME(message)
A specific CRC algorithm run over a message of arbitrary length using the seed and final exclusive-or as specified by that algorithm.
CRC-NAME(seed, message, final_xor)
A specific CRC algorithm run over a message of arbitrary length stating the seeds and final exclusive-or explicitly because they’re relevant to the discussion.
X | Y
A message consisting of X followed by Y.
0 × N
A message consisting of some number of zero bits (another letter may be used instead of N).
⊕
An exclusive-or operation.

These may be combined, so CRC-32M,8 is the CRC algorithm named as “CRC-32” run over an eight byte message with the seed and final exclusive-or set to zero.

Each bit in the CRC is an exclusive-or of some bits in the message

Despite all the maths, each bit in the CRC is just ends up being an exclusive-or of a set of bits in the message (and the seed and any final exclusive-or). This is easiest to see from an implementation2 of the core algorithm that processes a single data bit. The implementation I’ve chosen is close to the most likely single-bit-at-a-time software implementation you’re likely to see. This code is written in a more long-winded way than normal to make the steps a little clearer. 

#define POLY 0x…some_constant…

typedef unsigned …char/short/long… uint;

uint update_crc(uint crc_so_far, unsigned int next_bit)
{
    uint with_next_bit = crc_so_far ^ next_bit;

    crc_so_far >>= 1; /* equals with_next_bit >> 1 */

    if (with_next_bit & 1)
        crc_so_far ^= POLY;

    return crc_so_far;
}

At each step, each bit in the CRC is either a copy of the adjacent bit from the old value, or it’s the three-way exclusive-or of the adjacent bit from the old value, bit zero from the old value and the next data bit. By induction, this shows that each bit in the CRC is an exclusive-or of some set of data bits and the initial value of the CRC register (the seed).

Note that since the three-way exclusive-or contains the adjacent CRC bit and bit zero, and since a given seed or data bit can have been in the bit set for both bit zero and the adjacent bit, and since two exclusive-or operations cancel out, seed and data bits can be both added and removed from the set as the CRC calculation progresses. A seed or data bit will end up in the final set if it was incorporated an odd number of times.

The exact sequence of bits depends on the polynomial that’s chosen but is static when measured from the end of the message. For example, if POLY was 0x81, then bits 0 and 7 of the CRC depend on the last bit of the message but bits 1 through 6 don’t, irrespective of the length of the message.

Flipping a bit in the message flips some bits in the CRC

This is the reverse of the previous result. Each bit in the CRC is the exclusive-or of some set of message bits (and some constants). If that message bit is flipped, then the CRC bits that have that message bit in their list (an odd number of times) are flipped and those that don’t, aren’t.

Again, the pattern depends on the distance from the end of the message. Flipping the last bit in the message flips the bits that are set in the polynomial.

Similarly, flipping a bit in the seed flips some pattern of bits of the CRC. Which bits depends on the length of the message. Flipping a bit in any final exclusive-or flips the corresponding bits in the CRC.

The seed is just the initial value of the CRC accumulator

In the code given earlier, you need an initial value for crc_so_far. That’s known as the seed. That means CRCs have the property:

CRCs are linear

Given the result that each bit in the CRC is an exclusive-or of bits in the seed, message and final exclusive-or and given that the pattern of the bits depends only on the length of the message:

That is, if you exclusive-or together two CRCs for messages of the same length, then that’s the same as one CRC calculated over the exclusive-or of the original components.

In general, you don’t have control of the seed and final exclusive-or. However, you can use the results so far to help. Notably, you can factor out the contribution of the seed and final exclusive-or by calculating the CRC over an all-zero message of the correct length:

CRC error analysis doesn’t depend on the message contents

There is a useful class of analysis where control of the seed doesn’t matter. That’s when you’re dealing with errors induced in communication. These errors don’t alter the seed or final exclusive-or. In that case, the effect is:

Of course, this is not an accident. CRCs are designed to have this property. It’s much easier to make assertions, such as a CRC being able to detect all two-bit errors, if the analysis doesn’t depend on the message contents.

Error separation examples

It’s probably easiest to see what’s going on by looking at some examples and putting together the results so far. I’ll use LDDGO.NET’s online CRC calculator. I’ll use CRC-32 as it has both a non-zero seed and a final exclusive-or and I want to show these can be removed. I’ll start with an eight-byte message.

All data bytes and CRCs are in hex.

First, calculate the CRC over an all-zero message of the right length to isolate the effect of the seed and the final exclusive-or.

This allows us to calculate the CRC contribution from just the eight-byte message contents.

In turn, this means we can calculate the error induced in the CRC by an error in the message regardless of the message contents. Here’s an example for a single bit error:

This can be cross-checked by looking at a couple of arbitrary messages and checking that a bit error in that location gives the same error in both cases:

We can also see that the error depends only on the distance from the error to the CRC by using a longer message:

Zero bits don’t affect a zero CRC

If the CRC accumulator is currently zero and the next data bit is zero, then the CRC stays at zero, that is:

Some CRC choices will start with a non-zero seed so that a sequence of zero bits prepended to the start of the message can be detected. However, for error analysis there’s no error in the seed, so for as long as there are no bits in error, the error contribution to the CRC will stay at zero. This is, of course, by design.

Patterns of errors are undetectable regardless of position

Suppose some pattern of bits, Z, has a CRC of zero (with zero seed and final exclusive-or), that is, CRCM(Z) = 0 then adding zeros to the start and end of this sequence will still have a CRC of zero. That is,

This also works with multiple sequences of undetectable errors at different, or even overlapping, parts of the message.

Quick tests for random CRC errors in a file transfer

Suppose you’ve transferred a file with some protocol which splits the file into pieces and applies a CRC to each piece. You check the final file and it has some errors. You want to know if the errors can be explained by random CRC matches. You can probably just run the CRC algorithm over the original transmitted file and the final received file to see if this is a plausible explanation.

This will work only if each error sequence was confined to bits in the received file and not in other protocol bits that were protected by the CRCs or in the CRCs themselves. Since the data bits can be the overwhelming bulk of the transferred bits, the data bits may be the most likely locations of errors.

This can give both false positives and false negatives, but if you have a lot of erroneous transfers and the bit error rate is low, this can be a good place to start.

Don’t use the same CRC polynomial at multiple layers

It’s likely a short (fits within one packet) error sequence at one layer will be passed intact to the next layer. Because patterns of bit errors missed by an algorithm are missed regardless of position, then if two layers use the same algorithm, the common case is that either both will detect the error or both will miss the error. You don’t get the improved error detection capability you’d expect from two algorithms.

If you’re adding a second CRC specifically to detect errors missed by a CRC in the other layer, then using the same algorithm defeats the purpose.

The restriction is tighter than the layers not using the same algorithm. The pattern of errors missed is independent of the seed and final exclusive-or. The layers must use different polynomials (different CRCM calculations).

You can see this in the Bluetooth® specification. The 16-bit CRC algorithm used for bulk data transfer (ACL) on the original protocol (BR/EDR) was found to be weak when transferring large amounts of data. By the time this was discovered, it was too late to change the over-the-air protocol design (hardware was already shipping). So an extra, optional 16-bit CRC was added at the L2CAP layer. The air protocol already used CRC-CCITT (0x1021) so the L2CAP layer chose the different polynomial CRC-16 (0x8005).

Bluetooth Low Energy, designed later, uses a 24-bit CRC to avoid the weakness in the original 16-bit CRC. Nowadays, both BR/EDR and Low Energy have the option of using cryptographic signatures over the air which have the side effect of providing an extra 32 bits of error detection.

Appending zeros can be calculated in O(log N) time

Recall that the state of the CRC accumulator after part of a message is used as the seed for the calculation for the next part of the message. Recall also that each bit in the CRC is the exclusive-or of some bits in the message and the seed. We can work out where each bit in the seed ends up after appending L zeros by calculating a set of CRCs each with a single bit set in the seed followed by L zeros. That is, we calculate CRCL(1, 0 × L, 0), CRCL(2, 0 × L, 0), CRCL(4, 0 × L, 0) and so on. We can use the linearity of CRCs to work out the result of combine these results for an arbitrary seed, that is, to calculate CRCL(seed, 0 × L, 0), by doing an exclusive-or of the results for each bit that is set in the CRC.

This allows us to work out the CRC for a message with L zero-bytes appended in as many operations as there are bits in the CRC, regardless of L. That makes it O(1) with respect to L.

If we know the polynomial and L in advance we can pre-calculate these tables and append L zeros in one step. However, typically we don’t know L.

Instead, we calculate a set of tables for power-of-two lengths. Then to advance a CRC by an arbitrary length, we advance by the appropriate powers of two for the given length. This is an operation for each bit set in the value of L, and hence has O(log L) performance on average.

If you know neither the polynomial nor the length in advance, or don’t have the space to store the tables for all power-of-two lengths, then the table for length 2L can be calculated for from the table for length L. Again, this has O(log L) performance. This is similar to the technique for raising a matrix to a high integer power.

This technique can be used in odd situations where you don’t know the seed until after the message has been received. You calculate the CRC with a zero seed, work out what the seed should be, advance the seed by the length of the message, then exclusive-or it into the result.

CRCs can be calculated in parallel

Combining the previous results allows you to calculate CRCs in parallel. The most common method you’ll see is to calculate a CRC a nibble or byte at a time using a lookup table. However, with parallel processing you can go further and calculate the CRC in chunks.

Calculate the CRC for chunk in parallel (using zero seed and zero final exclusive-or), then append the appropriate number of zeros in logarithmic time as noted earlier. The results for each chunk can then be combined with exclusive-or using the linearity property. Note that nothing special needs to be done to account for a chunk not starting at the start of the message as prepending zero bits when starting with a zero seed as no effect (as noted earlier).

A non-zero seed can be handled either by using that non-zero seed for the first chunk or by advancing the seed to the end of the message as a separate action (as was done in the error separation example earlier).

If the message is not a multiple of the chunk size, then either use an undersized first chunk (works with a zero or non-zero seed) or prepend zeros the start of the message to bring it up to the chunk size (works only with a zero seed).

You could do a block-chunk parallelism. Break the message up into blocks then each block into chunks. Calculate the CRCs for the chunks within a block as just described. Then combine the results for each block using the same technique.

Parallel calculation example

For a worked example, let’s suppose we want to calculate CRC-8 over the 16 byte message “CRC in parallel.” but doing the two 8 byte blocks in parallel. We build our helper table:

Then we calculate the CRCs for the two parts of the message in parallel using zero seed and final exclusive-or.

We use that CRC for the first part, 0x4C, is 0x40 ⊕ 0x08 ⊕ 0x04, to select entries from the table to wind the first part forward. Then we can combine the parts.

CRC-8 uses a zero seed and final exclusive-or so no fix up is required.

Forcing the CRC to zero

Ignoring the final exclusive-or, for an N-bit CRC, it’s always possible to force the accumulated CRC to zero in at most N bits.

This can be seen most easily from the implementation. Provided we make sure the if expression is always false the CRC calculation will collapse to a shift with zeros inserted at the top. Eventually, all the set bits will be shifted out, leaving the CRC at zero.

Depending on the pattern of bits, it might be possible to get the CRC to zero in fewer than N bits.

Once the CRC has got to zero it can be kept at zero as noted earlier.

For messages this isn’t always very interesting, a zero CRC is just as probable as any other. However, for error analysis it is important. Given any sequence of errors, it’s possible to bring the CRC error contribution back to zero in at most N bits.

Force zero example

It’s easiest to show this on a CRC where there’s no final exclusive-or. So, I’ll use CRC-32-MPEG-2. To make this work, you need get the bit-ordering correct so it can take a few goes. Here’s one:

A more interesting trick is to find an error pattern that’s not detected. That means doing calculations with a seed of zero. We could write our own calculator or we could use an on-line calculator and cancel out the seed. Since the seed is just the initial contents of the CRC the trick we just did will get it back to zero.

So exclusive-oring the sequence 01 00 00 00 00 00 00 4F 57 68 11 into any message at any position leaves an undetected error.

As exciting as that trick looks, remember that an attacker that can rewrite the message can typically also rewrite the CRC. So instead of changing an uninteresting part of the message, they could just change the CRC.

CRCs are designed to protect against random corruption. They don’t protect against malice.

CRC calculations can be run backwards given the message data

CRC calculations are built on exclusive-or. Exclusive-or has the property that if you know any two out of the two inputs and the output, then you can calculate the missing value. Other logical operations do not have this property (for example, for the and operation, if you know the output is zero and one of the inputs is zero you can’t tell whether the other input was a zero or a one).

The CRC operation as a whole doesn’t have this property. The input was an arbitrary long sequence of bits and the output has finite length. You can’t go back from the CRC to the message. However, given the message and the CRC at one point, you can work backwards to find the intermediate value of the CRC at an earlier point.

Given the message data, this can be seen from the implementation. After each step of the calculation, the top bit is the exclusive-or of the previous bottom bit of the CRC and the bit of the message. So, working backwards, the exclusive-or of the top bit of the CRC calculation state and that same message bit is the new bottom bit of the CRC state. If the top bit was one, then we also need to exclusive-or the polynomial constant

In general, this isn’t very useful on its own. You can use it to unwind a CRC calculation over the end of a message and then run it forward over a different message ending, but in general it’s faster to calculate the CRC over the exclusive-or of the old and new message and merge that into the final CRC.

You can use this to work out the CRC seed. If you know the message and the CRC, then running the calculation all the way back to the start of the message will give the seed. This may be useful if the algorithm doesn’t have a fixed seed and you want to determine what it was.

Forcing an arbitrary CRC

Forcing the CRC to an arbitrary value, is most easily done in two steps and then optimised. In the first step, the CRC is forced to zero, as described earlier. In the second step the zero CRC is forced to the desired value. The optimisation reduces the number of message bits needed for the full conversion.

The second step looks a lot like the reverse of the first step. We’ve already seen we can run the CRC calculation in reverse. The mechanism of this calculation ends up looking like a forward CRC calculation feeding in the bits in reverse order and using a different polynomial.

This second polynomial is known as the reciprocal of the original polynomial but the relationship between this and the original polynomial isn’t immediately obvious due to the way polynomials are normally written, so I need to digress onto this notation issue.

Written in full, a polynomial with N-bit strength has N+1 bits from the first set bit to the last set bit. To avoid doing calculations with bits that are always zero, the polynomial is right justified so it covers bits zero to N inclusive. For example, the CRC-16-CCITT polynomial is 𝑥¹⁶ + 𝑥¹² + 𝑥⁵ + 1. You could write this in seventeen bits as 1 0001 0000 0010 0001, or 0x11021, where the bits indicate which powers of 𝑥 are present.

However, the way the CRC algorithm is implemented, the knowledge that the most- and least-significant bits must be set can be optimised out. That allows a N-bit CRC to be implemented with N-bit registers. Specifically, the highest power of 𝑥 is optimised out.

So, for code in normal orientation, the constant you’ll see for CRC-16-CCITT is 0x1021 and for reverse orientation its 0x8408 (1 0001 0000 0010 0001 → 0001 0000 0010 0001 → 1000 0100 0000 1000).

To calculate the reciprocal, reverse the full polynomial before the implementation optimisation, then optimise. That gives a normal representation of 0x0811 (1 0001 0000 0010 0001 → 1 0000 1000 0001 0001 → 0000 1000 0001 0001) and a reverse orientation of 0x8810.

With the reciprocal polynomial, we can start with the desired target CRC and then calculate the bit sequence to force that to zero using the technique from earlier. We just have to be careful to reverse bit sequences in a couple of places.

You can also use the reciprocal polynomial to alter bits at any position in the message to get the target CRC.

Arbitrary CRC worked example

Here’s an example using CRC-32 as that has a non-zero seed and final exclusive-or to show all the details. Let’s suppose we want to add something to the end of the ASCII text “A message” so that the CRC-32, read little-endian, is ASCII “CRC!”.

Our target CRC after the final exclusive-or is is 0x21435243. That means before that exclusive-or it was 0xDEBCADBC.

The first step is to force the CRC to zero as described earlier but note that after the final exclusive-or this will be 0xFFFFFFFF:

Then we need to take the target CRC value and run it through the reciprocal polynomial with zero input for as many bits as there are in the polynomial (in this case 32 bits):

If we take this result, reverse the bits (to give 0x0B66A11D) and output it as data in the forward CRC calculation it will give the desired CRC output:

It should be clear that appending this to the sequence that takes the existing CRC to zero will then produce the desired final CRC:

However, it is possible to do better than this. As you might expect from a simple counting argument, you should be able to turn any CRC accumulator to any other CRC accumulator in just 32-bits. Using the linearity property of CRCs we can run the sequences that take the CRC from its old value to zero and from zero to its desired value in parallel. Writing out the seeds and final exclusive-or makes this clearer:

And here’s an example of altering bits in the middle of the message to give a desired CRC:

1 By analogy, if I was trying to write an article on how to change an engine in a car, I might need to tell you that you need to use a torque wrench. I don’t need to start the article with an explanation of heat treatment of metals and the effect on the grain size of steel on ductility and hardness. I can assume the designers of the torque wrench knew all that and did their job properly.

So, for this article, we can assume that the mathematicians and computer scientists did their job, that the tools we’re going to use have all been correctly designed, and that the system we’re looking at is using them in a regime where they behave themselves.

There won’t be enough information in here for you to design a system from scratch. So be careful using those tools. Just because a torque wrench has a handle and a bulbous end does not mean you can use it to pound nails into a wall.

If you’re interested in more detail, there’s a Wikipedia article Mathematics of cyclic redundancy checks. However, like many Wikipedia mathematics articles, it is heavy on technical jargon and may be difficult to follow if you’re not familiar with the mathematics. I’m trying to avoid exactly that problem with this article.

There’s also a good article A Painless Guide to CRC Error Detection Algorithms.

2 There are several endianness issues:

None of these decisions affect the results I’m discussing.

[Up] Up to the welcome page.
Comments should be addressed to webmaster@pertinentdetail.org
Copyright © 2025 Steven Singer.