Linear dependencies in product ciphers.
Helen Gustafson, Anthony N. Pettitt, Ed Dawson, Luke O’Connor · 1994
In this paper we will survey three forms of statistical dependency found in block ciphers. Each dependency is based on some notion of linearity, forming the basis of several attacks which are particularly applicable to product ciphers. We consider linear relationships between the plaintext and ciphertext bits, using elementary arguments from linear algebra, and then using linear relationships under real number addition based on canonical correlation analysis. Linear structures [4] are also examined, which are a form of linearity that leads to degeneracy in the key, meaning that certain bits do not affect the ciphertext. We show that most functions are not expected to have a linear structure, though even partial linearity in this respect leads to a powerful attack known as differential cryptanalysis. Lastly, we consider linear approximation as a cryptanalytic tool, and present the recent linear cryptanalysis due to Matsui on the Data Encryption Standard (DES). The work reported in thi...