Abstract
KeeLoq is a block cipher used in wireless devices that unlock the doors and alarms in cars manufactured by Chrysler, Daewoo, Fiat, GM, Honda, Jaguar, Toyota, Volvo, Volkswagen, etc [8,9,33,34]. KeeLoq is inexpensive to implement and economical in gate count, yet according to Microchip [33] it should have “a level of security comparable to DES”.
In this paper we present several distinct attacks on KeeLoq, each of them is interesting for different reasons. First we show that when about 232 known plaintexts are available, KeeLoq is very weak and for example for 30% of all keys the full key can be recovered with complexity of 228 KeeLoq encryptions. Then we turn our attention to algebraic attacks with the major challenge of breaking KeeLoq given potentially a very small number of known plaintexts.
Our best “direct” algebraic attack can break up to 160 rounds of KeeLoq. Much better results are achieved in combination with slide attacks. Given about 216 known plaintexts, we present a slide-algebraic attack that uses a SAT solver with the complexity equivalent to about 253 KeeLoq encryptions. To the best of our knowledge, this is the first time that a full-round real-life block cipher is broken using an algebraic attack.
Chapter PDF
Similar content being viewed by others
Keywords
References
Bardet, M., Faugère, J.-C., Salvy, B.: On the complexity of Gröbner basis computation of semi-regular overdetermined algebraic equations. In: Proceedings of International Conference on Polynomial System Solving (ICPSS, Paris, France), pp. 71–75 (2004)
Biryukov, A., Wagner, D.: Advanced Slide Attacks. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 589–606. Springer, Heidelberg (2000)
Biryukov, A., Wagner, D.: Slide Attacks. In: Knudsen, L.R. (ed.) FSE 1999. LNCS, vol. 1636, pp. 245–259. Springer, Heidelberg (1999)
Bogdanov, A.: Cryptanalysis of the KeeLoq block cipher, 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)
Bogdanov, A.: Linear Slide Attacks on the KeeLoq Block Cipher. In: The 3rd SKLOIS Conference on Information Security and Cryptology (Inscrypt 2007). LNCS. Springer, Heidelberg (2007)
Cid, C., Babbage, S., Pramstaller, N., Raddum, H.: An Analysis of the Hermes8 Stream Cipher. In: Pieprzyk, J., Ghodosi, H., Dawson, E. (eds.) ACISP 2007. LNCS, vol. 4586, pp. 1–10. Springer, Heidelberg (2007)
Keeloq wikipedia article. On 25 January 2007 the specification given here was incorrect and was updated since, http://en.wikipedia.org/wiki/KeeLoq
Keeloq C source code by Ruptor, http://cryptolib.com/ciphers/
Courtois, N.: Examples of equations generated for experiments with algebraic cryptanalysis of KeeLoq, http://www.cryptosystem.net/aes/toyciphers.html
Courtois, N., Patarin, J.: About the XL Algorithm over GF(2). In: Joye, M. (ed.) CT-RSA 2003. LNCS, vol. 2612, pp. 141–157. Springer, Heidelberg (2003)
Courtois, N., Shamir, A., Patarin, J., Klimov, A.: Efficient Algorithms for solving Overdefined Systems of Multivariate Polynomial Equations. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 392–407. Springer, Heidelberg (2000)
Courtois, N., Pieprzyk, J.: Cryptanalysis of Block Ciphers with Overdefined Systems of Equations. In: Zheng, Y. (ed.) ASIACRYPT 2002. LNCS, vol. 2501, pp. 267–287. Springer, Heidelberg (2002)
Courtois, N., Meier, W.: Algebraic Attacks on Stream Ciphers with Linear Feedback. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 345–359. Springer, Heidelberg (2003)
Courtois, N.: General Principles of Algebraic Attacks and New Design Criteria for Components of Symmetric Ciphers. In: Dobbertin, H., Rijmen, V., Sowa, A. (eds.) AES 2005. LNCS, vol. 3373, pp. 67–83. Springer, Heidelberg (2005)
Courtois, N.: The Inverse S-box, Non-linear Polynomial Relations and Cryptanalysis of Block Ciphers. In: Dobbertin, H., Rijmen, V., Sowa, A. (eds.) AES 2005. LNCS, vol. 3373, pp. 170–188. Springer, Heidelberg (2005)
Courtois, N.T.: How Fast can be Algebraic Attacks on Block Ciphers? In: Biham, E., Handschuh, H., Lucks, S., Rijmen, V. (eds.) online proceedings of Dagstuhl Seminar 07021, Symmetric Cryptography (January 07-12, 2007), http://drops.dagstuhl.de/portals/index.php?semnr=07021 , http://eprint.iacr.org/2006/168/ ISSN 1862 - 4405
Courtois, N.: CTC2 and Fast Algebraic Attacks on Block Ciphers Revisited, http://eprint.iacr.org/2007/152/
Courtois, N., Bard, G.V.: Algebraic Cryptanalysis of the Data Encryption Standard. In: Cryptography and Coding, 11-th IMA Conference, Cirencester, UK, December 18-20, 2007. Springer, Heidelberg (2007), eprint.iacr.org/2006/402/ ; Also presented at ECRYPT workshop Tools for Cryptanalysis, Krakow, September 24-25 (2007)
Bard, G.V., Courtois, N.T., Jefferson, C.: Efficient Methods for Conversion and Solution of Sparse Systems of Low-Degree Multivariate Polynomials over GF(2) via SAT-Solvers, http://eprint.iacr.org/2007/024/
Courtois, N., Bard, G.V., Wagner, D.: Algebraic and Slide Attacks on KeeLoq, Older preprint with using incorrect specification of KeeLoq, eprint.iacr.org/2007/062/
Courtois, N., Bard, G.V., Wagner, D.: An Improved Algebraic-Slide Attack on KeeLoq, A sequel to the oresent paper (preprint available from the authors)
Biham, E., Dunkelman, O., Indesteege, S., Keller, N., Preneel, B.: How to Steal Cars – A Practical Attack on KeeLoq, Crypto 2007, rump session talk (2007); Full paper will be presented at Eurocrypt 2008 and published in Springer LNCS, http://www.cosic.esat.kuleuven.be/keeloq/keeloq-rump.pdf
Faugère, J.-C.: A new efficient algorithm for computing Gröbner bases (F4). Journal of Pure and Applied Algebra 139, 61–88 (1999), www.elsevier.com/locate/jpaa
Flajolet, P., Sedgewick, R.: Analytic Combinatorics, 807 pages. Cambridge University Press, Cambridge (to appear, 2008), http://algo.inria.fr/flajolet/Publications/book.pdf
Phan, R.C.-W., Furuya, S.: Sliding Properties of the DES Key Schedule and Potential Extensions to the Slide Attacks. In: Lee, P.J., Lim, C.H. (eds.) ICISC 2002. LNCS, vol. 2587, pp. 138–148. Springer, Heidelberg (2003)
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)
Granboulan, L., Pornin, T.: Perfect Block Ciphers with Small Blocks. In: Biryukov, A. (ed.) FSE 2007. LNCS, vol. 4593, pp. 452–465. Springer, Heidelberg (2007)
Gemplus Combats SIM Card Cloning with Strong Key Security Solution, Press release, Paris ( November 5, 2002), http://www.gemalto.com/press/gemplus/2002/r_d/strong_key_05112002.htm
Grossman, E.K., Tuckerman, B.: Analysis of a Feistel-like cipher weakened by having no rotating key, IBM Thomas J. Watson Research Report RC 6375 (1977)
Kahn, D.: The Codebreakers, The Comprehensive History of Secret Communication from Ancient Times to the Internet (first published in 1967) (new chapter added in 1996)
Marraro, L., Massacci, F.: Towards the Formal Verification of Ciphers: Logical Cryptanalysis of DES. In: Proc. Third LICS Workshop on Formal Methods and Security Protocols, Federated Logic Conferences (FLOC 1999) (1999)
Microchip. An Introduction to KeeLoq Code Hopping (1996), http://ww1.microchip.com/downloads/en/AppNotes/91002a.pdf
Microchip. Hopping Code Decoder using a PIC16C56, AN642 (1998), http://www.keeloq.boom.ru/decryption.pdf
Microchip. Using KeeLoq to Validate Subsystem Compatibility, AN827 (2002), http://ww1.microchip.com/downloads/en/AppNotes/00827a.pdf
MiniSat 2.0. An open-source SAT solver package, by Niklas Eén, Niklas Sörensson, http://www.cs.chalmers.se/Cs/Research/FormalMethods/MiniSat/
Mironov, I., Zhang, L.: Applications of SAT Solvers to Cryptanalysis of Hash Functions. In: Biere, A., Gomes, C.P. (eds.) SAT 2006. LNCS, vol. 4121, pp. 102–115. Springer, Heidelberg (2006), http://eprint.iacr.org/2006/254
Riedel, M.R.: Random Permutation Statistics, http://www.geocities.com/markoriedelde/papers/randperms.pdf
Singular, A.: Free Computer Algebra System for polynomial computations, http://www.singular.uni-kl.de/
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Courtois, N.T., Bard, G.V., Wagner, D. (2008). Algebraic and Slide Attacks on KeeLoq. In: Nyberg, K. (eds) Fast Software Encryption. FSE 2008. Lecture Notes in Computer Science, vol 5086. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-71039-4_6
Download citation
DOI: https://doi.org/10.1007/978-3-540-71039-4_6
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-71038-7
Online ISBN: 978-3-540-71039-4
eBook Packages: Computer ScienceComputer Science (R0)