
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Fast Fourier Transform Key Recovery for Integral Attacks
Yosuke TODO Kazumaro AOKI
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E98A
No.9
pp.19441952 Publication Date: 2015/09/01 Online ISSN: 17451337
DOI: 10.1587/transfun.E98.A.1944 Type of Manuscript: PAPER Category: Cryptography and Information Security Keyword: block ciphers, integral attack, EvenMansour, keyalternating cipher, Feistel structure, FFT, FWHT,
Full Text: PDF(867.4KB)>>
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 EvenMansour scheme, a keyalternating 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 8round Prøst P_{128,K} can be attacked with about an approximate time complexity of 2^{79.6}. For the keyalternating cipher, a 6round AES and a 10round PRESENT can be attacked with approximate time complexities of 2^{51.7} and 2^{97.4}, respectively. For the Feistel structure, a 12round CLEFIA can be attacked with approximate time complexities of 2^{87.5}.

