KeeLoq

From Wikipedia, the free encyclopedia

KeeLoq is a proprietary hardware-dedicated NLFSR-based block cipher. It was designed 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 (Form:10-K reference). 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.

1 Description
2 KeeLoq Encryption Process
3 KeeLoq Decryption Process
4 Security
5 External links

[edit] 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 least significant 32 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 2, 9, 20, 26 and 31 of the NLFSR state as its inputs during encryption and bits 1, 8, 19, 25 and 30 during decryption. Its output is linearly combined (XORed) with one of the bits of the NLFSR state (bit 0 on encryption and bit 31 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.

[edit] KeeLoq Encryption Process

[edit] KeeLoq Decryption Process

[edit] Security

Nicolas Courtois has published the first cryptanalysis of KeeLoq by studying its resistance to algebraic attacks. Courtois' attacks 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.