Statistical cryptanalysis of block ciphers

Since the development of cryptology in the industrial and academic worlds in the seventies, public knowledge and expertise have grown in a tremendous way, notably because of the increasing, nowadays almost ubiquitous, presence of electronic communication means in our lives. Block ciphers are inevitable building blocks of the security of various electronic systems. Recently, many advances have been published in the field of public-key cryptography, being in the understanding of involved security models or in the mathematical security proofs applied to precise cryptosystems. Unfortunately, this is still not the case in the world of symmetric-key cryptography and the current state of knowledge is far from reaching such a goal. However, block and stream ciphers tend to counterbalance this lack of "provable security" by other advantages, like high data throughput and ease of implementation. In the first part of this thesis, we would like to add a (small) stone to the wall of provable security of block ciphers with the (theoretical and experimental) statistical analysis of the mechanisms behind Matsui's linear cryptanalysis as well as more abstract models of attacks. For this purpose, we consider the underlying problem as a statistical hypothesis testing problem and we make a heavy use of the Neyman-Pearson paradigm. Then, we generalize the concept of linear distinguisher and we discuss the power of such a generalization. Furthermore, we introduce the concept of sequential distinguisher, based on sequential sampling, and of aggregate distinguishers, which allows to build sub-optimal but efficient distinguishers. Finally, we propose new attacks against reduced-round version of the block cipher IDEA. In the second part, we propose the design of a new family of block ciphers named FOX. First, we study the efficiency of optimal diffusive components when implemented on low-cost architectures, and we present several new constructions of MDS matrices; then, we precisely describe FOX and we discuss its security regarding linear and differential cryptanalysis, integral attacks, and algebraic attacks. Finally, various implementation issues are considered.

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

Quantitative security of block ciphers

Thomas Baignères

Block ciphers probably figure in the list of the most important cryptographic primitives. Although they are used for many different purposes, their essential goal is to ensure confidentiality. This thesis is concerned by their quantitative security, that is, by measurable attributes that reflect their ability to guarantee this confidentiality. The first part of this thesis deals with well know results. Starting with Shannon's Theory of Secrecy, we move to practical implications for block ciphers, recall the main schemes on which nowadays block ciphers are based, and introduce the Luby-Rackoff security model. We describe distinguishing attacks and key-recovery attacks against block ciphers and show how to turn the firsts into the seconds. As an illustration, we recall linear cryptanalysis which is a classical example of statistical cryptanalysis. In the second part, we consider the (in)security of block ciphers against statistical cryptanalytic attacks and develop some tools to perform optimal attacks and quantify their efficiency. We start with a simple setting in which the adversary has to distinguish between two sources of randomness and show how an optimal strategy can be derived in certain cases. We proceed with the practical situation where the cardinality of the sample space is too large for the optimal strategy to be implemented and show how this naturally leads to the concept of projection-based distinguishers, which reduce the sample space by compressing the samples. Within this setting, we re-consider the particular case of linear distinguishers and generalize them to sets of arbitrary cardinality. We show how these distinguishers between random sources can be turned into distinguishers between random oracles (or block ciphers) and how, in this setting, one can generalize linear cryptanalysis to Abelian groups. As a proof of concept, we show how to break the block cipher TOY100, introduce the block cipher DEAN which encrypts blocks of decimal digits, and apply the theory to the SAFER block cipher family. In the last part of this thesis, we introduce two new constructions. We start by recalling some essential notions about provable security for block ciphers and about Serge Vaudenay's Decorrelation Theory, and introduce new simple modules for which we prove essential properties that we will later use in our designs. We then present the block cipher C and prove that it is immune against a wide range of cryptanalytic attacks. In particular, we compute the exact advantage of the best distinguisher limited to two plaintext/ciphertext samples between C and the perfect cipher and use it to compute the exact value of the maximum expected linear probability (resp. differential probability) of C which is known to be inversely proportional to the number of samples required by the best possible linear (resp. differential) attack. We then introduce KFC a block cipher which builds upon the same foundations as C but for which we can prove results for higher order adversaries. We conclude both discussions about C and KFC by implementation considerations.

EPFL2008

FOX: a new family of block ciphers

Pascal Junod, Serge Vaudenay

In this paper, we describe the design of a new family of block ciphers based on a Lai-Massey scheme, named FOX. The main features of this design, besides a very high security level, are a large implementation flexibility on various platforms as well as high performances. In addition, we propose a new design of strong and efficient key-schedule algorithms. We provide evidence that FOX is immune to linear and differential cryptanalysis, and we discuss its security towards integral cryptanalysis, algebraic attacks, and other attacks