dramforever

a row of my life

Magic tricks with CRC

2021-12-25

An adjustable desk

A friend of mine bought a motorized adjustable desk a long time ago and recently got the idea to hook up the controller to the Internet for some reason. They tapped the wire coming from the controls panel with a logic analyzer and was able to capture some packets, hexdumps shown:

AAFF 0040 2EEC
AAFF 0060 2964
AAFF 0050 2B08
AAFF 040E02 0450
AAFF 050E02 8EDA
AAFF 060E02 1D05
AAFF 070E02 978F
... (and many more samples)

They were reasonably sure that the framing was correctly decoded, meaning that each line of hexdump is exactly one complete transmission. The message format of two bytes of (seemingly fixed) header, variable number of bytes of message, and two bytes of checksum resembles Modbus RTU.

An implementation of the Modbus CRC-16, however, gives check sequences that don’t match up with what we see. It’s still suspiciously like some sort of CRC-16 though, so I decided to go though with the assumption that it is a CRC-16 variant waiting to be discovered.

But what is a CRC anyway?

The cyclic redundancy check (CRC) is a family of error-checking codes that is widely used to detect inadvertent data corruption of data during transmission or in storage. The most common way a CRC is implemented is using a linear feedback shift register (LFSR), and the mathematical structure of it is taking the remainder of a polynomial division, where the polynomial is defined in \mathrm{GF}(2).

Let’s go into details of how CRCs work in practice, in particular how the details of the algorithms maps to polynomials, and how we can manipulate CRCs using its properties, along with how I applied the ideas while reverse engineering the exact parameters used for my friend’s desk.

Mathematical basics

Just for a warm up, let’s go into some basics of how polynomials work. These things are immensely useful in various fields of computer science because they provide an interesting way to work with bit strings, so it can’t hurt to take a closer look.

The Galois field \mathrm{GF}(2)

GF(2) might have a scary name, but it really is just the integers modulo 2. This field only has two elements, 0 and 1. Thinking of them as logical bits, addition is exclusive-or (xor), and multiplication is logical ‘and’. Anything added with itself is gone, and subtraction is the same as addition:

Polynomials in \mathrm{GF}(2), in particular univariate polynomials in x, called \mathrm{GF}(2)[x], is what we’re interested in here. In particular, since the coefficients of the terms are either 0 or 1, we can write them as if each term just exists or doesn’t exist, like:

x^{16} + x^{3} + x^{1} + x^{0}

(Side note: Polynomials are not polynomial functions. There are only 4 functions of \mathrm{GF}(2) \to \mathrm{GF}(2), but if the term coefficients of two polynomials differ they are not the same polynomial, regardless of whether they correspond to the same function.)

We can the coefficients of a polynomial into a bit string, highest power term first, omitting (the infinite sequence of) leading zeros. For example, the above example corresponds to:

1 0000 0000 0000 1011

We can then read that as an (unsigned) integer in binary, which is a convenient representation of \mathrm{GF}(2)[x] polynomials in computers.

Polynomial addition and multiplication

Addition and multiplications work exactly as we expect, if you take care that the coefficients should be calculated modulo 2. As we all know, 2 = 0, so each term will cancel with itself:

x^{n} + x^{n} = x^{n} - x^{n} = 0

So for example:

(x^{4} + x^{2}) + (x^{2} + x^{0}) = x^{4} + 2 x^{2} + x^{0} = x^{4} + x^{0}

Addition and multiplication have the commutativity, associativity and distributivity properties we all know and love.

Using the representation of polynomials as unsigned integers, polynomial addition is just bitwise-xor. Meanwhile, multiplication is known as ‘carry-less multiplication’, which is often available as dedicated instructions in modern CPUs for cryptographic applications.

Polynomial (Euclidean) division

What we’re concerned here most, when working with CRCs, is polynomial division. It is defined analogously to integer division with remainder, except instead of comparing the magnitude of numbers, we compare the degree of polynomials.

Given two polynomials a(x) and b(x) (where b(x) \ne 0), there is only one quotient q(x) and remainder r(x) such that r(x) has strictly smaller degree than b(x), and:

