You send a file, but how do you know it arrived intact? In other words, how do you know that it didn’t get cut off, garbled, or changed somehow? Simplistically, you could just add up all the bytes in the file — a checksum — and send that along with the file. You compute the checksum when you know the file is good, and the receiver can compare the checksum to see if they match.

However, a simple addition doesn’t catch certain classes of errors, which is why there are better checksum algorithms that, for example, wrap the carry bit around or otherwise modify files with common errors so they produce different checksums. There are two problems with checksums. First, no matter how much you modify the algorithm, the chances that two files produce the same checksum are pretty high. Especially with common error patterns.

For example, assume a very simple algorithm that simply adds the bytes and discards any carry. If a file contains 0x80, 0x80, those numbers essentially cancel each other out. If you replace them with 0, 0, you’ll get the same checksum. To some degree, using anything other than a second copy of the entire file will have this problem — some corruption goes undetected — but you want to minimize the number of times that happens.

The other problem is that a checksum by itself doesn’t let you correct anything. You know the data is bad, but you don’t know why. If you think about it, the simplest checksum is a parity bit on a byte: odd parity is simply summing all the bits together. If the parity bit doesn’t match, you know the byte is bad, but you don’t know why. Any even number of errors goes undetected, but I am sure one-, three-, five-, or seven-bit errors will get caught.

People invent better error-checking codes by devising schemes that can promise they can detect a certain number of bit flips and, at least in some cases, correct them. One of these is the cyclic redundancy check (CRC). It is easy to think of the CRC as a “strong checksum,” but it actually works differently. What’s more, there isn’t just a single CRC algorithm. You have to select or design a particular algorithm based on your needs. Most people pick a “named” implementation like CCITT or Ethernet and assume it must be the best. It probably isn’t.

A CRC is a checksum in the broad sense: you feed it a message, and it gives you a small value that you append, store, or compare later. But unlike a simple additive checksum, a CRC is based on polynomial division over GF(2), which is a fancy way of saying “divide using XOR instead of carries.” That detail matters. It gives CRCs very strong guarantees against common classes of errors, provided you choose the right polynomial for the job. That’s the key. You must choose the right polynomial.

The Polynomial Machine

A CRC treats your message as a long binary polynomial. For example, the byte stream is interpreted as a sequence of coefficients: each bit is either present or absent. The CRC algorithm divides the message polynomial, after shifting it by the CRC width, by a generator polynomial. The remainder is the CRC.

In normal arithmetic, division involves subtraction and carries. In CRC arithmetic, subtraction is XOR. That is why CRC code often looks like this:

if (crc & topbit)
crc = (crc << 1) ^ poly;
else
crc <<= 1;

That loop is implementing polynomial long division, one bit at a time. The generator polynomial is the magic number. For a 16-bit CRC, the polynomial has degree 16. For a 32-bit CRC, degree 32. You will usually see it written as a hex constant, such as 0x1021 for CRC-16/CCITT or 0x04C11DB7 for the classic Ethernet/ZIP/PNG CRC-32. But the polynomial is not just an arbitrary constant. It determines what error patterns the CRC is guaranteed to detect.

What CRCs Catch

A well-chosen CRC can guarantee detection of all single-bit errors, many multi-bit errors, all burst errors up to a certain length, and a very high percentage of longer random errors. The key metric is Hamming distance, often abbreviated HD. If a CRC has HD=4 for messages up to a certain length, it detects all 1-, 2-, and 3-bit errors in messages of that length.

That last qualifier is important. CRC strength is not just “16-bit CRC good, 32-bit CRC better.” It depends on the maximum message length. A polynomial that is excellent for 32-byte embedded packets may be mediocre for kilobyte-size messages. A polynomial standardized decades ago may be familiar but not optimal.

[Philip Koopman’s] work at Carnegie Mellon is the go-to reference here. [Koopman] and [Chakravarty’s] paper on CRC polynomial selection for embedded networks specifically looked for good CRC polynomials for short embedded messages, and [Koopman’s] “Best CRC Polynomials” tables list polynomials by width and Hamming-distance performance. The important takeaway is that many standard polynomials were chosen for historical reasons, not because they are mathematically best for your packet size.

There are plenty of videos that explain CRC, but if you are going to watch a video, you might as well pick one of the many from [Phil Koopman] himself, like the one below.

Famous Does Not Mean Optimal

