Degree of composition of highly nonlinear functions and applications to higher order differential cryptanalysis.
Anne Canteaut
INRIA, projet CODES
BP 105
78153 Le Chesnay Cedex, France
Anne.Canteaut@inria.fr
Marion Videau
INRIA, projet CODES
BP 105
78153 Le Chesnay Cedex, France
Marion.Videau@inria.fr
In Advances in Cryptology - EUROCRYPT 2002, Lecture Notes in
Computer Science. Springer-Verlag, 2002.
Abstract
To improve the security of iterated block ciphers, the resistance
against linear cryptanalysis has been formulated in terms of
provable security which suggests the use of highly nonlinear
functions as round functions. Here, we show that some properties of
such functions enable to find a new upper bound for the degree of
the product of its Boolean components. Such an improvement holds
when all values occurring in the Walsh spectrum of the round
function are divisible by a high power of 2. This result leads to a
higher order differential attack on any 5-round Feistel ciphers
using an almost bent substitution function. We also show that the
use of such a function is precisely the origin of the weakness of a
reduced version of MISTY1 reported by Tanaka et al. and by Babbage and Frisch.
Keywords
Block ciphers, higher order differential cryptanalysis, Boolean
functions, nonlinearity.
See also
A. Canteaut and M. Videau.
Weakness of block ciphers using highly nonlinear confusion functions.
Rapport de recherche RR-4367, INRIA, February 2002.