Tesla Opens with Precomputed Key Fob Attack

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.

Via [Wired].

43 thoughts on “Tesla Opens with Precomputed Key Fob Attack

  1. What amazes me, is that a brand like Tesla uses this stone age cipher. Since then TI and others produced several generations of devices with improved and finally AES encryption. DST40 has been broken a long time ago.

  2. What the article leaves out (and what was covered in the news when this made its rounds a few days ago in the European press) is that not only Tesla is subject to this hack but also other car and motorcycle manufacturers. It was hinted that more chips than this one could show the same issue.

    What is also missing from the article is the information that Tesla had reacted to the breach in July 2018 already, I cannot remember if June or July was the month when new vehicles had a better system installed. Anyway, a software update for Tesla vehicles was release (I think) last year addressing issues like this that requires a PIN-to-drive (you have to enter a pin in order to start the vehicle, without that patch the hacked key could be used to actually steal the car, not just everything from inside it).

    There has been a lot of additional coverage on the story in the European press – just do a quick google, it is easy to find, since this has been widely discussed.

    1. According to The Register, Tesla have not only reacted to this, but have also paid out a bug bounty to the researchers.

      Tesla statement:-

      “Due to the growing number of methods that can be used to steal many kinds of cars with passive entry systems, not just Teslas, we’ve rolled out a number of security enhancements to help our customers decrease the likelihood of unauthorized use of their vehicles.

      None of these options would be possible for any traditional automaker – our ability to update software over the air to improve functionality and security is unique.

      Based on the research presented by this group, we worked with our supplier to make our key fobs more secure by introducing more robust cryptography for Model S in June 2018. A corresponding software update for all Model S vehicles allows customers with cars built prior to June to switch to the new key fobs if they wish.

      In addition, we had already been working on several other over-the-air updates to help protect our customers from thefts – last year we introduced an update that allows all customers to turn off passive entry entirely, and this year we introduced PIN to Drive, which allows customers to set a unique PIN that needs to be entered before their vehicle is driven.”

      1. And the reverse is also true, no other company has the potential to collect as much telemetry about their customers, except for maybe Google, Microsoft, Apple, Twitter, Facebook and most phone and electricity companies.

        1. it also makes it easier to attack one source (teslas update mechanism) than to continually work on individual cars. In the end it relies on the idea that tesla has better security and will be continually security focused in the future. They are putting all of their eggs into one basket and making it worth more for attackers to go after their source code and update mechanism.

          What if attackers sneak a back door into their code that opens the doors and starts the car for a specific handshake request (much like intelligence agencies have spoiled certain cypher protocols) Tesla will surly find out eventually but not until a lot of cars have been taken.

          Its a bold strategy and it makes them stand out for now but the always connected and phoning home cars is a double edged sword that can come back and bite them in the ass. especially when certain of their models hit EOL and are no longer supported, its easy to throw out updates today, but what about in 10 years when they have all sorts of new models and support becomes too costly a burden.

    1. My ride just starts with a button. It’s hidden somewhere on the vehicle, and I left the keyhole and original wiring harness disconnected but in place to confuse anyone trying to force or hotwire it. So far it’s been downtown and in shady areas plenty and no takers. Plus I never have to remember my keys or worry about losing them. And I can let a trusted friend know where it is if they need to borrow it, so I don’t need to coordinate handing off a spare.

      1. Just to add some more security, put TWO buttons in series in different (but reachable by a single person) places. A button start is hard but possible to imagine, two buttons to be pushed at the same time are definitely not.

    1. Maybe there could be a charging cable hidden in a panel somewhere to give you enough power to boot your phone and unlock your car. And to allow homeless people to charge off it, probably.

  3. I really don’t like this fashion for keyless locks on cars; it is quite easy to see how easily a car can ba stolen, even by just relaying the signal. Humans have the bad habit of parking right in front of their door, and leave the car keys by the door, which makes the signal relay technique an easy task even for the less talented thief. Although this case the method requires hardware that is a bit more complex, the locks still fail to perform their task.

    What is wrong with getting the key out the pocket and pushing a button?

    If that is not secure enough just add a two level authentication, such as key plus thumbprint, or key and phone proximity.

    Putting aside the security flaws of the keyless system, what I really detest is the fact that you can get into the car and drive away with the key in one of your pockets, but when you get to destination, you have to search for the key to be able to lock the car, which renders completely pointless the keyless system.

    Rant over

    1. Within the last 5000++ years with cars around, there have been a huge number of ways to open and start a car without the valid key.

      To me it looks like simple thermodynamic laws: it might change but at the end the sum is still the same.

    2. My ease of use vs the probability of my car being stolen through a very unlikely method is why I have a proximity key. If by some minuscule chance my car is stolen by someone hacking the encryption on my key or uses it to relay the connection, I have insurance that will replace it.

      Most proximity key systems have the ability to lock the door using either a button on the drivers exterior door handle (Mazda, Dodge, Mercedes, etc.) or simply touching a spot on the outside handle (Subaru, Toyota).

      I’ll never buy another new car that doesn’t have a proximity key system.

  4. I’d like it if my phone automatically unlocked my car if I was near it and I unlock the screen, press ok on a prompt. You could probably set this up via Bluetooth, and a relay attack wouldn’t work without pressing ok.

      1. I’ll take an additional layer of security with obscurity any day.
        …unless my team is woefully incompetent and therefore needs others to close our massive security holes.
        Then maybe open source is a better game plan.

  5. I broke into my i10 once using an optical delay line costing under £1 for the parts. Took me 29 seconds.
    Interesting hack: use the number plate to reverse engineeer the key using pen and paper :-) don’t ask how I found that out.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.