a(x) = b(x) q(x) + r(x)

The algorithm to figure out q(x) and r(x) is a variation on the integer long division algorithm. In particular, we don’t usually care about q(x), so it is fairly easy to ‘reduce’ a(x) with multiples of b(x) until the degree is strictly less than b(x). Moreover, since the only possible non-zero coefficient is 1, we don’t even need a division to figure out the scalar to multiply b(x) x^k by.

a = (polynomial dividend)
b = (polynomial divisor)

while (degree of a) >= (degree of b):
    a = a + b x^((degree of a) - (degree of b))

return a

In Python for example, the int.bit_length method returns the length of an integer in binary representation, excluding leading zeros. It is one more than the polynomial’s degree, which is not important in our case:

def poly_mod(a, b):
    while a.bit_length() >= b.bit_length():
        a ^= b << (a.bit_length() - b.bit_length())
    return a

For convenience we can use a(x) \bmod b(x) to refer to r(x).

One notable thing is that adding two polynomials together doesn’t increase the degree, so:

(u + v) \bmod b = (u \bmod b) + (v \bmod b)

Cyclic redundancy checks

Basic CRCs

For a message consisting of bytes, we can also convert it to a bit string, by putting each byte in order, and for each byte, put the least significant bit first. So f0 30 becomes 0000 1111 0000 1100.

For simplicity, consider this CRC generation code, with a single parameter tap:

crc = 0

for each bit b in message:
    crc = crc ^ b
    if least significant bit of crc is 1:
        crc = (crc >> 1) ^ tap
    else:
        crc = crc >> 1

return crc

This structure is called a linear feedback shift register, or LFSR. We can try to reverse engineer this in terms of polynomials in \mathrm{GF}(2).

As the message is read in bit by bit, we can say that the ‘current polynomial’ starts at 0, and for each bit b we read, we update the polynomial from m to mx + b. This continues until the message is completely read, and m is the polynomial corresponding to the entire message.

Since the crc ‘register’ is constantly being shifted to the right, it actually contains a ‘bit reversed’ polynomial. The least significant bit is actually the highest power term. So similarly, if tap were some polynomial, it should also be bit reversed. For convenience, say crc and tap are N-bit integers.

The ‘bit reversed’ part is not weird anymore if we write the integer crc as an N bit integer in little endian as a bit string and find the corresponding polynomial. It is the correct polynomial we’re looking for.

We can start interpreting the bit operations taken:

Noting that for the operation crc >> 1, it discards the least significant bit if it’s zero. So in terms of polynomials, this means that a x^N term cannot occur in \mathtt{crc} and would be discarded. That’s what adding (or really, subtracting) x^n means.

A bit of distributing gives:

Each time a b term is shifted into m, m turns into mx + b, and, \mathtt{crc} is turned into \mathtt{crc} \cdot x + b x^N. If we don’t bother with the ‘if’ step, then after reading everything \mathtt{crc} = m x^N.

But after reading each bit, x^N + \mathtt{tap} is either added or not. This means \mathtt{crc} and m x^N are actually only equal modulo x^N + \mathtt{tap}. Also notice that \mathtt{crc} has degree strictly smaller than N. Therefore:

\mathtt{crc} = (m x^N) \bmod (\mathtt{tap} + x^N)

Realistic CRCs

Realistic CRCs have a few more parameters. I call them init and final.

crc = init

for each bit b in message:
    crc = crc ^ b
    if least significant bit of crc is 1:
        crc = (crc >> 1) ^ tap
    else:
        crc = crc >> 1

return crc ^ final

(Side note: A particular may also reverse or not reverse the order of the bits on input, and may reverse or not reverse the bit order of crc. In practice, these options have not shown up at least for me, and only takes 4 tries to brute force, so they’re not considered.)

Just like before, we notice that if we don’t do the ‘reduction’ step, \mathtt{crc} = \mathtt{init} \cdot x^L + m x^N, where L is the length of the message, this time counting leading zeros. A \mathtt{final} thing is added to the result.

