You are looking at a specific version 20070815:095746 of this paper. See the latest version.

Paper 2007/062

Algebraic and Slide Attacks on KeeLoq

Nicolas T. Courtois and Gregory V. Bard and David Wagner

Abstract

KeeLoq is a block cipher used in wireless devices that unlock doors in cars manufactured by Chrysler, Daewoo, Fiat, GM, Honda, Jaguar, Toyota, Volvo, Volkswagen, etc. It was designed in the 80's by Willem Smit from South Africa and in 1995 was sold to Microchip Technology Inc for more than 10 million USD. Though no attack on this cipher have been found thus far, the 64-bit key size makes it no longer secure. Hackers and car thieves exploit this, to recover the key by brute force with FPGA's. From our point of view however, this cipher is interesting for other reasons. Compared to typical block ciphers that have a few carefully designed rounds, this cipher has 528 extremely simple rounds with extremely few intermediate variables (one per round). This seems a perfect target to study algebraic attacks on block ciphers. The cipher also has a periodic structure with period of 64 rounds, and an unusually small block size of 32 bits. We present several slide-algebraic attacks on KeeLoq, the best of which allows one to recover the full key for the full cipher within 2^48 CPU clocks. Until now algebraic attacks didn't give interesting results on block ciphers and most researchers seriously doubted if any block cipher will EVER be broken by such attacks. In this paper however, we show that, for the first time in history, a full round real-life block cipher is broken by an algebraic attack. Moreover, our attacks are easy to implement, have been tested experimentally, and the full key can be recovered in practice on a PC.

Note: updated

Metadata
Available format(s)
PDF PS
Category
Secret-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
algebraic attacks on block ciphersSAT solvers
Contact author(s)
n courtois @ ucl ac uk
History
2007-08-15: last of 7 revisions
2007-02-20: received
See all versions
Short URL
https://ia.cr/2007/062
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.