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
Self-similarity Attacks on Block Ciphers and Application to KeeLoq
  • Publication Type:
    Chapter
  • Authors:
    COURTOIS N
  • Publication date:
    2011
  • Volume:
    6805
  • Series:
    Lecture Notes in Computer Science
  • Editors:
    Naccache D
  • Status:
    In preparation
  • Book title:
    Quisquater Festschrift
  • Language:
    English
  • Publisher URL:
  • Notes:
    in press, to appear in late 2011
Abstract
KeeLoq is a lightweight cipher that is widely used in car locks. The fastest known attack on KeeLoq is a Slide-Determine attack by Bard, Courtois and Wagner with a complexity of 2p28 KeeLoq computations. However this attack requires the knowledge of the whole code-book of 2p32 known plaintexts, which is totally unrealistic. The first attack on KeeLoq with a far more realistic requirement of 2p16 known plaintexts was proposed by Courtois, Bard and Wagner [FSE 2008] and can be used to clone KeeLoq devices in practice. Later, Dunkelman et al. proposed another faster attack in this setting. From the practitioner point of view, the question remains however what is the best attack in the weakest possible setting, when the attacker is given only two (or a bit more) known plaintexts (one does not suffice due to the key size being larger than block size). In this case, the fastest known attack on KeeLoq remains brute force, which is actually feasible and reportedly criminals implement this attack in FPGA to steal cars. In this paper we show that there is a better attack. More precisely, we show that due to a self-similarity property of KeeLoq the exhaustive key search process can be substantially accelerated and the security of KeeLoq is strictly lower as soon as the adversary disposes of two chosen plaintexts. Then we get an attack faster then brute force. Independently, these attacks can be improved by a factor of 2 with some storage. Due to the protocol used, our attacks are realistic and allow to clone a KeeLoq entry devices more easily than previously thought. In this paper we introduce a new general and powerful attack on block ciphers, a self-similarity attack. It is strictly more general than sliding attacks. For KeeLoq, but also for DES, self-similarity allows to speed up the brute force attack on the cipher. Both in case of DES and KeeLoq brute force is the most realistic attack known, and it can be improved by a self similarity attack, at the price of a chosen plaintext attack. Only 2 chosen plaintexts are needed in all these attacks.
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