Improved linear sieving techniques with applications to step-reduced LED-64

Itai Dinur; Orr Dunkelman; Nathan Keller; Adi Shamir

doi:10.1007/978-3-662-46706-0_20

Back

Improved linear sieving techniques with applications to step-reduced LED-64

Journal article

Peer reviewed

Improved linear sieving techniques with applications to step-reduced LED-64

Itai Dinur, Orr Dunkelman, Nathan Keller and Adi Shamir

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol.8540, pp.390-410

2015

DOI: https://doi.org/10.1007/978-3-662-46706-0_20

Files and links (2)

url

https://doi.org/10.1007/978-3-662-46706-0_20View

Published (Version of record) Restricted

url

https://ezproxy.weizmann.ac.il/login?url=http://dx.doi.org/10.1007/978-3-662-46706-0_20View

Published (Version of record) Restricted

Abstract

In this paper, we present advanced meet-in-the-middle (MITM) attacks against the lightweight block cipher LED-64, improving the best known attacks on several step-reduced variants of the cipher in both single-key and related-key models. In particular, we present a known-plaintext attack on 2-step LED-64 with complexity of 248 and a related-key attack on 3-step LED-64 with complexity of 249. In both cases, the previously known attacks have complexity of 260, i.e., only 16 times faster than exhaustive key search. While our attacks are applied to the specific scheme of LED-64, they contain several general methodological contributions: First, we present the linear key sieve technique, which allows to exploit linear dependencies between key bits to obtain filtering conditions in MITM attacks on block ciphers. While similar ideas have been previously used in the domain of hash functions, this is the first time that such a technique is applied in block cipher cryptanalysis. As a second contribution, we demonstrate for the first time that a splice-and-cut attack (which so far seemed to be an inherently chosen-plaintext technique) can be used in the knownplaintext model, with data complexity which is significantly below the code-book size. Finally, we extend the differential MITM attack on AESbased designs, and apply it independently in two stages from both sides of the cipher, while using the linear key sieve and other enhancements. International Association for Cryptologic Research 2015.

Details

Title: Improved linear sieving techniques with applications to step-reduced LED-64
Creators: Itai Dinur (null) - 972WIS_INST___83
Orr Dunkelman (null) - 972WIS_INST___83
Nathan Keller (null) - 972WIS_INST___84
Adi Shamir (null) - 972WIS_INST___83
Resource Type: Journal article
Publication Details: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol.8540, pp.390-410; 2015
Language: English
DOI: https://doi.org/10.1007/978-3-662-46706-0_20
Record Identifier: 993263456303596

Metrics

3 Record Views