Efficient Implementations for Practical Linear Cryptanalysis and Its Application to FEAL-8X

Sho SAKIKOYAMA; Yosuke TODO; Kazumaro AOKI; Masakatu MORII

doi:10.1587/transfun.E99.A.31

Efficient Implementations for Practical Linear Cryptanalysis and Its Application to FEAL-8X

Sho SAKIKOYAMA, Yosuke TODO, Kazumaro AOKI, Masakatu MORII

Full Text Views

0

Share
Cite this

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 FEAL-8X. 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 FEAL-8X. Our implementation can recover the secret key of FEAL-8X with 2¹⁰KPs in practical computation time with non-negligible probability, and it is the best attack on FEAL-8X in data complexity.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E99-A No.1 pp.31-38

Publication Date: 2016/01/01

Publicized

Online ISSN: 1745-1337

DOI: 10.1587/transfun.E99.A.31

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

Category

Authors

Sho SAKIKOYAMA
  Kobe University
Yosuke TODO
  NTT Corporation
Kazumaro AOKI
  NTT Corporation
Masakatu MORII
  Kobe University

Keyword

linear cryptanalysis, FFT, FWHT, multiple linear cryptanalysis, FEAL-8X

Cite this

Copy

Sho SAKIKOYAMA, Yosuke TODO, Kazumaro AOKI, Masakatu MORII, "Efficient Implementations for Practical Linear Cryptanalysis and Its Application to FEAL-8X" in IEICE TRANSACTIONS on Fundamentals, vol. E99-A, no. 1, pp. 31-38, January 2016, doi: 10.1587/transfun.E99.A.31.
Abstract: 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 FEAL-8X. 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 FEAL-8X. Our implementation can recover the secret key of FEAL-8X with 2¹⁰KPs in practical computation time with non-negligible probability, and it is the best attack on FEAL-8X in data complexity.
URL: https://globals.ieice.org/en_transactions/fundamentals/10.1587/transfun.E99.A.31/_p

Copy

@ARTICLE{e99-a_1_31,
author={Sho SAKIKOYAMA, Yosuke TODO, Kazumaro AOKI, Masakatu MORII, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Efficient Implementations for Practical Linear Cryptanalysis and Its Application to FEAL-8X},
year={2016},
volume={E99-A},
number={1},
pages={31-38},
abstract={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 FEAL-8X. 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 FEAL-8X. Our implementation can recover the secret key of FEAL-8X with 2¹⁰KPs in practical computation time with non-negligible probability, and it is the best attack on FEAL-8X in data complexity.},
keywords={},
doi={10.1587/transfun.E99.A.31},
ISSN={1745-1337},
month={January},}

Copy

TY - JOUR
TI - Efficient Implementations for Practical Linear Cryptanalysis and Its Application to FEAL-8X
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 31
EP - 38
AU - Sho SAKIKOYAMA
AU - Yosuke TODO
AU - Kazumaro AOKI
AU - Masakatu MORII
PY - 2016
DO - 10.1587/transfun.E99.A.31
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E99-A
IS - 1
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - January 2016
AB - 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 FEAL-8X. 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 FEAL-8X. Our implementation can recover the secret key of FEAL-8X with 2¹⁰KPs in practical computation time with non-negligible probability, and it is the best attack on FEAL-8X in data complexity.
ER -