KeeLoq

KeeLoq is a proprietary hardware-dedicated NLFSR-based block cipher. The uni-directional command transfer protocol was designed by Frederick Bruwer PhD, CEO at Nanoteq (Pty) Ltd and the crypto algorithm was done by Professor Gideon Kuhn with the silicon implementation by Willem Smit, PhD at Nanoteq Pty Ltd (South Africa) in the mid 80's and sold to Microchip Technology Inc in 1995 for $10 million. It's used in "code hopping" encoders and decoders such as NTQ105/106/115/125D/129D and HCS101/2XX/3XX/4XX/5XX. KeeLoq is used in the majority of remote keyless entry systems by such companies as Chrysler, Daewoo, Fiat, GM, Honda, Toyota, Volvo, VW, Clifford, Shurlok, Jaguar, etc. [Some evidence that Chrysler indeed uses KeeLoq can be found in [http://www.archive.org/details/tps_episode_04 (this video)] .]

Description

KeeLoq "code hopping" encoders encrypt a 0-filled 32-bit block with KeeLoq cipher to produce a 32-bit "hopping code". A 32-bit initialization vector is linearly added (XORed) to the 32 least significant bits of the key prior to encryption or decryption.

KeeLoq cipher accepts 64-bit keys and encrypts 32-bit blocks by executing its single-bit NLFSR for 528 rounds. The NLFSR feedback function is 0x3A5C742E or F(a,b,c,d,e) = d ⊕ e ⊕ ac ⊕ ae ⊕ bc ⊕ be ⊕ cd ⊕ de ⊕ ade ⊕ ace ⊕ abd ⊕ abc. It uses bits 1, 9, 20, 26 and 31 of the NLFSR state as its inputs during encryption and bits 0, 8, 19, 25 and 30 during decryption. Its output is linearly combined (XORed) with two of the bits of the NLFSR state (bits 0 and 16 on encryption and bits 31 and 15 on decryption) and with a key bit (bit 0 of the key state on encryption and bit 15 of the key state on decryption) and is fed back into the NLFSR state on every round.

Cryptanalysis

KeeLoq was first cryptanalyzed by Andrey Bogdanov using sliding techniques and efficient linear approximations. Nicolas Courtois attacked KeeLoq using sliding and algebraic methods. The attacks by Bogdanov and Courtois do not pose any threat to the actual implementations that seem to be much more vulnerable to simple brute-force of the key space that is reduced in all the code-hopping implementations of the cipher known to date. Individual "code hopping" implementations are also often vulnerable to a replay attack exploited by jamming the channel while intercepting the code, since code hopping is done by incrementing the IV on each use instead of using the current time. It made KeeLoq "code grabbers" quite popular among most car thieves, although some of them use FPGA-based devices to break KeeLoq-based keys by brute force within about two weeks thanks to the reduced key length in the real world implementations.

In 2007, researchers in the COSIC group at the university at Leuven, Belgium, (K.U.Leuven) in cooperation with colleagues from Israel found a new attack against the system. [ [http://www.cosic.esat.kuleuven.be/keeloq/ How To Steal Cars — A Practical Attack on KeeLoq ] ] Using the details of the algorithm that were leaked in 2006, the researchers started to analyze the weaknesses. After determining the part of the key common to cars of a specific model, the unique bits of the key can be cracked with only sniffed communication between the key and the car, e.g. unlocking. Their paper asserts that "KeeLoq is badly broken", joking that "Soon, cryptographers will all drive expensive cars."

ide-channel attacks

In March 2008, researchers from the Ruhr University Bochum, Germany, presented a complete break of remote keyless entry systems based on the KeeLoq RFID technology [ [http://www.crypto.rub.de/keeloq A complete break of the KeeLoq access control system] ] . Their attack works on all known cars and building access control systems that rely on the KeeLoq cipher.

The attack by the Bochum team allows recovering the secret cryptographic keys embedded in both the receiver and the remote control. It is based on measuring the electric power consumption of a device during an encryption. Applying what is called side-channel analysis methods to the power traces, the researchers can extract the manufacturer key from the receivers, which can be regarded as a master key for generating valid keys for the remote controls of one particular manufacturer. Unlike the cryptanalytic attack described above which requires about 65536 chosen plaintext-ciphertext pairs and days of calculation on a PC to recover the key, the side-channel attack can also be applied to the so-called KeeLoq Code Hopping mode of operation (AKA rolling code) that is widely used for keyless entry systems (cars, garages, buildings, etc.).

The most devastating practical consequence of the side-channel analysis is an attack in which keys can be cloned by intercepting only two messages sent by the legitimate key from a distance of up to Convert|100|m|ft. Another attack allows to re-set the internal counter of the receiver (garage door, car door, etc.) which makes it imposible for a legitimate user to open the door, car etc.

It should be noted that Microchip introduced a version of KeeLoq ICs which use a 60-bit seed. The eavesdropping attack described above is not feasible if a 60-bit seed is being used.

References

External links

* [http://www.crypto.rub.de/ Embedded Security Group at the University of Bochum]
* [http://www.nanoteq.com/ Nanoteq Pty Ltd website]
* [http://www.microchip.com/ Microchip Technology Inc website]
* [http://www.keeloq.boom.ru/decryption.pdf KeeLoq Decryption Algorithm Specification]
* [http://cryptolib.com/ciphers/keeloq C source code by Ruptor]
* [http://sec.edgar-online.com/2002/06/03/0000950147-02-000745/Section8.asp MICROCHIP TECHNOLOGY INC - Form:10-K Filing Date:6/3/2002]
* [http://eprint.iacr.org/2007/055 Andrey Bogdanov, 'Cryptanalysis of the KeeLoq block cipher']
* [http://eprint.iacr.org/2007/062 N.T. Courtois and G.V. Bard, 'Algebraic and Slide Attacks on KeeLoq']
* [http://www.microchip.com/stellent/idcplg?IdcService=SS_GET_PAGE&nodeId=2018&mcparam=en013157 'Microchip Press Release on the acquisition of KeeLoq']
* [http://www.microchip.com/stellent/idcplg?IdcService=SS_GET_PAGE&nodeId=2018&mcparam=en531686 'Microchip Press Release on Theoretical Code Cracking']
* [http://www.crypto.rub.de/imperia/md/content/projects/keeloq/keeloq_en.pdf University of Bochum / HGI Press Release on the complete break of KeeLoq based entry systems]
* [http://eprint.iacr.org/2008/058 Physical Cryptanalysis of KeeLoq Code Hopping Applications]