Every keyless/wireless car key already uses a challenge-response scheme, just like you described, to prevent replay attacks. However, that will not work against relay attacks. Cryptography does not prevent relaying.
Fun fact: Even most physical car keys produced >1990 have a small RFID based transponder in the key head (the plastic part that you hold). This transponder responds to a challenge transmitted by the ignition barrel. Without a correct response, the ECU will refuse to start the engine. This is mainly done to prevent 'Hollywood' style theft where you connect 2 wires from the ignition barrel together to start a car.
They used a relay attack which means that they tunneled the actual keyfob signal over the internet (or a direct connection).
Tesla and others try to mitigate that by making sure that the latency of the signal is not too high.
<Everything you described> Car: your encrypted authentication looks right but you took 200ms to send it. You are probably not within BLE range.
The researchers contribution was to show that despite that a relay attack is still possible.
I believe they have an option where you need a pin to start the engine at least however I'm not an owner
What a world!
The attack is defeated by keeping your fob in something that blocks radio frequencies I guess. Same idea as those metal wallets but this time for an actual threat.
Identity verification and public/private keys are a solved problem, how is it at all impossible to prevent relay attacks?
Key: I want to unlock the door.
Car: Here's a random number encrypted with my key, which only the real fob should have the pair key to.
Fob: Here's the number encrypted with another key, which only the car should have the pair key for.
Car: This matches, opening the door.
Blindly repeating these bits won't work and it should be impossible to eavesdrop without an NSA cluster of supercomputers. What am I missing?