In this paper we study the influence of key-scheduling algorithms on t
he strength of blockciphers. We show that the key-scheduling algorithm
s 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 complexi
ty of exhaustive search attacks (and the faster variants based on comp
lementation properties), and new low-complexity chosen key attacks. Th
ese attacks are independent of the number of rounds of the cryptosyste
ms and of the details of the F-function and may have very small comple
xities. These attacks show that the key-scheduling algorithm should be
carefully designed and that its structure should not be too simple. T
hese attacks are applicable to both variants of LOKI and to Lucifer. D
ES is not vulnerable to the related keys attacks since the shift patte
rn in the key-scheduling algorithm is not the same in all the rounds.