Dismantling the AUT64 Automotive Cipher, Part II

This is the second (rather lengthy) part of a two-part series on the AUT64 automotive cipher – you can read the first part here. AUT64 is a proprietary 64 bit block cipher used by a number of major automotive manufacturers. We reverse engineered the design from an immobiliser firmware image and exposed a number of weaknesses in the design.

Since posting the first part I have presented the work we did on AUT64 at CHES 2018. The conference attracted over 600 attendees and featured a great side-channel analysis hackathon which I will write about soon.

My presentation was recorded and has been put on youtube (see below) – speaking of which, I’m really thankful when conference organisers do this. I find it very helpful to be able to watch the presentation and read the paper.

In the remainder of this post I’m going to summarise the key cryptographic weaknesses which we found in AUT64.

Briefly,

  • The AUT64 Feistel network compression function is weak.
  • In eight-round AUT64, the input to the compression function can be precisely controlled for a subset of the message space.
  • The AUT64 substitution-permutation network is weak.
  • AUT64 has certain weak keys.

The AUT64 compression function is weak (and introduces certain weak keys)

The AUT64 compression function
The AUT64 compression function

The AUT64 compression function takes as input a 64 bit bitstring, a 32 bit compression function key \(k_G\) and a round number \(r\) between 0 and 23. The output is 8 bits. The function depends on three key-independent lookup tables \(T_U, T_L\) and \(T_{\text{offset}}\). The first two lookup tables \(T_U, T_L\) prescribe a nibble-wise permutation of the compression function key \(k_G\) which is unique for each round. For each of the 16 nibbles in the input, a round-dependent nibble from  \(k_G\) is concatenated and the resulting byte is input to \(T_{\text{offset}}\).

The AUT64 lookup table T_offset

\(T_{\text{offset}}\) is a 8×8 lookup table which substitutes each nibble in the input according to the key \(k_G\) and the round number \(r\). The way the function is implemented means that the key nibble selects a row and the input nibble selects a column. One of the first things we noticed was that the first row and the first column contains only zeroes. In practice what this means is that the compression function key should not contain any nibbles with the value zero, else bijectivity is lost (which is used in at least one remote keyless entry application) and the cipher is weakened. The resulting key size is reduced from 32 bits to \(15^8\approx {31.25}\) bits.

(Un)Fortunately there’s a much more significant weakness in this design. In each round, for every byte in the input, two values from \(T_{\text{offset}}\) are output and stored in the registers \(gu\) and \(gl\). Where \(i\) is the input byte index, \(X^\prime_i\) is the \(i\)’th input byte and \(uk,lk\) are the upper and lower key nibbles selected by \(T_U\) and \(T_L\), respectively

\[ gu = \bigoplus^{7}_{i = 0} T_{\text{offset}}\Big[uk(k_G, r, i)\parallel un(X’_i) \Big] \]\[ gl = \bigoplus^{7}_{i = 0} T_{\text{offset}}\Big[lk(k_G, r, i)\parallel ln(X’_i) \Big] \]

Significantly the XOR sum is a commutative operation – the order of the operands does not change the result. When we combine this with the fact that each round key is a permutation of the same underlying compression function key, we learn that if we can fix all the input nibbles to have the same value then the round output will always be a fixed value. The bijective design of \(T_{\text{offset}}\) further indicates that if we do this for all 256 byte values then we will get a different fixed output byte for each input.

In eight-round AUT64, the input to the compression function can be precisely controlled for a subset of the message space.

Now we seek to exploit the compression function weakness we just described. To do this we first need to have (somewhat) chosen-plaintext access to the compression function.

Fortunately, the input to the compression function is just the output of the byte-wise permutation \(R\) in the Feistel network design.

The AUT64 Feistel network design
The AUT64 Feistel network design

So provided that each input byte \(x_0\ldots x_7\) has the same value, the permuted input \(x^\prime_0\ldots x^\prime_7\) will be unchanged. Great – this means we can control the input to the compression function \(G\) under 256 different inputs. Better yet, these are exactly the form of inputs which exploit the AUT64 compression function weakness.

Next, we need to be able to discern the output from the compression function in the ciphertext output by AUT64.

The AUT64 substitution-permutation network is weak

The AUT64 round function \(F\) is as follows

The AUT64 round function F
The AUT64 round function F

We’ve shown we can control \(x^\prime_0 \ldots x^\prime_7\) for an interesting subset of messages and that these inputs will cause the output from the compression function \(G\) to be distinguishable from random. What follows \(G\) is a simple substitution-permutation network comprising a single S-box \(S\) applied both at the input and output and a bitwise permutation \(\sigma_{\text{bit}}\) applied in between.

