KeeLoq Remake
Introduction
KeeLoq was invented at Nanoteq (South Africa) in the 1980's by Frederick Bruwer (uni-directional command transfer protocol), Gideon Kuhn (cryptographic algorithm) and Willem Smit (silicon implementation). The specifications of KeeLoq are patented and can only be used under license. In November 1995 Microchip Technologie Inc. acquired the KeeLoq code hopping technology patents along with the worldwide marketing rights. Typical applications for the KeeLoq encoders and decoders include remote keyless entry (RKE) systems, alarm systems, immobilizers, car alarms, garage door openers, burglar alarms, secure communications such as in smoke/carbon monoxide/radon detectors, remote-control toys, model cars/airplanes, appliances, identity tokens and tracking of parts/packages. \cite{MC_PR_Archive} Also allows KeeLoq block cipher a low cost hardware implementation with low power consumption. Having such a broad field of application, also mainly in security related topics, KeeLoq became interesting for researchers, as well criminals all over the world. After releasing implementation details on a Russian website in 2006, first successful attacks on the algorithm are published in 2007, were the weakness of self similarity of the key schedule, combined with a quite short key length, allowed to mount a slide attack. Over the years many flavours of attack strategies got developed, from attacking the cipher directly using mathematical methods, or the protocol using replay or man-in-the-middle attacks. Also the implementation offers attack vectors using side-channel-attack methods by measuring power consumption, temperature, electromagnetic fields on the chips or by measuring response times. The weaknesses within KeeLoq and its implementation will be presented in this document.
KeeLoq Basics
Before jumping into some details of different type of attacks, this section begins with an introduction to the basic concepts of KeeLoq cipher, which is in principle an unbalanced Feistel-network used for decoding and encoding. Later in this section the authentication protocols are covered, which both use KeeLoq. Further is shown how synchronization between sender and receiver works, were an attacker could also see a potential security hole. Finally this section presents how the key derivation is managed, and show that all devices from a manufacturer use the same key kMan, which makes cloning of senders an easy task.
KeeLoq Encryption/Decryption Algorithm
KeeLoq block cipher uses a 64 bit key register which operates as simple circular shift register, that becomes initialized with the secret key, and a 32 bit state register implemented as a nonlinear feedback shift register (NLFSR), that is initialized with the first 32 bits of the clear text. Each round i of the total 528 rounds, the NLF feedback depends on five bits (b31, b26, b20, b9, b1) of the state register combined (XOR) with the state bits b17, b0 and a bit of the secret key ki mod(64) and shifted to the right. After 528 rounds the cipher can be read from the state register. (Figure \ref{figure:1}) caption When decoding the state register is initially filled with the cipher text, and five different bits of the state register are used (b30, b25, b19, b8, b0) and state bits b31, b15 get combined with the key bit k(15-\textit{i}) mod 64 and shifted to the left in each round i. After 528 rounds the corresponding clear text can be read from the state register. (Figure \ref{figure:2})