An algorithm to analyze substitution permutation network resistance to linear and differential cryptanalysis

Abstract

In this thesis, we propose a practical novel algorithm, called the Two-Round Iterative (TRI) algorithm that analyzes the block cipher structure referred to as a Substitution Permutation Network (SPN). The algorithm characterizes the resistance of the cipher to linear cryptanalysis and differential cryptanalysis. By finding the best of close to best linear approximation and differential characteristics of the cipher, the algorithm can be used to find the number of plaintext/ciphertext pairs required to mount either attack on the cipher successfully. An important feature of the algorithm is that the complexity of algorithm is linear in terms of number of rounds and hence is able to give results in practical time. -- In this thesis, the algorithm has been applied to 16-bit ciphers to verify the effectiveness of the algorithm in finding optimal linear biases and differential probabilities. Further, it is applied to realistic 64-bit ciphers based on 8X8 and 4X4 S-boxes that possess good cryptographic properties. In addition to the TRI algorithm, we have also developed two algorithms that are guaranteed to find the optimal linear approximation and differential characteristic and applied them to 16-bit ciphers in order to examine the TRI algorithm efficiency and effectiveness. It is shown that the TRI algorithm is effective in finding the best or close to the best linear approximation and differential characteristic and the corresponding linear bias and differential probability. Also the TRI algorithm can be practically applied to realistically sized cipher (e.g. 64-bits) where the other algorithms are too inefficient to be practical. Experimental data is presented in the form of figures and tables which demonstrate the usefulness of the TRI algorithm in characterizing the security level of realistic SPN block ciphers.