Periodic Ciphers with Small Blocks and Cryptanalysis of KeeLoq
Nicolas T. Courtois, Gregory V. Bard, Andrey Bogdanov · Tatra Mountains Mathematical Publications · 2008
ABSTRACT. KeeLoq is a lightweight block cipher that is massively used in theautomobile industry [12, 13, 31, 32]. KeeLoq has two remarkable properties: itis periodic and has a very short block size (32 bits). Many difierent attacks onKeeLoq have been published in recent years [8, 15, 9, 10, 5]. In this paper we studya unique way of attacking KeeLoq, in which the periodic property of KeeLoq isused in to distinguish 512 rounds of KeeLoq from a random permutation. Ourattacks require the knowledge of the entire code-book and are not among thefastest attacks known on this cipher. However one of them works for 100 % ofall including so called \strong keys, see [15]. In general, it is important toshow how many difierent attacks are possible on a weak cipher such as KeeLoq. 1. Introduction KeeLoq was designed in the 1980’s by Willem Smit from South Africa [36].It is a block cipher used in wireless devices that unlock the doors of cars manu-factured by Chrysler, Daewoo, Fiat, GM, Honda, Jaguar, Toyota, Volvo, Volk-swagen, etc...[12, 13, 31, 32]. In 1995 KeeLoq was sold to Microchip TechnologyInc. for more than 10 million US dollars (which is documented in [12]). FollowingMicrochip, [33], the speciflcation of KeeLoq is ot secret but is patented andwas released only under license. The question whether one can really break intocars, and how, is a secondary one in a scientiflc paper. The main question iswhat ciphers could be broken, how, due to what properties, and how to designbetter ciphers.KeeLoq operates with 32-bit blocks and 64-bit keys. Compared to the typ-ical block ciphers which have a few carefully-designed rounds, this cipher has528 extremely simple rounds with extremely few intermediate variables (in ourformulation one per round). Also, only one bit of the state is modifled in eachround. As a result, KeeLoq can be implemented very e–ciently in hardware.