Welcome to the resource topic for 2019/938
Title:
Low-Memory Attacks against Two-Round Even-Mansour using the 3-XOR Problem
Authors: Gaëtan Leurent, 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 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 O(2^n (\ln^2{n/n^2}), improving the previous asymptotic complexity of O(2^n/n), using a variant of the 3-SUM algorithm of Baran, Demaine, and Patrascu.
ePrint: https://eprint.iacr.org/2019/938
Talk: https://www.youtube.com/watch?v=MgeRjuMLBTM
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .