Philip Søgaard Vejre: As we move towards a highly digital world, security of electronic communication is becoming increasingly important. Computers, mobile phones, smart cards, the Internet etc., all rely heavily on various cyber security systems.
The security of these
depend on cryptographic primitives, such as block ciphers, hash functions, and
random number generators. Therefore, the security of these primitives is intensely
studied, and the knowledge is used to build safer and more robust primitives.
One extremely important cryptographic primitive is the block cipher, which provides
basic encryption functionality. In order to have a high confidence in the security of a
given block cipher, we need to evaluate its resistance to all known attacks. This
thesis focuses on one particular statistical attack against block ciphers, called linear
cryptanalysis. This attack exploits linear expressions of the input bits to the block
cipher that are strongly correlated with linear expressions of the output bits, so-called
linear approximations. Despite being one of the most prolific attacks, there are many
aspects of linear cryptanalysis that are not well understood. This thesis therefore
presents new works that aim to advance our understanding of this attack, in particular
for advanced variants that use multiple linear approximations simultaneously.
As a first result, we develop a new algorithm for finding good linear approximations.
This algorithm also facilitates the development of new statistical models for linear
cryptanalysis. These models use much fewer assumptions about the probabilistic
behaviour of linear approximations than earlier models, hopefully providing a more
accurate evaluation of the strength of these types of attacks. Using these new tools
and models, we show new attacks on two block ciphers, DES and PRESENT, and
investigate many other ciphers. As a result of this investigation, we show that the
statistical behaviour of linear approximations can vary greatly between ciphers. This
demonstrates that it is paramount that the cryptanalyst forgoes simplifying
assumptions and carefully examines this behaviour for each cipher she intends to
attack, in order to get precise attack estimates.
PhD project: 2016 - 2019
DTU Supervisors: Andrey Bogdanov and Lars Ramkilde Knudsen
Status: Published as report: Correlations Aplenty - Linear Cryptanalysis of Block Ciphers