Dismantling DST80-based Immobiliser Systems

Abstract. Car manufacturers deploy vehicle immobiliser systems in order to prevent car theft. However, in many cases the underlying cryptographic primitives used to authenticate a transponder are proprietary in nature and thus not open to public scrutiny. In this paper we publish the proprietary Texas Instruments DST80 cipher used in immobilisers of several manufacturers. Additionally, we expose serious flaws in immobiliser systems of major car manufacturers such as Toyota, Kia, Hyundai and Tesla. Specifically, by voltage glitching the firmware protection mechanisms of the microcontroller, we extracted the firmware from several immobiliser ECUs and reverse engineered the key diversification schemes employed within. We discovered that Kia and Hyundai immobiliser keys have only three bytes of entropy and that Toyota only relies on publicly readable information such as the transponder serial number and three constants to generate cryptographic keys. Furthermore, we present several practical attacks which can lead to recovering the full 80-bit cryptographic key in a matter of seconds or permanently disabling the transponder. Finally, even without key management or configuration issues, we demonstrate how an attacker can recover the cryptographic key using a profiled side-channel attack. We target the key loading procedure and investigate the practical applicability in the context of portability. Our work once again highlights the issues automotive vendors face in implementing cryptography securely.

Introduction

A vehicle immobiliser system is an imperative anti-theft device in any modern car. By requiring cryptographic authentication from a Radio Frequency IDentification (RFID) transponder embedded within the key fob, the immobiliser prevents an attacker from hot-wiring a car. The car typically authenticates the low-frequency transponder through a challenge-response protocol based on symmetric key cryptographic primitives. However, the use of proprietary cryptography in several widespread immobiliser systems has rendered these practically ineffective. In order to safeguard the security of the immobiliser, it is crucial that the community can publicly scrutinise the underlying cryptographic primitives. Texas Instruments (TI) produced their first cryptographically enabled transponder in 1995, named Digital Signal Transponder 40 (DST40). Bono et al. reverse engineered the DST40 cipher using a black-box approach in 2005 and showed that an attacker could exhaustively search the key space using an FPGA cluster. As a consequence, TI released DST80 as a successor to the insecure DST40 in 2008 in order to prevent exhaustive search attacks. DST80 transponders use an 80-bit cryptographic key to encrypt a 40-bit challenge generated by the reader. To this date, DST80 remains confidential and the immobiliser systems relying on it have not been publicly scrutinised.

The immobiliser is a mandatory anti-theft device in any motorised vehicle sold in the European Union since 1995. Its primary purpose is to prevent unauthorised use of the vehicle, which it achieves by requiring an RFID transponder to authenticate before starting the vehicle. Figure 1 depicts the general layout of such an immobiliser system, comprising an ignition coil, the immobiliser ECU, the Engine Control Unit and a transponder embedded in a key fob. The immobiliser identifies the transponder, which it powers through the ignition coil, through a Transponder Base-Station IC such as the TMS3705. Subsequently, it challenges the transponder chip, which authenticates by generating a cryptographic response. Only when this response is correct, the immobiliser authenticates to the Engine Control Unit and enables it to start the engine. The security of the link between the immobiliser and engine ECU is beyond the scope of this paper.

Contributions

The contributions of this paper can be summarised as follows:

• Recovering and reverse engineering immobiliser firmware. We present a novel fault attack to recover the firmware of the Renesas 78K0 microcontroller. We reverse engineered the proprietary DST80 cipher from this immobiliser firmware, and we publicly document this cipher for the first time in full detail. Additionally, we recovered the key diversification schemes from three major manufacturers.

• Security analysis of key diversification schemes. We analyse the security of the key diversification schemes used in Toyota, Kia and Hyundai immobiliser systems. We reduce the complexity for recovering the cryptographic key from 2^80 to 2^24 off-line encryptions for Kia and Hyundai. For Toyota immobiliser systems, we show how the key is based on publicly readable information such as the transponder serial number, therefore losing all of its entropy.

• Practical attacks on DST80 transponders. We show how a downgrade attack can reduce the key space from 2^80 to 2^41. Depending on the exact configuration, this can lead to recovery of the DST80 key using two lookup tables and only four challenge response pairs. This attack affects the second version of the Tesla Model S key fob. Moreover, we describe Denial-Of-Service attacks, which can render the key
fob unusable.

• A portable profiled side-channel attack on the key loading procedure. We propose a profiled side-channel attack to recover the cryptographic key from a properly configured transponder. Specifically, we target the key loading procedure performed before each invocation of the cipher. Attacking static data loads using a profiled attack is considered one of the most difficult side-channel targets. In this paper, we document how this can be done in practice and take portability issues into account. Previous work proposes correcting for DC offset and using normalization techniques to overcome portability issues. These techniques do not solve the issues encountered in this scenario, instead we create a model for the family of devices and attack a previously unseen device to evaluate the model. Using this technique, we can reduce the key space from 2^80 to approximately 2^40 using only 10 traces.

RELATED WORK

Immobiliser and Keyless Entry systems

