Periodic Ciphers with Small Blocks and Cryptanalysis of KeeLoq

Nicolas T. Courtois; Gregory V. Bard; Andrey Bogdanov

Periodic Ciphers with Small Blocks and Cryptanalysis of KeeLoq

Nicolas T. Courtois, Gregory V. Bard, Andrey Bogdanov

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

Abstract

KeeLoq is a lightweight block cipher that is massively used in the automobile industry [12, 13, 31, 32]. KeeLoq has two remarkable properties: it is periodic and has a very short block size (32 bits). Many different attacks on KeeLoq have been published in recent years [8, 15, 9, 10, 5]. In this paper we study a unique way of attacking KeeLoq, in which the periodic property of KeeLoq is used in to distinguish 512 rounds of KeeLoq from a random permutation. Our attacks require the knowledge of the entire code-book and are not among the fastest attacks known on this cipher. However one of them works for 100 % of all keys, including so called "strong keys", see [15]. In general, it is important to show how many different attacks are possible on a weak cipher such as KeeLoq.

Original language	English
Title of host publication	Tatracrypt '07 - 7th Central Europe Conference Of Cryptology
Publisher	Slovak Academy Sciences Mathematical Institute
Publication date	2008
Pages	167-188
Publication status	Published - 2008
Event	7th Central European Conference on Cryptology (TATRACRYPT 2007) - Smolenice, Slovakia Duration: 22 Jun 2007 → 24 Jun 2007 http://zeus.fei.stuba.sk/Katedry/KAIVT/Tatracrypt2007/

Conference

Conference	7th Central European Conference on Cryptology (TATRACRYPT 2007)
Country/Territory	Slovakia
City	Smolenice
Period	22/06/2007 → 24/06/2007
Internet address	http://zeus.fei.stuba.sk/Katedry/KAIVT/Tatracrypt2007/

Series	Tatra Mountains Mathematical Publications
Volume	41
ISSN	1210-3195

OpenUrl availability

Full text

Cite this

@inproceedings{5a99d3112e7f4b4aa37f1cd3a5954496,

title = "Periodic Ciphers with Small Blocks and Cryptanalysis of KeeLoq",

abstract = "KeeLoq is a lightweight block cipher that is massively used in the automobile industry [12, 13, 31, 32]. KeeLoq has two remarkable properties: it is periodic and has a very short block size (32 bits). Many different attacks on KeeLoq have been published in recent years [8, 15, 9, 10, 5]. In this paper we study a unique way of attacking KeeLoq, in which the periodic property of KeeLoq is used in to distinguish 512 rounds of KeeLoq from a random permutation. Our attacks require the knowledge of the entire code-book and are not among the fastest attacks known on this cipher. However one of them works for 100 % of all keys, including so called {"}strong keys{"}, see [15]. In general, it is important to show how many different attacks are possible on a weak cipher such as KeeLoq.",

author = "Courtois, {Nicolas T.} and Bard, {Gregory V.} and Andrey Bogdanov",

year = "2008",

language = "English",

series = "Tatra Mountains Mathematical Publications",

publisher = "Slovak Academy Sciences Mathematical Institute",

pages = "167--188",

booktitle = "Tatracrypt '07 - 7th Central Europe Conference Of Cryptology",

note = "7th Central European Conference on Cryptology (TATRACRYPT 2007) ; Conference date: 22-06-2007 Through 24-06-2007",

url = "http://zeus.fei.stuba.sk/Katedry/KAIVT/Tatracrypt2007/",

}

Courtois, NT, Bard, GV & Bogdanov, A 2008, Periodic Ciphers with Small Blocks and Cryptanalysis of KeeLoq. in Tatracrypt '07 - 7th Central Europe Conference Of Cryptology. Slovak Academy Sciences Mathematical Institute, Tatra Mountains Mathematical Publications, vol. 41, pp. 167-188, 7th Central European Conference on Cryptology (TATRACRYPT 2007), Smolenice, Slovakia, 22/06/2007.

Periodic Ciphers with Small Blocks and Cryptanalysis of KeeLoq. / Courtois, Nicolas T.; Bard, Gregory V.; Bogdanov, Andrey.
Tatracrypt '07 - 7th Central Europe Conference Of Cryptology. Slovak Academy Sciences Mathematical Institute, 2008. p. 167-188 (Tatra Mountains Mathematical Publications, Vol. 41).

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

TY - GEN

T1 - Periodic Ciphers with Small Blocks and Cryptanalysis of KeeLoq

AU - Courtois, Nicolas T.

AU - Bard, Gregory V.

AU - Bogdanov, Andrey

PY - 2008

Y1 - 2008

N2 - KeeLoq is a lightweight block cipher that is massively used in the automobile industry [12, 13, 31, 32]. KeeLoq has two remarkable properties: it is periodic and has a very short block size (32 bits). Many different attacks on KeeLoq have been published in recent years [8, 15, 9, 10, 5]. In this paper we study a unique way of attacking KeeLoq, in which the periodic property of KeeLoq is used in to distinguish 512 rounds of KeeLoq from a random permutation. Our attacks require the knowledge of the entire code-book and are not among the fastest attacks known on this cipher. However one of them works for 100 % of all keys, including so called "strong keys", see [15]. In general, it is important to show how many different attacks are possible on a weak cipher such as KeeLoq.

AB - KeeLoq is a lightweight block cipher that is massively used in the automobile industry [12, 13, 31, 32]. KeeLoq has two remarkable properties: it is periodic and has a very short block size (32 bits). Many different attacks on KeeLoq have been published in recent years [8, 15, 9, 10, 5]. In this paper we study a unique way of attacking KeeLoq, in which the periodic property of KeeLoq is used in to distinguish 512 rounds of KeeLoq from a random permutation. Our attacks require the knowledge of the entire code-book and are not among the fastest attacks known on this cipher. However one of them works for 100 % of all keys, including so called "strong keys", see [15]. In general, it is important to show how many different attacks are possible on a weak cipher such as KeeLoq.

M3 - Article in proceedings

T3 - Tatra Mountains Mathematical Publications

SP - 167

EP - 188

BT - Tatracrypt '07 - 7th Central Europe Conference Of Cryptology

PB - Slovak Academy Sciences Mathematical Institute

T2 - 7th Central European Conference on Cryptology (TATRACRYPT 2007)

Y2 - 22 June 2007 through 24 June 2007

ER -

Periodic Ciphers with Small Blocks and Cryptanalysis of KeeLoq

Abstract

Conference

OpenUrl availability

Fingerprint

Cite this