Welcome to the resource topic for
**2005/212**

**Title:**

Probability distributions of Correlation and Differentials in Block Ciphers

**Authors:**
Joan Daemen, 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.

**ePrint:**
https://eprint.iacr.org/2005/212

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

**Example resources include:**
implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .