Drive away a Tesla today (even if it isn’t yours)

Fancy driving a Tesla, but can’t convince your local dealer to let you have a go?
If it’s a Model S you’re after, and you don’t mind going to prison for a while if you get caught, you might now be able to fulfil your dream.
Cybersecurity researchers at the Catholic University of Leuven in Belgium just published a report describing how easy it is to clone Tesla Model S car keys.
Tesla’s use of underpowered, way-past-its-sell-by-date keyfob cryptography was to blame.
If you’ve got the popular and convenient “passive entry” setting turned on – where just bringing the key close enough to the car will unlock it – then breaking into your Tesla car, and very likely driving off in it, may be cryptographically trivial for a car thief.

The flaw described here was responsibly reported to Tesla in mid-2017 and a bug bounty paid out. From June 2018, all Tesla cars have apparently shipped with more secure keyfobs. Also, a recent firmware upgrade for Tesla vehicles allows you to set a start-and-drive-off PIN so that the keyfob alone, whether cloned or stolen, isn’t enough for a crook to make off with your vehicle. And although the researchers explain the cryptographic issues in a way that will help you avoid similar blunders in future, they aren’t handing out any hack-a-Tesla source code for crooks to abuse.

• A one-off blast of number-crunching power. (Rented cloud computing time will do fine.)
• About 5500GB of disk space. (Rented cloud storage will do fine.)
• A suitable NFC/RFID hardware device. (Commodity item.)
• A small, portable computer such as a laptop or a Raspberry Pi. (Commodity item.)
• A missing conscience.

The cryptographic problem

Until recently, Tesla Model S keyfobs were based on an early-2000s product known as DST (short for Digital Signature Transponder) based on 1990s-era cryptography.
In fact, the DST hardware was analysed by Johns Hopkins University researchers back in 2005; they found it cryptographically inadequate even then, and warned that:

The weakness we have demonstrated in [this] system is ultimately due to the inadequate key length of the underlying DST40 cipher […] The authors hope that future cryptographic RFID system designers will embrace a critical lesson preached by the scientific community: cryptographic hardware systems are generally strongest when they employ industry standard cryptographic algorithms with key lengths sufficient to endure over the life of the devices and assets they protect.

Briefly put: don’t knit your own crypto, and attacks only ever get faster.
You’ve probably inferred from the name DST40 in the quote above that Tesla was using an encryption algorithm with a 40-bit key, and you’re probably aware that 40-bit keys are just half the length of the “absolute legacy minimum” of 80 bits.
(Any symmetric-key cryptographic algorithm still in use from before 2016 really ought to be using 112-bit keys or longer by now; any implementation first fielded in 2016 or later, or expected still to be in use after 2030, ought to have at least 128-bit keys.)
Remember, also, that although 40-bit keys are half the length of 80-bit keys, they are much, much, much less than half as safe against brute force attacks, where you simply try every key until you hit the jackpot.
That’s because you halve the number of different key choices every time you subtract just a single bit from the key – so shortening a key by two bits makes it a quarter as safe, by four bits makes it one sixteenth as safe…
…and, all other things being equal, shortening a key by 40 bits makes it one million million times less secure against brute force attacks. (2⁴⁰ is approximately 10¹², or 1,000,000,000,000.)

How the attack works

The Belgian researchers have a short and punchy explanation of their attack, with a fun and informative 2-minute video.
Read the explanation through before you watch the video – it’s much cooler that way round!
Simply put, here’s why 40-bit crypto simply isn’t enough.
The so-called passive entry feature, where your Tesla automatically opens up for you as you get to it, relies on the car regularly transmitting 40-bit RFID “challenges”, which are just randomly-chosen bit strings sent out to probe for nearby keyfobs.
Your keyfob, if it’s in range, encrypts the challenge into a 24-bit hash value, using the abovementioned DST40 algorithm with a pre-shared 40-bit key, and sends the resulting hash as a response.
The car, which is paired with your fob and therefore has its own copy of the pre-shared key, does the same calculation and verifies the fob’s response.
The theory is that:

• A 24-bit hash is long enough – you only have a 1/2²⁴ chance of getting lucky by blindly guessing the response. (That’s a 1 in 16 million chance – worse than the UK lottery, at 1 in 14 million – and you have to do it twice before you can drive off.)
• A 40-bit pre-shared key is long enough – keeping tables of every possible challenge hashed with every possible key is as good as impossible.
• Guessing at responses is seriously rate-limited – the car only transmits a new challenge string every second or so.

In practice, however, you don’t need a full lookup table of every challenge hashed with every key, and you don’t need to try millions of responses in order to hit the jackpot, either.
You can make what’s called a time/memory tradeoff (TMTO), where you store a table of containing some, but not all, pre-calculated hashes; you then use this partial table as a shortcut to figuring out the key.
The Belgians picked a random challenge value of their own (0x636f736963 is the number to look out for in the video) and pre-calculated the 24-bit hash of that challenge for every possible 40-bit key.
That’s a lot of computation, and a lot of storage, to be sure – but nowhere near an impossible task, at least by 2018 standards.
If we assume that every possible 24-bit hash turns up randomly, and there are 2⁴⁰ different hashes computed (one for each possible 40-bit key), it follows that each hash should show up in the list about 2⁴⁰/2²⁴ times. (2⁴⁰/2²⁴ = 2¹⁶ = 64K = 65536.)
So, the researchers ordered their TMTO list so that it started with all the roughly 65,000 different encryption keys that produced a hash of 0x000000; then they listed the keys that hashed to 0x000001; and then 0x000002; and so on for all 2²⁴ different possible hashes.
Each 40-bit key appears once in the list of 2⁴⁰ different keys for a total of 40×2⁴⁰ bits of storage space – that’s 5,497,558,138,880 bytes at 8 bits per byte, which is where the “about 5500GB” comes from above.
In other words, after paying the one-time cost of preparing the TMTO table, the researchers can now quickly read off the 65,000 possible keys capable of producing any specific hash value for their magic challenge value of 0x636f736963.
.
There’s no longer any need to try 2⁴⁰ different keys to see which one produces a given hash – the TMTO table swiftly chops the brute force search to a mere 2¹⁶ candidate keys.

Tricking the fob

The researchers now need to get close enough to your keyfob to trick it into performing two challenge-response sequences.
Firstly, they ask your fob to reply to a “challenge” of their magic number 0x636f736963 – the value used when building the TMTO table – and capture the 24-bit hash that comes back.
They look up that 24-bit hash in their 5500GB table, which quickly gives them an exhaustive list of 2¹⁶ candidate keys that could have produced that hash.
Then they generate a second, random “challenge”, and pre-calculate the hash that would come back from each of the candidate keys.
Using a battery-powered Raspberry Pi 3+, like the researchers did, calculating the list of possible hashes for all 2⁴⁰ keys would take about two years.
But calculating a list of just 2¹⁶ different hashes is 2²⁴ (16 million) times faster and therefore takes just a few seconds.
Now the attackers know, for the second challenge, what response matches up with which key.
You can see how the attack pans out:

• The first challenge/response, using the TMTO challenge value 0x636f736963, quickly narrows the keyspace down to 65,000 possibilities.
• The second challenge/response, using a randomly chosen challenge, lets the attackers check for the correct key from those 65,000 possibilities.

In the video, the simulated fob attack (watch at about 1’00”) collects the two challenge/response pairs first. Then the Raspberry Pi downloads, via Wi-Fi, the list of candidate keys indexed by the first challenge/response hash that came back (0x0a72c9 in reply to 0x636f736963). Then the Pi does the 2¹⁶ different encryptions to figure out which candidate key matches the second challenge/response pair (0x1858a1 in reply to 0x7465736c61). Downloading the candidate keys via Wi-Fi means the Pi doesn’t have to be plugged into a 6TB USB drive, making the attack much more portable. In the video, downloading the 65,000 candidate keys actually took longer than trying them out – 2.72 seconds compared to just under 1.85 seconds.

