Passive Keyless Entry and Start Systems in Modern Supercars

Abstract. The security of immobiliser and Remote Keyless Entry systems has been extensively studied over many years. Passive Keyless Entry and Start systems, which are currently deployed in luxury vehicles, have not received much attention besides relay attacks. In this work we fully reverse engineer a Passive Keyless Entry and Start system and perform a thorough analysis of its security. Our research reveals several security weaknesses. Specifically, we document the use of an inadequate proprietary cipher using 40-bit keys, the lack of mutual authentication in the challenge-response protocol, no firmware readout protection features enabled and the absence of security partitioning. In order to validate our findings, we implement a full proof of concept attack allowing us to clone a Tesla Model S key fob in a matter of seconds with low cost commercial off the shelf equipment. Our findings most likely apply to other manufacturers of luxury vehicles including McLaren, Karma and Triumph motorcycles as they all use the same system developed by Pektron.

Introduction

The first Remote Keyless Entry (RKE) system for cars was introduced by Renault in 1982. Back then these systems used infrared instead of Radio Frequency (RF) transmissions. Nowadays, vehicles are typically equipped with a RKE system and often include a Passive Keyless Entry (PKE) system. The former allows users to lock and unlock their vehicle by the press of a button on a key fob. The latter unlocks the vehicle automatically when the key fob is in its close proximity.
Additionally, cars employ an immobilizer system that verifies the legitimacy of the user’s key fob before starting the engine. According to Van Ours and Vollaard, the use of immobilizer systems reduced the number of car thefts significantly. Immobilizers are usually implemented using a cryptographically enabled Radio-Frequency IDentification (RFID) device embedded in the key fob. The first family of such RFID chips was introduced by Texas Instruments in 1995. These Digital Signature Transponders (DST) relied on the proprietary DST40 cipher.
While traditionally keyless entry and immobilization were two separate systems, nowadays luxury cars often combine these features into a single Passive Keyless Entry and Start (PKES) system. This allows to unlock the vehicle and disengage the immobilizer without any user interaction. The move towards PKES systems results in higher convenience for users but could also facilitate certain attacks as no interaction of the legitimate user is required. For example, recent reports have shown car thieves using relay attack systems which can be purchased online.

Contributions

The main contributions of our work are twofold.

• Security analysis. We provide the reader with a detailed explanation of our reverse engineering efforts and protocol analysis. By doing so we identify multiple security issues in the PKES system designed by Pektron such as the use of an inadequate proprietary cipher, the lack of mutual authentication in the challenge-response protocol, no firmware readout protection features enabled and the absence of security partitioning. Additionally, we explore the feasibility of a car-only attack, i.e. without access to the key fob.

• Proof of Concept attack. The combination of the identified issues allows for a very efficient attack. We implement a Proof of Concept (PoC) attack allowing us to clone the key fob of high-end vehicles such as the Tesla Model S using Commercial Off The Shelf (COTS) equipment in seconds. We are hence able to unlock and start the vehicle at any time.

1. Related work

