So, what is the solution? Implementing a PKI over between the key and the car? This would be quite nice, wouldn't it? -Key asks car to unlock and sends public key for recognition, -Car sends challenge encrypted with key Public key -Key sends back private-key-encrypted challenge Bing, authenticated.
All you need is to include a counter in the signal that is incremented for each button press. The car remembers the last counter value it receives and ignores any before that. Obviously the counter needs to be encrypted in some way but it's not exactly difficult.
I'm kind of amazed this still happens in 2016. Or maybe it doesn't. The cars could be old.