32-bit CRCs might be insufficient for WiFi

A new paper suggests CRCs might not be enough for WiFi.

Is It Time to Upgrade From CRC-32?  /  Mohit Balany; Craig Partridge
(IEEE Xplore / paywall)

The authors set up a WiFi network with fault injection (aluminum foil helped here) and found that the types of bit faults they were injecting slipped past the HD of IEEE CRC-32.  Their data suggests, but did not test, that an alternate 32-bit CRC would not be sufficient. However, they did not seem to take into account that other CRCs have a better HD performance for sparse burst faults, which is suggested would be relevant by their Figure 5.

That having been said, CRCs not being enough for any radio transmission is not a huge surprise since it is a much more fault-prone transmission medium than copper or optical fiber.

Paper Abstract:

IEEE CRC-32 is widely used in data communications to detect transmission errors. The decision to use CRC-32 was made in the 1970s, based on studies that compared the performance of various 32-bit CRCs on relatively small (2 000 bit) packets subjected to errors described by a renewal process. In today’s networks we often see far larger packets (8 000 bits or more) and experiments have shown that errors do not fit a renewal process. The world has changed. To get a sense of that change, we captured 1 900 gigabit WIFI (802.11n) transmissions errors to better understand error distributions and patterns. Our data suggest that a considerable fraction of errors could slip past IEEE CRC-32. It may soon be time to consider a new generation of error codes.

Comparative speeds for different Checksum & CRC implementations

Comparative speeds for different Checksum & CRC implementations.

For more information see my new book:  Understanding Checksums and Cyclic Redundancy Checks -- which includes downloadable open source example implementations for the checksums mentioned below.  This is a preview of section 12.1 from that book.

Book: Understanding Checksums and Cyclic Redundancy Checks

Amazon e-book: https://www.amazon.com/dp/B0CVXWDZ99   (Also available from country-specific Amazon web sites for:  UK, DE, FR, ES, IT, NL, JP, BR, CA, MX, AU, IN).  

Updated, permanent post with more info here: https://checksumcrc.blogspot.com/p/book.html

Explanation of CRC Operation: Polynomial Division, Shift Register, and Comparison (video)

 Here is a video explaining the mechanics of Cyclic Redundancy Check computations, including:

• An example of the polynomial division approach
• An example of the XOR-feedback shift register approach
• A step-by-step comparison of how the polynomial division and shift register approaches are actually doing exactly the same computation.

If you've ever wondered why it is that a shift register and polynomial division end up with the same result, this video explains it.

FULL VIDEO:   YouTube | Archive.org

The full video consists of these four parts: (YouTube Play List):

• Part 1: Example CRC Division to compute check value (YouTube 4:25)
• Part 2: Example CRC Validation via Polynomial Division (YouTube 3:30)
• Part 3: Example CRC Computation via Hardware Shift Register (YouTube 8:10)
• Part 4: Comparison of CRC Polynomial Division and Hardware Shift Register (YouTube 6:21)

Pending clean-up of papers

 I received the following comments with potential issues in some of my work.  I'm delighted to receive such feedback since a major point of my work is to try to get a complex topic straight.

At the moment I'm fully engaged working on self-driving car safety so it will be a while before I can resolve these. However, in the spirit of transparency here are the points raised so you know to be careful on these points when reading my work.

(This is posted with permission conditioned on anonymity. Thanks to the person who sent the comments.)

----------------------------------------------

1) On page 5 of http://users.ece.cmu.edu/~koopman/roses/dsn04/koopman04_crc_poly_embedded.pdf you say that SMBus uses CRC-8, polynomial 0xEA in your notation and say that 0x83 would be better. I am not familiar with SMBus but three sources say that the polynomial chosen for SMBus was 0x83.

CRC Catalogue entry CRC-8/SMBUS lists poly=0x07 (they use what Wikipedia calls Normal form)

SMBus Spec page 27 clearly states that the polynomial is x8 + x2 + x1 + 1

Presentation 22 April 1999 USAR Systems has the same.

2) On same page of same document as 1), it says XMODEM also uses CRC-8 polynomial 0xEA but it appears that XMODEM uses a 16-bit CRC according to Wikipedia and the CRC Catalogue amongst others. There is reference to an earlier 8-bit FCS but that was called a checksum in the references I found, not a CRC. ref1, ref2, ref3

