CRC and Checksum Tutorial Webinar

I've completed my FAA-sponsored look at CRC and Checksum performance for aviation systems. While some of the material is aircraft-specific, it is all relevant to safety critical systems and contains quite a bit of information about CRC vs. checksum performance.

I'm pleased to be able to share a two-hour Webinar recording describing all the work, as well as the slides and draft report. There is a guide to the material below that you may find useful if you are looking for a specific topic.

• Video: Vimeo (streaming and download)
• Video:  Youtube (streaming)
• Slides (Acrobat)
• Final report (Acrobat)
• My other blog posts on CRCs and checksums

The general flow of the presentation is as follows, by slide number:

• 6 - CRC and checksum background and terminology

• 10 - Why picking the right CRC isn't as easy as you might think

• 20 - Summary of project technical approach

• 21 - Project results overview

• 24 - Checksum results (Checksum, Fletcher Checksum, ATN-32)

• 30 - CRC-32 compared to checksums

• 31 - It's all about the Hamming Distance

• 33 - Table of checksum compared to CRC-32

• 35 - Good CRC choices (8 & 16 bits)

• 36 - Good CRC choices (24 & 32 bits)

• 37 - Aviation industry results (might be enlightening for everyone)

• 43 - Multiple CRC & memory-specific CRC results

• 46 - System level effects and cross-layer interactions (e.g., unprotected length field, bit encoding)

• 48 - ARINC-825 / CAN issues

• 52 - 8b10b encoding Gbit Ethernet issue

• 53 - Mapping to criticality levels (how do you know your CRC/checksum is good enough?)

• 64 - Determining Bit Error Ratio (BER)

• 71 - Error detection mechanism failure and scrubbing

• 74 - A simple recipe for how to determine how big and capable a CRC/checksum you need

• 76 - CRC/Checksum seven deadline sins (bad ideas)

• 79 - Review of the study project subtasks (most readers can skip this part)

I owe significant thanks to my Co-Investigators Kevin Driscoll and Brendan Hall at Honeywell labs, without whom this work could not have been done. And also a warm and sincere thanks to our FAA contacts, and especially to Chuck Kilgore for his good spirits, kind words, and unfailing support.

NOTES:

"The provided links will give you the option of downloading the video file or view it through your web browser.   Some people have reported problems viewing the video with their web browser due to the 2 hour length.  Others have been able to view the video in a browser without any problems.   If you encounter problems, we recommend that you download the file for offline viewing if possible to avoid any streaming issues."

"This work was supported by the Federal Aviation Administration, Aircraft Certification Service, and Assistant Administration for NextGen, William J. Hughes Technical Center, Aviation Research Division, Atlantic City International Airport, New Jersey 08405. The findings and conclusions in this presentation are those of the author(s) and do not necessarily represent the views of the funding agency.  This presentation does not constitute FAA policy."

The Webinar was scheduled Oct 1, 2013, but was delayed due to the government shutdown. The webinar was actually held on Oct 29, 2013.

Secrecy vs. Integrity and Why Encryption Might Be the Wrong Choice

Summary: Encryption doesn't solve all security problems.  In many cases you need authentication and integrity, not secrecy, and encryption can be the wrong tool for the job.  In those cases you need a Message Authentication Code, not encryption.

---

It's pretty typical to see embedded system designers use encryption to solve security problems. And it's also common for that to be the wrong answer to the real problem.

To understand why, consider a simplistic security need. (This example is naive in many ways, but serves to illustrate a point.) Let's say you want to set a light bulb intensity to one of 256 levels, and you want to make sure that only an authorized person can set that level.  To do this with no security, you'd send a message on an embedded network to that light bulb:

Message =  BulbLevel               (where BulbLevel is an 8 bit unsigned integer)

OK, so now you want to encrypt things.  You compute  X = Encrypt(BulbLevel) with a shared secret key that only you and the light bulb know and send that in the message:

Encrypted Message = X              (still 8 bits)

Now there is no way for anyone to know what level you've sent -- you've accomplished secrecy.  (Ignore all those attacks that just came into your head, such as recording past messages and playing them back .. or peeking to see what the light bulb did when it received the message ... this is just an illustrative example.) But is secrecy what you really wanted?   Remember our goal in this example wasn't to keep it a secret what the level was, but rather to prevent someone unauthorized from setting the light bulb level.

What if an adversary just sent random garbage:

Encrypted Message = RANDOM_8_bits         (still 8 bits)

