Why not just make the keys responsible for starting the car again?
We've traded too much security for convenience and it's time to take a step back.
You can still start the car with the push of a button.. only now that button is on the key.
Problem solved.
Yes, the problem becomes substantially easier if you require a direct physical connection, but that's not such an interesting problem.
Also, given that modern cars are vastly more difficult to steal, I object to your characterization of "traded too much security for convenience." If the current state is too insecure, then you must think that cars from 20+ years ago are absolutely appalling.
Although from what I was seeing in the rest of the thread it seemed that preventing relaying may be more difficult than expected (as most methods relied on timing the signal response). I don't expect it to be impossible though.
The trouble is that the wires must be fairly exposed to the occupants of the car, since the switch has to be accessible. That means you can just bypass the switch entirely by removing the appropriate covers and attacking the wires directly. This is "hotwiring."
Physical locks are also not all that difficult to defeat directly. You can pick an ignition switch much like you might pick any other lock.
Starting around the late 90s or so, car manufacturers started adding more robust security measures. These include things simple like locking the steering column when the ignition switch is off (thus preventing you from driving the car after hotwiring it), all the way up to authenticating the key with a relatively sophisticated protocol, and having the engine computer refuse to run the car unless it can sense a real key.
As a result of these changes, the list of most stolen car models is still topped by cars manufactured in the late 90s. Low-end Hondas from around 1998 are right at the top of the list, because they occupy a sweet spot of being relatively valuable and still fairly easy to steal. Modern cars are stolen literally orders of magnitude less frequently; about 100,000 older Hondas stolen per year in the US, whereas new cars are stolen at a rate of hundreds per model per year at worst. Also as a natural result of these changes, car theft is way down in the US. About 700,000 cars were stolen in the US in 2013, compared to almost 1.7 million in 1991. Pretty much the only way to steal a newer car is to either tow it away or steal the owner's keys. (A common scenario for car thefts is a burglary turned into auto theft when the burglars find car keys in the house.)
It's easy to get into many older cars. Slim jim past the window is the classic example (and I opened my 80s Toyota with a coathanger multiple times when I locked myself out), but many times the locks could be opened by keys to other cards from the same manufacturer as well, they just didn't seem to be that precise. And of course, smash the window as a last resort, that wouldn't set off an alarm in the past. Nowdays cars have recessed lock things in the door panels (or button-controlled-locks that can't be as easily manipulated with a coathanger, or even that don't work at all if the car was locked from outside) to help prevent this, and the interior of the doors has more protection built around the lock mechanism so you can't easily fish through there and hook onto the right lever.
Once inside an old car, starting it is usually just a matter of shorting the right pair of wires. Or using brute strength to turn the ignition cylinder even if they key isn't an exact match (or maybe with a screwdriver, as another poster mentioned doing in the past in this thread). Modern cars have chips in the keys so that it's not just a matter of closing a circuit, the key has to be coded to the car.
Or just tow the car somewhere and work on picking the lock later at your leisure. Overkill for a common car, but for something really nice it could be practical. Nowdays your more expensive cars have tilt and motion sensors that'll set off the alarm if you locked it, left it, and someone else comes up and tries to tow it. Possibly GPS tracking or similar as well, IIRC, on some fancy stuff.
The fob-in-pocket entry/pushbutton start stuff gives up some of those improvements given an exploit like this, but overall I'd say is still much more secure. You need specialized hardware (that's only useful for breaking into someone else's car) and it wouldn't work to, say, steal cars from an airport parking lot or somewhere else where they were left and the owner wasn't in range. Keeping your car in a garage at home seems to mitigate a lot of the easiest vectors for this attack.
Your opinion is an unpopular one, albeit one I share.
There are far too many cases where security is getting removed in the name of convenience, and this is no exception.
Further, a Tesla has a GPS, sophisticated processor, and a 4G WAN. It would be easy enough to have the car report back to the owner if it's being driven without sensing the key, and give the owner the option to route a theft report and live location of the vehicle to police with one click. That's something I wished for in my revenge fantasies when my car was stolen a decade ago.
We could do more, sure -- but it's hard to argue that we are making cars less secure, or even that car security should be a major care-about for the buyer.
The Tesla app does show the car location on a map; they don't have a "report to police" option, but they aren't that far away from it.
BTW the Tesla modem is 3G.
https://news.ycombinator.com/item?id=9383462
https://en.wikipedia.org/wiki/Distance-bounding_protocol
(I don't pretend to have a clue whether it can be effective or not)
1. Use a modified form of triangulation. Have multiple transceivers in the car (At the front and back) and make the remote directional aware. Then have the remote and transceivers ask each other if the angles they are seeing are the same. The only way for the thieve to bypass this would be two remote amps set at almost 180 from each other.
2. stick an ultrasonic speaker in the key fob and have the car send it a random sequence to play back. For those worried about battery life use a wireless charging system.
Both of these assume that the transmission is encrypted and the thieves are just boosting the signal.
the attacker has two devices communicating by radio. Device A is near the keyfob, and device B is near the car. Each is a repeater for the other: Whatever the car sends is picked up by device B and repeated by device A. Then the keyfob's response is picked up by device A and repeated by device B.
This type of setup will defeat both of your proposals. Triangulation won't detect anything out of the ordinary, because device B can be right next to the car. And the ultrasonic challenge/response can be defeated just like a radio challenge/response, using microphones and speakers on the repeaters.
I don't see how ultrasound helps matters at all. You just change the nature of what the attacker has to relay.
Rather than put an ultrasonic speaker in the fob, I'd put a microphone. The car would send an ultrasonic signal, and the fob would send a radio response indicating it heard it. The car could then calculate how far away the fob is.
The speed of sound in air is about 1ms/foot, so if you're trying to measure proximity within 30ft, you're looking for a 60ms roundtrip delay, or 30ms for one-way. If the attacker has ultrasonic microphones and speakers connected with radio waves, that means he can spoof your fob from up to 9,000km away for roundtrip ultrasound, and 4,500km away for one-way, under ideal conditions.
The speed of light imposes difficult constraints in terms of how fast you have to respond, but at least the attacker can't outrun it (as far as anyone knows).
If the car then did an ultrasonic distance check by emitting a coded ultrasonic signal that the fob had to receive, and then relay the code back to open the door, I don't see how the attacker would spoof that. Even if he has an ultrasonic microphone near the car, and an ultrasonic transmitter somewhere else, with a radio link to tell the transmitter what the send...how does he place the transmitter so that your fob will hear it?
If the attack is targeted against a specific individual, where the attacker knows both where the car is parked and where the individual is when away from the car, and the attacker can place equipment at both locations, then yes, I see that the attacker can get around ultrasonic distance measurement.
But for the most common case, where the attacker is at the car and has no idea where the owner is, it seems workable to me.
So, in theory, if you wanted to steal a REALLY expensive keyless car you could have two devices connected over a mobile data connection that just relays communication with the keyfob. You put one device near the owner of the fob, so in his office, and you keep the other. Then you can just walk off with the car.
Yikes.
Although sometimes you can even skip the second device and just have the one near the keyfob.
The timer idea is a good one, although a ns-accurate timer is starting to get a bit much for something to put into a key fob. Especially give it's run off of a watch battery (power requirements) and often exposed to heat / cold (thermal drift).
Dylan's comment requires a timer in both the key fob and in the car. The key fob to delay transmission of the challenge response, the car to check if there isn't too much delay in the challenge / response pair.
You really need a timer in the key fob, as the processor in the key fob is often so slow (for battery / cost reasons) that an extra couple clock cycles somewhere would throw off the timing enough to make it fail.
Cool trick in that one, the Prover(i.e. the key fob) does the distance measuring part of the challenge response protocol using analog only components. This means its response time is <1 nano second.
So you can do it with only the car having a good timer.
https://en.wikipedia.org/wiki/Quantum_key_distribution
Edit: Nope, I am wrong, as the comments below point out.
1. You place device A near car and device B near fob. 2. Device A relays all Rf transmissions in the target frequency range(s) to device B, which rebroadcasts, and vice versa.
Public-key encryption / authentication only ensures that no-one in the middle is reading or editing your connection. It does not prevent someone from relaying your communication. (And a good thing too, else the entire encrypted web wouldn't work.)
When the driver presses lock/unlock on the fob, the car first sends a signed message with a session secret. The fob checks the signature, takes the secret and creates a _single use_ auth token and signs it with the private key stored on the fob. That signed auth token is then sent from the fob to the car to lock/unlock the car.
To check if there was a MITM you would have to pull the door handle to see if your keypress was successful. If it was successful, you don't need to worry if the key was grabbed by a MITM, they can't use it even if they tried. If it was unsuccessful for some reason (e.g. the MITM knew it was single use auth token so they didn't pass the token onto the car in hopes you might not be paying attention and will press the button a second time) then there should be a manual override outside and inside the car that clears the valid auth tokens and allows you to lock/unlock/start the vehicle without sending any RF transmissions. A slot that you insert the key would work.
The entire discussion here is based around not requiring interaction with the key fob.
In that case device B picks up on the unlock command and relays is back to device A which rebroadcasts the unlock command to the car.
No matter what tricky message protocol you come up with, it won't matter. The car and the fob can't detect the difference between being next to each other, and being next to a set of relays rebroadcasting their signals. Not by reading and transmitting radio signals at least.
The one thing that I could see working in theory would be detecting the roundtrip transmission time with a strict ceiling on it. No matter how good your relay is, it can't relay data faster than the speed of light, so you can enforce the fob being close by only listening to it if it responds fast enough.
The problem with this is that light moves pretty fast, and internal delays within the fob will dominate. If you want to put the range limit at, say, 30ft, that means your response time ceiling is a mere 60ns. Can you build a fob that responds anywhere close to that fast?
Edit: one other possibility is if the fob knows where it is. A GPS receiver on the fob, for example, would allow the fob and the car to securely confirm proximity (absent GPS spoofing). Getting a GPS receiver to run on a wireless fob's battery is left as an exercise for the reader.