I'm confused why this is still an unsolved problem. A simple cryptographic challenge with pre-shared keys + button press ought to make key fobs perfectly secure for all practical purposes. Is there something I'm missing here?
Cars are not very secure by nature: they have easy to break glass windows, and are made of relatively lightweight materials. The key system just needs to match that level of security, and AFAIK, attacks on the keyfob are uncommon compared to other, less subtle techniques.
The more complex and sensitive "PKES" system, according to the article already has a challenge-response system, but it doesn't help with relay attacks.
the problem is they "improved" the usability
it was safe when you had to push a button, but now roles are flipped so the car is the initiator, and doing it constantly
the protocol is now subject to a whole entire extra class of attacks it was never designed to deal with
As for replay attacks, that's where the button press comes in (like on a hardware security token) -- the key only responds to challenges within a second or so of a button press and the car sets a similar timeout for validity.
Re power: Key fobs already do some form of crypto and broadcast. Adding reception capabilities ought not to be that power hungry.