Periodic Ciphers with Small Blocks and Cryptanalysis of KeeLoq

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

    Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-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 languageEnglish
    Title of host publicationTatracrypt '07 - 7th Central Europe Conference Of Cryptology
    PublisherSlovak Academy Sciences Mathematical Institute
    Publication date2008
    Pages167-188
    Publication statusPublished - 2008
    Event7th Central European Conference on Cryptology (TATRACRYPT 2007) - Smolenice, Slovakia
    Duration: 22 Jun 200724 Jun 2007
    http://zeus.fei.stuba.sk/Katedry/KAIVT/Tatracrypt2007/

    Conference

    Conference7th Central European Conference on Cryptology (TATRACRYPT 2007)
    CountrySlovakia
    CitySmolenice
    Period22/06/200724/06/2007
    Internet address
    SeriesTatra Mountains Mathematical Publications
    Volume41
    ISSN1210-3195

    Cite this

    Courtois, N. T., Bard, G. V., & Bogdanov, A. (2008). Periodic Ciphers with Small Blocks and Cryptanalysis of KeeLoq. In Tatracrypt '07 - 7th Central Europe Conference Of Cryptology (pp. 167-188). Slovak Academy Sciences Mathematical Institute. Tatra Mountains Mathematical Publications, Vol.. 41
    Courtois, Nicolas T. ; Bard, Gregory V. ; Bogdanov, Andrey. / Periodic Ciphers with Small Blocks and Cryptanalysis of KeeLoq. Tatracrypt '07 - 7th Central Europe Conference Of Cryptology. Slovak Academy Sciences Mathematical Institute, 2008. pp. 167-188 (Tatra Mountains Mathematical Publications, Vol. 41).
    @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",

    }

    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 proceedingArticle in proceedingsResearchpeer-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

    ER -

    Courtois NT, Bard GV, Bogdanov A. Periodic Ciphers with Small Blocks and Cryptanalysis of KeeLoq. In Tatracrypt '07 - 7th Central Europe Conference Of Cryptology. Slovak Academy Sciences Mathematical Institute. 2008. p. 167-188. (Tatra Mountains Mathematical Publications, Vol. 41).