KeeLoq Still Broken

That’s the key entry system used by Chrysler, Daewoo, Fiat, General Motors, Honda, Toyota, Lexus, Volvo, Volkswagen, Jaguar, and probably others. It’s broken:

The KeeLoq encryption algorithm is widely used for security relevant applications, e.g., in the form of passive Radio Frequency Identification (RFID) transponders for car immobilizers and in various access control and Remote Keyless Entry (RKE) systems, e.g., for opening car doors and garage doors.

We present the first successful DPA (Differential Power Analysis) attacks on numerous commercially available products employing KeeLoq. These so-called side-channel attacks are based on measuring and evaluating the power consumption of a KeeLoq device during its operation. Using our techniques, an attacker can reveal not only the secret key of remote controls in less than one hour, but also the manufacturer key of the corresponding receivers in less than one day. Knowing the manufacturer key allows for creating an arbitrary number of valid new keys and generating new remote controls.

We further propose a new eavesdropping attack for which monitoring of two ciphertexts, sent from a remote control employing KeeLoq code hopping (car key, garage door opener, etc.), is sufficient to recover the device key of the remote control. Hence, using the methods described by us, an attacker can clone a remote control from a distance and gain access to a target that is protected by the claimed to be “highly secure” KeeLoq algorithm.

We consider our attacks to be of serious practical interest, as commercial KeeLoq access control systems can be overcome with modest effort.

I’ve written about this before, but the above link has much better data.

EDITED TO ADD (4/4): A good article.

Tags: academic papers, cars, cryptanalysis, cryptography, encryption, keys, locks, physical security, RFID

Posted on April 4, 2008 at 6:03 AM • 24 Comments

Comments

Jeroen • April 4, 2008 6:42 AM

Nice, a single attack to open both the garage and the car.

Is this also usable to start a car? Renault has a system where the car starts by pressing a button as soon as the owner-token is inside the car. Very handy, but potentially vulnerable to similar attacks.

Sparky • April 4, 2008 8:56 AM

Especially worrisome is that such systems tend to used for relatively expensive cars, which are, I presume, more lucrative to steal than cars in the lower en medium price ranges.

Would it be possible to attack a key that is inside the house of the owner, using a man-in-the-middle attack using better transceivers and/or high gain directional antennas?

I would think this would be possible, as the physical layer seems to be the standard passive RFID interface, which basically means the system is less secure than a plain old metal key, for which a thief would at least have to break in to the house and find or threaten the owner for.

derf • April 4, 2008 9:10 AM

These systems are used to not only open the door locks on the car, but to disable the alarms. At that point, if they want to steal the car, they still have to hotwire the car without tripping the lockout mechanism. However, this would make it trivial to steal your iPod, umbrella, and radar detector.

TS • April 4, 2008 9:21 AM

@Sparky

High end cars will fetch high prices, but it’s a “big time” operation, you need to ship those cars out of the country.

It’s the popular mid range cars that are stolen the most. Because there are so many of them on the road, there’s a huge market for parts, thus they get stolen more often. It’s more lucrative to smaller organizations and petty thieves because it’s easier to fence the stolen goods.

Jeremy Duffy • April 4, 2008 9:40 AM

Well duh. These companies are so eager to adopt the “convenience of wireless” that they don’t bother to consider the negative security multiplier of adding wireless to a system.

Maybe if enough of these stories come out we’ll finally see some preemptive legislation against over use of RFID.

Peter Pearson • April 4, 2008 9:44 AM

Does this mean the manufacturers will no longer be able to charge $400 for an additional copy of the key? Maybe then they’ll care about security.

ICH • April 4, 2008 10:15 AM

The RKE may be broken, but so what?
RKE systems are replacing old fashioned physical keys. They may still be a step up even if they are flawed.

Michael Chermside • April 4, 2008 10:33 AM

I think Peter Pearson has it right. One of the significant factors ought to be the creation of a secondary market in keys and remote controls. Unfortunately, some clever lawyer will figure out a way to apply the DMCA so it’s illegal to do so. (My proposal? If anyone offers such a service sue them for ten billion dollars under the DMCA. You suit may not have any merit, but the group selling the off-market keys will fold before the litigation reaches that conclusion.)

