Improved Linear Sieving Techniques with Applications to Step-Reduced LED-64
In this paper, the authors describe new techniques in meet-in-the-middle attacks. Their basic technique is called a 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 linear state sieve (i.e., linear dependencies between state bits that are computed from both sides of the attack). They 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.