Attacks on the KeeLoq Block Cipher and Authentication Systems

Andrey Bogdanov

3rd Conference on RFID Security 2007 (RFIDSec 2007), Malaga, ES, July 11-13, 2007.


Abstract

KeeLoq is a block cipher used in numerous widespread passive entry and remote keyless entry systems as well as in various component identi?cation 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 ?rst one has a complexity of about 2 50.6 KeeLoq encryptions. The second attack ?nds 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 plaintextciphertext pairs.

We also analyze the KeeLoq key management and authentication protocols applied in rollingcode and IFF access systems widely used in real-world applications. We demonstrate several practical vulnerabilities.

[Talk Slides] [Bibtex] [pdf]

tags: Cryptanalysis, hopping codes, keeloq, linear cryptanalysis, rolling codes, slide attacks