The implied context here was "while keeping wireless keyfobs."
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.
I think he was not saying a physical connection was necessary, only that a physical button on the key fob was necessary to start the car. Still wireless, it just requires interaction from the driver who must physically have the key fob.
Oh yes, that would obviously work, but of course you're changing the nature of the device. There are some easy ways to prevent relaying if you're open to that. It's more interesting to me to think about how you might solve the problem without changing anything from the user's perspective.
Ah yeah, I'd like that more as well because I really like driving without ever taking the keys out of my pocket :P I was mostly clarifying for the person you responded to.
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.
Really old cars have very simple electronics. Even after computers started showing up in cars, they were pretty simple and didn't interact much with the security aspect of things. When you start a car like this, you're just making a connection between two wires to power up the electronics, and briefly making a connection between another two wires to run the starter motor. The only security in the whole system is provided by the fact that the connection is made by a switch that requires a key to turn it. If you don't have the right key, you can't turn the switch, and that means you can't connect the wires.
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.
To add to the comments about immobilisers, in a number of countries (UK and Germany, amongst others), from 1998 all new cars were required to have an engine immobiliser. Most manufacturers simply made them standard for all countries, so nearly all cars built since 1998 have had them fitted.
It's important to look at this in the context of overall auto theft trends. Auto theft has dropped by more than 50% over the past decade, driven mostly by the broad use of smart keys. (http://www.iii.org/issue-update/auto-theft). The lion's share of the thefts are of older cars (mentioned in the above cite) -- thefts of 2013 vehicles number in the hundreds.
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.
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.