UCL  IRIS
Institutional Research Information Service
UCL Logo
Please report any queries concerning the funding data grouped in the sections named "Externally Awarded" or "Internally Disbursed" (shown on the profile page) to your Research Finance Administrator. Your can find your Research Finance Administrator at http://www.ucl.ac.uk/finance/research/post_award/post_award_contacts.php by entering your department
Please report any queries concerning the student data shown on the profile page to:

Email: portico-services@ucl.ac.uk

Help Desk: http://www.ucl.ac.uk/ras/portico/helpdesk
Publication Detail
Random Permutation Statistics and An Improved Slide-Determine Attack on KeeLoq
  • Publication Type:
    Conference
  • Authors:
    Courtois NT, Bard GV
  • Publisher:
    Springer-Verlag
  • Publication date:
    2011
  • Place of publication:
    Berlin/Heidelberg, Germany
  • Published proceedings:
    Festschrift Jean-Jacques Quisquater
  • Volume:
    6805
  • Series:
    Lecture Notes in Computer Science
  • Editors:
    Naccache D
  • Status:
    Accepted
  • Language:
    English
  • Keywords:
    block ciphers, highly-unbalanced compressing Feistel ciphers, random permutation statistics, slide attacks, KeeLoq, automobile locks
  • Notes:
    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
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.
Publication data is maintained in RPS. Visit https://rps.ucl.ac.uk
 More search options
UCL Researchers
Author
Dept of Computer Science
University College London - Gower Street - London - WC1E 6BT Tel:+44 (0)20 7679 2000

© UCL 1999–2011

Search by