KeeLoq Broken
There’s been a lot of hype, but finally there’s a good article about the cryptanalysis of the KeeLoq electronic car-door entry system.
Presentation here.
Comments
Bill, Dallas, TX • September 13, 2007 3:09 PM
Interesting coincidence. I just discovered an exploit for the keyless entry for my car. It’s a lot easier to do, and requires only any keyless remote for the car:
http://restlessobsessive.blogspot.com
I agree that if cars like Prius, which also doesn’t use a key, are subject to this exploit, there could be trouble. Hop in and push the start button once you have the code.
Michael • September 13, 2007 3:10 PM
As interesting as the article is, the comments are even more so. About half blame the cryptographers for putting their cars at risk. One even suggested that, in this era of terrorism, cryptographers should not publish. A more graphic demonstration that people don’t get it could not be asked for.
Milan • September 13, 2007 3:12 PM
Does this also work for immobilizers?
If so, that may be a bigger security breach than its ability to open car doors which, as the people mentioned in this article stress, can be easily done in other ways.
Mike • September 13, 2007 4:00 PM
This was one of the most interesting talks at the CRYPTO rump session. The comments on the NBC page are really really disturbing, though..
Nigel Sedgwick • September 13, 2007 4:28 PM
Why is an exhaustive search 18 billion long thought adequate in a world with compuers costing less than $700 per billion instructions per second?
Best regards
sooth_sayer • September 13, 2007 4:48 PM
2 Questions for Bruce –
Where is your “new” Bentley parked today?
And how do you square with the story that the researchers were able to break it after the details of the algorithm got published on some Russian web site.
You have held that “secret” encryption systems are generally very poor, but it appears that this secret system lasted a long time .. even with $50K targets on every street corner !!!
McGavin • September 13, 2007 4:50 PM
I think this is more serious than the article suggests. If I start making my master keys now, then I can do pretty well this December in mall parking lots by stealing the stuff that is INSIDE THE CARS.
Anton • September 13, 2007 5:01 PM
The top building locks company in Switzerlands (KABA.ch) uses a combination of electronic as well as mechanical technologies in its access devices. Obviously very prudent.
It seems in todays modern world you
– don’t own anything that is expensive and if you do, don’t keep it in your car
– drive something standard and unobtrusive and insure it at replacement value, so if it gets stolen you win.
Knowler Longcloak • September 13, 2007 5:22 PM
@Nigel Sedgwick
How many instructions are needed to try each of those 18 billion keys?
If they number in the thousands of instructions for each of the keys then it is beyond the realm of everyone but major governments to brute force a single car in less than 30 minutes.
Someone hanging around your car for more than a few seconds is acting “hinky” to any passerby.
It is not a bad practice for infrequently used crypto like a keyless FOB to throttle brute-force attempts by using more rounds than are necessary in the crypto. Things like websites can’t do it because the throughput needs are so high. A keyless FOB just needs to respond in 1 second or less.
Matt • September 13, 2007 7:19 PM
FTA: “18 billion keys”
From the presentation linked from the article: “64-bit key”
2**64 ~ 18 quintillion. I’m willing to bet that it wasn’t due to a mistake on Eli Biham’s part that the article gives a (drastically) wrong order of magnitude for the key space.
I bet developing that attack was really fun work 🙂
Andy • September 13, 2007 8:54 PM
“18 Billion” — Read it again it’s 18 Billion billions which is 2^64 ~ 18 x 10^18 = 18 x 10^9 x 10^9
J van der Merwe • September 14, 2007 2:11 AM
I hope someone from Nanoteq is reading this. This was the Pretoria-based company that Microchip bought Keeloq from. About 15 years ago they sent lawyers letters and threatened to sue everyone who had implemented code-hopping transmitters (code-hopping was and still is not a big deal and fairly obvious to anyone, basically one or more LFSR with a look-forward window). Now is payback time, bullies.
ZZZ • September 14, 2007 2:21 AM
My god the comments on the MSNBC site are moronic. Many comments along the lines of “Why don’t those scientists stop teaching thieves how to do their work. They have no morals blah blah blah…”
Dennis • September 14, 2007 4:22 AM
What about Super KeeLoq Pro II ? Is it also broken?
Woo • September 14, 2007 4:46 AM
Well.. “50 dualcore CPUs, about two days” for a successful attack. I guess it’s still easier for a burglar to carry around a Slim Jim instead of a Cray T3E. The concept of the attack may be nice, but the real use isn’t there. By the time that hardware has advanced enough for this attack to be mountable on a notebook or similar device, car manufacturers will have thought of new systems – or at least of a way to limit the number of attempts in a given timeframe.
Anonymous • September 14, 2007 6:47 AM
@Nigel
“beyond the realm of everyone but major governments to brute force a single car in less than 30 minutes ”
By some estimates the larger botnets qualify for the top 100 supercomputers list. One particular botnet might actually have more processing power than the current no. 1 at Sandia labs.
So criminal gangs now have more processing power than is available to most governments.
This really should become a National Security issue. Perhaps it could even lead to some effective anti-virus solutions (like holding an ISP responsable for “owned” machines attached to thier networks.)
CGomez • September 14, 2007 8:14 AM
I actually thought this was broken years ago. It was just not worth the effort compared to traditional methods.
I guess I had believed some urban legend about it being broken, but now it is!
DigitalCommando • September 14, 2007 10:06 AM
Keypad based security systems have used a “wrong code lockout” strategy for years. Keeloq could apply this same principle to prevent a continuous stream of “try out” codes as would be used in a brute force attack. They would need to reduce the range of the receiver to prevent lockout due to legitimate nearby transmissions in areas such as shopping mall parking lots. Fingerprint based locks will probably replace this technology in the near future anyway….
dragonfrog • September 14, 2007 11:41 AM
@Woo “Well.. “50 dualcore CPUs, about two days” for a successful attack. I guess it’s still easier for a burglar to carry around a Slim Jim instead of a Cray T3E.”
That’s how much CPU time it takes to recover one manufacturer’s master key, which is good for every car from that manufacturer. Once you have that key, you never need to repeat those calculations. You can now open any car from that manufacturer in seconds, with only the CPU power available on a PDA or cellphone.
dragonfrog • September 14, 2007 11:44 AM
@DigitalCommando
I’ll never drive a car with a fingerprint lock. I’d much rather have thieves steal my keys, than have to hack off my hand, if they want my car. (Yes that does happen)
GameOwl • September 16, 2007 10:42 PM
Why not make a OTP (one time pad) generated by the button you press to unlock/lock your car that would be pressure sensitive when you press it. Depending on every bodies unique pressure it would generate a new OTP each time pressed when you lock it. Then just press the unlock button to unlock the car with the OTP. Just an idea I came up with.
-ac- • September 17, 2007 2:15 PM
Lol, I read “key log”.
Off-topic: is the number of keylogger trojans that can run simultaneously limited? If so, run your own keylogger intercept to foil the keyloggers.
Subscribe to comments on this entry
Leave a comment
Sidebar photo of Bruce Schneier by Joe MacInnis.
Nicholas Weaver • September 13, 2007 2:48 PM
However, such things are worrysome as keyless ignition proliferates.
EG, my motorcycle uses a fob & keyless ignition system (made by mitsubishi, the cypher for the challenge/response is MISTY supposidly)