Paper 2005/212

Probability distributions of Correlation and Differentials in Block Ciphers

Joan Daemen and Vincent Rijmen

Abstract

In this paper, we derive the probability distributions of difference propagation probabilities and input-output correlations for random functions and block ciphers, for several of them for the first time. We show that these parameters have distributions that are well-studied in the field of probability such as the normal, Poisson, Gamma and extreme value distributions. For Markov ciphers there exists a solid theory that expresses bounds on the complexity of differential and linear cryptanalysis in terms of average difference propagation probabilities and average correlations, where the average is taken over the keys. The propagation probabilities and correlations exploited in differential and linear cryptanalysis actually depend on the key and hence so does the attack complexity. The theory of Markov ciphers does not make statements on the distributions of these fixed-key properties but rather makes the assumption that their values will be close to the average for the vast majority of keys. This assumption is made explicit in the form of the hypothesis of stochastic equivalence. In this paper, we study the distributions of propagation properties that are relevant in the resistance of {\em key-alternating ciphers} against differential and linear cryptanalysis. Key-alternating ciphers are basically iterative ciphers where round keys are applied by an XOR operation in between unkeyed rounds and are a sub-class of Markov ciphers. We give the distributions of fixed-key difference propagation probability and fixed-key correlation of iterative ciphers. We show that for key-alternating ciphers, the hypothesis of stochastic equivalence can be discarded. In its place comes the explicit formulation of the distribution of fixed-key \emph{differential probability (DP)} of a differential in terms of its \emph{expected differential probability (EDP)} and the distribution of the fixed-key \emph{linear probability} (or rather \emph{potential}) (\emph{LP}) of a linear approximation (or hull) in terms of its \emph{expected linear probability (ELP)}. Here the ELP and EDP are defined by disregarding the key schedule of the block cipher and taking the average over independently selected round keys, instead of over all cipher keys. Proving these distributions requires no assumptions standardly made in Markov cipher theory as perfectly uniform behavior, independently acting rounds or the technique of averaging over keys. For key-alternating ciphers, we show that if the EDP is equal to $2^{-n}$ with $n$ the block length, the fixed-key DP has a distribution that is very close to that in a random $n$-bit cipher. The same holds for the ELP and the corresponding fixed-key LP. Finally we present a technique for computing bounds on the EDP based on the distribution of probabilities of differential characteristics and of the ELP based on the distribution of LP of linear characteristics.

Note: Applied comments we got from several reviewers.