Tweaking Key-Alternating Feistel Block Ciphers

Tweakable block cipher as a cryptographic primitive has found wide applications in disk encryption, authenticated encryption mode and message authentication code, etc. One popular approach of designing tweakable block ciphers is to tweak the generic constructions of classic block ciphers. This paper focuses on how to build a secure tweakable block cipher from the Key-Alternating Feistel (KAF) structure, a dedicated Feistel structure with round functions of the form 𝐹𝑖(𝑘𝑖⊕𝑥𝑖) , where 𝑘𝑖 is the secret round key and 𝐹𝑖 is a public random function in the i-th round. We start from the simplest KAF structures that have been published so far, and then incorporate the tweaks to the round key XOR operations by (almost) universal hash functions. Moreover, we limit the number of rounds with the tweak injections for the efficiency concerns of changing the tweak value. Our results are two-fold, depending on the provable security bound: For the birthday-bound security, we present a 4-round minimal construction with two independent round keys, a single round function and two universal hash functions; For the beyond-birthday-bound security, we present a 10-round construction secure up to 𝑂(min{22𝑛/3,22𝑛𝜖−1‾‾‾‾‾‾√4}) adversarial queries, where n is the output size of the round function and 𝜖 is the upper bound of the collision probability of the universal hash functions. Our security proofs exploit the hybrid argument combined with the H-coefficient technique.

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

Design and Analysis of Multi-Block-Length Hash Functions

Onur Özen

Cryptographic hash functions are used in many cryptographic applications, and the design of provably secure hash functions (relative to various security notions) is an active area of research. Most of the currently existing hash functions use the Merkle-Damgård paradigm, where by appropriate iteration the hash function inherits its collision and preimage resistance from the underlying compression function. Compression functions can either be constructed from scratch or be built using well-known cryptographic primitives such as a blockcipher. One classic type of primitive-based compression functions is single-block-length : It contains designs that have an output size matching the output length n of the underlying primitive. The single-block-length setting is well-understood. Yet even for the optimally secure constructions, the (time) complexity of collision- and preimage-finding attacks is at most 2n/2, respectively 2n ; when n = 128 (e.g., Advanced Encryption Standard) the resulting bounds have been deemed unacceptable for current practice. As a remedy, multi-block-length primitive-based compression functions, which output more than n bits, have been proposed. This output expansion is typically achieved by calling the primitive multiple times and then combining the resulting primitive outputs in some clever way. In this thesis, we study the collision and preimage resistance of certain types of multi-call multi-block-length primitive-based compression (and the corresponding Merkle-Damgård iterated hash) functions : Our contribution is three-fold. First, we provide a novel framework for blockcipher-based compression functions that compress 3n bits to 2n bits and that use two calls to a 2n-bit key blockcipher with block-length n. We restrict ourselves to two parallel calls and analyze the sufficient conditions to obtain close-to-optimal collision resistance, either in the compression function or in the Merkle-Damgård iteration. Second, we present a new compression function h: {0,1}3n → {0,1}2n ; it uses two parallel calls to an ideal primitive (public random function) from 2n to n bits. This is similar to MDC-2 or the recently proposed MJH by Lee and Stam (CT-RSA'11). However, unlike these constructions, already in the compression function we achieve that an adversary limited (asymptotically in n) to O (22n(1-δ)/3) queries (for any δ > 0) has a disappearing advantage to find collisions. This is the first construction of this type offering collision resistance beyond 2n/2 queries. Our final contribution is the (re)analysis of the preimage and collision resistance of the Knudsen-Preneel compression functions in the setting of public random functions. Knudsen-Preneel compression functions utilize an [r,k,d] linear error-correcting code over 𝔽2e (for e > 1) to build a compression function from underlying blockciphers operating in the Davies-Meyer mode. Knudsen and Preneel show, in the complexity-theoretic setting, that finding collisions takes time at least 2(d-1)n2. Preimage resistance, however, is conjectured to be the square of the collision resistance. Our results show that both the collision resistance proof and the preimage resistance conjecture of Knudsen and Preneel are incorrect : With the exception of two of the proposed parameters, the Knudsen-Preneel compression functions do not achieve the security level they were designed for.

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.