Abstract
KeeLoq is a lightweight block cipher with a 32-bit block size and a 64-bit key. Despite its short key size, it is widely used in remote keyless entry systems and other wireless authentication applications. For example, authentication protocols based on KeeLoq are supposedly used by various car manufacturers in anti-theft mechanisms. This paper presents a practical key recovery attack against KeeLoq that requires 216 known plaintexts and has a time complexity of 244.5 KeeLoq encryptions. It is based on the slide attack and a novel approach to meet-in-the-middle attacks. The fully implemented attack requires 65 minutes to obtain the required data and 7.8 days of calculations on 64 CPU cores. A variant which requires 216 chosen plaintexts needs only 3.4 days on 64 CPU cores. Using only 10 000 euro, an attacker can purchase a cluster of 50 dual core computers that will find the secret key in about two days. We investigated the way KeeLoq is intended to be used in practice and conclude that our attack can be used to subvert the security of real systems. An attacker can acquire chosen plaintexts in practice, and one of the two suggested key derivation schemes for KeeLoq allows to recover the master secret from a single key.
This work was supported in part by the Concerted Research Action (GOA) Ambiorics 2005/11 of the Flemish Government, by the IAP Programme P6/26 BCRYPT of the Belgian State (Belgian Science Policy), and in part by the European Commission through the IST Programme under Contract IST-2002-507932 ECRYPT.
Chapter PDF
Similar content being viewed by others
References
Biham, E.: New Types of Cryptanalytic Attacks Using Related Keys. Journal of Cryptology 7(4), 229–246 (1994)
Biryukov, A., Mukhopadhyay, S., Sarkar, P.: Improved Time-Memory Tradeoffs with Multiple Data. In: Preneel, B., Tavares, S. (eds.) SAC 2005. LNCS, vol. 3897, pp. 245–260. Springer, Heidelberg (2006)
Biryukov, A., Wagner, D.: Slide Attacks. In: Knudsen, L.R. (ed.) FSE 1999. LNCS, vol. 1636, pp. 245–259. Springer, Heidelberg (1999)
Biryukov, A., Wagner, D.: Advanced Slide Attacks. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 586–606. Springer, Heidelberg (2000)
Bogdanov, A.: Cryptanalysis of the KeeLoq block cipher, Cryptology ePrint Archive, Report 2007/055, February 16 (2007), http://eprint.iacr.org/2007/055/
Bogdanov, A.: Attacks on the KeeLoq Block Cipher and Authentication Systems. In: 3rd Conference on RFID Security 2007 (RFIDSec 2007), http://rfidsec07.etsit.uma.es/slides/papers/paper-22.pdf
Courtois, N.T., Bard, G.V.: Algebraic and Slide Attacks on KeeLoq, Cryptology ePrint Archive, Report 2007/062, May 8 (2007), http://eprint.iacr.org/2007/062/
Courtois, N.T.: Personal communication (May 31, 2007)
Courtois, N.T., Bard, G.V., Wagner, D.: Algebraic and Slide Attacks on KeeLoq. In: Proceedings of Fast Software Encryption 2008, LNCS, Springer, Heidelberg (to appear)
Furuya, S.: Slide Attacks with a Known-Plaintext Cryptanalysis. In: Kim, K.-c. (ed.) ICISC 2001. LNCS, vol. 2288, pp. 214–225. Springer, Heidelberg (2002)
Hellman, M.E.: A Cryptanalytic Time-Memory Trade-Off. IEEE Transactions on Information Theory 26, 401–406 (1980)
Kumar, S., Paar, C., Pelzl, J., Pfeiffer, G., Schimmler, M.: Breaking Ciphers with COPACOBANA — A Cost-Optimized Parallel Code Breaker. In: Goubin, L., Matsui, M. (eds.) CHES 2006. LNCS, vol. 4249, pp. 101–118. Springer, Heidelberg (2006)
Microchip Technology Inc. KeeLoq® Authentication Products, http://www.microchip.com/keeloq/
Microchip Technology Inc., HCS410 KeeLoq® Code Hopping Encoder and Transponder Data Sheet, http://ww1.microchip.com/downloads/en/DeviceDoc/40158e.pdf
Microchip Technology Inc., AN642: Code Hopping Decoder using a PIC16C56, http://www.keeloq.boom.ru/decryption.pdf
Microchip Technology Inc., TB001: Secure Learning RKE Systems using KeeLoq Encoders, http://ww1.microchip.com/downloads/en/AppNotes/91000a.pdf
Wikipedia, KeeLoq (August 2007), http://en.wikipedia.org/wiki/KeeLoq
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Indesteege, S., Keller, N., Dunkelman, O., Biham, E., Preneel, B. (2008). A Practical Attack on KeeLoq. In: Smart, N. (eds) Advances in Cryptology – EUROCRYPT 2008. EUROCRYPT 2008. Lecture Notes in Computer Science, vol 4965. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-78967-3_1
Download citation
DOI: https://doi.org/10.1007/978-3-540-78967-3_1
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-78966-6
Online ISBN: 978-3-540-78967-3
eBook Packages: Computer ScienceComputer Science (R0)