Take CRC-16/CCITT, polynomial 0x1021. It is found everywhere: telecom, embedded examples, and bootloaders. It is not a terrible polynomial, but it is not automatically the best 16-bit choice. [Koopman’s] tables include other 16-bit polynomials with better Hamming-distance behavior over useful embedded-message lengths.

Likewise, classic CRC-32 using polynomial 0x04C11DB7 is deeply entrenched because of Ethernet, ZIP, gzip, and PNG. But CRC-32C, the Castagnoli polynomial, is often a better general-purpose choice. It has excellent error detection properties over common message lengths and is also supported by hardware instructions on many CPUs. Intel added CRC32 instructions with SSE4.2, and ARM AArch64 also includes CRC acceleration for CRC-32 and CRC-32C.

Of course, standards matter if you have to meet the standard. But if you are designing a new private protocol between your sensor board and your controller, blindly copying the first CRC-16 example from the Internet is not engineering. Pick a polynomial based on your packet length and your risk model.

The Practical Embedded View

For very small messages, even an 8-bit CRC may be adequate. For moderate packets, a good 16-bit CRC is often enough. For firmware images or large records, 32 bits is more reasonable. The point is not to use the biggest CRC you can tolerate. The point is to choose a CRC width and polynomial that give the desired detection strength for your longest protected message.

Also, remember what a CRC does not do. It is not cryptographic. It does not stop malicious tampering. The point of a CRC is to detect accidental corruption, not protect against sophisticated hacking attempts.

Real-world CRC definitions also include bit reflection, initial value, final XOR value, and sometimes byte order conventions. Two CRCs can use the same polynomial and still produce different answers because those parameters differ. That is a common embedded debugging trap. Someone says “CRC-16,” and both sides implement different CRC-16s. CRC-16/IBM, CRC-16/CCITT-FALSE, CRC-16/XMODEM, CRC-16/KERMIT, and CRC-16/MODBUS are not interchangeable.

If you specify a CRC in a protocol document, include at least the width, the polynomial (which can be represented in different formats, by the way), the initial value, if you use reflection on the input or output, and any value to XOR the output with. It is also a great idea to include the computed checksum for ASCII “123456789” so anyone can compare their algorithm to yours.

If you are working with Linux systems, be sure to look at the cksum program which can use several CRC algorithms or other methods like sha1 and other digest-style methods.

Efficiency

Computing CRCs a bit at a time is compact, but it costs eight loop iterations per byte. In some cases, that’s ok, but for performance, you want a table if you can afford the memory. For a 16-bit CRC, the table is only 512 bytes and can be generated at compile time, if desired.

Many CPUs have CRC peripherals. Use them, but read the fine print to make sure they can handle your desired CRC. It is often a good idea to check a hardware implementation against a known-good software implementation before you send it out into the wild. You can do many CRC tests using an online tool. Of course, there are several out there.

Choosing a CRC Today

For a new embedded protocol, define the maximum length of data you need to check. Then decide how many bits of overhead you can afford. Then head to Koopman’s tables to pick a polynomial with good Hamming-distance performance for that length.

The CRC has been around for a long time. But it isn’t just something you grab off the shelf. You need to plan and understand the ramifications of picking different polynomials.

CRCs aren’t the only game in town. Credit card numbers, for example, use check digits. There are other ways you can identify and, in some cases, zap bit errors, too.

If you could dump the flash from your smart toothbrush and reverse engineer it, enabling you to play whatever you wanted on the vibrating motor, what would you do? Of course there’s no question: you’d never give up, or let down. Or at least that’s what [Aaron Christophel] did. (Videos, embedded below.)

But that’s just the victory lap. The race began with previous work by [Cyrill Künzi], who figured out that the NFC chip inside was used for a run-time counter, and managed to reset it by sniffing the password with an SDR as it was being transmitted. A great hack to be sure, but it only works for people with their own SDR setup.

With the goal of popularizing toothbrush-head-NFC-hacking, [Aaron] busted open the toothbrush itself, found the debug pins, dumped the flash, and got to reverse engineering. A pass through Ghidra got him to where the toothbrush reads the NFC tag ID from the toothbrush head. But how does it get from the ID to the password? It turns out that it runs a CRC on a device UID from the NFC tag itself and also a manufacturer’s string found in the NFC memory, and scramble-combines the two CRC values.

