Paper 2007/062

Algebraic and Slide Attacks on KeeLoq

Nicolas T. Courtois, 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