Paper 2013/391

Key Recovery Attacks on 3-round Even-Mansour, 8-step LED-128, and Full $\mbox{AES}^{2}$

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


The Even-Mansour (EM) encryption scheme received a lot of attention in the last couple of years due to its exceptional simplicity and tight security proofs. The original $1$-round construction was naturally generalized into $r$-round structures with one key, two alternating keys, and completely independent keys. In this paper we describe the first key recovery attack on the one-key 3-round version of EM which is asymptotically faster than exhaustive search (in the sense that its running time is $o(2^n)$ rather than $O(2^n)$ for an $n$-bit key). We then use the new cryptanalytic techniques in order to improve the best known attacks on several concrete EM-like schemes. In the case of LED-128, the best previously known attack could only be applied to 6 of its 12 steps. In this paper we develop a new attack which increases the number of attacked steps to 8, is slightly faster than the previous attack on 6 steps, and uses about a thousand times less data. Finally, we describe the first attack on the full $\mbox{AES}^{2}$ (which uses two complete AES-128 encryptions and three independent $128$-bit keys, and looks exceptionally strong) which is about 7 times faster than a standard meet-in-the-middle attack, thus violating its security claim.

Available format(s)
Secret-key cryptography
Publication info
Published elsewhere. Minor revision. Extended version of the Asiacrypt 2013 paper
Contact author(s)
itai dinur @ weizmann ac il
2013-09-10: revised
2013-06-18: received
See all versions
Short URL
Creative Commons Attribution


      author = {Itai Dinur and Orr Dunkelman and Nathan Keller and Adi Shamir},
      title = {Key Recovery Attacks on 3-round Even-Mansour, 8-step LED-128, and Full $\mbox{AES}^{2}$},
      howpublished = {Cryptology ePrint Archive, Paper 2013/391},
      year = {2013},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.