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 w
- PDF / 433,771 Bytes
- 15 Pages / 430 x 660 pts Page_size
- 86 Downloads / 191 Views
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 realworld applications. We demonstrate several practical vulnerabilities. Keywords: KeeLoq, cryptanalysis, slide attacks, linear cryptanalysis, hopping codes, rolling codes, authentication protocols, identify friendor-foe, key generation.
1
Introduction
KeeLoq is a block cipher based on an NLFSR with a nonlinear boolean feedback function of 5 variables. The algorithm uses a 64-bit key and operates on 32-bit blocks. Its architecture consists of two registers (a 32-bit text register and a 64-bit key register), which are rotated in each of 528 encryption cycles, and of a nonlinear function (NLF) providing nonlinear feedback. One bit of the key is added to the output of the NLF modulo 2 in each cycle. The light-weight architecture of the KeeLoq cipher allows for an extremely low-cost and efficient hardware implementation (about 700 GE and 528 clock cycles per block). This contributed to the popularity of the KeeLoq cipher among designers of remote keyless entry systems, automotive and burglar alarm systems, automotive immobilizers, gate and garage door openers, identity tokens,
This is a short version of the full work [1] on the analysis of KeeLoq systems presented at the 3rd Conference on RFID Security (RFIDSec’07) in Malaga, Spain.
Dingyi Pei et al. (Eds.): Inscrypt 2007, LNCS 4990, pp. 66–80, 2008. c Springer-Verlag Berlin Heidelberg 2008
Linear Slide Attacks on the KeeLoq Block Cipher
67
component identification systems. For instance, the KeeLoq block cipher is used by such automotive OEMs as Chrysler, Daewoo, Fiat, GM, Honda, Toyota, Volvo, VW, Jaguar [2] and in the HomeLink wireless control systems to secure communication with garage door openers [3]. The KeeLoq technology supplied by Microchip Technology Inc. includes the KeeLoq cipher and a number of authentication protocols as well as key management schemes. Our description of KeeLoq is based on the newly published article [2], [4] and a number of the manufacturer’s documents [5], [6], [7], [8]. Our contribution. The contribution of the paper is many-fold. First, a new technique to perform recovery attacks on KeeLoq is proposed. Our direct attack recovers the key in 250.6 . Second, the techniques allow us to propose an extende
Data Loading...
