Analysis and design of block cipher constructions

This thesis is dedicated to symmetric cryptographic algorithms. The major focus of the work is on block ciphers themselves as well as on hash functions and message authentication codes based on block ciphers. Three main approaches to the cryptanalysis of symmetric cryptographic algorithms are pursued. First, several block cipher constructions are analyzed mathematically using statistical cryptanalysis. Second, practical attacks on real-world symmetric cryptosystems are considered. Finally, novel cryptanalytic techniques using side-channel leakage are studied with applications to block ciphers and message authentication codes. Differential and linear cryptanalyses are well-known statistical attacks on block ciphers. This thesis studies the security of unbalanced Feistel networks with contracting MDS diffusion with respect to differential and linear cryptanalysis. Upper bounds on the differential trail probabilities and linear probabilities of linear trails in such constructions are proven. It is shown that such unbalanced Feistel networks can be highly efficient and are comparable to many known balanced Feistel network constructions with respect to differential and linear cryptanalysis. Ultra-lightweight substitution-permutation networks with diffusion layers based on the co-design of S-boxes and bit permutations are proposed. This results in lightweight block ciphers and block cipher based compression functions for hash functions designed and analyzed. These constructions have very small footprint and can be efficiently implemented on the majority of RFID tags This work also studies practical attacks on real-world symmetric cryptographic systems. Attacks are proposed on the KeeLoq block cipher and authentication systems widely used for automotive access control and component identification. Cryptanalysis of the A5/2 stream cipher used for protecting GSM connections worldwide is performed. Linear slide attacks on KeeLoq are proposed resulting in the fastest known attack on the KeeLoq block cipher working for all keys. Severe weaknesses of the KeeLoq key management are identified. The KeeLoq real-world authentication protocols for access control and component identification are also analyzed. A special-purpose hardware architecture for attacking A5/2 is developed that allows for real-time key recovery within one second for different GSM channels. This engine is based on an optimized hardware algorithm for fast Gaussian elimination over binary finite fields. iv Finally, this thesis deals with methods of cryptanalysis using side-channel leakage such as power or electromagnetic traces obtained from the attacked implementation of a cryptographic algorithm. Unlike simple and differential side-channel analysis, side-channel collision attacks possess the distinctive feature that they substantially rely on the cryptanalytic properties of the attacked algorithm. Additionally to applying basic side-channel collision attacks to AES-based message authentication codes, this thesis proposes numerous ways of optimizing side-channel collision attacks, including generalized collisions, linear and algebraic collision-based key recovery as well as statistical multiple-differential collision detection methods. In case of AES, these techniques provide considerable improvements and can make side-channel collision attacks more efficient than such state-of-the-art side-channel attacks as stochastic side-channel analysis and template attacks.