The search functionality is under construction.

The search functionality is under construction.

We propose new key recovery attacks on the two-round single-key *n*-bit Even-Mansour ciphers (2SEM) that are secure up to 2^{2n/3} queries against distinguishing attacks proved by Chen et al. Our attacks are based on the meet-in-the-middle technique which can significantly reduce the data complexity. In particular, we introduce novel matching techniques which enable us to compute one of the two permutations without knowing a part of the key information. Moreover, we present two improvements of the proposed attack: one significantly reduces the data complexity and the other reduces the time complexity. Compared with the previously known attacks, our attack first breaks the birthday barrier on the data complexity although it requires chosen plaintexts. When the block size is 64 bits, our attack reduces the required data from 2^{45} known plaintexts to 2^{26} chosen plaintexts with keeping the time complexity required by the previous attacks. Furthermore, by increasing the time complexity up to 2^{62}, the required data is further reduced to 2^{8}, and *DT*=2^{70}, where *DT* is the product of data and time complexities. We show that our data-optimized attack requires *DT*=2^{n+6} in general cases. Since the proved lower bound on *DT* for the single-key one-round *n*-bit Even-Mansour ciphers is 2* ^{n}*, our results imply that adding one round to one-round constructions does not sufficiently improve the security against key recovery attacks. Finally, we propose a time-optimized attacks on 2SEM in which, we aim to minimize the number of the invocations of internal permutations.

- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E102-A No.1 pp.17-26

- Publication Date
- 2019/01/01

- Publicized

- Online ISSN
- 1745-1337

- DOI
- 10.1587/transfun.E102.A.17

- Type of Manuscript
- Special Section PAPER (Special Section on Cryptography and Information Security)

- Category

Takanori ISOBE

University of Hyogo

Kyoji SHIBUTANI

Nagoya University

The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.

Copy

Takanori ISOBE, Kyoji SHIBUTANI, "Meet-in-the-Middle Key Recovery Attacks on a Single-Key Two-Round Even-Mansour Cipher" in IEICE TRANSACTIONS on Fundamentals,
vol. E102-A, no. 1, pp. 17-26, January 2019, doi: 10.1587/transfun.E102.A.17.

Abstract: We propose new key recovery attacks on the two-round single-key *n*-bit Even-Mansour ciphers (2SEM) that are secure up to 2^{2n/3} queries against distinguishing attacks proved by Chen et al. Our attacks are based on the meet-in-the-middle technique which can significantly reduce the data complexity. In particular, we introduce novel matching techniques which enable us to compute one of the two permutations without knowing a part of the key information. Moreover, we present two improvements of the proposed attack: one significantly reduces the data complexity and the other reduces the time complexity. Compared with the previously known attacks, our attack first breaks the birthday barrier on the data complexity although it requires chosen plaintexts. When the block size is 64 bits, our attack reduces the required data from 2^{45} known plaintexts to 2^{26} chosen plaintexts with keeping the time complexity required by the previous attacks. Furthermore, by increasing the time complexity up to 2^{62}, the required data is further reduced to 2^{8}, and *DT*=2^{70}, where *DT* is the product of data and time complexities. We show that our data-optimized attack requires *DT*=2^{n+6} in general cases. Since the proved lower bound on *DT* for the single-key one-round *n*-bit Even-Mansour ciphers is 2* ^{n}*, our results imply that adding one round to one-round constructions does not sufficiently improve the security against key recovery attacks. Finally, we propose a time-optimized attacks on 2SEM in which, we aim to minimize the number of the invocations of internal permutations.

URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E102.A.17/_p

Copy

@ARTICLE{e102-a_1_17,

author={Takanori ISOBE, Kyoji SHIBUTANI, },

journal={IEICE TRANSACTIONS on Fundamentals},

title={Meet-in-the-Middle Key Recovery Attacks on a Single-Key Two-Round Even-Mansour Cipher},

year={2019},

volume={E102-A},

number={1},

pages={17-26},

abstract={We propose new key recovery attacks on the two-round single-key *n*-bit Even-Mansour ciphers (2SEM) that are secure up to 2^{2n/3} queries against distinguishing attacks proved by Chen et al. Our attacks are based on the meet-in-the-middle technique which can significantly reduce the data complexity. In particular, we introduce novel matching techniques which enable us to compute one of the two permutations without knowing a part of the key information. Moreover, we present two improvements of the proposed attack: one significantly reduces the data complexity and the other reduces the time complexity. Compared with the previously known attacks, our attack first breaks the birthday barrier on the data complexity although it requires chosen plaintexts. When the block size is 64 bits, our attack reduces the required data from 2^{45} known plaintexts to 2^{26} chosen plaintexts with keeping the time complexity required by the previous attacks. Furthermore, by increasing the time complexity up to 2^{62}, the required data is further reduced to 2^{8}, and *DT*=2^{70}, where *DT* is the product of data and time complexities. We show that our data-optimized attack requires *DT*=2^{n+6} in general cases. Since the proved lower bound on *DT* for the single-key one-round *n*-bit Even-Mansour ciphers is 2* ^{n}*, our results imply that adding one round to one-round constructions does not sufficiently improve the security against key recovery attacks. Finally, we propose a time-optimized attacks on 2SEM in which, we aim to minimize the number of the invocations of internal permutations.},

keywords={},

doi={10.1587/transfun.E102.A.17},

ISSN={1745-1337},

month={January},}

Copy

TY - JOUR

TI - Meet-in-the-Middle Key Recovery Attacks on a Single-Key Two-Round Even-Mansour Cipher

T2 - IEICE TRANSACTIONS on Fundamentals

SP - 17

EP - 26

AU - Takanori ISOBE

AU - Kyoji SHIBUTANI

PY - 2019

DO - 10.1587/transfun.E102.A.17

JO - IEICE TRANSACTIONS on Fundamentals

SN - 1745-1337

VL - E102-A

IS - 1

JA - IEICE TRANSACTIONS on Fundamentals

Y1 - January 2019

AB - We propose new key recovery attacks on the two-round single-key *n*-bit Even-Mansour ciphers (2SEM) that are secure up to 2^{2n/3} queries against distinguishing attacks proved by Chen et al. Our attacks are based on the meet-in-the-middle technique which can significantly reduce the data complexity. In particular, we introduce novel matching techniques which enable us to compute one of the two permutations without knowing a part of the key information. Moreover, we present two improvements of the proposed attack: one significantly reduces the data complexity and the other reduces the time complexity. Compared with the previously known attacks, our attack first breaks the birthday barrier on the data complexity although it requires chosen plaintexts. When the block size is 64 bits, our attack reduces the required data from 2^{45} known plaintexts to 2^{26} chosen plaintexts with keeping the time complexity required by the previous attacks. Furthermore, by increasing the time complexity up to 2^{62}, the required data is further reduced to 2^{8}, and *DT*=2^{70}, where *DT* is the product of data and time complexities. We show that our data-optimized attack requires *DT*=2^{n+6} in general cases. Since the proved lower bound on *DT* for the single-key one-round *n*-bit Even-Mansour ciphers is 2* ^{n}*, our results imply that adding one round to one-round constructions does not sufficiently improve the security against key recovery attacks. Finally, we propose a time-optimized attacks on 2SEM in which, we aim to minimize the number of the invocations of internal permutations.

ER -