An average case analysis of a differential attack on a class of SP-networks

We propose a differential attack on tree-structured substitution-permutation networks. The number of chosen plaintexts required for the differential attack to succeed is called the complexity. Our main result is to show that the expected complexity of the attack is linear in the size of the network. This is the first rigorous result concerning the complexity of a differential attack for a general class of product ciphers. 1 Introduction Differential cryptanalysis [4] has been applied to a considerable number of block ciphers, with great success in most cases. The attack proceeds by finding a series of differences \Omega known as a characteristic, or a set of related of characteristics known as a differential , which then gives information about the secret key used in a cipher, when a sufficient number of plaintext/ciphertext pairs are examined. Assume that we wish to determine the subkey KR that is being used in round R. The method of differential cryptanalysis can be summarized as S..