Master Thesis no. 1996-01
Correlation Attacks on Block Ciphers
January 1996
Abstract
This report presents a new statistical attack on iterative block ciphers
called the correlation attack which is a natural generalization of
linear cryptanalysis. The attack is based on finding complex-valued
functions on the input and the output of a cipher which have a high
correlation. Their mutual relation is then exploited to yield
information about the final round key.
Introducing the notion of imbalance, I/O product, and correlation matrix,
it is shown how to measure a cipher's security against the attack, and
the mini-cipher IDEA(8) is found to be provably secure ( assuming
independency of subkeys).
Links to other kinds of statistical attacks are explored. In particular,
it is shown that the correlation matrix of a cipher and the matrix of
differential transition probabilities used with differential
cryptanalysis are connected by the 2-dimensional Fourier transform.
This implies that correlation cryptanalysis and differential
cryptanalysis are essentially of the same strength.
Pages: 91
AMS classification: 94
Keywords: Correlation, Boolean complexity, linear crypanalysis, partitioning cryptanalysis,
differential cryptanalysis, statisti