3) Finally, I am having trouble reproducing your Probability of Undetected Error graphs from your koopman04 paper. The maxino_ms.pdf, page 9 gives the equation for Pud as

Pud = HW * BER^x * (1-BER)^(n-x)

where n is code word length in bits, x is number of bit errors, HW is Hamming weight at the HD. For example, polynomial 0x9C at 9 bit data word length is shown as just above 1e-33 (I used a tool to read scaled values off log charts to get about 6e-33 since I can't find a numeric value anywhere), but the formula gives 3.4e-29 at same BER of 1e-6, since HD=5 and HW(5)=34.

I suspect this is because your Pud graphs are, as you say in section 4.1, "weighted by the percentage of errors caught per corresponding polynomial weights for each data word length" but I cannot find a formula or example of this weighting which gives the required correction. Although formula (2) in page 18 of the faa15_tc-14-49.pdf document is different from the above, as far as I can see the combin(c, HD) term cancels out because UndetectedFractionHD = HW/combin(c, HD). So please could you provide the weighting formula, preferably with one numerical example.

----------------------------------------------

Initial responses:

- I would not be at all surprised for #1 and #2 I was referring to documents that got the polynomials wrong, which was previously quite common but is getting better over time.

- For #3 the graphs and probability equations can be a bit tricky.  I'll have to get all that stuff back in my head before being able to respond.  I'd suggest going with the analysis here if you're in doubt, which had the math reviewed by researchers from Honeywell, so hopefully it's OK: http://www.tc.faa.gov/its/worldpac/techrpt/tc14-49.pdf  

Effect of Initial Seed Values on CRCs and Checksums

Checksums and CRCs involve a repeated computation over the length of a dataword that
accumulates a result to form an FCS value. The accumulation value must be initialized to some
known value for this process to produce a predictable result for any given codeword. When the
initial value is unstated, it is typically assumed to be zero.

In some cases, a non-zero value is used instead, such as 0xFFFF for a 16-bit checksum or CRC.
This has the advantage of making an all zero codeword impossible. Perhaps more importantly
for Fletcher checksum, ATN-32, and CRCs, this has the additional advantage of causing leading
zeros of a message to affect the FCS value. To better understand, consider a CRC initialized
with an all zero seed value. Any number of all zero dataword chunks can be fed into the CRC
and it will stay at a zero value, throwing away information about how many zero chunks have
been processed. However, if the CRC computation is initialized to any non-zero value,
processing chunks with a value of zero will cycle patterns through the CRC, tracking the number
of zero-valued chunks that have been processed as a sort of counter. This can help with
situations in which additional leading-zero bytes have been erroneously added to a dataword.

In general, any non-zero seed value can be used. The value selected does not affect
error-detection properties beyond those previously discussed. In particular, CRC error detection,
in terms of the BER fault model, is independent of the seed value used.

The CRC and checksum values can be alternately or additionally modified to create an FCS
value. A common modification is to XOR the result of a checksum computation with a value,
such as 0xFFFF, which inverts bits, but does not lose any of the information content of the
checksum computation. In some cases, CRC result values must be bit-reversed to preserve burst
error properties across the dataword to FCS boundary, depending upon the computation method and message bit ordering in the dataword.

Note:
The "seed value" is sometimes also called the "initial value"

Source:

• Koopman, Driscoll, Hall, "Selection of Cyclic Redundancy Code and Checksum Algorithms to Ensure Critical Data Integrity," DOT/FAA/TC-14/49 , March 2015

Data Integrity Techniques: Aviation Best Practices for CRC & Checksum Error Detection

I just presented a session at an FAA sponsored conference on "Data Integrity Techniques: Aviation Best Practices for CRC & Checksum Error Detection" on Sept. 25.  Here are the slides:


 (Acrobat download: http://users.ece.cmu.edu/~koopman/pubs/koopman14_crc_faa_conference_presentation.pdf)

---

A recording of an older variant of this presentation can be viewed below:



Webinar download:  https://cmu.box.com/s/nn5r9ogwpw100fqkp6g2
Accompanying slides for that older webinar can be found: here

Consolidated Wikipedia Pointers for Checksums and CRCs

Here are some starting points within Wikipedia if you are interested in checksum and CRC background. (These articles also point to other places of interest.) Over time I hope to distill the practical application of all this in my blog, but for now these are reasonable starting points.

• List of checksum and CRC algorithms: http://en.wikipedia.org/wiki/List_of_checksum_algorithms

• Longitudinal Redundancy Check (XOR checksum): http://en.wikipedia.org/wiki/Longitudinal_redundancy_check

• Overview of Checksums: http://en.wikipedia.org/wiki/Checksum
  
• Fletcher Checksum: http://en.wikipedia.org/wiki/Fletcher%27s_checksum
• Adler Checksum: http://en.wikipedia.org/wiki/Adler-32

• Overview of CRC: http://en.wikipedia.org/wiki/Cyclic_redundancy_check
• More detailed example of CRC computation: http://en.wikipedia.org/wiki/Computation_of_CRC 
• Mathematics of CRCs: http://en.wikipedia.org/wiki/Mathematics_of_CRC

 Related pages:

• Overview of error detection and correction codes: http://en.wikipedia.org/wiki/Redundancy_check
• Discussion of parity: http://en.wikipedia.org/wiki/Parity_bit
• Check digits (it's like parity for numbers handled by people): http://en.wikipedia.org/wiki/Check_digit

It is important to realize that Wikipedia is not necessarily an authoritative source. For this area it seems there is enough critical mass of authors, editors and reviewers to get the pages into reasonable shape.

CRC for Protecting A Single Value

Some critical applications need to protect a single byte or word of data in memory against corruption. (For example, if you want to be extra-sure about protecting EEPROM values against corruption.) A previous post gives good CRC polynomials for a wide range of circumstances, but it is always nice to know if you can do better for a special case. Below are optimal CRC polynomials for a few special cases involving small data words that might be stored in memory (RAM, EEPROM, or otherwise).

Protecting an 8-bit data word:
8-bit CRC:  HD=5;  0x9C = x^8 + x^5 + x^4 + x^3 + 1  
16-bit CRC: HD=8; 0xE92F = x^16 + x^15 + x^14 + x^12 + x^9 + x^6 + x^4 + x^3 + x^2 + x + 1
32-bit CRC: HD=16; 0xC563942F = x^32 +x^31 +x^27 +x^25 +x^23 +x^22 +x^18 +x^17 +x^16 +x^13 +x^11 +x^6 +x^4 +x^3 +x^2 +x +1

Protecting a 16-bit data word:
8-bit CRC:  HD=4;  0x93 = x^8 + x^5 + x^2 + x + 1  
16-bit CRC: HD=7; 0x978A = x^16 + x^13 + x^11 + x^10 + x^9 + x^8 + x^4 +  x^2 + 1
32-bit CRC: HD=14; 0xB396786D = x^32 +x^30 +x^29 +x^26 +x^25 +x^24 +x^21 +x^19 +x^18 +x^15 +x^14 +x^13 +x^12 +x^7 +x^6 +x^4 +x^3 +x +1

Protecting a 32-bit data word:
8-bit CRC:  HD=4;  0x92 = x^8 + x^5 + x^2 + 1  
16-bit CRC: HD=6; 0x8BFC = x^16 + x^12 + x^10 + x^9 + x^8 + x^7 + x^6 + x^5 +  x^4 + x^3 + 1
32-bit CRC: HD=12; 0xB527A43B = x^32 +x^30 +x^29 +x^27 +x^25 +x^22 +x^19 +x^18 +x^17 +x^16 +x^14 +x^11 +x^6 +x^5 +x^4 +x^2 +x +1

The hex number has an implicit +1. "HD" means Hamming Distance. Other information about this topic can be found at my previous post on good CRCs.

Note that for this sort of use it is a good idea to "seed" the CRC computation with a value of that is not zero. That avoids a data word value of zero giving a CRC computed value of zero -- which will result in an undetected error if memory is wiped to all zeros for some reason.

Pointers to other CRC discussions

Over time I'll add links to postings on CRCs that I find interesting or entertaining:

Nigel Jones has an essay on how we don't always stop to think about whether what we're doing is actually good enough, even if it is what we've always done. In this case he's talking about CRC selection.
(link: Thoughts on BCC's, LRC's, CRC's and being experienced)

 Lammert Bies has a Q&A forum about practical implementations of standard CRC functions.
(link: Error Correction and Detection Forum )

What is the best CRC up to 16 bits in size?

Please see the posting at this link for this article:
http://betterembsw.blogspot.com/2010/05/whats-best-crc-polynomial-to-use.html

Should you use a CRC or Checksum?

Please use this link to see this blog posting:
http://betterembsw.blogspot.com/2010/05/which-error-detection-code-should-you.html