Sounds complicated, but the NFC UID can be read with a cellphone app, and the manufacturer’s string is also printed right on the toothbrush head itself for your convenience. Armed with these two numbers, you can calculate the password, and convince your toothbrush head that it’s brand new, all from the comfort of your smartphone! Isn’t technology grand?

We’re left guessing a little bit about the Rickroll hack, but we’d guess that once [Aaron] had the debug pins on the toothbrush’s microcontroller, he just couldn’t resist writing and flashing in a custom firmware. Talk about dedication.

[Aaron] has been doing extensive work on e-paper displays, but his recent work on the Sumup payment terminal is a sweet look at hacking into higher security devices with acupuncture needles.

We probably don’t have to tell most Hackaday readers why the current wave of low-cost software defined radios (SDRs) are such a big deal for hackers looking to explore the wide world of wireless signals. But if you do need a refresher as to what kind of SDR hardware and software should be in your bag of tricks, then this fantastically detailed account from [RK] about how he hacked his La Crosse WS-9611U-IT weather station is a perfect example.

Looking to brush up his radio hacking skills, [RK] set out to use the ADALM-PLUTO software defined radio from Analog Devices to intercept signals between the La Crosse base station and its assorted wireless sensors. He notes that a $20 USD RTL-SDR dongle could do just as well if you only wanted to receive, but since his ultimate goal was to spoof a temperature sensor and introduce spurious data into the system, he needed an SDR that had transmit capabilities.

No matter your hardware, Universal Radio Hacker (URH) is the software that’s going to be doing the heavy lifting. In his write-up, [RK] walks the reader through every step required to find, capture, and eventually decode the transmissions coming from a TX29U wireless temperature sensor. While the specifics will naturally change a bit depending on the device you’re personally looking to listen in on, the general workflow is going to be more or less the same.

In the end, [RK] is not only able to receive the data coming from the wireless sensors, but he can transmit his own spoofed data that the weather station accepts as legitimate. Getting there took some extra effort, as he had to figure out the proper CRC algorithm being used. But as luck would have it, he found a Hackaday article from a couple years back that talked about doing exactly that, which help put him on the right path. Now he can make the little animated guy on the weather station’s screen don a winter coat in the middle of July. Check out the video below for a demonstration of this particular piece of radio prestidigitation.

While we often see the power of tools like URH brought up in talks, nothing quite beats following along with a step-by-step account of how somebody used software and hardware from the modern hacker’s toolkit to achieve their goals. If reading this post doesn’t make you want to finally pull the trigger on a cheap RTL-SDR and start cruising the airwaves, maybe nothing will.

If you’ve used Spotify, you might have noticed a handy little code that it can generate that looks like a series of bars of different heights. If you’re like [Peter Boone], such an encoding will pique your curiosity, and you might set out to figure out how they work.

Spotify offers a little picture that, when scanned, opens almost anything searchable with Spotify. Several lines are centered on the Spotify logo with eight different heights, storing information in octal. Many visual encoding schemes encode some URI (Uniform Resource Identifier) that provides a unique identifier for that specific song, album, or artist when decoded. Since many URIs on Spotify are pretty long (one example being spotify :show:3NRV0mhZa8xeRT0EyLPaIp which clocks in at 218 bits), some mechanism is needed to compress the URIs down to something more manageable. Enter the media reference, a short sequence encoding a specific URI, generally under 40 bits. The reference is just a lookup in a database that Spotify maintains, so it requires a network connection to resolve. The actual encoding scheme from media reference to the values in the bars is quite complex involving CRC, convolution, and puncturing. The CRC allows the program to check for correct decoding, and the convolution enables the program to have a small number of read errors while still having an accurate result. Puncturing is just removing bits to reduce the numbers encoded, relying on convolution to fill in the holes.

[Peter] explains it all in his write-up helpfully and understandably. The creator of the Spotify codes stopped by in the comments to offer some valuable pointers, including pointing out there is a second mode where the lines aren’t centered, allowing it to store double the bits. [Peter] has a python package on Github with all the needed code for you to start decoding. Maybe you can incorporate a Spotify code scanner into your custom Spotify playing mini computer.

Cyclic redundancy codes (CRC) are a type of checksum commonly used to detect errors in data transmission. For instance, every Ethernet packet that brought you the web page you’re reading now carried with it a frame check sequence that was calculated using a CRC algorithm. Any corrupted packets that failed the check were discarded, and the missing data was detected and re-sent by higher-level protocols. While Ethernet uses a particularly common CRC, there are many, many different possibilities. When you’re reverse-engineering a protocol that contains a CRC, although it’s not intended as a security mechanism, it can throw a wrench in your plans. Luckily, if you know the right tool, you can figure it out from just a few sample messages.

