CryptoDB
Algebraic and Slide Attacks on KeeLoq
| Authors: | |
|---|---|
| Download: | |
| 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. |
BibTeX
@misc{eprint-2007-13344,
title={Algebraic and Slide Attacks on KeeLoq},
booktitle={IACR Eprint archive},
keywords={secret-key cryptography / algebraic attacks on block ciphers, SAT solvers},
url={http://eprint.iacr.org/2007/062},
note={ n.courtois@ucl.ac.uk 13740 received 19 Feb 2007, last revised 15 Aug 2007},
author={Nicolas T. Courtois and Gregory V. Bard and David Wagner},
year=2007
}