New Types of Cryptanalytic Attacks Using Related Keys

In this paper we study the influence of key scheduling algorithms on the strength of blockciphers. We show that the key scheduling algorithms of many blockciphers inherit obvious relationships between keys, and use these key relations to attack the blockciphers. Two new types of attacks are described: New chosen plaintext reductions of the complexity of exhaustive search attacks (and the faster variants based on complementation properties), and new low-complexity chosen key attacks. These attacks are independent of the number of rounds of the cryptosystems and of the details of the F-function and may have very small complexities. These attacks show that the key scheduling algorithm should be carefully designed and that its structure should not be too simple. These attacks are applicable to both variants of LOKI and to Lucifer. DES is not vulnerable to the related keys attacks since the shift pattern in the key scheduling algorithm is not the same in all the rounds.