A case in point was discussed recently on the hackaday.io Hack Chat, where [Thomas Flayols] came for help reverse engineering the protocol for some RFID tags used for race timing. Let’s have a look at the CRC, how it is commonly used, and how you can reverse-engineer a protocol that includes one, using [Thomas’] application as an example.

What’s a CRC, Anyway?

A CRC is a type of code designed to add redundancy to a message in such a way that many transmission errors can be detected. There are a number of different types of codes that can be used in this way, but the CRC has some properties that make it especially useful for communications protocols. First, it’s efficiently implemented in hardware or software. More importantly, it can be particularly good at detecting the kinds of errors often seen in common data channels, specifically, runs of bit errors. The simplest way to use a CRC is to apply the algorithm to the message to be sent, then append the resulting CRC value to the message. The receiver applies the same algorithm, then checks that the transmitted and locally calculated CRC values match. CRCs vary in length, with the most common ones being 8, 16, or 32-bits long.

Mathematically, a CRC is  based on division of polynomials over GF(2), the Galois Field of two elements. There’s a lot of interesting math involved, and a simple web search will turn up plenty of resources if you want to dive further into the subject. But, this is Hackaday, and I’m going to try to give you enough background to be able attack practical situations, so here we go.

In simple terms, the polynomials involved with the CRC algorithms have coefficients of only 0 or 1. There’s a simple mapping between binary strings and such polynomials, in which each set bit becomes a term with the bit position as the exponent. For example, the binary string 11011 can be represented as x⁴ + x³ + x + 1. (As a mnemonic device, think about x = 2.) To calculate an n-bit CRC, we append n zero bits to our message, then convert to a polynomial. We then divide this message polynomial by a generator polynomial specified as part of the CRC algorithm. The polynomial remainder of this division algorithm is the CRC.

Calculating CRCs

OK, it’s going to get a little more relatable now. The division operation maps to a sequence of XOR operations that will remind you of basic arithmetic. For example, to calculate a trivial 2-bit CRC of the message string 1101 with the generator polynomial 11, we first append 00 to the message to get 110100, then divide to get a quotient of 10011 and a (2-bit) remainder of 01. This remainder is the CRC. Note that at each step of the long division, an XOR operation is used instead of the more familiar subtraction with borrowing.

This is all interesting if you want to write your own CRC implementation, but that’s probably not necessary; you can easily find implementations in your language of choice. If you do want to dig into the algorithms in more detail, here’s a good place to start.

Complications

Besides the generator polynomial, there are four other parameters that describe a general CRC algorithm. First, the input bytes may be reflected — swapped bit order from left to right. There may also be an initial starting value for the CRC calculation; this is prepended to the message before the division. After the division, the n-bit CRC may also be reflected, and finally, it may be XOR’d with a constant before use. While each of these steps is relatively trivial in itself, the resulting number of possible CRC algorithms is huge; too large for practical brute-force search for reverse engineering.

Reverse-engineering a CRC

Remember [Thomas] and his RFID tags? After examining the RF-output of one of the tags on an oscilloscope, he made a simple receiver using a diode detector, RC filter, and a homebrew antenna. Connecting the receiver to an ESP32, he wrote some code to send back the received pulses to his computer for analysis. What he found was that each tag repeated the same 32-bit message about every 4 ms. Sixteen bits of the message were recognizable as the ID number which was printed on each tag, but the other half of each message was a mystery.

This kind of transmission is exactly why CRCs are used. Imagine if tag 5’s message suffered a bit flip during transmission and was received as tag 13. Adding a CRC allows this error to be detected, and the message discarded — a new one will be along soon enough. But, [Thomas], assuming the remaining sixteen bits of the message were a checksum, was now faced with determining which one. The first approach by the Hack Chat denizens was to try online calculators for common CRC types, but this didn’t yield results. While you might get lucky this way, checking the most common handful of CRC parameters, this method doesn’t scale. Luckily, there’s an efficient alternative.

CRC RevEng

A search for CRC reverse engineering turns up the right tool for the job. CRC RevEng by [Gregory Cook] was written to do exactly that: given a few examples of message/CRC pairs, it can determine the parameters of the CRC algorithm used. [Thomas] had collected the IDs and checksums from a number of tags, four of which are shown here:

5A2C DAFC
5B25 C378
5BBC 8B71
5C0A 3EEC

To execute the search, the reveng program is invoked with the ‘-s’ switch, and in this case, the known size of the CRC,  ‘-w 16’. Given just one sample, the program cannot determine which CRC generates the code:

With two samples, the program determines three sets of parameters which could possibly be used:

Finally, given three examples, the code narrows down the search to a single set of parameters.

From here, it’s relatively easy to verify that this set of parameters also reproduces the remainder of the 40 or so tags that [Thomas] has access to. With the CRC algorithm determined, he can now generate his own tags, or reliably receive data from existing ones.

It’s important to remember that the addition of a CRC code to these messages wasn’t intended to keep an adversary from faking the transmissions. As [Thomas] points out, since the tags are not synchronized in any way, their on-off-keying signals can easily collide and create receive errors. Checking the CRC on received messages provides some insurance against this possibility.

Spoofing CRCs

The CRC RevEng code can also manipulate a message to generate a desired CRC value, which can be useful for spoofing.  Called “reversing”, by the program, the behavior is invoked with the ‘-v’ switch. This usage requires that you can identify an n-bit section of the the message that you can change without negative effect – for instance, a comment field that is ignored. If you can locate such a contiguous space in the message,  you can substitute a value there to make any message have a given CRC code. This can be useful in spoofing packets that you need to change in some way, while maintaining a specific checksum value.

Wrapping Up

If you find yourself faced with some unknown data in a message protocol, consider the possibility that it might be a checksum. Although many RF protocols hide these values from users, if you’re looking at messages at the lowest levels, you may well find them. If you do, remember there’s a tool to figure out what’s going on.

When working on a project that needs to send data from place to place the distances involved often dictate the method of sending. Are the two chunks of the system on one PCB? A “vanilla” communication protocol like i2c or SPI is probably fine unless there are more exotic requirements. Are the two components mechanically separated? Do they move around? Do they need to be far apart? Reconfigurable? A trendy answer might be to add Bluetooth Low Energy or WiFi to everything but that obviously comes with a set of costs and drawbacks. What about just using really long wires? [Pat] needed to connect six boards to a central node over distances of several feet and learned a few tricks in the process.

When connecting two nodes together via wires it seems like choosing a protocol and plugging everything in is all that’s required, right? [Pat]’s first set of learnings is about the problems that happen when you try that. It turns out that “long wire” is another way to spell “antenna”, and if you happen to be unlucky enough to catch a passing wave that particular property can fry pins on your micro.

Plus it turns out wires have resistance proportional to their length (who would have though!) so those sharp square clock signals turn into gently rolling hills. Even getting to the point where those rolling hills travel between the two devices requires driving drive the lines harder than the average micro can manage. The solution? A differential pair. Check out the post to learn about one way to do that.

It looks like [Pat] needed to add USB to this witches brew and ended up choosing a pretty strange part from FTDI, the Vinculum II. The VNC2 seemed like a great choice with a rich set of peripherals and two configurable USB Host/Peripheral controllers but it turned out to be a nightmare for development. [Pat]’s writeup of the related troubles is a fun and familiar read. The workaround for an incredible set of undocumented bad behaviors in the SPI peripheral was to add a thick layer of reliability related messaging on top of the physical communication layer. Check out the state machine for a taste, and the original post for a detailed description.

[BaronVonSchnowzer] is spinning up some home automation and settled on an inexpensive ambient temperature sensor which is sold to augment the data a home weather station collects. He found that the RF protocol had been reverse engineered and will use this information to harvest data from a sensor in each room. In true hacker fashion, he rolled his own advances out to the Internet so that others may benefit. Specifically, he reverse engineered the checksum used by the Ambient F007TH.

He got onto this track after trying out the Arduino sketch written to receive the sensor’s RF communications. One peculiar part of the code turned out to be a filter for corrupt messages as the protocol’s checksum hadn’t yet been worked out. Figuring out how the checksum byte owrks wasn’t an easy process. The adventure led him to dump 13k samples into a spreadsheet to see if sorting similar sets of 5-byte message and 1-byte checksum would shed some light on the situation. The rest of the story is some impressive pattern matching that led to the final algorithm. Now [BaronVonSchnowzer] and anyone else using these modules can filter out corrupt data in the most efficient way possible.