Tyler Karaszewski • April 4, 2008 11:01 AM

While I’d like a perfect security system in my car too, perfect security doesn’t exist anywhere. And this system, in a practical sense, rather than the very academic sense in which these researchers looked at it, is actually quite good, when backed up with a few other bits of information:

1) You can’t sell stolen cars in the US. This means that if you’re going to steal my car, you can only sell it as parts. The market for used car parts is limited, and generally limited to people with a small income. Dealers and auto parts stores are not buying stolen parts off the street. How many people do you know who own a car with an electronic key, but buy replacement parts for it from a junkyard rather than the dealer?

2) Getting the equipment required for this attack is expensive. How many car thieves do you think have access to the sort of equipment (or skill) necessary to pull this off?

3) Insurance. People with mid to high-end new cars generally have them insured, so even if they do go missing, they’re replaced in a few days by the insurer. If this was seriously a problem, insurance companies would charge a premium for cars with these keys, or offer a discount on cars without them.

And, as far as I know, despite this attack being a theoretical possibility, no one’s ever actually stolen a car using it.

As it stands, it’s for more difficult to steal my car than it is to break into my house and murder me in the night, so maybe our car security is “good enough” for now.

Anonymous007 • April 4, 2008 12:22 PM

For the moment, the threat is small.

Won’t be long before this attack is scripted and available for download … such as, the malicious bug-kits we’ve read about.

Now, let’s cruise the airport, pop open trunks and doors, have a look at what’s in there … oh, a laptop with non-encrypted disk … a sheaf of papers with all sorts of goodies on them …

Bruce has written that security is always going to be an attacker/defender scenario. So they will upgrade the security, and someone will write a hack for that, and they’ll upgrade, and the cycle will repeat.

Best thing I’ve seen is publicize the flaw; this put puts the producers on the carpet to kick it up a notch, and will in some cases, likely open the competition field some.

End result? I think security will enhance over time, but the hard part is consumers want to simply push a button and viola! things happen. That scheme may have to change, albeit unpopular to do so.

Just my .02

Rionn Fears Malechem • April 4, 2008 1:29 PM

So… you can start the car, and close the garage door. I feel an episode of Monk coming on.

trvth • April 4, 2008 1:48 PM

Take a look at this article from VeloNews.com, http://www.velonews.com/article/13724

Here’s an excerpt:
“The technical aspect of this story begins with how the theft was accomplished. Apparently, the perpetrator had a scanner and used it to grab Guerciotti’s electronic key code as he locked the car with the remote. My understanding of the technology is that the scanned code can be stored in a small radio device like a cell phone, which can then produce the code again and unlock the car.”

MikeA • April 4, 2008 2:04 PM

“You can’t sell stolen cars in the U.S.”

Right… so the thieves are just stupid?
While I agree that mid-range cars are the most popular (both because the parts are easier to fence and because there are so many of them to choose from), one thing that Tyler K (not Durden?) seems to be missing is the common, since at least the 1990s practice of:
1) Steal a car, strip all easily removable parts and dump it.
2) Wait for insurance auction of hulk, buy hulk.
3) re-equip hulk with stolen parts, sell result, to which you have clear title.

Of course, with the popular models, you don’t really have to wait around for that exact hulk to be auctioned. There will be another one soon.

Tyler Karaszewski • April 4, 2008 3:17 PM

“common, since at least the 1990s practice of…”
Is this really a particularly common practice? What percentage of stolen cars go through something like this? Do you have any statistics about this sort of thing?

MikeA • April 4, 2008 4:49 PM

“…do you have statistics…”.

No. Just random conversations with LEOs and insurance examiners. And of course if they had solid evidence of it happening in any particular case, they would prosecute, rather than piling it on the “needs more investigation” pile that grows without limits for most of us. However, although neither of us can prove or disprove it, it does seem a better explanation for the fact that auto theft still occurs in the U.S. than the notion that it is somehow difficult to profit from it. 🙂
Also, from some of the same LEOs, you would be surprised how many drivers of top-end cars are not averse to purchasing “highly discounted replacement parts from unorthodox sources” 🙂

