Complete Practical Side-Channel-Assisted Reverse Engineering of AES-Like Ciphers

Public knowledge about the structure of a cryptographic system is a standard assumption in the literature and algorithms are expected to guarantee security in a setting where only the encryption key is kept secret. Nevertheless, undisclosed proprietary cryptographic algorithms still find widespread use in applications both in the civil and military domains. Even though side-channel-based reverse engineering attacks that recover the hidden components of custom cryptosystems have been demonstrated for a wide range of constructions, the complete and practical reverse engineering of AES-128-like ciphers remains unattempted. In this work, we close this gap and propose the first practical reverse engineering of AES-128-like custom ciphers, i.e., algorithms that deploy undisclosed SubBytes, ShiftRows and MixColumns functions. By performing a side-channel-assisted differential power analysis, we show that the amount of traces required to fully recover the undisclosed components are relatively small, hence the possibility of a side-channel attack remains as a practical threat. The results apply to both 8-bit and 32-bit architectures and were validated on two common microcontroller platforms.

Statistical and Algebraic Cryptanalysis of Lightweight and Ultra-Lightweight Symmetric Primitives

Pouyan Sepehrdad

Symmetric cryptographic primitives such as block and stream ciphers are the building blocks in many cryptographic protocols. Having such blocks which provide provable security against various types of attacks is often hard. On the other hand, if possible, such designs are often too costly to be implemented and are usually ignored by practitioners. Moreover, in RFID protocols or sensor networks, we need lightweight and ultra-lightweight algorithms. Hence, cryptographers often search for a fair trade-off between security and usability depending on the application. Contrary to public key primitives, which are often based on some hard problems, security in symmetric key is often based on some heuristic assumptions. Often, the researchers in this area argue that the security is based on the confidence level the community has in their design. Consequently, everyday symmetric protocols appear in the literature and stay secure until someone breaks them. In this thesis, we evaluate the security of multiple symmetric primitives against statistical and algebraic attacks. This thesis is composed of two distinct parts: In the first part, we investigate the security of RC4 stream cipher against statistical attacks. We focus on its applications in WEP and WPA protocols. We revisit the previous attacks on RC4 and optimize them. In fact, we propose a framework on how to deal with a pool of biases for RC4 in an optimized manner. During this work, we found multiple new weaknesses in the corresponding applications. We show that the current best attack on WEP can still be improved. We compare our results with the state of the art implementation of the WEP attack on Aircrack-ng program and improve its success rate. Next, we propose a theoretical key recovery and distinguishing attacks on WPA, which cryptographically break the protocol. We perform an extreme amount of experiments to make sure that the proposed theory matches the experiments. Finally, we propose a concrete theoretical and empirical proof of all our claims. These are currently the best known attacks on WEP and WPA. In the second part, we shed some lights on the theory behind ElimLin, which is an algorithm for solving multivariate polynomial systems of equations. We attack PRESENT and LBlock block ciphers with ElimLin algorithm and compare their security using this algebraic technique. Then, we investigate the security of KATAN family of block ciphers and multi-purpose cryptographic primitive ARMADILLO against algebraic attacks. We break reduced-round versions of several members of KATAN family by proposing a novel pre-processing technique on the original algebraic representation of the cipher before feeding it to a SAT solver. Finally, we propose a devastating practical key recovery attack against the ARMADILLO1 protocol, which breaks it in polynomial time using a few challenge-response pairs.

EPFL2012

LPN in Cryptography

Sonia Mihaela Bogos

The security of public-key cryptography relies on well-studied hard problems, problems for which we do not have efficient algorithms. Factorization and discrete logarithm are the two most known and used hard problems. Unfortunately, they can be easily solved on a quantum computer by Shor's algorithm. Also, the research area of cryptography demands for crypto-diversity which says that we should offer a range of hard problems for public-key cryptography. If one hard problem proves to be easy, we should be able to provide alternative solutions. Some of the candidates for post-quantum hard problems, i.e. problems which are believed to be hard even on a quantum computer, are the Learning Parity with Noise (LPN), the Learning with Errors (LWE) and the Shortest Vector Problem (SVP). A thorough study of these problems is needed in order to assess their hardness. In this thesis we focus on the algorithmic study of LPN. LPN is a hard problem that is attractive, as it is believed to be post-quantum resistant and suitable for lightweight devices. In practice, it has been employed in several encryption schemes and authentication protocols. At the beginning of this thesis, we take a look at the existing LPN solving algorithms. We provide the theoretical analysis that assesses their complexity. We compare the theoretical results with practice by implementing these algorithms. We study the efficiency of all LPN solving algorithms which allow us to provide secure parameters that can be used in practice. We push further the state of the art by improving the existing algorithms with the help of two new frameworks. In the first framework, we split an LPN solving algorithm into atomic steps. We study their complexity, how they impact the other steps and we construct an algorithm that optimises their use. Given an LPN instance that is characterized by the noise level and the secret size, our algorithm provides the steps to follow in order to solve the instance with optimal complexity. In this way, we can assess if an LPN instance provides the security we require and we show what are the secure instances for the applications that rely on LPN. The second framework handles problems that can be decomposed into steps of equal complexity. Here, we assume that we have an adversary that has access to a finite or infinite number of instances of the same problem. The goal of the adversary is to succeed in just one instance as soon as possible. Our framework provides the strategy that achieves this. We characterize an LPN solving algorithm in this framework and show that we can improve its complexity in the scenario where the adversary is restricted. We show that other problems, like password guessing, can be modeled in the same framework.

EPFL2017

A Study of Persistent Fault Analysis

Subhadeep Banik, Andrea Felice Caforio

Persistent faults mark a new class of injections that perturb lookup tables within block ciphers with the overall goal of recovering the encryption key. Unlike earlier fault types persistent faults remain intact over many encryptions until the affected device is rebooted, thus allowing an adversary to collect a multitude of correct and faulty ciphertexts. It was shown to be an efficient and effective attack against substitution-permutation networks. In this paper, the scope of persistent faults is further broadened and explored. More specifically, we show how to construct a key-recovery attack on generic Feistel schemes in the presence of persistent faults. In a second step, we leverage these faults to reverse-engineer AES- and PRESENT-like ciphers in a chosen-key setting, in which some of the computational layers, like substitution tables, are kept secret. Finally, we propose a novel, dedicated, and low-overhead countermeasure that provides adequate protection for hardware implementations against persistent fault injections.