Serial Lightweight Implementation Techniques for Block Ciphers

Most of the cryptographic protocols that we use frequently on the internet are designed in a fashion that they are not necessarily suitable to run in constrained environments. Applications that run on limited-battery, with low computational power, or area constraints, therefore requires the new designs as well as improved implementations of cryptographic primitives, hence emerges the field lightweight cryptography.

In this thesis, we contribute to this effort in few separate directions, in particular regarding block ciphers and block-cipher-based authentication scheme implementations as application-specific integrated circuits (ASIC).

First, we look at optimizations that can be achieved at higher level. In particular, we show that the complete AES family (with varying key sizes 128, 192 and 256) can be realized as combined lightweight circuit, in a manner that shares the storage elements in order to save up silicon area.

Secondly, we contribute in the evaluation of a new design paradigm of fork cipher. We look at how much lightweight efficiency can be gained with this new AEAD design approach, by implementing ForkAES both in round-based and byte-serial implementations. Our comparison with respect to silicon area and energy consumption provides useful insights into AEAD design process.

Lastly, in the large portion of this thesis, we look at the permutation layer of block ciphers from the perspective of serial-circuits. Based on the permutation theory, we establish a method to divide the permutation layers of AES, SKINNY, GIFT and PRESENT into simpler swap operations. Given that these swap operations are cheap in ASIC, we further provide architectural optimization techniques for the implementation of these block ciphers, and we provide the smallest 1-bit implementations of them.

Bringing Theory Closer to Practice in Post-quantum and Leakage-resilient Cryptography

Alexandre Raphaël Duc

Modern cryptography pushed forward the need of having provable security. Whereas ancient cryptography was only relying on heuristic assumptions and the secrecy of the designs, nowadays researchers try to make the security of schemes to rely on mathematical problems which are believed hard to solve. When doing these proofs, the capabilities of potential adversaries are modeled formally. For instance, the black-box model assumes that an adversary does not learn anything from the inner-state of a construction. While this assumption makes sense in some practical scenarios, it was shown that one can sometimes learn some information by other means, e.g., by timing how long the computation take. In this thesis, we focus on two different areas of cryptography. In both parts, we take first a theoretical point of view to obtain a result. We try then to adapt our results so that they are easily usable for implementers and for researchers working in practical cryptography. In the first part of this thesis, we take a look at post-quantum cryptography, i.e., at cryptographic primitives that are believed secure even in the case (reasonably big) quantum computers are built. We introduce HELEN, a new public-key cryptosystem based on the hardness of the learning from parity with noise problem (LPN). To make our results more concrete, we suggest some practical instances which make the system easily implementable. As stated above, the design of cryptographic primitives usually relies on some well-studied hard problems. However, to suggest concrete parameters for these primitives, one needs to know the precise complexity of algorithms solving the underlying hard problem. In this thesis, we focus on two recent hard-problems that became very popular in post-quantum cryptography: the learning with error (LWE) and the learning with rounding problem (LWR). We introduce a new algorithm that solves both problems and provide a careful complexity analysis so that these problems can be used to construct practical cryptographic primitives. In the second part, we look at leakage-resilient cryptography which studies adversaries able to get some side-channel information from a cryptographic primitive. In the past, two main disjoint models were considered. The first one, the threshold probing model, assumes that the adversary can put a limited number of probes in a circuit. He then learns all the values going through these probes. This model was used mostly by theoreticians as it allows very elegant and convenient proofs. The second model, the noisy-leakage model, assumes that every component of the circuit leaks but that the observed signal is noisy. Typically, some Gaussian noise is added to it. According to experiments, this model depicts closely the real behaviour of circuits. Hence, this model is cherished by the practical cryptographic community. In this thesis, we show that making a proof in the first model implies a proof in the second model which unifies the two models and reconciles both communities. We then look at this result with a more practical point-of-view. We show how it can help in the process of evaluating the security of a chip based solely on the more standard mutual information metric.

EPFL2015

High performance VLSI architectures implementing strong cryptographic primitives

Feth Allah Cherigui

The main topic of this thesis is related to the state of the art in designing cryptographic primitives from a hardware point of view. A special emphasis is dedicated to low-power/low-energy CMOS design. A set of solutions is proposed including an LFSR based stream cipher with self-synchronizing capabilities, a new memory-less Rijndael block cipher architecture and a public key scheme in the class of discrete logarithm. The former is based on arithmetic in large finite field, mainly Galois extension field GF(2‴). These solutions are droved using low-energy techniques, in order to decrease both the switching activity and the total delay. The fundamental motivation supporting this work, is to demonstrate that practical solutions can be obtained for implementing such complex primitives in large scaled circuits, that arc at once, high performance architectures (low-power, high-speed) and cryptographicaly strong, using the well known trade-off between area-speed or area-power. Security constraint has been duly considered, mainly by increasing the key-size. In this work, we explore the general aspects of designing the above mentioned cryptographic functions. We give an extensive survey of some cryptographic primitives from the hardware point of view and expose their security properties. The thesis favours stream cipher and public-key schemes, as currently the most promising advance to capture the notion of key generation and establishment and data bulk encryption. One contribution is the convenient notation for expressing cryptographic self-synchronizing stream ciphers SSSC schemes and our SSMG proposal, a scheme based on packet fingerprint identification, that relies on keyed cryptographic hash function to achieve the security requirements. We maintain an important distinction between hardware implementation and algorithm's security, because the security of cryptographic primitives cannot be based on mathematically strong functions only but requires an extensive cryptanalysis at different levels including the application. This causes a concern for a formalization of the security of an implemented cryptographic primitive. Nevertheless, while some schemes arc well known to be secure such as DL based public key schemes and enough cryptanalyzed such as the new standard Rijndael, some security aspects of the SSMG are discussed. A part of this work studies the specific aspects related to hardware implementation of Rijndael block cipher, the new standard designed to be a substitute for DES. An efficient architecture is developed targeting FPGA implementation, by simply avoiding memory blocks dedicated to the implementation of S-boxes and replacing them by on-chip forward computation using composite Galois field. This technique helps to reduce considerably the amount of hardware required at the cost of little increase of the switching activity. The main conclusion is that, while security constraint of cryptographic primitives increases the hardware complexity and reduces the performances, practical solutions exist for reducing such complexities while keeping or increasing the level of security. Nevertheless, major open questions remain both for a firm theoretical foundation and the proper cryptanalysis of certain solutions.

EPFL2002

On the Use of GF-Inversion as a Cryptographic Primitive

Serge Vaudenay

Inversion in Galois Fields is a famous primitive permutation for designing cryptographic algorithms e.g. for Rijndael because it has suitable differential and linear properties. Inputs and outputs are usually transformed by addition (e.g. XOR) to key bits. We call this construction the APA (Add-Permute-Add) scheme. In this paper we study its pseudorandomness in terms of k-wise independence. We show that the pairwise independence of the APA construction is related to the impossible differentials properties. We notice that inversion has many impossible differentials, so x --> 1/(x+a)+b is not pairwise independent. In 1998, Vaudenay proposed the random harmonic permutation h:x --> a/(x-b)+c. Although it is not perfectly 3-wise independent (despite what was originally claimed), we demonstrate in this paper that it is almost 3-wise independent. In particular we show that any distinguisher limited to three queries between this permutation and a perfect one has an advantage limited to 3/q where q is the field order. This holds even if the distinguisher has access to h-1. Finally, we investigate 4-wise independence and we suggest the cross-ratio as a new tool for cryptanalysis of designs involving inversion.