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.