Fast Fourier Transform Key Recovery for Integral Attacks

Yosuke TODO; Kazumaro AOKI

doi:10.1587/transfun.E98.A.1944

Fast Fourier Transform Key Recovery for Integral Attacks

Yosuke TODO, Kazumaro AOKI

Full Text Views

0

Share
Cite this

Summary :

An integral attack is one of the most powerful attacks against block ciphers. We propose a new technique for the integral attack called the Fast Fourier Transform (FFT) key recovery. When N chosen plaintexts are required for the integral characteristic and the guessed key is k bits, a straightforward key recovery requires the time complexity of O(N2^k). However, the FFT key recovery only requires the time complexity of O(N+k2^k). As a previous result using FFT, at ICISC 2007, Collard etal proposed that FFT can reduce the time complexity of a linear attack. We show that FFT can also reduce the complexity of the integral attack. Moreover, the estimation of the complexity is very simple. We first show the complexity of the FFT key recovery against three structures, the Even-Mansour scheme, a key-alternating cipher, and the Feistel structure. As examples of these structures, we show integral attacks against Prøst, AES, PRESENT, and CLEFIA. As a result, an 8-round Prøst P_128,K can be attacked with about an approximate time complexity of 2^79.6. For the key-alternating cipher, a 6-round AES and a 10-round PRESENT can be attacked with approximate time complexities of 2^51.7 and 2^97.4, respectively. For the Feistel structure, a 12-round CLEFIA can be attacked with approximate time complexities of 2^87.5.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E98-A No.9 pp.1944-1952

Publication Date: 2015/09/01

Publicized

Online ISSN: 1745-1337

DOI: 10.1587/transfun.E98.A.1944

Type of Manuscript: PAPER

Category: Cryptography and Information Security

Authors

Yosuke TODO
NTT Corporation
Kazumaro AOKI
NTT Corporation

Keyword

block ciphers, integral attack, Even-Mansour, key-alternating cipher, Feistel structure, FFT, FWHT

Cite this

Copy

Yosuke TODO, Kazumaro AOKI, "Fast Fourier Transform Key Recovery for Integral Attacks" in IEICE TRANSACTIONS on Fundamentals, vol. E98-A, no. 9, pp. 1944-1952, September 2015, doi: 10.1587/transfun.E98.A.1944.
Abstract: An integral attack is one of the most powerful attacks against block ciphers. We propose a new technique for the integral attack called the Fast Fourier Transform (FFT) key recovery. When N chosen plaintexts are required for the integral characteristic and the guessed key is k bits, a straightforward key recovery requires the time complexity of O(N2^k). However, the FFT key recovery only requires the time complexity of O(N+k2^k). As a previous result using FFT, at ICISC 2007, Collard etal proposed that FFT can reduce the time complexity of a linear attack. We show that FFT can also reduce the complexity of the integral attack. Moreover, the estimation of the complexity is very simple. We first show the complexity of the FFT key recovery against three structures, the Even-Mansour scheme, a key-alternating cipher, and the Feistel structure. As examples of these structures, we show integral attacks against Prøst, AES, PRESENT, and CLEFIA. As a result, an 8-round Prøst P_128,K can be attacked with about an approximate time complexity of 2^79.6. For the key-alternating cipher, a 6-round AES and a 10-round PRESENT can be attacked with approximate time complexities of 2^51.7 and 2^97.4, respectively. For the Feistel structure, a 12-round CLEFIA can be attacked with approximate time complexities of 2^87.5.
URL: https://globals.ieice.org/en_transactions/fundamentals/10.1587/transfun.E98.A.1944/_p

Copy

@ARTICLE{e98-a_9_1944,
author={Yosuke TODO, Kazumaro AOKI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Fast Fourier Transform Key Recovery for Integral Attacks},
year={2015},
volume={E98-A},
number={9},
pages={1944-1952},
abstract={An integral attack is one of the most powerful attacks against block ciphers. We propose a new technique for the integral attack called the Fast Fourier Transform (FFT) key recovery. When N chosen plaintexts are required for the integral characteristic and the guessed key is k bits, a straightforward key recovery requires the time complexity of O(N2^k). However, the FFT key recovery only requires the time complexity of O(N+k2^k). As a previous result using FFT, at ICISC 2007, Collard etal proposed that FFT can reduce the time complexity of a linear attack. We show that FFT can also reduce the complexity of the integral attack. Moreover, the estimation of the complexity is very simple. We first show the complexity of the FFT key recovery against three structures, the Even-Mansour scheme, a key-alternating cipher, and the Feistel structure. As examples of these structures, we show integral attacks against Prøst, AES, PRESENT, and CLEFIA. As a result, an 8-round Prøst P_128,K can be attacked with about an approximate time complexity of 2^79.6. For the key-alternating cipher, a 6-round AES and a 10-round PRESENT can be attacked with approximate time complexities of 2^51.7 and 2^97.4, respectively. For the Feistel structure, a 12-round CLEFIA can be attacked with approximate time complexities of 2^87.5.},
keywords={},
doi={10.1587/transfun.E98.A.1944},
ISSN={1745-1337},
month={September},}

Copy

TY - JOUR
TI - Fast Fourier Transform Key Recovery for Integral Attacks
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1944
EP - 1952
AU - Yosuke TODO
AU - Kazumaro AOKI
PY - 2015
DO - 10.1587/transfun.E98.A.1944
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E98-A
IS - 9
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - September 2015
AB - An integral attack is one of the most powerful attacks against block ciphers. We propose a new technique for the integral attack called the Fast Fourier Transform (FFT) key recovery. When N chosen plaintexts are required for the integral characteristic and the guessed key is k bits, a straightforward key recovery requires the time complexity of O(N2^k). However, the FFT key recovery only requires the time complexity of O(N+k2^k). As a previous result using FFT, at ICISC 2007, Collard etal proposed that FFT can reduce the time complexity of a linear attack. We show that FFT can also reduce the complexity of the integral attack. Moreover, the estimation of the complexity is very simple. We first show the complexity of the FFT key recovery against three structures, the Even-Mansour scheme, a key-alternating cipher, and the Feistel structure. As examples of these structures, we show integral attacks against Prøst, AES, PRESENT, and CLEFIA. As a result, an 8-round Prøst P_128,K can be attacked with about an approximate time complexity of 2^79.6. For the key-alternating cipher, a 6-round AES and a 10-round PRESENT can be attacked with approximate time complexities of 2^51.7 and 2^97.4, respectively. For the Feistel structure, a 12-round CLEFIA can be attacked with approximate time complexities of 2^87.5.
ER -