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 $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 $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 $2^{w/3}$ queries, and the best known algorithms require around $2^{w/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.