
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.

Efficient Implementations for Practical Linear Cryptanalysis and Its Application to FEAL8X
Sho SAKIKOYAMA Yosuke TODO Kazumaro AOKI Masakatu MORII
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E99A
No.1
pp.3138 Publication Date: 2016/01/01
Online ISSN: 17451337
DOI: 10.1587/transfun.E99.A.31
Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security) Category: Keyword: linear cryptanalysis, FFT, FWHT, multiple linear cryptanalysis, FEAL8X,
Full Text: PDF(1.1MB)>>
Summary:
Linear cryptanalysis proposed by Matsui is one of the most effective attacks on block ciphers. Some attempts to improve linear cryptanalysis have been made since Matsui introduced. We focus on how to optimize linear cryptanalysis with such techniques, and we apply the optimized linear cryptanalysis on FEAL8X. First, we evaluate two existing implementation methods so as to optimize the computation time of linear cryptanalysis. Method 1 removes redundant round function computations and optimizes the other computation of linear cryptanalysis by transforming it into bitwise operations. Method 2 transforms the computation of linear cryptanalysis into a matrix multiplication and reduces the time complexity of the multiplication using the fast Fourier transform (FFT). We implement both methods optimized for modern microprocessors and compare their computation time to clarify the appropriate method for practical cryptanalysis. From the result, we show that the superior implementation depends on the number of given known plaintexts (KPs) and that of guessed key bits. Furthermore, we show that these results enable us to select the superior method to implement linear cryptanalysis without another comparative experiment. By using the superior method, we implement the multiple linear cryptanalysis (MLC) on FEAL8X. Our implementation can recover the secret key of FEAL8X with 2^{10}KPs in practical computation time with nonnegligible probability, and it is the best attack on FEAL8X in data complexity.

