High performance VLSI architectures implementing strong cryptographic primitives

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.

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

Neutrality-Based Symmetric Cryptanalysis

Shahram Khazaei

Cryptographic primitives are the basic components of any cryptographic tool. Block ciphers, stream ciphers and hash functions are the fundamental primitives of symmetric cryptography. In symmetric cryptography, the communicating parties perform essentially the same operation and use the same key, if any. This thesis concerns cryptanalysis of stream ciphers and hash functions. The main contribution of this work is introducing the concept of probabilistic neutrality for the arguments of a function, a generalization of the definition of neutrality. An input argument of a given function is called neutral if it does not affect the output of the function. This simple idea has already been implicitly used in key recovery cryptanalysis of block ciphers and stream ciphers. However, in 2004, Biham and Chen explicitly used the idea of neutrality to speed up collision finding algorithms for hash functions. We call an input argument of a function probabilistic neutral if it does not have a "significant" influence on the output of the function. Simply stated, it means that if the input argument is changed, the output of the function stays the same with a probability "close" to one. We will exploit the idea of probabilistic neutrality to assess the security of several stream ciphers and hash functions. Interestingly, all our cryptanalyses rely on neutrality and/or probabilistic neutrality. In other words, these concepts will appear as a common ingredient in all of our cryptanalytic algorithms. To the best of our knowledge, this is the first time that the probabilistic neutrality has found diverse applications in cryptanalysis.

EPFL2010

Location verification and key management in wireless networks

Srdan Capkun

This thesis is primarily concerned with two security mechanisms for wireless networks: location verification and key management. These mechanisms are potential building blocks in the security architectures of a range of applications. Under location verification, we consider mechanisms for secure encounter, distance and position verification. Possible applications of location verification mechanisms include node tracking, secure topology discovery, secure positioning and the detection of node removal and stealing. Key management protocols are used to ensure that correct public keys of entities are known and used with the entities to which they correspond, and that correct shared secret keys are used with the entities with which they are established. Key management protocols thus provide a good basis for achieving various security objectives, such as securing routing, or the protection of users' personal communications. In the first part of this thesis, we propose several location verification mechanisms and we show their applicability to wireless networks. First, we analyze the resistance of the distance and position measurement techniques to attacks. We then propose mechanisms for secure position verification. We further demonstrate the applicability of these mechanisms to secure positioning and node removal detection in wireless multi-hop networks. We then present a set of mechanisms for the verification of node encounters in wireless multi-hop networks. Finally, we show how encounter verification can be used to prevent wormhole attacks, to secure lastencounter routing, and to secure topology discovery. Our location verification mechanisms are based on distance-bounding and distance estimation techniques, and rely on conventional cryptographic primitives. In the second part of the thesis, we propose a straightforward, mobility-assisted technique that can be used to provide peer-to-peer security in mobile networks. We show that far from being a hurdle, mobility can be exploited to set up security associations among users. We leverage on the temporary vicinity of users, during which appropriate cryptographic protocols are run. We illustrate the operation of the solution in fully self-organized ad hoc networks, and in ad hoc networks that are controlled by an off-line central authority. We then explore routing in ad hoc networks in which security associations are not established between all pairs of nodes. We show that in that case, secure routing is still possible, and we propose related protocols. We then propose a set of protocols for public-key management in self-organized ad hoc networks. We base our approach on public-key certificates and certificate chaining. We show that this approach is efficient in scenarios in which users issue mutual certificates in a random manner, and in those in which users create PGP-like certificate graphs. We further present a detailed analysis of the PGP certificate graph and we show that this graph exhibits some small world properties. We also present a model for the construction of PGP-like small world certificate graphs.