Suppose that \mathtt{init} and \mathtt{final} have degree less than N, then:

\mathtt{crc} = (m x^N + \mathtt{init} \cdot x^L + \mathtt{final}) \bmod (\mathtt{tap} + x^N)

We note that the previous zero-initialized CRC does not depend on L, which means that it cannot detect extra/missing leading zeros. A non-zero init mitigates this. I have absolutely no idea what final is supposed to achieve, but it’s just there.

From now on, we’ll use these symbols consistently:

Now the equation for a realistic CRC can be written:

r = (m x^N + I x^L + F) \bmod P

The following one just means both sides are equal after doing a \bmod P. If you’re familiar with modulo congruences in integers, it’s basically the same thing.

r \equiv m x^N + I x^L + F \pmod P

Linearity properties of CRCs

CRCs are linear

(Or affine, if you’re pedantic)

Suppose we have two messages m_1 and m_2 of the same length L, with CRCs r_1 and r_2 respectively.

\begin{aligned} r_1 &\equiv m_1 x^N + I x^L + F \pmod{P} \\ r_2 &\equiv m_2 x^N + I x^L + F \pmod{P} \end{aligned}

Adding the two equations together gives something quite nice (remember, anything added with itself equals zero):

r_1 + r_2 \equiv (m_1 + m_2) x^N \pmod{P}

Suppose that we have another pair of messages m_3 and m_4, still with lengths L, such that m_1 + m_2 = m_3 + m_4, i.e. the four messages bitwise-xor to all zeros. Then we have:

r_1 + r_2 \equiv (m_1 + m_2) x^N \equiv (m_3 + m_4) x^N \equiv r_3 + r_4 \pmod{P}

This is actually fairly common. For example, with consecutive numbers as strings:

Or, taking these four message hexdumps from the samples:

AAFF 040E02 0450
AAFF 050E02 8EDA
AAFF 060E02 1D05
AAFF 070E02 978F

The messages match up just like the consecutive numbers example above, and the check sequences also match up. That’s some encouraging confirmation that we’re indeed looking at a CRC.

(I guess technically this kind of property should be called ‘affine’ instead of ‘linear’, but, meh…)

Applications

This property is tremendously useful if we actually know the parameters of a certain CRC algorithm. For example, going back to bitwise land, if we have two messages a and b of the same length, and z is the all-zeros messages of that length, then:

\mathrm{crc}(a \oplus b) = \mathrm{crc}(a) \oplus \mathrm{crc}(b) \oplus \mathrm{crc}(z)

Suppose for some inexplicable reason, someone uses a CRC-32 as a hash function to hash string representations of integers, as an attempt to hide the original numbers:

crc("123456") = 0x0972d361

The number can range up to 10 digits, so they’re hoping that we can’t brute force our way through a billion numbers to find a match.

Nobody with even a tiny bit of sanity would think that’s a reasonable way to hide a number… Right?

(Right? I suppose that’s a story for another time…)

To reverse the digit string out of the CRC, we can do a meet-in-the-middle attack, matching up strings like 123\0\0\0 (that’s 123 then 3 NUL bytes) with \0\0\0456. The details are not that hard, and it takes milliseconds to ‘crack’ each hash (if memory serves). For collisions we also get every solution.

However in our case of the adjustable desk, we don’t actually know the parameters used. We must dig deeper. But before that, let’s take a detour into how CRCs are transmitted:

Messages with CRC appended

There’s another thing about how CRCs are implemented. Take a look back at the ‘CRC equation’

r \equiv m x^N + I x^L + F \pmod P

Let’s rearrange it a bit:

m x^N + r \equiv I x^L + F \pmod P

The right hand side only depends on the message length, and the left hand side… It’s the message with N zeros appended, then bitwise-xor with the CRC, i.e. exactly the message and the CRC concatenated. If you like thinking of CRCs as integers, that’s the messages concatenated with the CRC in little endian.