Over the years, researchers have shown that manufacturers often rely on proprietary ciphers for their keyless entry and immobilizer systems. The proprietary DST40 cipher was reverse engineered by Bono et al. back in 2005. Subsequently, the authors constructed a key cracker using 16 FPGAs allowing the recovery of the 40-bit cryptographic key from two challenge-response pairs in less than one hour. At the time of their research, DST40 was used in an estimated 150 million vehicle immobilizers and 7 million Speedpass tags for Exxon Mobil’s payment system.
    The only publicly known attack on DST40’s successor DST80 is a physically invasive downgrade attack using a laser and probing station. In addition, it requires prolonged physical access to the victim’s key fob, expensive equipment and a skilled operator. It is important to note that these researchers had access to the specifications of DST80 during the development of their attack.
    Bogdanov was the first to analyze and conduct attacks on the proprietary KeeLoq block cipher owned by Microchip. A more practical algebraic attack was introduced by Indesteege et al. in 2008. This attack required 65 minutes of access to the victim’s key fob in order to collect the necessary plaintext-ciphertext pairs for recovering the key. Eisenbarth et al. presented a Differential Power Analysis (DPA) attack on a Microchip HCS encoder requiring only ten power traces. In 2009 Kasper et al. introduced a Simple Power Analysis (SPA) attack on a KeeLoq software implementation. This led them to recover the manufacturer key from a single power trace.
    In 2012 Verdult et al. executed multiple cryptanalytic attacks on the Hitag2 stream cipher used in NXP transponders. Their attacks allow to recover the 48-bit key in less than 360 seconds. Despite these attacks, Hitag2 is still widely used in vehicle immobilizers and RKE systems. In 2013 Verdult et al. reverse engineered the Megamos Crypto cipher from an automotive key programmer’s software. Furthermore, they proposed practical attacks on both the cipher and the authentication protocol.
     In addition to the weaknesses identified at the cryptographic primitive level, manufacturers often neglect key management. Garcia et al. conducted a security analysis of multiple keyless entry systems used by the Volkswagen Group between 1995 and 2016. Their findings revealed that some of these systems rely on a single master key which can be retrieved using commercial programmers. This flaw enables adversaries to clone a key fob after eavesdropping on a single transmission. The authors also proposed a novel attack on a Hitag2-based rolling code scheme used by several car manufacturers. This attack requires eavesdropping on 4–8 transmissions and about one minute of computation. Benadjila et al. analyzed a variant of this Hitag2-based rolling code scheme which is not susceptible to the attack proposed by Garcia et al. They propose an attack through which it is possible to forge valid packets without needing to retrieve the cryptographic key; this attack requires eavesdropping on two legitimate transmissions.
    Even if strong cryptographic primitives with unpredictable random keys are used, attacks that exploit weaknesses in the protocol such as relay attacks and eavesdroppingand-jamming may still be possible. The former can be executed by relaying the messages exchanged between genuine devices. The latter can compromise the security of rolling-code-based systems by capturing a valid message while jamming it such that the legitimate device is unable to receive it. By repeatedly eavesdropping-and-jamming valid messages and transmitting the previously recorded message, adversaries always have one valid rolling code that will be accepted by the victim’s car.

2. DST transponder exploration

The key fobs analyzed during this research use the Texas Instruments TMS37F128 chip. The TMS37F128 is a multi-chip package containing two dies; one identical to the die found in the TMS37126 package and one MSP430F1232 microcontroller. To explore the DST transponders we purchased some TMS37126 chips which can be controlled by an external microcontroller using the Serial Peripheral Interface (SPI).
To obtain the datasheets for the TMS37F128 or TMS37126, one has to sign a nondisclosure agreement (NDA) with Texas Instruments which we did not do. Nevertheless, there is one public application note that discloses some basic information about how a microcontroller can interact with the TMS37126 using SPI. For example, it illustrates the SPI frame structure and shows how to interact with the chip to execute DST40.
This section covers the techniques we used to identify publicly undocumented SPI commands. Our initial goal was to learn more about the functionality provided by these transponders and to identify the command used to perform DST80.

