Paper 2013/634

Improved Linear Sieving Techniques with Applications to Step-Reduced LED-64

Itai Dinur, Orr Dunkelman, Nathan Keller, and Adi Shamir

Abstract

In this paper, we describe new techniques in meet-in-the-middle attacks. Our basic technique is called a \emph{linear key sieve} since it exploits as filtering conditions linear dependencies between key bits that are guessed from both sides of the attack. This should be contrasted with related previous attacks, which only exploited a \emph{linear state sieve} (i.e., linear dependencies between state bits that are computed from both sides of the attack). We apply these techniques to the lightweight block cipher LED-64, and improve some of the best known attacks on step-reduced variants of this cipher in all attack models. As a first application of the linear key sieve, we describe a chosen plaintext attack on 2-step LED-64, which reduces the time complexity of the best previously published attack on this variant from $2^{56}$ to $2^{48}$. Then, we present the first attack on 2-step LED-64 in the \emph{known plaintext model}. In this attack, we show for the first time that the splice-and-cut technique (which inherently requires chosen messages) can also be applied in the known plaintext model, and we use the linear key sieve in order to obtain an attack with the same time complexity as our chosen plaintext attack. Finally, we describe a related-key attack on 3-step LED-64 which improves the best previously published attack (presented at Asiacrypt 2012) in all the complexity parameters of time/data/memory from $2^{60}$ to $2^{49}$. As our first two single-key attacks, the related-key attack is also based on the linear key sieve, but it uses additional techniques in differential meet-in-the-middle which are interesting in their own right.