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.
Category / Keywords: secret-key cryptography / algebraic attacks on block ciphers, SAT solvers Date: received 19 Feb 2007, last revised 15 Aug 2007 Contact author: n courtois at ucl ac uk Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation Note: updated Version: 20070815:095746 (All versions of this report) Short URL: ia.cr/2007/062 Discussion forum: Show discussion | Start new discussion