Key-Recovery Security of Single-Key Even-Mansour Ciphers

Takanori ISOBE  Kyoji SHIBUTANI  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E103-A   No.7   pp.893-905
Publication Date: 2020/07/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.2019EAP1118
Type of Manuscript: PAPER
Category: Cryptography and Information Security
block cipher,  Even-Mansour ciphers,  meet-in-the-middle attack,  key recovery,  partial invariable pair,  matching with the input-restricted public permutation,  

Full Text: PDF(920.9KB)>>
Buy this Article

In this paper, we explore the security of single-key Even-Mansour ciphers against key-recovery attacks. First, we introduce a simple key-recovery attack using key relations on an n-bit r-round single-key Even-Mansour cipher (r-SEM). This attack is feasible with queries of DTr=O(2rn) and $2^{ rac{2r}{r + 1}n}$ memory accesses, which is $2^{ rac{1}{r + 1}n}$ times smaller than the previous generic attacks on r-SEM, where D and T are the number of queries to the encryption function EK and the internal permutation P, respectively. Next, we further reduce the time complexity of the key recovery attack on 2-SEM by a start-in-the-middle approach. This is the first attack that is more efficient than an exhaustive key search while keeping the query bound of DT2=O(22n). Finally, we leverage the start-in-the-middle approach to directly improve the previous attacks on 2-SEM by Dinur et al., which exploit t-way collisions of the underlying function. Our improved attacks do not keep the bound of DT2=O(22n), but are the most time-efficient attacks among the existing ones. For n=64, 128 and 256, our attack is feasible with the time complexity of about $2^{n} cdot rac{1}{2 n}$ in the chosen-plaintext model, while Dinur et al.'s attack requires $2^{n} cdot rac{{ m log}(n)}{ n} $ in the known-plaintext model.