Because of their security critical function, immobilisers have been a hot topic of research ever since they became an integral part of the car’s internal network. As early as 2005, Bono et al. published and cracked the DST40 cipher used in immobiliser systems of many vehicles by exhaustively searching the keyspace with an FPGA cluster. More recently, Wouters et al. uncovered the use of the same DST40 cipher in immobiliser systems of several high-end contemporary supercars, including certain Tesla and McLaren models. In contrast, in this work we analyse the security of multiple real world immobiliser systems using the DST80 cipher and demonstrate multiple practical attacks. In 2012, Verdult et al. found several flaws in the Hitag2 cipher, allowing an attacker to bypass the electronic protection within minutes. One year later, researchers proposed several attacks on the Megamos Crypto transponder, another cipher widely used in car immobilisers. Finally, Hicks et al. disclosed several vulnerabilities in AUT64, a 64-bit feistel network block cipher used in immobiliser systems of Mazda, Ford and Proton cars.
The immobiliser, Passive Keyless Entry (PKE), and Remote Keyless Entry (RKE) systems are often intertwined in modern vehicles. When combined, they are referred to as a Passive Keyless Entry and Start (PKES) system, which allows the vehicle to unlock and start automatically when the legitimate user is near-by the vehicle. Francillon et al. showed that several models with PKES systems are vulnerable to relay attacks in NDSS 2011.
In 25th USENIX Security Symposium, Garcia et al. presented a novel correlation-based attack on the Hitag2 cipher in order to bypass the RKE system in vehicles of several manufacturers. They also revealed the lack of key diversification in the VW Group RKE systems. Furthermore, it has been demonstrated that the Keeloq cipher, used in both immobiliser and RKE, is vulnerable to a plethora of physical and cryptanalytical attacks.

Side-Channel Analysis

With respect to the physical security of transponder chips, Side-Channel Analysis (SCA) is a well established field of research in which side-channel emanations of a target device are captured and analysed to extract secret information. In contrast to an exhaustive search or a cryptanalytic attack the goal of SCA is to recover (part of) the cryptographic key by observing one or more side-channels such as power consumption, electromagnetic radiation, time, temperature and photonic emissions. The attacks discussed in this paper use power side-channel measurements to recover the cryptographic key from DST80 transponders.
   Side-channel attacks are generally divided into non-profiled and profiled attacks. Nonprofiled attacks such as Differential Power Analysis (DPA) do not assume any prior knowledge about the device being attacked [KJJ99]. In contrast, a profiled side-channel attack consists of two phases commonly referred to as the profiling and the attack phase. During the profiling phase an adversary is assumed to have access to one or multiple unlocked devices which they can use to acquire side-channel measurements. These profiling measurements are used to create a model for the device. During the attack phase the attacker will acquire measurements from a Device Under Test (DUT) for which he cannot modify the key. The model created during the profiling phase is now used to recover the key from the DUT. Multivariate Gaussian templates and stochastic models are the most common types of profiled attacks.
   Recently machine learning techniques such as Multi-Layer Perceptron (MLP) models and Convolutional Neural Networks (CNNs) have been shown to perform well in the profiled attack scenario, in some cases outperforming classical profiled attacks. For example, the translation invariability of CNNs is an advantage when measurements suffer from misalignment. Carbone et al. showed that machine learning can be an effective tool when evaluating cryptographic implementations with countermeasures.
   The practical applicability of profiled attacks is often overestimated by using the same device, and measurements from the same acquisition campaign during both the profiling and attack phases. In this setting the inter-device variability and environmental factors such as changes in the measurement setup or ambient temperature are neglected. Montminy et al. demonstrated that using the zero mean, unit variance normalization technique on both the training and attack dataset significantly improved the effectiveness of their template attack on the AES AddRoundKey operation. Choudary and Kuhn have shown that template attacks can be made portable in certain situations by using dimensionality reduction techniques and manipulating the DC content of the eigenvectors. In an artificial scenario they were able to recover the exact value of an 8-bit data load across multiple devices with a success rate of 85% using 1000 attack traces. In their experiments the main difference between devices and acquisition campaigns were due to DC offset, their results show that compensating for this DC offset and using multiple devices in the profiling step greatly improves the template efficiency.
   Recent work by Golder et al. has shown that using Principal Component Analysis in combination with Dynamic Time Warping (DTW) and a Multi-Layer Perceptron (MLP) model trained on traces from multiple devices can achieve an accuracy up to 99.43% on unseen devices. Similarly to the work by Choudary et al. they targeted the Atmel 8-bit XMEGA family of microcontrollers but instead of focusing on a single byte load their target was the AES block cipher. In contrast, in this work, we target multiple subsequent byte loads in a real-world scenario in which we do not know the implementation and have no control over it.

DST80

DST80 transponders

The Texas Instruments DST transponders are available in different package types; the classical wedge type transponder (TMS37145), a TSSOP package (TMS37126) and a TSSOP package containing both the TMS37126 and an MSP430 microcontroller (TMS37F128). All of these incorporate an 80-bit authentication key, which is internally stored in two 40-bit chunks, keyL and keyR. The transponders can be configured either for fast authentication (the reader is not authenticated) or mutual authentication. DST80 transponders are uniquely identified by a 32-bit serial number stored in EEPROM consisting of a 3-byte unique identifier and a 1-byte manufacturer code. According to the datasheet, pages 1, 2 and 3 are always publicly readable. Additionally, the transponder incorporates several pages of EEPROM user memory, all of which can be write-locked. Table 2 gives an overview of several significant EEPROM pages of a DST80 transponder.

