Linear Slide Attacks on the KeeLoq Block Cipher

摘要

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 2~(50.6) KeeLoq encryptions. The second attack finds the key in 2~(37) 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 2~(32) 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.