UCL logo

UCL Discovery

UCL home » Library Services » Electronic resources » UCL Discovery

Random Permutation Statistics and An Improved Slide-Determine Attack on KeeLoq

Courtois, NT; Bard, GV; (2011) Random Permutation Statistics and An Improved Slide-Determine Attack on KeeLoq. In: Naccache, D, (ed.) Festschrift Jean-Jacques Quisquater. Springer-Verlag: Berlin/Heidelberg, Germany. (In press). Green open access

[img]
Preview
PDF - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
253Kb

Abstract

KeeLoq is a lightweight block cipher which is extensively used in the automotive industry. Its periodic structure, and overall simplicity makes it vulnerable to many different attacks. Only certain attacks are considered as really "practical" attacks on KeeLoq: the brute force, and several other attacks which require up to 2p16 known plaintexts and are then much faster than brute force, developed by Courtois et al., and (faster attack) by Dunkelman et al. On the other hand, due to the unusually small block size, there are yet many other attacks on KeeLoq, which require the knowledge of as much as about 2p32 known plaintexts but are much faster still. There are many scenarios in which such attacks are of practical interest, for example if a master key can be recovered, see Section 2 in [11] for a detailed discussion. The fastest of these attacks is an attack by Courtois, Bard and Wagner from that has a very low complexity of about 2p28 KeeLoq encryptions on average. In this paper we will propose an improved and refined attack which is faster both on average and in the best case. We also present an exact mathematical analysis of probabilities that arise in these attacks using the methods of modern analytic combinatorics.

Type:Proceedings paper
Title:Random Permutation Statistics and An Improved Slide-Determine Attack on KeeLoq
Open access status:An open access version is available from UCL Discovery
Publisher version:http://www.springer.com/series/558
Additional information:Special volume to be published in the Springer Lecture Notes in Computer Science series in 2011, containing papers from the Jean-Jacques Quisquater Emeritus Workshop held at Louvain-La-Neuve, Belgium in 2010. The original publication will be available at www.springerlink.com
Keywords:block ciphers, highly-unbalanced compressing Feistel ciphers, random permutation statistics, slide attacks, KeeLoq, automobile locks
UCL classification:UCL > School of BEAMS > Faculty of Engineering Science > Computer Science

View download statistics for this item

Archive Staff Only: edit this record