Aug. 28, 2007 at 8:00 AM ET
A group of computer security researchers in Israel and Belgium say they've discovered the electronic equivalent of a Slim Jim -- a way to pop the electronic door locks on most cars without ever touching them.
Drivers don’t have to worry about their cars being hacked just yet – a baseball bat is still a more effective auto theft tool – but the announcement shows yet again that newfangled security devices can be more vulnerable than you think.
Most modern cars are now equipped with convenient remote keyless entry systems. Now it seems that tool could be a convenient way for criminals to break into hundreds of cars in an afternoon.
By listening in on the wireless “conversation” between a car and its key, the researchers found they could crack the code that keeps the communication secret. Then they were able to emulate the electronic key and trick the car into unlocking itself.
Nearly all cars with remote keyless entry use an encryption system called KeeLoq. It was developed during the 1980s and purchased by Microchip Technology Inc. in the 1990s. Like all encryption systems, KeeLoq scrambles messages so they can't be read by anyone who intercepts them. Only someone -- or something -- with the appropriate deciphering key can unscramble the message.
Eli Biham, a computer science professor at the Technion-Israel Institute of Technology, says there are 18 billion possible keys for a KeeLoq transmission, making it practically impossible for even the fastest computer to work out the key through brute force.
"But," he said, "we found a shortcut."
By intercepting several transmissions from the electronic key and analyzing them, Biham and his colleagues say they were able to eliminate many of those 18 billion possibilities and work out a master key in about one day. All that’s required is remote access to one key for about an hour -- say, while a person is sitting in his office with the key still in a shirt pocket.
Then, after working out the encryption scheme, Biham’s group says it can unlock all cars using that master key within a few minutes.
"In modern ciphers, you don't expect this to happen," Biham says, noting that carmakers are still relying on 20-year-old cryptography to keep cars safe. "I don't understand how companies sell cryptography from the 1980s."
The research paper, called “How to Steal Cars, (PDF)” was presented at the Crypto 2007 conference at the University of California, Santa Barbara, last week. Exact details for exploiting the discovery won't be published for several months, Biham says, but Microchip Technology was informed weeks ago.
"KeeLoq is badly broken," the paper says, adding, tongue-in-cheek, "Soon, cryptographers will all drive expensive cars."
Microchip wouldn't comment on the team's discovery.
"Microchip Technology Inc. doesn’t address matters of security in the public domain," was all that spokesman Eric Lawson would say.
But other cryptography experts said the research was significant.
"This is a very practical application of cryptanalysis," said Jon Callas, chief technology officer with the encryption firm PGP Corp., who attended the presentation. "There is a larger lesson here, which is some of these devices aren't as secure as they are being sold to us."
Slim Jim a bigger threat
Still Callas isn't worried about his car locks being hacked just yet. There are several barriers to using the technology. While a key hacker would be able to pop the lock on the door and perhaps disarm and alarm, he or she probably couldn't get the car started without using old-fashioned car theft tools, he said. And even with the most sophisticated computers, hacking the locks still takes over an hour, while a baseball bat can do just as good a job in a second or two.
"There is not a whole lot of threat to the end consumer," he said. "A guy with a Slim Jim is a bigger threat."
The method could prove lucrative under the right circumstances, however. A thief armed with a master key could park a car with listening devices in the middle of a shopping mall lot and eavesdrop on every car as a driver parks, walks away, and pushes their key to lock the doors. Within seconds, the transmission could be intercepted, analyzed, paired with information about a known master key and used to pop the locks. A criminal could theoretically open hundreds of cars each day that way, stealing a treasure trove of iPods and GPS gadgets without leaving a trace
"That would be worth someone's time," Callas said. Victims "would have a hard time convincing (their) insurance companies that this had happened."
A simple fix
Modest adjustments to encryption tools would foil such a plot, Callas said. Biham's method requires tricking the car's system into answers a long series of questions. But the use of "throttling" -- inserting a delay after every three requests, as some Web sites now do – can slow or eliminate such brute force attacks. So Callas has no plans to disable his electronic locks, which could be done by disconnecting the car's battery while parked.
"I'm more concerned about losing my radio presets than having my car stolen like this," he joked.
Intense research into Keeloq by several groups began last year after proprietary information about KeeLoq’s cryptography was leaked onto a Russian Web site. Biham said the information aided his group’s research, but argued that properly implemented cryptography should withstand publication of such details.
Both he and Callas were critical of Microchip for not publishing its cryptographic scheme in public earlier, which would have allowed researches to probe it for holes.
“Those of us who are in the field believe that algorithms should be published from the start because an analysis can strengthen them,” Callas said. “We only use public algorithms because in long term they are more secure.”
While the immediate threat to car owners is low, Biham says the research shows the technology used to protect remote keyless entry systems is outdated.
"There are other tools criminals can use today (to steal cars) that are easier," Biham says. "But we show that it's possible to (hack the locks) and these systems to be replaced."