James • April 4, 2008 5:05 PM

I recently purchased a Toyota Prius, which comes with Toyota’s “Smart Key” entry system. I have not been able to find details of how this system is implemented. Unfortunately, with this system the Prius will start and can be driven away using solely the electronic key.

Does anyone know if Prius keys use KeeLoq?

False Data • April 4, 2008 6:10 PM

@James:

I’m in the same situation. A web search turned up a number of sites strongly suggesting the Prius uses KeeLoc. (The fob’s not labeled, of course.) I’ve sent Toyota e-mail with a link to the paper and a non-technical summary asking if they’re going to address the situation. You might want to do the same. Enough inquiries from owners might raise the issue’s profile enough to get their attention.

Terry Cloth • April 4, 2008 10:05 PM

A side light is that using a regular key is getting harder. We bought a used Volvo wagon, and it didn’t have the remote control. No biggie, we’ve got the keys, but, the /only/ manual lock is the driver’s door. Not only is it a pain if you’re on the passenger side, or just want to grab something from the cargo area, but it’s a single point of failure.

Does anyone make a key-free auto? It’s got to be coming.

notanothervolvodriver!!!! • April 5, 2008 12:31 AM

@Terry Cloth: “We bought a used Volvo wagon”

You bought a Volvo ??

😉

xf • April 5, 2008 9:25 AM

I’ve never been asked to show title to a car when buying spare keys at the dealer.

Ultimately, it’s unclear how good car security really has to be. Probably the most frequent attack on cars is smash-and-grab, causing far more damage and a much greater loss than would have been the case if you’d just left your iPod lying outside, on the roof of the car, or even inside it with the doors unlocked. In that scenario the door locks are actually counterproductive.

Using bad crypto is still a boneheaded idea, though.

Doctor Jekyll • April 6, 2008 12:33 PM

Side Note: I know someone with a chevy equinox. Their remote-unlock thing’s battery died. They opened the drivers door with the key and the alarm went off.

markm • April 6, 2008 5:51 PM

A few technical notes:

“These so-called side-channel attacks are based on measuring and evaluating the power consumption of a KeeLoq device during its operation. Using our techniques, an attacker can reveal not only the secret key of remote controls in less than one hour,”

To measure the power consumption, you have to be in possession of the device, so you can steal that car already. (OTOH, it allows unauthorized remote control duplication, not only breaking a lucrative manufacturer monopoly but making it conceivable that a parking valet will turn the car and garage remotes over for analysis and duplication, then when you pick up the car they follow you home and steal it from your garage.)

“but also the manufacturer key of the corresponding receivers in less than one day. Knowing the manufacturer key allows for creating an arbitrary number of valid new keys and generating new remote controls.” This is the serious part. I think it means you can steal one Beemer remote, analyze it, then re-program any Beemer, at least within the same model and year…

markm • April 6, 2008 6:08 PM

xf: If the car has a car alarm, and if anyone in the area pays attention when one goes off anymore, it greatly limits the time a smash-and-grab thief has for finding valuables. An IPOD sitting on the seat in plain sight is still vulnerable, but will a thief risk spending a couple of minutes to search under the seats for possible valuables, or to unscrew your car stero from the dash (if those things are even worth stealing anymore)? Aside from commonsense advice about not taking expensive cars into bad neighborhoods, the issue is getting the false alarms down to where people do pay attention to car alarms… It certainly isn’t necessary to have an alarm set so sensitively it goes off when a pedestrian brushes against the fender to have it go off when a window is smashed.

Doctor Jekyll: I consider that a feature, not a bug. You can still drive the car without the remote, but eventually you’ll wind up showing a cop your ID and registration to prove you aren’t stealing it.

Vlad • May 12, 2008 3:33 PM

I don’t understand, how can you measure the power consumption of a garage door or car? since you don’t have an access to it.

KeeLoq Still Broken

Comments

Leave a comment Cancel reply