Semester Project at the Signal and Information Processing Laboratory

The Hypothesis of Fixed-Key Equivalence for the Group Generalization of Linear Cryptanalysis

3 July 1998


In 1993, Matsui presented a new attack on iterated block ciphers (as for example the often used DES- or SAFER-ciphers) which he called linear cryptanalysis. This approach that has been generalized several times already (by Harpes, Kramer, and Massey) tries to find linear dependencies between some bits of the plaintext and the ciphertext. The success of the attack is based on two assumptions that have to be fulfilled: The Hypothesis of Wrong-Key Randomization which ensures that the attack really is successful if enough plaintext/ciphertext-pairs are available, and the even more basic Hypothesis of Fixed-Key Equivalence which makes sure that the assumption made by the cryptanalyst that the round keys are uniformly random does not change the success probability. Kukorelly has shown that the latter hypothesis holds for the binary generalization of linear cryptanalysis if the blocks are large enough and if there are sufficiently many rounds.

This semesterwork studies the Hypothesis of Fixed-Key Equivalence for the group generalization of linear cryptanalysis. It is shown that the approach used by Kukorelly for the binary case can not be applied anymore because of a large increase of complexity of the situation. However, the problem can be solved for a few cases with feasible computational complexity, and for some more cases at least good evidence is shown. A lot of examples have been made and are listed in detailed tables. The listings of the C++-programs used for all simulations have been appended.

Download of the Report

The written report can be downloaded here.

In case you are interested in some more information or data, please do not hesitate to contact me at !

-||-   _|_ _|_     /    __|__   Stefan M. Moser
[-]     --__|__   /__\    /__   Senior Researcher & Lecturer, ETH Zurich, Switzerland
_|_     -- --|-    _     /  /   Adj. Professor, National Chiao Tung University (NCTU), Taiwan
/ \     []  \|    |_|   / \/    Web:

Last modified: Wed Feb 18 08:01:25 UTC+8 2009