Attacks on the Keeloq Block Cipher and Authentication Systems
Andrey Bogdanov · 2007
www.crypto.rub.de Abstract. KeeLoq is a block cipher used in numerous widespread passive entry and remote keyless entry systems as well as in various component identification applications. The KeeLoq algorithm has a 64-bit key and operates on 32-bit blocks. It is based on an NLFSR with a nonlinear feedback function of 5 variables. In this paper new key recovery attacks on KeeLoq are proposed. The first one has a complexity of about 250.6 KeeLoq encryptions. The second attack finds the key in 237 encryptions and works for the whole key space. In our attacks we use the techniques of guess-and-determine, slide, and linear attacks as well as cycle structure analysis. Both attacks need 232 known plaintext-ciphertext pairs. We also analyze the KeeLoq key management and authentication protocols applied in rolling-code and IFF access systems widely used in real-world applications. We demonstrate several practical vulnerabilities.