Once you’ve worked backwards to the pre-shared key, your rogue Raspberry Pi can now take the place of the real owner’s keyfob to unlock the car and drive off in it.

What to do?

There are several things you can do if you’re a Tesla owner, or a Tesla designer:

• Upgrade to a new, more secure fob. According to Wired, this is an option, but it sounds at the moment as though you’ll have to pay for it yourself.
• Keep your Tesla key in one of those shielding wallets that limits the propagation of NFC/RFID transmissions. We tried some of these products out and they do seem to work as claimed.
• Consider turning off passive keyless entry and turning on the “PIN to drive” feature available in recent Tesla firmware. Be aware, however, that this makes your car harder to start in an emergency.
• Don’t knit your own crypto.
• Remember that attacks only ever get faster, so never skimp on strength.

HERE’S ONE WE PREPARED EARLIER

TIME/MEMORY TRADE OFF - A SIMPLIFIED EXAMPLE
Assume a hash function H that takes a 4-bit pre-shared key K plus a
4-bit challenge C, and returns a 2-bit response R:
H(K,C) = R
A table of every R for every (K,C) combination would let you look
up the key K directly from a single challenge/response. But you'd
need a table with 16x16 = 256 entries.
Here's a time/memory tradeoff (TMTO).
Pick a random value for C and compute every R for every K.
You end up with a table of just 16 entries, say like this:
 K    C     R
---- ----   --
0000,1011 → 00
0001,1011 → 00
0010,1011 → 10
0011,1011 → 11
0100,1011 → 10
0101,1011 → 01
0110,1011 → 10
0111,1011 → 01
1000,1011 → 00
1001,1011 → 11
1010,1011 → 10
1011,1011 → 00
1100,1011 → 01
1101,1011 → 01
1110,1011 → 11
1111,1011 → 11
Sort the table on the last column (R) and you get an alternative way
of using the data:
if H(K,1011) = 00 then K ∈ {0000,0001,1000,1011}
if H(K,1011) = 01 then K ∈ {0101,0111,1100,1101}
if H(K,1011) = 10 then K ∈ {0010,0100,0110,1010}
if H(K,1011) = 11 then K ∈ {0011,1001,1110,1111}
Send the keyfob your "magic" C value of 1011, causing it to compute
H(K,1011) for you and respond with the answer, say:
H(K,1011) = 10
From the table above, if H=10 then K must be one of 0010, 0100,
0110 or 1010, so you've cut the keysearch list from 16 entries to 4.
Now pick a second value for C, say 0001, and send it to the keyfob.
Say the fob comes back with:
H(K,0001) = 11
Try the four candidate keys yourself for C=0001, say like this:
H(0010,0001) = 00
H(0100,0001) = 11
H(0110,0001) = 10
H(1010,0001) = 01
You're done - the only value of K that fits both responses is 0100,
so you have cracked the pre-shared key!
The tradeoffs are as follows:
* To solve the problem with no cryptographic calculations at attack
time, you need a single eavesdropped challenge/response pair plus
a precomputed mapping of H → R for all 256 combinations of K and C.
* To solve the problem with no precomputed mapping table, you need
a single eavesdropped challenge/response pair followed by a runtime
calculation of H → R for all 16 possible values of K.
* The TMTO uses a 16-entry precomputed table, two eavesdropped
challenge/response pairs and a runtime calculation of H → R for only
4 possible values of K. Your attack computer needs one quarter
of the power that would be needed in the "no mapping table" case,
and your precomputation computer needs one sixteenth of the time and
storage that would be needed in the "no attack time calculation" case.
Generally speaking, the more work you do up front in a TMTO,  the
less work you need to do every time you mount the attack; and vice
versa.