Rather than a single 16×16 S-Box, \(S\) is formed from the concatenation of a single 8×8 S-Box which is defined by the 64-bit key part \(k_\tau\). This means that if the upper and lower 4 bits output from \(G\) have the same value, the output of \(S\) will retain their symmetry and output a byte with an equivalent upper and lower 4 bits.

This gives us the final piece of our puzzle. We can cause each of the 256 chosen inputs \(0x00\ldots, 0x00\) to \(0xFF,\ldots , 0xFF\) to be input to G, we know the output for each will be a unique byte and we know that of these, the sixteen bytes \(0x00,0x11,\ldots , 0xFF\) which are symmetric will also have symmetric outputs from the substitution-permutation network into the final ciphertext.

Breaking semantic security

Semantic security
Semantic security

We can now break semantic security (shown above) as follows. We target distinguishing the first round of encryption as this is when we can fully control the input to the compression function with our chosen plaintexts.

We create the set \(\mathbb{P}\) of all 256 plaintexts with the property that every byte has the same value. \[ \mathbb{P} = \Big \{n^8 : n\in \{0,\ldots,255\} \Big \} \]

Then we encrypt every plaintext in \(\mathbb{P}\) using 8 round AUT64 and save the resulting set of ciphertexts \(\mathbb{C}\). Our goal is to distinguish the output from the first round by looking at each of the eight byte positions over all 256 ciphertexts.

Next, we create 8 new sets \(\mathbb{C}_0 \ldots\mathbb{C}_7\), In each new set we store the 256 ciphertext bytes corresponding to each byte position in every ciphertext in the ciphertexts set \(\mathbb{C}\). The output from the first round will be contained within a single set because the byte permutation \(R\) which mixes the output from each round is fixed. The output from the first round will also be a uniform distribution over the byte-value space. i.e. the set corresponding to the first round will contain exactly one of each byte value \(0, \ldots, 255\)! Semantic security is now broken with an advantage of 1 as we can always distinguish the output of 8 round AUT86 from a random permutation.

Breaking AUT64

Now we’ve broken semantic security, we’d also like to break the cipher more pragmatically.

The nominal key size of AUT64 is 120 bits and is comprised from three parts: a 32-bit compression function key \(k_G\), a 64-bit S-Box key \(k_\tau\) and a 24-bit permutation key \(k_\sigma\). The compression function key is a simple bit-string, the S-Box key defines a 4×4 S-Box and the permutation key defines an 8-element permutation.

The maximum entropy of an AUT64 key is therefore \(232×16!×8!≈91.55\) bits – too much for us to brute force.

In our paper we describe a purely cryptanalytic attack which can recover an AUT64 key in fewer than \(\approx 2^{49.6}\) encryptions!

AUT64 divide and conquer attack
AUT64 divide and conquer attack

First, encrypt \[ \mathbb{P}_1 = \Big \{n^8 : n\in \{0,\ldots,255\} \Big \} \] to get \(\mathbb{C}_0 \ldots\mathbb{C}_7\) (as described above) and then identify the set \(\mathbb{C}_i\) which is equal to the set of all byte values \(\mathbb{Z}_{256}\) and therefore identifies the byte position \(i\) corresponding to the first round of encryption.

Once the position \(i\) is known, construct the second set of chosen plaintexts \[\mathbb{P}_2 = \Bigg \{ \Big(n\ll (64-8\times i)\Big) : n\in \{0,\dots,15\} \Bigg \}\] such that the nibble counter \(n\in\{0,\ldots , 15\}\) is placed in the lower nibble of byte position \(i\).

Encrypting \(\mathbb{P}_2\) will cause the output of the compression function \(G\) to be dependent (in the first round) on only one nibble from the substitution table \(T_{\text{offset}}\). This is because for 15 of the 16 input nibbles, the value 0 will be selected from \(T_{\text{offset}}\) and XORed into the output registers. Now all that remains (see paper for specifics of key sizes remaining) is to brute-force the 15 possible key-nibble values, the possible \(\approx 2^{37.3}\) S-Box values and the \(\approx 2^{8.4}\) permutation values. The resulting attack takes just \(15\times 2^{37.3} \times 2^{8.4} \approx \mathbf{2^{49.6}}\) encryptions to recover the full 120 bit AUT64 key!

I found reverse engineering and breaking AUT64 very exciting, particularly once it became practical. I’ve since (for predominantly diplomatic reasons) moved on to working on PKI solutions in the V2X domain so this may be the last cryptanalysis post I make for a while, although I did recently make an interesting observation about the DES round function I would like to afford some time to.

— Happy new years!