Paper 2013/674

Cryptanalysis of Iterated Even-Mansour Schemes with Two Keys

Eli Biham and Yaniv Carmeli and Itai Dinur and Orr Dunkelman and Nathan Keller and Adi Shamir

Abstract

The iterated Even-Mansour (EM) scheme is a generalization of the original 1-round construction proposed in 1991, and can use one key, two keys, or completely independent keys. In this paper, we methodically analyze the security of all the possible iterated Even-Mansour schemes with two $n$-bit keys and up to four rounds, and show that none of them provides more than $n$-bit security. In particular, we can apply one of our new attacks to 4 steps of the LED-128 block cipher, reducing the time complexity of the best known attack on this scheme from $2^{96}$ to $2^{64}$. As another example of the broad applicability of our techniques, we show how to reduce the time complexity of the attack on two-key triple-DES (which is an extremely well studied and widely deployed scheme) when fewer than $2^n$ known plaintext-ciphertext pairs are given. Our attacks are based on a novel cryptanalytic technique called \emph{multibridge} which connects different parts of the cipher such that they can be analyzed independently, exploiting its self-similarity properties. Finally, the key suggestions of the different parts are efficiently joined using a meet-in-the-middle attack.