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
Note: Applied comments we got from several reviewers.
Metadata
- Available format(s)
-
PDF
- Category
- Secret-key cryptography
- Publication info
- Published elsewhere. Unknown where it was published
- Keywords
- block cipherslinear cryptanalysisdifferential cryptanalysis
- Contact author(s)
- vincent rijmen @ iaik tugraz at
- History
- 2006-04-13: last of 2 revisions
- 2005-07-05: received
- See all versions
- Short URL
- https://ia.cr/2005/212
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2005/212, author = {Joan Daemen and Vincent Rijmen}, title = {Probability distributions of Correlation and Differentials in Block Ciphers}, howpublished = {Cryptology {ePrint} Archive, Paper 2005/212}, year = {2005}, url = {https://eprint.iacr.org/2005/212} }