The key entry system used by Chrysler, Daewoo, Fiat, General Motors, Honda, Toyota, Lexus, Volvo, Volkswagen, Jaguar, and probably others is broken. This system uses the encryption algorithm called KeeLoq. It 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. The COmmunication SecuritY (COSY) research group of the Ruhr-Universität Bochum has discovered a method that allows practical attacks against devices that use this algorithm. In their paper, they show that it is technically possible to clone a device that open the car or door by eavesdropping wirelesses at most two messages.
Code Hopping algorithms
The history of remote door openers begin around 1950. At this time the transmitters were extremely simple. They sent out a single signal, and the garage door opener responded by opening or closing. As this technology became fairly common, the simplicity of this system became a big problem:
a single transmitter can be used to open any garage door.
By the 1970s, garage door openers became more sophisticated. Usually an eight DIP switches was used to assign a unique code to each door. The 256 possible combinations was enough to keep several neighbors from opening each other’s doors, but not enough to provide any real security.
This is to address this need that hopping code, also known as rolling code, was invented. Each pair of device, the transmitter and the receiver, uses the same pseudo random generator, a shared secret key and a counter to derive the next message code. It is called rolling code because each time a code is emitted the code is “burned” and the counter is incremented. As a result a new code is generated, each time a message is transmitted. Of course to work, the receiver and the transmitter need to be synchronized. It might happen that the transmitter is used out of the range of the receiver because for example a kid is playing with it. This is handled by the receiver because it accepts the few next upcoming codes. This mechanism is called in KeeLoq technical documentation the opening windows
The KeeLoq algorithm
The KeeLoq algorithm, is licensed by Microchip Technology to car makers and other entities. Each KeeLoq key or key fob uses a unique value, out of billions and billions of possibilities, to unlock a car. As the WEP and the A5 algorithm, the exact algorithm was kept secret until last year, when confidential informations were leaked by a russian site.
Similarly of what happened to the WEP and the A5 algorithm when their details became public, it turn out that attack against against KeeLoq where found by the scientific community within days. KeeLoq first cryptanalysis was done by Andrey Bogdanov using sliding techniques and efficient linear approximations. Nicolas Courtois attacked KeeLoq using sliding and algebraic methods. Eli Biham, Orr Dunkelman, Sebastiaan Indesteege, Nathan Keller and Bart Preneel. published a more efficient attack based on a weakness of the protocol in the paper called “How To Steal Cars A Practical Attack on KeeLoq“.
However theses attacks were still hard to use in practice.
The paper from Cosy research group shows that using DPA (differential power analysis), it is possible with 10 traces to recover the manufacturer key. Once it is done any key from a device from the same manufacturer can be found by sniffing at most two messages. Of course performing the DPA analysis is straightforward, but it can be accomplish in matter of weeks. What can be even more concerning is that it is likely that sooner or later manufacturer keys will be leaked on the net, and once the pandora box is open…
Latest Comments