Dismantling the AUT64 Automotive Cipher, Part 1

I recently got my first academic paper published! This was a big moment for me and it feels great to have my hard work validated and preserved in the literature.

My paper was published in the IACR Transactions on Cryptographic Hardware and Embedded Systems 2018, at which I’ll be presenting the work in September later this year 🙂

In this post I’ll give a very brief overview of the AUT64 cipher which we reverse engineered from an immobiliser box firmware. In a follow-up post I’ll go into more detail about the cryptographic and implementational weaknesses which we found (read the paper for spoilers!).

My PhD supervisor Flavio Garcia has a long history of exposing weak cryptography in embedded applications, perhaps most prominently the MIFARE classic smartcard which, at one time, comprised 70% of the wireless smartcard market and was widely used for public transport payment schemes such as the Oyster Card in London and the OV-chipkaart in The Netherlands.  It is also widely used for access control in office and governmental buildings. The attacks on MIFARE classic allowed the recovery of all secret keys, typically in less than a second.

AUT64 is an automotive block cipher which was used by a number of automotive manufacturers including Volkswagen group and Mazda. AUT64 has been used both for traditional vehicle immobiliser systems (which prevent hotwiring) and the more-recent remote keyless entry systems which allow the doors of the vehicle to be unlocked remotely. AUT64 was first discovered in an earlier paper by Garcia et al. which showed how the majority of Volkswagen group vehicles between 1995 and 2016 were undermined, in addition to significant cryptographic issues, by frankly laughably inadequate key management practices in which global master keys were used across entire product families.

In the paper, I reverse engineer an AUT64 immobiliser system, find a number of cryptographic and key management weaknesses and then combine them to show how the system is critically flawed.

A common wisdom in cryptography is that `security by obscurity’ doesn’t work. The details of AUT64 were proprietary and obscured away beneath patents, datasheets and compiled implementations. My first task was to take the datasheets, the patent and a firmware dump from a vehicle immobiliser box and to work out exactly how the cipher operated.

I reverse engineered the firmware using IDA. Once the correct processor type had been identified it was relatively easy to identify the routines of interest, it took a lot (lot lot..) longer to discern all the logic.

At a high-level, this is what I found

AUT64 is a 64-bit block cipher which uses a 120-bit key. This means it takes an input message of length eight bytes \(x_0\ldots x_7\) and outputs a ciphertext of eight bytes. This specific type of block cipher is called a Feistel construction, the cipher is iterated in rounds which gradually modify the output until it is (ideally!) indistinguishable from a random string. In each round, a byte permutation \(\sigma_{byte}\) is applied to the input and then the Feistel function \(F\) is applied to the permuted bytes \(x’_0\ldots x’_7\).

The Feistel function \(F\) comprises a compression function \(G\), an S-Box \(S\) and a bit-wise permutation \(\sigma_{\text{bit}}\) applied as follows

The compression function takes as input the permuted eight bytes \(x’_0\ldots x’_7\) and outputs just a single byte. The substitution-permutation network composed from the S-Box, the bit-wise permutation and then the S-Box again is used to provide the final output byte \(x{”}_7\).

Finally, the compression function \(G\) is composed as follows

The compression function operates nibble-wise (on 4-bit values) and uses a three of key-independent look-up tables \(T_U, T_L\) and \(T_{\text{offset}}\) which define the key schedule and the diffusion property, respectively.

What makes AUT64 particularly interesting is that a great deal of the construction is dependent on the key. A 120-bit AUT64 \(K\) 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 \(2^{32}\times 16! \times 8!\approx 91.55\) bits. Unlike some of the earlier work on weak proprietary cryptography, this is far too large to be exhaustively searched.

A second interesting property of AUT64 is that it is an unbalanced Feistel construction. Consequently, in each round of AUT64 just one-byte of the ciphertext is changed, the other bytes are only rearranged. This is in contrast to the traditional Feistel construction (i.e. DES) in which half of the ciphertext is changed in each round. This means we need to apply at least eight rounds of AUT64 before the ciphertext could ever hope to be statistically indistinguishable from the plaintext. A comprehensive taxonomy of Feistel networks by Schneier et al. can be found here.

To summarise, AUT64 is a 64-bit block cipher with an unbalanced Feistel-network type construction. The key has around 96-bits of entropy, the round size is at least eight and the cryptographic properties of the cipher are key-dependent to an unusually large degree.

That’s all for now. In the follow up post on this paper I’ll highlight the key cryptographic and implementational weaknesses which let us break AUT64!