We found that the behavior of the busy line in combination with two key observations can be used to recover all valid commands supported by the transponder. The first observation is that the busy line produces an error state (i.e. by remaining high or low for an extended period of time) if the CMD of the frame is invalid. Secondly, by setting the value of the LEN byte to 0xFF, one can determine the correct length for a given command by observing when the busy line indicates an error. For example, if the correct LEN value for a certain command is 0x06, the busy line will indicate an error after the 6th byte. Using these observations, we were able to uncover all valid values for the CMD and LEN fields.
Applying this technique in an automated fashion revealed four publicly undocumented commands each requiring a 5-byte input (challenge) and returning a 3-byte output (response). Additionally, we found two commands allowing to set two independent 40-bit keys. Table 1 shows an overview of the commands we have identified. After some initial tests with different challenges and keys, we determined that the responses produced by two of these four commands correspond to the ones we would expect from a DST40 implementation. For a given challenge we observed that changing one of the 40-bit keys results in a different response for two of the four commands. From these initial tests, we were able to conclude that the chip contains two independent DST40 implementations. Additionally, there are two independent implementations of an unknown cryptographic function relying on a 40-bit key. We denote this unknown function as DST40_UNK. We also reversed engineered this algorithm and found that it is similar in nature to DST40 but with some minor differences. A description of this algorithm is out-of-scope for this paper and is not included.

Action	LEN	CMD	WA
DST40(C, K1)	0x06	0x84	NA
DST_UNK(C, K1)	0x06	0x85	NA
DST40(C, K2)	0x06	0x86	NA
DST_UNK(C, K2)	0x06	0x87	NA
Change K1	0x07	0x01	0x11
Change K2	0x07	0x01	0x15

3.1 Firmware analysis

There are two ways for recovering the SPI commands used in a key fob with a DST transponder: (i) sniffing the SPI communication or (ii) acquiring and analyzing the microcontroller firmware. Sniffing the SPI communication in the TMS37F128 chip requires connecting to the bond wires interconnecting both dies, as can be seen in Figure 2. Reading the firmware of an MSP430F1232 requires an intact JTAG fuse or circumventing the bootstrap loader (BSL) password check.
In the case of the Tesla Model S key fob the security fuse was not blown, Figure 3 shows the key fob’s printed circuit board (PCB) with easily accessible debug pads. We used an Olimex MSP430 JTAG debugger to read the microcontroller’s program memory.

Tesla S key fob PCB - TMS37F128 - pads to connect an MSP430 compatible JTAG debugger.

Figure 3: The Tesla Model S key fob PCB with the TMS37F128 chip in the middle. The square shaped pads at the top can be used to connect an MSP430 compatible JTAG debugger.

We analysed the retrieved firmware in two stages in order to get a good understanding of its inner workings. In the first stage, we performed static firmware analysis using Binary Ninja in combination with the MSP430 plugin. In this stage the goal was to get a high level overview of the firmware and to identify the routines to be more closely investigated in stage two. Static analysis involves many hours of reading assembly code, but some information can be taken into account while trying to identify routines of interest.
    The Interrupt Vector Table (IVT), which is stored at the end of the program memory, enabled us to identify the routines that are executed when an interrupt occurs. Using the information from this table we were able to identify the entry point to the firmware image as well as the routines that handle the press of a button on the key fob. Special Function Registers (SFR) can also be used to identify routines of interest. As we are interested in the SPI communication we searched for references to the address of the SPI transmit buffer. Using these techniques we were able to identify a few routines to be analyzed in stage two.
    The second stage is dynamic firmware analysis. This analysis involved debugging a real Tesla Model S key fob using the Olimex debugger and the MSPdebug software. The MSP430F1232 supports up to two breakpoints that can be used to halt the processor at certain addresses. When the processor is halted we can inspect the contents of the registers and dump the memory, this is very useful when trying to understand the firmware. For example, by setting breakpoints at the start and end of the SPI routine we could easily identify the bytes being sent and received by the MSP430 microcontroller. In fact, we used this method to identify all the SPI commands that are used during nominal operation of the key fob.
    As was already mentioned, we expected the microcontroller to query the transponder for a DST80 response; to our surprise we found that the microcontroller was using only one of the four cipher commands (0x86) identified in Section 2.1. Additionally, we had already identified this particular command to be the DST40 compression function.
    Using a 40-bit cipher today results in inadequate security levels as even an exhaustive search is feasible in a reasonable amount of time. While cryptanalysis might reveal weaknesses that further reduce the security of the cipher, it is a time consuming and unnecessary process for a 40-bit key. In the case of DST40 an exhaustive search will require two challenge-response pairs to recover the correct key as the challenge (40-bit) is larger than the response (24-bit).
    In Section 5.1 we show how a vulnerability in the PKES protocol can be exploited by a Time-Memory Trade-Off attack allowing key recovery in a matter of seconds.

3.2.1 Low frequency – 134.2 kHz

The vehicle uses Burst Width Modulation (BWM). This is also known as Binary Pulse Length Modulation (BPLM) or Pulse Position Modulation (PPM). In this modulation scheme bits are encoded by the period during which the carrier is modulated. Bits are separated by a fixed period in which the carrier is unmodulated.
    We used a Proxmark III RFID security research tool to receive and transmit LF signals, as it supports the 134.2 kHz operating frequency. During this research we had full-time access to a spare Tesla Model S key fob but only limited access to a vehicle. Because of this we first implemented car impersonation, allowing us to use a second Proxmark III to implement receiving.
    We configured the Proxmark’s relay and multiplexer to use the low frequency peak detect circuit and configured the FPGA to use the peak detection algorithm implemented by iZsh. Using one of the microcontroller’s timers the number of clock cycles between pulses can be counted in order to demodulate the received signal to bits. While this implementation could successfully receive frames transmitted by a Proxmark it did not allow us to receive frames transmitted by the car.
    The peak detect circuit on the Proxmark III is implemented using a diode, causing a voltage drop. This voltage drop in combination with the low received signal strength caused all information to be lost before entering the 8-bit Analog-to-Digital Converter (ADC), making it impossible for the FPGA to detect any peaks. To overcome this issue, we soldered a wire from the output of the low frequency raw input path amplifier to the input of the peak detect circuit. This effectively amplifies the signal before it reaches the analog peak detect circuit. Afterwards we reconfigured the relay and multiplexer in software to accommodate for this change. Additionally, we wrote our own peak detect Verilog code for the FPGA. Our peak detection algorithm allows to more reliably receive transmissions sent by the vehicle over longer distances.

4.1 Passive Keyless Entry and Start

Figure 4: The PKES protocol during nominal operation assuming the key fob is in range of the car.

We created a Python framework handling both the Proxmark III and YARD Stick One, allowing us to receive all communications exchanged by vehicle and key fob during passive entry and passive start.
Figure 4 gives an overview of the PKES protocol during nominal operation. Our experiments on two different Tesla Model S vehicles show that the general structure of LF frames is as outlined in Figure 5. The car periodically sends one of four 3-byte wake frames consisting of a 2-byte car identifier and a command byte. If the key fob is in range it receives this wake message and replies with a 3-byte frame that is fixed yet unique for each of the four wake messages. Our experiments show that the correct reply to a given wake message can be easily calculated as the latter is an obfuscated version (using byte swaps and logical shifts) of the former.

Figure 5: The structure of LF frames transmitted by the car. The 2-byte car ID is followed by a command byte, in case of a response request an additional challenge is concatenated.

The car verifies this reply and transmits an 8-byte frame consisting of the 2-byte car identifier, a command byte and a 5-byte challenge. In turn the key fob uses this challenge in the DST40 compression function to produce a 24-bit response before transmitting it over UHF. The vehicle verifies the response and, if successful, unlocks the doors. Afterwards the car and key fob engage in a keep-alive protocol in which the car repeatedly transmits one of the four wake messages to which the key fob replies. Once the driver presses down on the brake pedal to start the vehicle the key fob again authenticates to the vehicle using the same challenge-response protocol described above. This second authentication serves as the immobilizer; it uses the same 40-bit cryptographic key used for opening the car.
As there is no mutual authentication in the protocol the key fob replies to any challenge it receives as long as the frame format is correct. This allows for a chosen input attack which we exploit in our PoC. Additionally, as there is no security partitioning, recovering a single 40-bit key allows an adversary to both unlock the vehicle and start it. Furthermore, the protocol does not implement any distance bounding mechanisms and is thus vulnerable to a relay attack.

4.2 The remote keyless entry protocol

The RKE protocol allows to lock and unlock the car, open and close the trunk and open the front storage compartment or frunk of the car by the press of a button (one-way communication).
    In the previous section we explained how we recovered the protocol and frame structure by effectively building a protocol analyzer. For the RKE protocol we used a different approach in which we did not have to intercept any radio transmissions. For this we used the Olimex debugger in combination with mspdebug and a Saleae logic analyzer connected to the MICRF112 RF transmitter chip on the key fob PCB. This allowed us to set breakpoints at the start and finish of the SPI routine and retrieve the bytes sent to and received from the DST co-processor.
    This technique revealed that following a key press, the key fob will first retrieve a 40-bit counter from the DST transponder’s EEPROM. This counter value is used as the input or challenge to the DST40 compression function, using the same 40-bit key as in the PKES system. The final RF packet consists of a preamble followed by an action byte (lock/unlock) concatenated with the DST40 response (3 bytes) and the two least significant bytes of the 40-bit counter. Afterwards the counter is incremented and again stored in the EEPROM. The main goal of the counter is to prevent replay attacks, transmitting part of the counter allows for resynchronization of the car and key fob counters. This kind of construction is often referred to as a rolling code.
    This rolling code implementation is vulnerable to a jamming and eavesdropping attack as implemented in Kamkar’s RollJam attack. In this attack the adversary uses a transmitter to jam inside the car’s receiver bandwidth and a receiver with a narrow bandwidth to capture the key fob’s transmissions. The adversary thus ensures that the car is unable to receive the first transmission from the key fob and records it. The same action is performed when the legitimate user uses their key fob a second time; subsequently the adversary transmits the first captured message. At this point the adversary has a legitimate message which is still valid and can be transmitted at a later time. This rolling code scheme is particularly vulnerable to this attack since the action is not authenticated in any way. If the adversary succeeds in obtaining a valid lock command he would be able to unlock the car by changing the action byte before transmission.

4.3 A car-only attack

This section discusses the possibility of a car-only attack. The goal of such attack would be to retrieve the 40-bit cryptographic key without ever being in proximity of the legitimate key fob. This kind of attack could be feasible in practice in a situation were the owner leaves their car for a long period of time (e.g. parking their car at an airport).
    The PKES protocol requires the key fob to respond with a valid reply to a wake command transmitted by the vehicle. From our earlier analysis we learned that one can easily predict the correct reply based on the wake message. There is thus no need for an adversary to brute force the correct reply.
    The actual attack would go as follows: for each challenge transmitted by the car, the adversary will calculate the response based on a key guess and transmit it. For each challenge transmitted by the car there will be approximately 2^16 keys which produce a correct response. On average, it would thus take an adversary close to 2^23 guesses before he finds a key which produces the same response as the key used in the legitimate key fob. Testing 2^23 keys would take close to 97 days assuming a rate of one guess per second.
    After obtaining one challenge-response pair the adversary creates a list of keys which produce the same response for this challenge; this list will contain approximately 2^16 keys. The last step for the adversary is to test these keys until a match is found. Testing one such key per second would on average result in the correct key within 9 hours.
    An adversary would thus be able to recover the 40-bit cryptographic key from a target car without ever being close to the legitimate key fob in less than 100 days on average. It is important to note that this attack can be automated as the car will continue with the keep alive protocol once a correct response is received instead of sending another challenge (indicating that the received response was correct). However, unless an adversary is able to achieve a reasonable speedup (e.g. by increasing the symbol rate, by using de Bruyn sequences or exploiting a flaw in the protocol state machine) it is unlikely to be a practical attack.
    A controller area network intrusion detection system could detect this attack if the Body Control Module (BCM) communicates failed authentication attempts. However, in one of our experiments we started the challenge-response protocol and let it time out 40,000 times in a Tesla Model S during a 12-hour period without encountering any issues. Therefore, we believe that no rate limiting is implemented by the vehicle. We note that any naive rate limiting procedure would expose the car to DoS attacks.

