On weaknesses of non-surjective round functions (Q1369725)

Generally, there are no doubts that the well-known DES is reaching the end of its lifetime. However, quite a lot of new ciphers aspiring to become its replacement keep the original Feistel structure of DES. Their novelty is usually based on suggesting new structures for the \textit{round function}. In the article weaknesses introduced by the use of non-surjective, or, more generally, non-uniform round functions in Feistel-type ciphers are studied. Assuming round keys are independent and uniformly distributed, it is shown how non-surjectivity of round function makes attack in a known-plaintext setting possible. The idea of the basic attack is then extended and an estimate for the number of known plaintexts that are needed for the attack is derived. In the rest of the paper the attack is applied to some members of CAST ciphers family as well as to LOKI91. It is shown that reducing the number of rounds to 6 or less makes the ciphers vulnerable to the statistical attack presented. In the last section some design principles for Feistel ciphers are discussed.