Table 2: DST80 transponder memory layout

Page	Size (bytes)	Description
1	1	Selective addressing "Password page"
2	1	User data "Identity page"
3	4	Transponder ID
4	10	Encryption key
30	5	Configuration page

Reading out immobiliser firmware

We found the same immobiliser ECU in both Kia and Hyundai cars. An 8-bit microcontroller (the STM8AF6266) controls the ignition coil and enables or disables the Engine Control Unit over a serial connection depending on whether the authentication was successful. This particular microcontroller is part of the STM8AF series and has 8kB of flash and an internal EEPROM of 384 bytes. It also features memory read-out protection, however, in this case, the protection was not enabled. Thus, we could recover the firmware and internal EEPROM by connecting to the SWIM interface and issuing a Read-On-The-Fly (ROTF) command, which allows to read any byte in the 24-bit address space. If the read-out protection was enabled, an attacker could potentially recover the firmware by adapting existing physical attacks.

On the other hand, in Toyota cars, a dedicated ECU produced by Tokai Rika handles the immobilisation process. It contains an external ST96320 EEPROM chip connected to a main MCU with only a Tokai Rika part number on it, making it hard to identify the chip. In order to read out the firmware of this MCU, we had to determine its model and debug interfaces. By looking at the locations of standard pins, such as Vcc and Vss, we narrowed down the search to the Renesas 78K0 series . By taking the location of the oscillator pins (X1 and X2) into account, the 78K0/Kx2 resulted as the most likely candidate. The 78K0 microcontrollers contain an on-chip bootloader, which is accessible through the Renesas Flash Programming Interface. By setting the FLMD0 pin high on reset, an external programmer can access this serial interface to write, erase, and verify the internal flash. However, the 78K0 series does not provide a command to read the memory. We used a Raspberry Pi 3 to communicate with the chip using a combination of GPIO pins (for RESET and FLMD0 signals) and the UART pins. After issuing the signature command, we recovered the exact model of the MCU, namely the µPD78F0515A, a 64kB A-grade 78K0/KC2 MCU.

Bozzato et al. show several ways to read out the internal flash of such MCUs through voltage glitching attacks. One attack is based on overwriting an empty flash section of the MCU with a custom piece of code that outputs the memory over a serial interface, and finally overwriting the reset vector to boot from this section. We improved on this attack by targeting the Security Set command. The 78K0/Kx2 series provides several levels of security: block erase, chip erase, write and boot sector overwrite protection, which cannot be reversed once enabled. The Security Set command sends a byte containing each security bit individually, after which the Renesas bootloader checks that none of the given bits reverse the current security settings. By voltage glitching this command, we disabled all security bits on the MCU, giving us the ability to erase and overwrite the boot section with our custom program to dump the firmware over a serial interface. This attack only requires a single successful glitch. To read the boot section as well, we repeated the attack with a second, identical immobiliser ECU, however now overwriting a different, reachable section with our own program. Once the microcontroller executes this section, the boot section is dumped and we have recovered the whole firmware. Because we need to perform the attack twice in this case, we require a total of two successful glitches, improving significantly on the so far most efficient known attack, which required a total of 15,000 successful glitches.

Hardware setup and glitch parameters. For glitching the firmware protection of the 78K0 immobiliser MCU, we used the Generic Implementation ANalysis Toolkit, an open-source FPGA-based board used for glitching and hardware analysis. We used a Raspberry Pi 3 running Raspbian to interface with the microcontroller’s bootloader of the immobiliser ECUs and to control the glitching hardware. In order to read out the immobiliser ECU firmware, we implemented large parts of the Renesas Flash Programming Interface in Python. We acquired a 2011 Toyota Auris and a 2014 Toyota Hilux immobiliser ECU. We desoldered the chips from the ECUs, placed each of them on a breakout board, and connected a 16 MHz resonator to the oscillator pins X1 and X2. As shown in Figure 3, we connect the voltage output from the GIAnT to the REGC pin in order to bypass the internal regulatory capacitor of the 78K0. Next. we confirmed that both chips contain the same firmware by comparing the values obtained by the checksum command.
With a glitch voltage of 0 V and a normal operating voltage of 2.7 V, we triggered on the first transmitted bit of the Security Set message from the Raspberry Pi, resulting in a successful glitch of 100 ns width at an offset of 596.78 µs on the first and 818.05 µs on the second chip. We attribute the significant difference in glitch offsets to the initial value of the security byte: in the Hilux MCU, the write protection for non-boot sectors was already disabled, while in the chip desoldered from the Auris immobiliser, all protection bits were initially set.

DISMANTLING DST80-BASED IMMOBILISER SYSTEMS

Immobiliser and Keyless Entry systems

DST80 transponders

Reading out immobiliser firmware

Reverse engineering the cipher