Cryptology ePrint Archive: Report 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.

Category / Keywords: secret-key cryptography / Cryptanalysis, meet-in-the-middle attacks, iterated Even-Mansour, LED-128, 2K3DES.

Date: received 21 Oct 2013

Contact author: dinur at di ens fr

Available format(s): PDF | BibTeX Citation

Version: 20131024:084359 (All versions of this report)

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]