Please just use standard cryptography -- Jacek's Blog

TL;DR;

Tesla (and couple of other "luxury" car vendors) use "keyless fobs" to open the car, these fobs use proprietary, (formerly) trade secret algorithm which has laughable key (40bits) and response (24 bits) sizes.

This algorithm was broken by researchers and key can be recovered after listening to two challenge response exchanges.

Just use standard cryptography primitives people!.

Background

Reason for short key sizes and non-standard algorithm was supposedly, power constraints. They used proprietary DST40 which is designed to work in RIFD tags --- that is extremely low power (or possibly fob has no battery at all and is powered by car using radio waves).

Attack

Attack was quite simple (kudos to Ku Leuven team!). Since DST40 has 24 bit response size, and key size small enough for brute force search they created a database that stored every key that could generate this response.

Attack was as follows:

Car transmits a challenge, and response from the fob is intercepted.
All keys that could produce this response are downloaded (megabyte-sized package)
Second challenge response pair is intercepted
Raspberry pi locally tries all the keys to find key stored on fob.

And now you just need to copy the key on your fob.

Why low power argument is stupid

I found this article from 2004 (free to download pdf).

Here is an excerpt:

This paper presented a security-enhanced RFID system which allows the strong cryptographic authentication. With this security-enhanced RFID systems, we pave the way for new security-demanding applications and for the everyday usage of RFID technology. A symmetric challenge-response authentication protocol was proposed which was integrated into the existing ISO/IEC 18000 standard.

We showed an architecture for a low-power and low die-size implementation of the AES algorithm. The AES implementation has a chip area of 3,595 gates and has a current consumption of 8.15μA at a frequency of 100 kHz. The encryption of 128 bits requires about 1000 clock cycles.

So there was a documented possibility to deploy AES on extremely low powered and extremely small circuits. Also it looks like Texas Instruments (manufacturer of DST40 chips right now sells AES-enabled microcontrollers dedicated for car fobs).

Can Tesla be stolen?

There is this argument: "Well, Teslas are camera-surrounded, gps enabled, Internet connected surveillance devices", good luck stealing that! While most of these points are true, well here is good reasoning why this argument is irrevelant.

Cars are stolen (mostly) for parts

As far as I know (obviously my contact with car thieves is limited) cars are mostly stolen not to be sold, but to be dismantled for parts, and then parts are sold.

Here is (polish) news about a police raid on stolen parts warehouse, some things of note:

Police hauled "8 trucks" of these stolen parts
There were also some luxury cars there.

Getting into a car is a lot

Would luxury car owner say "yes" to: "Do you want anyone (with relatively cheap equipment) be able to enter your car, even if it required you to charge your car fob every couple of months?".

As far as I know getting car open is a lot, you can browse glove compartment, you have much easier access to internal bus, etc.

I understand that there is no such thing as "perfect security", that is: adversary with unlimited funds will always slice through your security, however in case of securing e.g. car, you just need to make whole enterprise not worthwile. And disallowing thief from trivially entering the car is good first step.

How to design safe protocol for fob

What really baffles me is: why they did not use known cryptographic primitives, once you know them they are so easy to use.

In case of key less entry you need protocol that looks like that:

Car and fob both store pre-shared secret key (in case of many fob's car can just store a all the keys of registered fobs, or car can have a secret key which is written to fob memory by authorized mechanic.
Car transmits an unique challenge;
Fob signs this challenge with pre shared key and transmits the response;
Car verifies response signature is valid;

As long as car won't repeat challenges this system is secure against replay attack (that is --- attacker stores response and retransmits it in the future). One way of making challenges unique is just to use a counter, another is using long pseudo-random values.

Primitive for signing is named MAC (Message Authentication Code), mostly there are two kinds of mac:

HMAC this is MAC that uses cryptographic hash function (e.g. SHA-1)
CMAC this is a MAC that uses a block cipher (e.g. AES).

Implementing these is not hard, as basic primitives (AES and SHA) are either implemented in a library (in case of desktop computers) or are part of microprocessor architecture (many microprocessors have cryptography primitives built in!).

Things you should note

If you use cryptography in your programs: use standard vetted primitives, used in standard ways for intended purposes. Otherwise you risk that your whole work amounts to security by obscurity.

Security and usability are conflicting things, not having a password is simpler than typing one, having login and password equal to rms is easier than typing four-word paraphrase on every login. "Hassle-free" security is an oxymoron, every time you hear about it there is some trade-off hidden well.