Paper 2019/938

Low-Memory Attacks against Two-Round Even-Mansour using the 3-XOR Problem

Gaëtan Leurent and Ferdinand Sibleyras

Abstract

The iterated Even-Mansour construction is an elegant construction that idealizes block cipher designs such as the AES. In this work we focus on the simplest variant, the 2-round Even-Mansour construction with a single key. This is the most minimal construction that offers security beyond the birthday bound: there is a security proof up to 22n/3 evaluations of the underlying permutations and encryption, and the best known attacks have a complexity of roughly 2n/n operations. We show that attacking this scheme with block size n is related to the 3-XOR problem with element size w=2n, an important algorithmic problem that has been studied since the nineties. In particular the 3-XOR problem is known to require at least 2w/3 queries, and the best known algorithms require around 2w/2/w operations: this roughly matches the known bounds for the 2-round Even-Mansour scheme. Using this link we describe new attacks against the 2-round Even-Mansour scheme. In particular, we obtain the first algorithms where both the data and the memory complexity are significantly lower than . From a practical standpoint, previous works with a data and/or memory complexity close to are unlikely to be more efficient than a simple brute-force search over the key. Our best algorithm requires just known plaintext/ciphertext pairs, for some constant , time, and memory. For instance, with and , the memory requirement is practical, and we gain a factor 32 over brute-force search. We also describe an algorithm with asymptotic complexity , improving the previous asymptotic complexity of , using a variant of the 3-SUM algorithm of Baran, Demaine, and Patrascu.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published by the IACR in CRYPTO 2019
DOI
10.1007/978-3-030-26951-7_8
Keywords
Even-MansourCryptanalysis3-XOR
Contact author(s)
gaetan leurent @ inria fr
ferdinand sibleyras @ inria fr
History
2019-08-18: received
Short URL
https://ia.cr/2019/938
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/938,
      author = {Gaëtan Leurent and Ferdinand Sibleyras},
      title = {Low-Memory Attacks against Two-Round Even-Mansour using the 3-{XOR} Problem},
      howpublished = {Cryptology {ePrint} Archive, Paper 2019/938},
      year = {2019},
      doi = {10.1007/978-3-030-26951-7_8},
      url = {https://eprint.iacr.org/2019/938}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.