> a car model only has a handful of key patterns for millions of cars
This reminds me of growing up in Eastern Europe. Story time: Under the Romanian communist regime, there was only one car factory (Dacia[1]) making cars for personal use. Their main model was essentially the same from the '70s until 2004. For the first 10 years or so after the '89 revolution, Dacia dominated the local car market (because their cars were cheap and really easy to fix).
Now that we have the oh-so-important context, your comment reminded me that when I was a kid, my parents bought a Dacia. What confused me at a time was that random people would periodically ask to borrow the key.
It turns out that for 30-something years, Dacia only used a few models of keys. In fact there were so few that if you locked your keys inside (doors were unlocked by key and they locked automatically) it was feasible to try keys from random cars until one worked.
To be fair, the engine key was different from the door key, and it didn't have this problem. But, getting back to your comment, if you're talking about a recent card model then that's just crazy.
Also, I would have thought that keyless entry systems use correctly implemented public key cryptography. Is that not the case?
Just to be perfectly clear, what you have is a synchronized incrementing number usually using some in-house block-cipher with a 2^16 period. When the car receives a PRN from the RKE, it checks the locality of its current sequence (usually about 2^8) and then if the PRN matches one of them, you are in. So if you have the 2^16 sequence, just skip over every 2^8 and see if it unlocks. That's 2^8 tries; under a second.
If you don't have that, with a few sequences you can deduce the key pretty easily; each PRN is 32 bits; providing you up to 32 bits of information.
Since the payload is an incrementing 16 bit number you have probably 3 bits of entropy on the 32 bits (8 PKE commands between your sniffing). Anyway, assume you have 29 bits from the 32. You also have to toss the 16 bit sequence on the 64 bit source key calculations since it is effectively a salt.
Therefore, you can conservatively get the magic 64-bit key in 6 transmissions assuming there are no sequence collisions of that length. And even if there are, the solution space of the collisions would be quite modest.
Since each transmission has a plaintext serial associated with it (usually a subset of the VIN ... available on the windshield and all), you are not at a loss as to which transmission is which car.
So install your sniffer in an office-building parking structure on Monday, assume codes before 1100 are locks, after 1400 are unlocks, and you are in the car of your choosing by Thursday.
Pretend you don't have this. Pretend you want to do brute force on the 32 bit key-space. There's something called guard time. The idea is that there's a backoff period before another code can be tried. That's usually about a millisecond or two; if at all.
The transmission of the payload is on the order of tens of microseconds.
So generally speaking you can presume that you can do about 1.5m keys an hour.
Now let's say you are a car thief and you go to a lot of new cars ... there's 64 of them (2^6) just to make our lives easy. You have a wonderful consequence of the birthday-problem.
A 2^32 key space with a 2^8 tolerance over 2^6 vehicles ... means (32 - 8 - 6) = 2^18 keys until you should have a match.
Now let's see, you can generate about 2^21 keys per hour ... oopsie daisy. Look what we just did ... Your mean time to unlock one of the cars passes a 50% threshold in all of 4 minutes.
And that's the naive approach, without doing any predictive plaintext attack.
Now let's assume you use both methods together. We aren't talking about much waiting time here.
So I mean yes, the rolling code means you can't just do a replay. Ok, fine ... right ... you have to do a napkin full of math and a little programming. It's not real security.
This reminds me of growing up in Eastern Europe. Story time: Under the Romanian communist regime, there was only one car factory (Dacia[1]) making cars for personal use. Their main model was essentially the same from the '70s until 2004. For the first 10 years or so after the '89 revolution, Dacia dominated the local car market (because their cars were cheap and really easy to fix).
Now that we have the oh-so-important context, your comment reminded me that when I was a kid, my parents bought a Dacia. What confused me at a time was that random people would periodically ask to borrow the key.
It turns out that for 30-something years, Dacia only used a few models of keys. In fact there were so few that if you locked your keys inside (doors were unlocked by key and they locked automatically) it was feasible to try keys from random cars until one worked.
To be fair, the engine key was different from the door key, and it didn't have this problem. But, getting back to your comment, if you're talking about a recent card model then that's just crazy.
Also, I would have thought that keyless entry systems use correctly implemented public key cryptography. Is that not the case?
[1]: http://en.wikipedia.org/wiki/Automobile_Dacia [2]: http://en.wikipedia.org/wiki/Romanian_Revolution_of_1989