Linear slide attacks on the KeeLoq block cipher

Andrey Bogdanov

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

Abstract

KeeLoq is a block cipher used in numerous widespread passive entry and remote keyless entry systems as well as ill various component identification applications. The KeeLoq algorithm has a 64-bit key and operates on 32-bit blocks. It is based oil all NLFSR with a nonlinear feedback function of 5 variables. In this paper new key recovery attacks on KeeLoq are proposed. The first one has a complexity of about 2(50.6) KeeLoq encryptions. The second attack finds the key in 2(37) encryptions and works for the whole key space. In our attacks we use the techniques of guess-and-determine, slide, and linear attacks as well as cycle structure analysis. Both attacks need 2(32) known plaintext-ciphertext pairs. We also analyze the KeeLoq key management and authentication protocols applied in rolling-code and IFF access systems widely used in real-world applications. We demonstrate several practical vulnerabilities.
Original languageEnglish
Title of host publicationInformation Security and Cryptology
PublisherSpringer
Publication date2008
Pages66-80
ISBN (Print)978-3-540-79498-1
ISBN (Electronic) 978-3-540-79499-8
Publication statusPublished - 2008
Externally publishedYes
Event3rd SKLOIS Conference, Inscrypt 2007 - Xining, China
Duration: 31 Aug 20075 Sep 2007

Conference

Conference3rd SKLOIS Conference, Inscrypt 2007
CountryChina
CityXining
Period31/08/200705/09/2007
SeriesLecture Notes in Computer Science
Volume4990
ISSN0302-9743

Cite this

Bogdanov, A. (2008). Linear slide attacks on the KeeLoq block cipher. In Information Security and Cryptology (pp. 66-80). Springer. Lecture Notes in Computer Science, Vol.. 4990