Efficient Recursive Diffusion Layers for Block Ciphers, and Hash Functions

Many modern block ciphers use maximum distance separable (MDS) matrices as the main part of their diffusion layers. In this paper, we propose a very efficient new class of diffusion layers constructed from several rounds of Feistel-like structures whose round functions are linear. We investigate the requirements of the underlying linear functions to achieve the maximal branch number for the proposed 4x4 words diffusion layer, which is an indication of the highest level of security with respect to linear and differential attacks. We try to extend our results for up to 8x8 words diffusion layers. The proposed diffusion layers only require simple operations such as word-level XORs, rotations, and they have simple inverses. They can replace the diffusion layer of several block ciphers and hash functions in the literature to increase their security, and performance. Furthermore, it can be deployed in the design of new efficient lightweight block ciphers and hash functions in future.

Recursive Diffusion Layers for Block Ciphers and Hash Functions

Pouyan Sepehrdad

Many modern block ciphers use maximum distance separable (MDS) matrices as the main part of their diffusion layers. In this paper, we propose a new class of diffusion layers constructed from several rounds of Feistel-like structures whose round functions are linear. We investigate the requirements of the underlying linear functions to achieve the maximal branch number for the proposed 44 words diffusion layer. The proposed diffusion layers only require word-level XORs, rotations, and they have simple inverses. They can be replaced in the diffusion layer of the block ciphers MMB and Hierocrypt to increase their security and performance, respectively. Finally, we try to extend our results for up to 88 words diffusion layers.

Springer2012

KFC - The Krazy Feistel Cipher

Thomas Baignères

We introduce KFC, a block cipher based on a three round Feistel scheme. Each of the three round functions has an SPN-like structure for which we can either compute or bound the advantage of the best d-limited adaptive distinguisher, for any value of d. Using results from the decorrelation theory, we extend these results to the whole KFC construction. To the best of our knowledge, KFC is the first practical (in the sense that it can be implemented) block cipher to propose tight security proofs of resistance against large classes of attacks, including most classical cryptanalysis (such as linear and differential cryptanalysis, taking hull effect in consideration in both cases, higher order differential cryptanalysis, the boomerang attack, differential-linear cryptanalysis, and others).

2006

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

Quantitative security of block ciphers

Thomas Baignères

EPFL2008