## CryptoDB

### Paper: Low-Memory Attacks Against Two-Round Even-Mansour Using the 3-XOR Problem

Authors: Gaëtan Leurent Ferdinand Sibleyras DOI: 10.1007/978-3-030-26951-7_8 Search ePrint Search Google 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 $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 3-XOR problem with element size $\ell = 2n$, an important algorithmic problem that has been studied since the nineties. In particular the 3-XOR problem is known to require at least $2^{\ell /3}$ queries, and the best known algorithms require around $2^{\ell /2}/\ell$ 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 $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 brute-force 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 brute-force search. We also describe an algorithm with asymptotic complexity $\mathcal {O}(2^{n} \ln ^2 n/n^2)$, improving the previous asymptotic complexity of $\mathcal {O}(2^n/n)$, using a variant of the 3-SUM algorithm of Baran, Demaine, and Pǎtraşcu.
##### BibTeX
@article{crypto-2019-29887,
title={Low-Memory Attacks Against Two-Round Even-Mansour Using the 3-XOR Problem},
booktitle={Advances in Cryptology – CRYPTO 2019},
series={Lecture Notes in Computer Science},
publisher={Springer},
volume={11693},
pages={210-235},
doi={10.1007/978-3-030-26951-7_8},
author={Gaëtan Leurent and Ferdinand Sibleyras},
year=2019
}