Paper 2019/938
LowMemory Attacks against TwoRound EvenMansour using the 3XOR Problem
Gaëtan Leurent and Ferdinand Sibleyras
Abstract
The iterated EvenMansour construction is an elegant construction that idealizes block cipher designs such as the AES. In this work we focus on the simplest variant, the 2round EvenMansour 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 $2^{2n/3}$ evaluations of the underlying permutations and encryption, and the best known attacks have a complexity of roughly $2^n/n$ operations. We show that attacking this scheme with block size $n$ is related to the 3XOR problem with element size $w = 2n$, an important algorithmic problem that has been studied since the nineties. In particular the 3XOR problem is known to require at least $2^{w/3}$ queries, and the best known algorithms require around $2^{w/2} / w$ operations: this roughly matches the known bounds for the 2round EvenMansour scheme. Using this link we describe new attacks against the 2round EvenMansour scheme. In particular, we obtain the first algorithms where both the data and the memory complexity are significantly lower than $2^n$ . From a practical standpoint, previous works with a data and/or memory complexity close to $2^n$ are unlikely to be more efficient than a simple bruteforce search over the key. Our best algorithm requires just $\lambda n$ known plaintext/ciphertext pairs, for some constant $0 < \lambda < 1$, $2^n/\lambda n$ time, and $2^{\lambda n}$ memory. For instance, with $n = 64$ and $\lambda = 1/2$, the memory requirement is practical, and we gain a factor 32 over bruteforce search. We also describe an algorithm with asymptotic complexity $O(2^n (\ln^2{n/n^2})$, improving the previous asymptotic complexity of $O(2^n/n)$, using a variant of the 3SUM algorithm of Baran, Demaine, and Patrascu.
Metadata
 Available format(s)
 Category
 Secretkey cryptography
 Publication info
 Published by the IACR in CRYPTO 2019
 DOI
 10.1007/9783030269517_8
 Keywords
 EvenMansourCryptanalysis3XOR
 Contact author(s)

gaetan leurent @ inria fr
ferdinand sibleyras @ inria fr  History
 20190818: received
 Short URL
 https://ia.cr/2019/938
 License

CC BY
BibTeX
@misc{cryptoeprint:2019/938, author = {Gaëtan Leurent and Ferdinand Sibleyras}, title = {LowMemory Attacks against TwoRound EvenMansour using the 3XOR Problem}, howpublished = {Cryptology ePrint Archive, Paper 2019/938}, year = {2019}, doi = {10.1007/9783030269517_8}, note = {\url{https://eprint.iacr.org/2019/938}}, url = {https://eprint.iacr.org/2019/938} }