That would set the light bulb output to some value. Maybe not a desired value, but the attacker would be able to change the light value to something other than what you commanded without knowing the secret key, (with probability 255/256 that it wasn't a repeat of the value already there) which is what you're trying to prevent.

The issue is that encryption is the wrong tool for the job.  What you really want is some combination of authentication (I know the right person sent it) and integrity (I know the contents have not been altered). Encryption isn't the best tool for this -- what you want is a Message Authentication Code (MAC). One way to get this is to compute an appropriately chosen secure hash function and append its results to the message:

Authenticated Message = BulbLevel  |  SecureHash         (8 bits concatenated with a hash value)

Both you and the light bulb still have a shared secret key with this approach. The light bulb receiving the message computes its own hash of the BulbLevel value and compares it to the received SecureHash value in the message. If they match, the message is authentic and it takes action. If they don't match, then it is a forgery and the message is ignored. Note that the BulbLevel isn't a secret -- it's transmitted "in the clear." That's because the point of this isn't secrecy; it's authentication (the sender knows the secret key to the cryptographic hash function) and integrity (the hash matches the value expected from the BulbLevel value, so the message hasn't been tampered with). If the hash value is sufficiently large, the chance of someone guessing the right hash value for a maliciously sent bulb level is low enough to be tolerated or even virtually impossible given the lifetime of the lightbulb, providing an arbitrarily good probabilistic level of security.

There's another important benefit to using a MAC. Encryption for the purpose of keeping data secret tends to be export controlled. Message Authentication Codes tend not to be export controlled. So ditching encryption in favor of a MAC usually helps with export issues. (Read the rules and talk to your lawyer -- this is just a sweeping generalization.)

The overall message is: if you want to ensure authenticity and integrity and secrecy isn't a big deal, using encryption is barking up the wrong tree.

The fine print: OK, now for those who have begun composing comments about how naive the above schemes are ... yes, I know .. it was only an example. You don't actually do it that way for either approach. For example, you need a time stamp or something to prevent playback attacks. And that tends to help encryption do better because of the reduced chance of accidentally coming up with a plausible decrypted timestamp value (if the receiver is checking for plausible timestamps). And certainly encryption can be made to work if you are careful. But, when I've looked into this for real systems what I've found is that a MAC is often a better tradeoff for a number of reasons and tends to provide better authentication and integrity for a given computational cost and bandwidth cost in practical scenarios. And, I've found designs in the real world based on encryption that weren't going to work as well as the designers thought because they didn't get the details of authentication right. Also, just to make sure it's said ... a CRC is not cryptographically secure, so don't use it as a secure hash function.

Even after the fine print, the message remains: use a MAC if it does the job. Don't jump to a default strategy of encryption if secrecy isn't what you really need. And if you do decide to use encryption, make sure it is really providing authentication and integrity checking in addition to secrecy.

Controller Area Network (CAN) Protocol Vulnerabilities

Controller Area Network (CAN)is a very popular embedded network protocol. It's widely used in automotive applications, and the low cost that results in makes it popular in a wide variety of other applications.

CAN is a very nice embedded protocol, and it's very appropriate for a wide variety of applications. But, like most protocols it has some faults. And like many protocol faults, they aren't widely advertised. They are the sort of thing you have to worry about if you need to create an ultra-dependable system. For a robust system architecture for every day control functions, probably they are not a huge deal.

Here is a summary of CAN Protocol faults I've run into.

(1) Unprotected header. The length bits of a CAN message aren't protected by the CRC. That means that a single corrupted bit in the length field can cause the CRC checker to look in the wrong place for the CRC. For example, if a 3-byte payload is corrupted to look like a 1-byte payload, the last two bytes of the payload will be interpreted as a CRC. This could cause an undetected 1-bit error. There are some other framing considerations that might or might not cause the error to be discovered, but it is a vulnerability in CAN that is fixed in later protocols via use of a dedicated header CRC (e.g., as done in FlexRay). I've never seen this written up for CAN in particular, but this is discussed on page 20 of [Driscoll09]

(2) Stuff bit errors compromising the CRC. A pair of bit errors in the bit-stuffed format of a CAN message (i.e., one on the wire) can cause a cascading of bit errors in the message, leading to undetected two-bit errors that are undetected by the CRC. See [Tran99] and slides 15-16 of
http://www.ece.cmu.edu/~ece649/lectures/13_can.pdf
In general there are issues in any embedded network if the physical layer encoding can cause the propagation of one physical data bit fault into affecting multiple data bits.

(NOTE: added 10/16/2013.  I just found about about the CAN-FD protocol. Among other things it includes the stuff bits in the CRC calculation to mitigate this problem.  Whether or not there are any holes in the scheme I don't know, but it is clearly a step in the right direction.)

(3) CAN is intended to provide exactly-once delivery of messages via the use of a broadcast acknowledgement mechanism. However, there are faults with this mechanism. In one fault scenario, some nodes see an acknowledge but others don't, so some nodes will receive two copies of a message (thinking they are independent copies rather than a retransmission) while others receive just one copy. In another less likely (but plausible) scenario, the above happens but the sender fails before retransmitting, resulting in some recipients having a copy of the message and others never having received a copy. [Rufino98]  Further info here: [Tindel20b]

(4) It is possible for a CAN node to lock up the network due to retries if a transmitter sees a different value on the bus than it transmitted. (This is a failure of the transmitter, but the point is one node can take down the network.) [Perez03]

(5) If a CAN nodes' transmitter gets stuck at a dominant bit value, it will jam up the entire network. The error counters inside each CAN controller are supposed to help mitigate this, but if you have a stuck-at-"on" transmitter that ignores "turn off" commands there isn't anything you can do with a standard CAN setup.

(6) CAN suffers from a priority inversion issue, which can cause delays of high priority messages due to queuing issues in nodes that locally use FIFO transmission order. [Tindell20]  Note that strictly speaking this is a CAN driver and hardware issue rather than something inherent to the on-wire protocol.  To quote Ken Tindell via a social media message: "Any software that does FIFO queuing of CAN frames in a critical application is broken."

There are various countermeasures you might wish to take to combat the above failure modes for highly dependable applications. For example, you might put an auxiliary CRC or checksum in the payload (although that doesn't solve the stuff bit vulnerability). You might shut down the network if the CAN controller error counter shows a high error rate. Or you might just switch to a more robust protocol such as FlexRay.

CAN is also not secure in that provides no message authentication. It was not designed to be secure, so this is more of limitation in scope than a design defect.

Have you heard of any other CAN failure modes? If so, let me know.

References:

[Driscoll09] Driscoll, K., Hall, B., Koopman, P., Ray, J., DeWalt, M., Data Network Evaluation Criteria Handbook, AR-09/24, FAA, 2009.
http://www.ece.cmu.edu/~koopman/pubs/faa09-24_data_network_evaluation_criteria_handbook.pdf

[Tran99] Eushiuan Tran Tsung, Multi-Bit Error Vulnerabilities in the Controller Area Network Protocol, MS Thesis, Carnegie Mellon University ECE Dept, May 1999
http://www.ece.cmu.edu/~koopman/thesis/etran.pdf

[Rufino98] Rufino, J.; Verissimo, P.; Arroz, G.; Almeida, C.; Rodrigues, L., Fault-tolerant broadcasts in CAN, FTCS 1998, pp. 150-159.
http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=689464

[Perez03] Perez, J., Reorda, M., Veiolante, M.; Accurate dependability analysis of CAN-based networked systems, 2003 SBBCCI.
http://porto.polito.it/1418994/

[Tindell20] Tindell, K., CAN Priority Inversion, June 29, 2020.
https://kentindell.github.io/2020/06/29/can-priority-inversion/

[Tindell20b[ Tindell, K., "CAN, atomic broadcast and Buridan's Ass,"  https://kentindell.github.io/2020/07/11/can-atomic-multicast/

Embedded Software Risk Areas -- Architecture

Series Intro: this is one of a series of posts summarizing the different red flag areas I've encountered in more than a decade of doing design reviews of industry embedded system software projects. You can read more about the study here. If one of these bullets applies to your project, you should consider whether that presents undue risk to project success (whether it does or not depends upon your specific project and goals). The results of this study inspired the chapters in my book.

Here are the Architecture red flags:

• No defined software architecture

There is no picture showing the system’s software architecture. (Many such pictures might be useful depending upon the context – but often there is no picture at all.) Ill defined architectures often lead to poor designs and poor quality code.

• No message dictionary for embedded network

There is no list of the messages, payloads, timing, and other aspects of messages being sent on an embedded real time network such as CAN. As a result, there is no basis for analysis of real time network performance and optimization of message traffic.

• Poor modularity of code

The design has poorly chosen interfaces and poorly decomposed functionality, resulting in high coupling, poor cohesion, and overly long modules. In particular, interrupt service routines are often too big and mask interrupts for too long. The result is often increased risk of software defects due to increased complexity.