Paper 2017/868

New Key Recovery Attacks on Minimal Two-Round Even-Mansour Ciphers

Takanori Isobe and Kyoji Shibutani

Abstract

Chen et al. proved that two variants of the two-round n-bit Even-Mansour ciphers are secure up to 22n/3 queries against distinguish- ing attacks. These constructions can be regarded as minimal two-round Even-Mansour ciphers delivering security beyond the birthday bound, since removing any component from the ciphers causes security to drop back to 2n/2 queries. On the other hand, for the minimal two-round con- structions, the proved lower bounds on the product of data and time complexities (DT) against the other attacks including key recovery at- tacks is 2n. However, an attack requiring DT close to the lower bound has not been known yet, and thus its tightness is not clear. In this pa- per, we propose new key recovery attacks on the two minimal two-round Even-Mansour ciphers by using the advanced meet-in-the-middle tech- nique. In particular, we introduce novel matching techniques called partial invariable pair and matching with input-restricted public permutation , which enable us to compute one of permutations without knowing a part of the key information. Moreover, we present two improvements of the proposed attack: one significantly reduces data complexity and the other reduces time complexity by dynamically finding partial invariant pairs. Compared with the previously known attacks, when blocksize is 64 bits, our attacks drastically reduce the required data from 245 to 226 with keeping time complexity required by the previous attacks, though our attack requires chosen plaintexts. Importantly, the previous attacks never break the birthday barrier of data complexity due to the usage of multicollisions in the internal state. Furthermore, by increasing time complexity up to 262, the required data is further reduced to 28, and DT = 270 which is close to the proved lower bound 264. We show that our data-optimized attack on the minimal two-round Even-Mansour ci- phers requires DT = 2n+6 in general cases. This implies that adding one round does not sufficiently improve the security against key recovery attacks of the Even-Mansour ciphers.

Metadata
Available format(s)
PDF
Publication info
Published by the IACR in ASIACRYPT 2017
Keywords
block cipherEven-Mansour ciphersmeet-in-the-middle attackkey recoverypartial invariable pair
Contact author(s)
takanori isobe @ ai u-hyogo ac jp
kyoji shibutani @ nagoya-u jp
History
2017-09-13: received
Short URL
https://ia.cr/2017/868
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/868,
      author = {Takanori Isobe and Kyoji Shibutani},
      title = {New Key Recovery Attacks on Minimal Two-Round Even-Mansour Ciphers},
      howpublished = {Cryptology ePrint Archive, Paper 2017/868},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/868}},
      url = {https://eprint.iacr.org/2017/868}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.