This clever precomputation attack was developed by a group of researchers at KU Leuven in Belgium. Unlike previous key fob attacks that we’ve covered in the past which have been essentially relay attacks, this hack precomputes a ton of data, looks for a collision in the dataset, and opens the door. Here’s how it works.
Tesla opted not to design their own key fob system, but licensed a product based on Texas Instruments’ DST40 Cipher. A vehicle using this system broadcasts a radio message containing the car’s unique identifier. If the key fob is in range, it will respond to that broadcast, initiating the cryptographic handshake. The vehicle sends a 40-bit challenge message, and the key fob replies with a 24-bit response.
DST40 is the cryptographic cipher that powers this handshake. The key fob has a 40-bit secret key burnt into it’s circuit. DST40 takes the 40-bit challenge, combines it with the 40-bit key, and produces the 24 bit response. The weakness here is that the 24 bit response message just isn’t long enough. For each challenge message, multiple keys will produce the same response.
The researches realized that they could pick a single challenge value and record which keys produce what responses. The resulting data structure was 5.4 TB. Organized by the response message, this massive database of keys and responses could be searched very quickly. With this in hand, a single response message narrows a 40-bit key down to just 2^16 possible keys.
Within this reduced keyspace, they can brute force the answer. The authors state that once the key space is narrowed, a Raspberry Pi 3b+ can calculate the key fob’s secret key in two seconds. Ouch!
They published a proof of concept attack on a real car, which is worth the watch. Trying to open the car’s door triggers a handshake attempt, which gives up the car’s unique ID. With this ID, they then get close enough to the key fob to perform two handshake attempts, the first with the pre-computed challenge, and the second with a random challenge. This requires less than two seconds of proximity to the target key fob. About 4.5 seconds of computation later, the attacker has a cloned key fob, and is able to drive the vehicle away.