KeeLoq is a proprietary hardware-dedicated block cipher that uses a non-linear feedback shift register (NLFSR). The uni-directional command transfer protocol was designed by Frederick Bruwer of Nanoteq (Pty) Ltd., the cryptographic algorithm was created by Gideon Kuhn at the University of Pretoria, and the silicon implementation was by Willem Smit at Nanoteq (Pty) Ltd (South Africa) in the mid-1980s. KeeLoq was sold to Microchip Technology Inc in 1995 for $10 million. It is used in 'hopping code' encoders and decoders such as NTQ105/106/115/125D/129D, HCS101/2XX/3XX/4XX/5XX and MCS31X2. KeeLoq has been used in many remote keyless entry systems by such companies like Chrysler, Daewoo, Fiat, Ford, GM, Honda, Mercedes-Benz, Toyota, Volvo, Volkswagen Group, Clifford, Shurlok, and Jaguar.
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 and after 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 ⊕ a c ⊕ a e ⊕ b c ⊕ b e ⊕ c d ⊕ d e ⊕ a d e ⊕ a c e ⊕ a b d ⊕ a b c {\displaystyle F(a,b,c,d,e)=d\oplus e\oplus ac\oplus ae\oplus bc\oplus be\oplus cd\oplus de\oplus ade\oplus ace\oplus abd\oplus abc}
KeeLoq 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.
Versions This article describes the Classic KeeLoq protocol, but newer versions has been developed. The Ultimate KeeLoq system is a timer-based algorithm enhancing the Classic KeeLoq system. The goal of this newer version is to contain stronger, industry standard AES-128 cipher which replaces KeeLoq cipher algorithm, and have a timer-driven counter which continuously increments, which is the opposite of the Classic KeeLoq where the counter increments based on the button press. This provides protection against brute-force attack and capture and replay attack, known as RollJam for Samy Kamkar's work.
Attacks
Replay attack For simplicity, individual "code hopping" implementations typically do not use cryptographic nonces or timestamping. This makes the protocol inherently vulnerable to replay attacks: For example, by jamming the channel while intercepting the code, a thief can obtain a code that may still be usable at a later stage. This sort of "code grabber," while theoretically interesting, does not appear to be widely used by car thieves. A detailed description of an inexpensive prototype device designed and built by Samy Kamkar to exploit this technique appeared in 2015. The device about the size of a wallet could be concealed on or near a locked vehicle to capture a single keyless entry code to be used at a later time to unlock the vehicle. The device transmits a jamming signal to block the vehicle's reception of rolling code signals from the owner's fob, while recording these signals from both of his two attempts needed to unlock the vehicle. The recorded first code is forwarded to the vehicle only when the owner makes the second attempt, while the recorded second code is retained for future use. A demonstration was announced for DEF CON 23.
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. Some KeeLoq "code grabbers" use FPGA-based devices to break KeeLoq-based keys by brute force within about two weeks due 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. 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. Microchip introduced in 1996 a version of KeeLoq ICs which use a 60-bit seed. If a 60-bit seed is being used, an attacker would require approximately 1011 days of processing on a dedicated parallel brute force attacking machine before the system is broken.
… excerpt ends here. Continue reading the full article.
