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 .