Paper 2005/251

Feistel Schemes and Bi-Linear Cryptanalysis

Nicolas Courtois

Abstract

In this paper we introduce the method of bi-linear cryptanalysis(BLC), designed specifically to attack Feistel ciphers. It allows to construct periodic biased characteristics that combine for an arbitrary number of rounds. In particular, we present a practical attack on DES based on a 1-round invariant, the fastest known based on such invariant, and about as fast as the best Matsui's attack. For ciphers similar to DES, based on small S-boxes, we claim that BLC is very closely related to LC, and we do not expect to find a bi-linear attack much faster than by LC. Nevertheless we have found bi-linear characteristics that are strictly better than the best Matsui's result for 3, 7, 11 and more rounds of DES. We also study s5DES substantially stronger than DES against LC, yet for BLC we exhibit several unexpectedly strong biases, stronger even than existing for DES itself. For more general Feistel schemes there is no reason whatsoever for BLC to remain only a small improvement over LC. We present a construction of a family of practical ciphers based on a big Rijndael-type S-box that are strongly resistant against linear cryptanalysis (LC) but can be easily broken by BLC, even with 16 or more rounds.

Metadata
Available format(s)
PDF PS
Category
Secret-key cryptography
Publication info
Published elsewhere. Long, very much extended version of Crypto 2004 paper with the same title
Keywords
Feistel schemesS-boxesRijndael S-boxlinear cryptanalysisgeneralised linear cryptanalysismultivariate quadratic equations
Contact author(s)
courtois @ minrank org
History
2005-08-02: received
Short URL
https://ia.cr/2005/251
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2005/251,
      author = {Nicolas Courtois},
      title = {Feistel Schemes and Bi-Linear Cryptanalysis},
      howpublished = {Cryptology ePrint Archive, Paper 2005/251},
      year = {2005},
      note = {\url{https://eprint.iacr.org/2005/251}},
      url = {https://eprint.iacr.org/2005/251}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.