Cryptographic Security of KeeLoq

page maintained by Nicolas T. Courtois

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. It is used by millions of people every day. Until now, algebraic attacks on block ciphers did not yield interesting results and most researchers seriously doubted if any block cipher would ever be broken by such attacks.

Combination of algebraic attacks and periodic (sliding) properties of KeeLoq allows to design many interesting attacks. KeeLoq have been sold in 1995 for 10 million dollars.

Main References on KeeLoq.

- Nicolas T. Courtois and Gregory V. Bard Random Permutation Statistics and An Improved Slide-Determine Attack on KeeLoq To appear in a special volume published in Springer LNCS series in 2010, David Naccache editor.
- Here is wikipedia KeeLoq entry.
- Here is KeeLoq source code by Ruptor (was updated in 2007 and now is really correct).
- A clever and very practical attack is by Biham, Dunkelman, Indesteege, Keller, Preneel see Crypto 2007 rump session.
- The fastest attack known is: Nicolas Courtois, Gregory V. Bard and David Wagner: Algebraic and Slide Attacks on KeeLoq. This paper describes the fastest attack ever found on KeeLoq. The complexity of the latter is about 2^28 KeeLoq encryptions on average (improved in another paper see above). The paper was presented at Fast Software Encryption 2008, Lausanne, Switzerland, February 10-13, 2008. See also Nicolas Courtois, Gregory V. Bard, David Wagner: Algebraic and Slide Attacks on KeeLoq. Very very old version / preprint - not updated, at http://eprint.iacr.org/2007/062/.
- Another attack in the same paper is also historically the first attack proposed that requires only 2^16 known plaintexts, and that remains the simplest attack ever found. It is also the first successful algebraic attack in history that breaks a full round real-life industrial block cipher.
- Nicolas T. Courtois: Self-similarity Attacks on Block Ciphers and Application to KeeLoq, In International Workshop on Coding and Cryptography, May 10-15, 2009, Ullensvang, Norway. Presented at the workshop and present in printed pre-proceedings but withdrawn from printed final proceedings, will be published elsewhere.
- Nicolas Courtois: Improved Brute Force Attacks on KeeLoq, In 6th ESCAR conference - Embedded Security in Cars 2008. Hotel Hafen Hamburg (Germany), 18-19 November 2008.
- Several other attacks were found by Andrey Bogdanov, let us quote only one of them, : Cryptanalysis of the KeeLoq block cipher. Preprint. Available at http://eprint.iacr.org/2007/055/.
- Nicolas Courtois, Gregory V. Bard and Andrey Bogdanov: Periodic Ciphers with Small Blocks and Cryptanalysis of KeeLoq , In Tatra Mountains Mathematic Publications, 41 (2008), pp. 167-188, post-proceedings of Tatracrypt 2007 conference.
- Sean O'Neil, Nicolas Courtois: Reverse-engineered Philips/NXP Hitag2 Cipher, presented at the rump session of FSE 2008, Lausanne, 12 February 2008. Source code + nice picture can be found here.
- Experimental algebraic cryptanalysis of block ciphers - web page.
- Presentation New Frontiers in Symmetric Cryptanalysis, from the invited talk given by N. Courtois at at ECRYPT workshop Tools for Cryptanalysis in Krakow, 24-25 September, full version is available here.

Some links:

Algebraic attacks on block ciphers and AES

Algebraic attacks applied to stream ciphers

Maintained by Nicolas T. Courtois

Last updated on 17th of February2008.