Courtois, NT;
Bard, GV;
Wagner, D;
(2008)
Algebraic and Slide Attacks on KeeLoq.
In: Nyberg, K, (ed.)
Fast Software Encryption. FSE 2008.
(pp. pp. 97-115).
Springer: Berlin, Germany.
![[thumbnail of keyloq.pdf]](https://discovery.ucl.ac.uk/style/images/fileicons/text.png) Preview |
Text
keyloq.pdf Available under License : See the attached licence file. Download (240kB) |
Abstract
KeeLoq is a block cipher used in wireless devices that unlock the doors and alarms in cars manufactured by Chrysler, Daewoo, Fiat, GM, Honda, Jaguar, Toyota, Volvo, Volkswagen, etc [8,9,33,34]. KeeLoq is inexpensive to implement and economical in gate count, yet according to Microchip [33] it should have “a level of security comparable to DES”. In this paper we present several distinct attacks on KeeLoq, each of them is interesting for different reasons. First we show that when about 232 known plaintexts are available, KeeLoq is very weak and for example for 30% of all keys the full key can be recovered with complexity of 228 KeeLoq encryptions. Then we turn our attention to algebraic attacks with the major challenge of breaking KeeLoq given potentially a very small number of known plaintexts. Our best “direct” algebraic attack can break up to 160 rounds of KeeLoq. Much better results are achieved in combination with slide attacks. Given about 216 known plaintexts, we present a slide-algebraic attack that uses a SAT solver with the complexity equivalent to about 253 KeeLoq encryptions. To the best of our knowledge, this is the first time that a full-round real-life block cipher is broken using an algebraic attack.
| Type: | Proceedings paper |
|---|---|
| Title: | Algebraic and Slide Attacks on KeeLoq |
| Event: | 15th International Workshop on Fast Software Encryption |
| Location: | Lausanne, SWITZERLAND |
| Dates: | 10 February 2008 - 13 February 2008 |
| ISBN-13: | 978-3-540-71038-7 |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.1007/978-3-540-71039-4_6 |
| Publisher version: | https://doi.org/10.1007/978-3-540-71039-4_6 |
| Language: | English |
| Additional information: | This version is the author accepted manuscript. For information on re-use, please refer to the publisher’s terms and conditions. |
| Keywords: | Science & Technology, Technology, Computer Science, Software Engineering, Computer Science, Theory & Methods, Computer Science, block ciphers, unbalanced Feistel ciphers, slide attacks, algebraic cryptanalysis, Grobner bases, SAT solvers, KeeLoq, BLOCK CIPHERS, OVERDEFINED SYSTEMS, CRYPTANALYSIS, ALGORITHM, EQUATIONS |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science |
| URI: | https://discovery.ucl.ac.uk/id/eprint/20441 |
Loading...
Loading...Loading...Loading...Archive Staff Only
 |
View Item |
