As long as you have two-way wireless communication (which any keyless entry/start system does), then you can simply do a Diffie-Hellman key exchange during the pairing process.
Diffie-Hellman is designed for exactly this usecase, allowing two parties to derive a shared secret key over a public channel without exposing it.
Part of the utility of the baked-in manufacturer key is that it is unable to be extracted by thieves.
Having to break into the vehicle already raises the bar significantly and makes the security equivalent to a physical lock.
If someone does successfully MITM while walking by the key is going to stop working as soon as they are out of range, and you will notice.
I'm just wanting a system that could be implemented with the hardware that's already there. I guess you could use the RFID chip that most keyless start cars already have as a secondary channel. Still Not 100% secure, but the MITM device would need to be physically in your car to intercept the pairing request, and at that point you have bigger problems.
While I worry that it's not really secure enough, the OP was suggesting that physical contact is a way to "prove" that you are indeed eligible to pair, by excluding everyone who lacks physical contact.
You're assuming the goal is to discretely enter the vehicle and leave no trace. If we consider the Kia challenge [https://en.wikipedia.org/wiki/Kia_Challenge] then the goal is to take possession of the vehicle in an immediate and opportunistic fashion. If the possession fails and the key FOB now stops working, whatever, not the thiefs care. If the possession works, now there's a sweet car to abuse. Or, in the case of a crime syndicate, a sweet car to take to the chop shop.
This type of attack is not to mention a simple relay attack. If radio waves of a home (say near the front door, where the keys are stored) are relayed to another location (the car, 30 feet away), then the exact crypto and protocol is irrelevant, the car "sees" the real life actual FOB as nearby. That's another attack used in the wild.
So it just needs to block rewrites, and the risk of any security barrier breach is negligible since it's done in factory.
Or if I lose my car key
A one-time out of band authentication (usually some form of trusted physical interaction) is key if you don’t want to trust intermediaries.
It'd instantly mean there is 0% chance of someone figuring the key based on day-to-day operation.
