Anzeige
Erschienen in:
2019 | OriginalPaper | Buchkapitel
Low-Memory Attacks Against Two-Round Even-Mansour Using the 3-XOR Problem
verfasst von : Gaëtan Leurent, Ferdinand Sibleyras
Erschienen in: Advances in Cryptology – CRYPTO 2019
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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 \(\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.
.