5. Proof of Concept implementation

In order to verify our findings we implemented a PoC attack. For this PoC we envision an attack scenario where an adversary is nearby while the legitimate owner parks their car; the adversary now has a limited amount of time in order to clone the key fob and drive off.
The attack will be carried out in three or four phases:

Phase 0: Receive car wake message (optional). As a first step, the attacker records one wake frame periodically transmitted by the car in order to learn the car identifier. This is an optional task since one could brute force the 2-byte identifier when in proximity of the victim’s key fob.

Phase 1: Car impersonation. During this phase, the adversary impersonates the victim’s car, transmits two chosen challenges to the victim’s key fob, and records the responses. During this phase the adversary would have to be relatively close (roughly 1 m) to the legitimate key fob for a few seconds (e.g. walking by the target) in order to acquire the two challenge-response pairs.

Phase 2: Key recovery. During the second phase the adversary recovers the 40-bit key from these two challenge-response pairs.

Phase 3: Key fob impersonation. After recovering the 40-bit key, the adversary proceeds to mimic the behavior of the victim’s key fob to unlock and start the target vehicle.

For Phases 1 and 3 of the proposed attack we made minor modifications to our protocol analyzer. Phase 1 is possible due to the lack of mutual authentication in the protocol. Our implementation of Phase 2 is now explained in detail.

5.1 Key recovery

Bono et al. used 16 FPGAs to brute force the 40-bit key in under 1 hour; today this time could be significantly reduced using more recent FPGAs or FPGA cloud services. Instead of executing a brute force attack using hardware acceleration we opted for a Time-Memory Trade-Off (TMTO) attack. In the case of DST40 there are 2^16 keys that produce the same 24-bit response to a fixed 40-bit challenge, on average. A second challenge response pair is thus required to determine the correct key. In order to speed up key recovery we grouped all keys producing the same response to a fixed challenge. Resulting in a lookup table consisting of 2^24 files, each containing roughly 2^16 keys. The entire file structure takes up 5.4 TB in size. Using this lookup table a key recovery requires two challenge-response pairs. The first pair is used to select the correct candidate key file. The second challenge-response pair is used to recover the correct key via 2^15 DST40 invocations, on average.

5.2 Practical results

Using our PoC implementation we were able to successfully retrieve the challenge-response pairs from a target key fob in a matter of seconds while being approximately 1 m away. It should be noted that an adversary could attempt to increase this distance, we made no such effort.
Using the first challenge-response pair and the lookup table the key space is reduced to 2^16 candidate keys. Using the second challenge-response pair we determine the correct key in 2^15 DST40 invocations, on average. This last step takes less than 2 seconds using a single ARMv7 core running at 1.4 GHz. After recovering the key we are able to successfully unlock and drive away with the vehicle. The entire attack was successfully carried out on two different Tesla Model S vehicles with consent of the owners.
The entire attack platform shown in Figure 6 was implemented using only Commercial Off The Shelf (COTS) equipment. The goal of the PoC attack was not to reduce the cost. Nevertheless, the entire attack platform can be build for 600$ and easily fits in a backpack.

Vehicle PKES attack platform - Yard Stick one, Proxmark III, Raspberry Pi 3 Model B+

Figure 6: The entire attack platform. Consisting of a Yard Stick one, Proxmark III, Raspberry Pi 3 Model B+, a battery pack and a 6 TB hard drive.

PASSIVE KEYLESS ENTRY AND START SYSTEMS IN MODERN SUPERCARS

2. DST transponder exploration

3. Reverse engineering the Tesla Model S PKES system

4.1 Passive Keyless Entry and Start