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 inputoutput correlations for random functions and block ciphers, for several of them for the first time. We show that these parameters have distributions that are wellstudied 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 fixedkey 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 keyalternating ciphers} against differential and linear cryptanalysis. Keyalternating ciphers are basically iterative ciphers where round keys are applied by an XOR operation in between unkeyed rounds and are a subclass of Markov ciphers. We give the distributions of fixedkey difference propagation probability and fixedkey correlation of iterative ciphers. We show that for keyalternating ciphers, the hypothesis of stochastic equivalence can be discarded. In its place comes the explicit formulation of the distribution of fixedkey \emph{differential probability (DP)} of a differential in terms of its \emph{expected differential probability (EDP)} and the distribution of the fixedkey \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 keyalternating ciphers, we show that if the EDP is equal to $2^{n}$ with $n$ the block length, the fixedkey 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 fixedkey 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.
Metadata
 Available format(s)
 Category
 Secretkey cryptography
 Publication info
 Published elsewhere. Unknown where it was published
 Keywords
 block cipherslinear cryptanalysisdifferential cryptanalysis
 Contact author(s)
 vincent rijmen @ iaik tugraz at
 History
 20060413: last of 2 revisions
 20050705: 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}, note = {\url{https://eprint.iacr.org/2005/212}}, url = {https://eprint.iacr.org/2005/212} }