International Association for Cryptologic Research

International Association
for Cryptologic Research


Multidimensional Linear Cryptanalysis of Feistel Ciphers

Betül Aşkın Özdemir , COSIC, KU Leuven, Leuven, Belgium
Tim Beyne , COSIC, KU Leuven, Leuven, Belgium
Vincent Rijmen , COSIC, KU Leuven, Leuven, Belgium; University of Bergen, Bergen, Norway
DOI: 10.46586/tosc.v2023.i4.1-27
Search ePrint
Search Google
Abstract: This paper presents new generic attacks on Feistel ciphers that incorporate the key addition at the input of the non-invertible round function only. This feature leads to a specific vulnerability that can be exploited using multidimensional linear cryptanalysis. More specifically, our approach involves using key-independent linear trails so that the distribution of a combination of the plaintext and ciphertext can be computed. This makes it possible to use the likelihood-ratio test as opposed to the χ2 test. We provide theoretical estimates of the cost of our generic attacks and verify these experimentally by applying the attacks to CAST-128 and LOKI91. The theoretical and experimental findings demonstrate that the proposed attacks lead to significant reductions in data-complexity in several interesting cases.
  title={Multidimensional Linear Cryptanalysis of Feistel Ciphers},
  journal={IACR Transactions on Symmetric Cryptology},
  publisher={Ruhr-Universität Bochum},
  volume={023 No. 4},
  author={Betül Aşkın Özdemir and Tim Beyne and Vincent Rijmen},