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.
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
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.
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
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
Algebraic attacks on block ciphers and AES
Algebraic attacks applied to stream ciphers
Maintained by Nicolas T. Courtois
Last updated on 17th of February2008.