It is not a coincidence that CRCs are often concatenated after the message in this exact way. Due to this nice property, this concatenation simplifies CRC checking hardware, which need not keep track of a ‘state’ of whether it’s reading data or reading the CRC, and only need an end-of-stream signal. We’ll not go into detail on that, but just notice that each line in our hexdump:

AAFF 0040 2EEC

Is already the polynomial m x^N + r.

Messages with equal length

In our case, we know several pairs of messages and their correct CRCs. We can work out a fair bit of information by comparing messages. We’ll first focus on pairs of messages with equal length.

Comparing several equal-length messages

Given two messages m_1 and m_2 with equal length L, and known CRCs r_1 and r_2,

\begin{aligned} m_1 x^N + r_1 &\equiv I x^L + F \pmod{P} \\ m_2 x^N + r_2 &\equiv I x^L + F \pmod{P} \end{aligned}

Adding the two equations together give:

(m_1 x^N + r_1) + (m_2 x^N + r_2) \equiv 0 \pmod{P}

Similarly, if we have more messages m_3, m_4, etc. still of length L, we have:

\begin{aligned} (m_1 x^N + r_1) + (m_3 x^N + r_3) \equiv 0 \pmod{P} \\ (m_1 x^N + r_1) + (m_4 x^N + r_4) \equiv 0 \pmod{P} \end{aligned}

Actually, it only matters that for each pair used in this adding, the messages have the same length. The pairs don’t have to be all L. Let’s call d_{k,l} = (m_k x^N + r_k) + (m_l x^N + r_l)

Since all the m_k x^N + r_k directly correspond to the data we dumped, we actually know them in full, not just modulo something. So we know all d_{k, l} in full. If m_k and m_l have the same length then for some unknown q_{k,l}:

d_{k, l} = P \cdot q_{k, l}

We have several multiples of P. How can we find P itself? This sounds like a job for…

Polynomial greatest common divisor (GCD)

So if we can calculate the remainder of polynomial division, is there an analogous Euclidean algorithm to calculate the greatest common divisor (GCD) of two polynomials? You bet:

def poly_gcd(a, b):
    while b != 0:
        a, b = b, poly_mod(a, b)
    return a

The GCD of two polynomials a(x) and b(x) is the polynomial g(x) with the highest degree such that a(x) and b(x) are both the product g(x) and another polynomial.

The Euclidean algorithm for finding GCD works with polynomials, just like with integers.

Finding P with GCD

Since if we have examples of P \cdot q_{k, l} available, even though all the q_{k, l} are unknown, we should be able to take the GCD of all of them and hopefully get P.

So for example with these three message hexdumps:

m1, r1 = AAFF 0040 2EEC
m2, r2 = AAFF 0060 2964
m3, r3 = AAFF 0050 2B08

Pairing them up arbitrarily give these polynomials:

\begin{aligned} (m_1 x^{16} + r_1) + (m_2 x^{16} + r_2) &= x^{18} + x^{15} + x^{14} + x^{13} + x^{4} + x^{0} \\ (m_1 x^{16} + r_1) + (m_3 x^{16} + r_3) &= x^{19} + x^{15} + x^{13} + x^{5} + x^{2} + x^{1} + x^{0} \end{aligned}

They should both be a multiple of P, so taking the polynomial GCD should give us a multiple of P of lower degree, hopefully P itself.

What we get is:

x^{16} + x^{14} + x^{13} + x^{2} + x^{0}

Since we guessed that it’s a CRC-16, P should have degree N = 16, and this result does have degree 16. So that’s it, we found our polynomial P = x^{16} + \mathtt{tap}.

For use in code, tap should be the bit reversal of 0x6005, i.e. 0xa006.

Messages with unequal length

Comparing messages with unequal length

Having figured out P, we can try working on the rest of our parameters. We’ll pick two messages m_1 and m_2 with unequal lengths L_1 and L_2, and known CRCs r_1 and r_2,

\begin{aligned} m_1 x^N + r_1 &\equiv I x^{L_1} + F \pmod{P} \\ m_2 x^N + r_2 &\equiv I x^{L_2} + F \pmod{P} \end{aligned}

