High-end vehicles are often equipped with a Passive Keyless Entry and Start (PKES) system. These PKES systems allow to unlock and start the vehicle based on the physical proximity of a paired key fob; no user interaction is required.
Researchers have already shown these systems to be particularly vulnerable to relay attacks [1, 2]. In this type of attack two adversaries relay the short-range communication over a long-range communication channel. Recent news reports and home security videos have shown that relay attacks are frequently used to steal luxury vehicles. Distance bounding mechanisms are gradually being deployed to preclude relay attacks.
The goal of our research was to evaluate the resistance of a modern-day PKES system to attacks other than relay attacks. We have completely reverse engineered the PKES system used in the Tesla Model S. Our research shows that this system is using the outdated proprietary DST40 cipher.
The Passive Keyless Entry and Start (PKES) system as introduced earlier allows to both unlock and start the car if the key fob is in proximity. In the remainder of this article we provide a simplified explanation of how the Tesla Model S PKES system works and why it is insecure. A more technical and thorough explanation of our research will be released soon as a paper.
How does it work?
The PKES system we analyzed uses a simple challenge response protocol as is shown in the figure below. The car uses the Low Frequency (LF) band at 134.2 kHz for transmission. The key fob on the other hand transmits in the Ultra High Frequency (UHF) band at 433.92 MHz in Europe.
During normal operation the car periodically advertises its identifier (denoted ‘wake’ in the figure below). The key will receive the car’s identifier, if it is the expected car identifier the key fob will reply, signaling it is ready to receive a challenge.
In the next step the car will transmit a random challenge to the key fob. The key fob computes a response and transmits it. After receiving the key fob’s response, the car must verify it before unlocking the doors. The same challenge response protocol is repeated to start the car.
The simple challenge-response protocol described earlier does have some issues. For example, the lack of mutual authentication allows anyone who knows the car’s identifier to get responses from a key fob. This identifier is broadcasted by the vehicle in the wake messages and can be recorded by anyone.
An even graver security issue lies in the cryptographic primitive used for computing responses. Our research shows that this system is using the outdated proprietary cipher DST40. Back in 2005 Bono et. al. reverse engineered this cipher using a black box approach and exhaustively searched the 40-bit key using an FPGA cluster .
Explaining the inner workings of the DST40 cipher is beyond the scope of this article. However, it is important to understand that DST40 transforms a 40-bit challenge into a 24-bit response, and that this transformation is dependent on a 40-bit secret cryptographic key. Additionally, Because the response or output (24-bit) is smaller than the input or challenge (40-bit) there will be multiple cryptographic keys that produce the same response to a given challenge. Because of this, an attacker requires at least two challenge response pairs to recover the cryptographic key.
Since the car’s identifier is public we can transmit any chosen challenge to a key fob and observe the response. We can thus transmit the same challenge to each key fob we try to attack. The combination of a very small key-space and lack of mutual authentication allow us to perform a Time-Memory Trade-Off (TMTO) attack. The idea is to perform precomputations and to store the results. These results will reduce the number of computations (and thus time) required to carry out every subsequent key recovery.
Specifically, we picked one challenge (0x636f736963), for every possible value of the key the response is computed. Afterwards, all keys that produced the same response can be grouped into a single file. The figure below is a visual representation of this 5.4TB data structure.
To recover the key used by a specific key fob, we first request a response to the fixed challenge. Using the value of this response we can read the correct file from the TMTO data structure giving us a list of approximately 2^16 or 65536 candidate keys. The next step is to query the key fob for a response to a different challenge. This second challenge-response pair can now be used to exhaustively search the 2^16 candidate keys. This last step takes 2 seconds on average in software on a Raspberry Pi 3 Model B+. Using the same Raspberry Pi and software it would have taken roughly 777 days to exhaustively search all 2^40 keys.
To show the practical nature of the proposed attack, we implemented a Proof of Concept (PoC) attack which allows to clone a key fob in a few seconds. The attacker device consists of a Raspberry Pi 3 Model B+, Proxmark3, Yard Stick One, and a USB battery pack. The Raspberry Pi connects to a smartphone’s WiFi hotspot allowing it to download files from a remote 6TB hard drive containing the TMTO tables.
The Proof of Concept attack
As shown in the video below the attack is carried out in multiple phases:
- Phase 0: the adversary records one wake frame periodically transmitted by the car to learn the 2-byte car identifier.
- Phase 1: the adversary can now impersonate the car and transmits two chosen 40-bit challenges to the key fob and records their respective 24-bit responses.
- Phase 2: using the captured challenge response pairs and the TMTO table the 40-bit key can be recovered. The first pair is used to select the correct subset of keys and the second pair is used to find the real key among the approximately 216 candidate keys.
- Phase 3: the adversary can now impersonate the key fob and thus unlock and start the car.
We have only been able to verify our attack on a Tesla Model S in practice. However, Tesla did not design this system themselves but purchased it from Pektron. According to the Federal Communication Commission (FCC) equipment authorization database, Pektron also designed keyless entry solutions for manufacturers such as McLaren, Karma and Triumph. The internal pictures included in the FCC database show that all these systems use the same Texas Instruments TMS37F128 chip. This leads us to believe that the attack described here also affects the other manufacturers.
Short term mitigations
It is often recommended to place the key fob in a Faraday bag or metal box to block the RF transmissions. While this could be an effective countermeasure, it is far from convenient.
Tesla has recently introduced some software features that could help hinder an adversary. Tesla Model S owners should disable passive entry and enable the pin to drive feature.
A third option is to modify the key fob by adding an extra push button which only enables the low frequency communication when pressed. The advantage of this modification is that it stops relay attacks and it makes our key fob cloning attack a lot harder to execute in practice. This countermeasure might be your only option if you own one of the affected vehicles that did not introduce software countermeasures. We will release a step by step tutorial on how to modify a key fob if there is enough interest.
- We first reported the vulnerability to Tesla Motors on 31/08/2017 following their responsible disclosure guidelines .
- Starting in January 2018, we made several attempts to contact Pektron, McLaren, Karma and Triumph. None of them have acknowledged the vulnerability.
- On the 6th of April 2018, we performed a live demonstration of our PoC attack on one of Tesla’s engineering vehicles.
- On September 10th 2018, we presented our findings during the CHES 2018 rump session in Amsterdam.
- The full research paper is currently under submission and will be released in the future.
References Aurélien Francillon, Boris Danev and Srdjan Capkun. Relay Attacks on Passive Keyless Entry and Start Systems in Modern Cars. In Proceedings of the Network and Distributed System Security Symposium, NDSS 2011, San Diego, California, USA, 6th February – 9th February 2011.  Yingtao Zeng, Qing Yang and Jun Li. Chasing Cars: Keyless Entry System Attacks. https://www.youtube.com/watch?v=rhm1TiFJc7s  Steve Bono, Matthew Green, Adam Stubblefield, Ari Juels, Aviel D. Rubin and Michael Szydlo
In Proceedings of the USENIX Security Symposium (2005), vol. 31, pp. 1–16.  https://web.archive.org/web/20170829141408/tesla.com/about/security
Q. The video shows that Phase X takes Y seconds, what does this mean exactly? A. In the case of Phase 0 we need to receive the identifier broadcasted by the target vehicle. Since receiving these radio frequency signals isn’t always reliable, we keep listening for identifiers as long as we haven’t received the same one thrice. The time shown in the video is the elapsed time between receiving the first identifier message and the last one.
Similarly, for Phase 1 we transmit challenges to the key fob which replies with a response. To make sure we received the correct response, we transmit the same challenge until we receive a response at least twice. The time shown is again the elapsed time between receiving a first response and the last one.