Random Permutation Statistics and An Improved Slide-Determine Attack on KeeLoq.
In: Naccache, D, (ed.)
Festschrift Jean-Jacques Quisquater.
Springer-Verlag: Berlin/Heidelberg, Germany.
Available under License : See the attached licence file.
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  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.
|Title:||Random Permutation Statistics and An Improved Slide-Determine Attack on KeeLoq|
|Open access status:||An open access version is available from UCL Discovery|
|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|
Archive Staff Only