Adding them this time gives:

(m_1 x^N + r_1) + (m_2 x^N + r_2) \equiv I (x^{L_1} + x^{L_2}) \pmod{P}

Everything except I is known here.

Solving for I

Suppose that:

I = \sum_{k = 0}^{N - 1} a_k x^k

Then:

I (x^{L_1} + x^{L_2}) \bmod P = \sum_{k = 0}^{N - 1} a_k \cdot (x^k (x^{L_1} + x^{L_2}) \bmod P)

The left hand side is just ((m_1 x^N + r_1) + (m_2 x^N + r_2)) \bmod P. Each one of x^k (x^{L_1} + x^{L_2}) \bmod P is also known.

Note also that each of those is a polynomial of degree smaller than N. These polynomials form a vector space over \mathrm{GF}(2). If we think in terms of vector spaces, the problem now is to figure out a linear combination of the base vectors x^k (x^{L_1} + x^{L_2}) \bmod P that gives I (x^{L_1} + x^{L_2}) \bmod P.

In other words, we need to solve a linear equation. That’s a job for our beloved Gauss-Jordan elimination. But this time we work in \mathrm{GF}(2), so adding rows just means bitwise-xor, and there is no scaling involved.

In the rare chance that we don’t get a unique solution, i.e. the base vectors aren’t actually linear independent, we can pick another message with a different length try again.

If we go back to the real data we collected and pick these two messages:

m1, r1 = AAFF 0040 2EEC
m2, r2 = AAFF 040E02 0450

The lengths are L_1 = 32 and L_2 = 40, so the base vectors are (remember first bit is highest power):

k  | x^k (x^L1 + x^L2) mod P
---|-------------------------
0  | 0001 1011 1100 0010
1  | 0011 0111 1000 0100
2  | 0110 1111 0000 1000
3  | 1101 1110 0001 0000
4  | 1101 1100 0010 0101
5  | 1101 1000 0100 1111
6  | 1101 0000 1001 1011
7  | 1100 0001 0011 0011
8  | 1110 0010 0110 0011
9  | 1010 0100 1100 0011
10 | 0010 1001 1000 0011
11 | 0101 0011 0000 0110
12 | 1010 0110 0000 1100
13 | 0010 1100 0001 1101
14 | 0101 1000 0011 1010
15 | 1011 0000 0111 0100

Our target polynomial ((m_1 x^N + r_1) + (m_2 x^N + r_2)) \bmod P is 1101 0110 1110 0110, or:

x^{15} + x^{14} + x^{12} + x^{10} + x^{9} + x^{7} + x^{6} + x^{5} + x^{2} + x^{1}

Solving for a_k, and we get that every single a_k is 1, i.e. init is the all-ones 0xffff.

Solving for F

Now the only thing remaining to figure out is the final value F. Going back to this:

r \equiv m x^N + I x^L + F \pmod P

Solving for F is pretty easy now, given that we know everything else:

F \equiv m x^N + r + I x^L \pmod P

In other words, we can do a CRC calculation on something we know, assuming that final is zero, and check the bitwise-xor with the real CRC to get the real value or final. In the case of this adjustable desk it turns out that final actually is just zero.

Now we have the complete set of parameters:

tap   = 0xa006
init  = 0xffff
final = 0x0000

This is not any standard CRC, as far as I know. I have no idea why the desk was programmed this way.

I tried this process on some other samples including some CRC-32 ones and it seems to work fairly reliably given like 10 example pairs.

Did you really do all these just to hack into a desk?

No, I just wrote a program that went through all 2^{16} values of tap, assuming that init = 0xffff and final = 0x0000 just like Modbus. I found tap = 0x2006 works.

Then they started talking about sending it into a solver like Z3 or something, in case brute force didn’t work (well, brute forcing 32-bit CRCs where you need to figure out both init and tap does seem to be intractable), but I was so sure that I can reverse engineer CRC without brute force or relying on solvers that I actually went ahead and did it. Got nerd snipped, I suppose.