PhD Thesis

If you are interested in my PhD work, here is the summary.

The goal of the thesis was to evaluate the security margin for selected lightweight ciphers (encryption algorithms). We focussed on two applications: lightweight cryptography and authenticated encryption. The first one is about providing secure communication to devices with constrained resources such as memory and computing power. The authenticated encryption tries to provide confidentiality and authenticity into a single, efficient algorithm.

There have a dozen of interesting, new algorithms, partly as a response to the CAESAR competition (Competition for Authenticated Encryption: Security, Applicability, and Robustness). These new designs can be used in many cryptographic scenarios; therefore, it is necessary to undertake extensive cryptanalysis, proving its reliability and security. The cryptographic community has invented multiple levels of cryptanalytic methods that target different possible designs and aim to exploit their weaknesses into successful and potentially practical attacks.

In particular, we focussed on two ciphers from the CAESAR competition: Scream and ASCON. The CAESAR contest has started in 2014 and received worldwide attention. In the first round, 57 algorithms were submitted to CAESAR and Scream was one of the 29 CAESAR round two candidates, while ASCON has been the winner in the lightweight cryptography category. We evaluated the security of Scream using different cryptanalytic techniques. Firstly we applied linear cryptanalysis to the cipher and then we extend this linear analysis with a differential part (known as differential-linear analysis). Further, we analysed the cipher with impossible differential cryptanalysis and then investigate the differential-linear path in the related-key scenario. For ASCON, we apply SAT-based cryptanalysis with an aim at the state recovery, using a SAT solver as the main tool. A SAT solver decides whether a given boolean formula has a satisfying valuation or not. It takes a boolean satisfiability problem and finds the solution to such the problem. We conclude the ASCON has a sufficient security margin against SAT-based cryptanalysis.

Furthermore, we focussed on differential cryptanalysis of the lightweight ARX (Addition/Rotation/XOR) block cipher SPECK and LEA. SPECK was designed by the U.S National Security Agency (NSA). ARX algorithms use three operations: modular addition, bitwise rotation, and eXclusive-OR. These algorithms are usually smaller and faster for software implementation than S-box based designs. However, in AES-like ciphers, an S-box is typically 8- or 4-bit. Such a size allows to compute the full distribution difference table (DDT) and investigate differential properties of the S-box and the algorithm. On the other hand, ARX-based designs use modular addition rather than S-boxes as a source of non-linearity. A word size in such ciphers are typically 32- or 64-bit and constructing a complete DDT is infeasible. This is the reason we need some clever heuristics to circumvent this limitation. For this purpose, we proposed an algorithm inspired by Nested Monte-Carlo Search (from Artificial Intelligence Research Field) to find the differential paths in SPECK and LEA. This method provides state-of-the-art (or close to) results but within a simpler framework and requires very less time for cryptanalysis and therefore saves a huge computational power.