## CryptoDB

### Joan Daemen

#### Affiliation: Radboud University, Netherlands

#### Publications

**Year**

**Venue**

**Title**

2018

TOSC

Column Parity Mixers
Abstract

We present column parity mixers (CPM), a generalization of the Θ mixing layer that is used in Keccak. Thanks to our description using matrix arithmetic, we can easily derive algebraic, diffusion, and mask propagation properties, leading to a surprising distinction between two types of CPMs. We compare CPMs to other popular types of mixing layers and argue that CPMs can be more efficient. While Keccak has a bit-oriented structure, we make the case that CPMs are also suitable for nibble- or byte-oriented designs. We outline a general substitution-permutation-network-based design strategy using a CPM, for which we show how one can attain strong bounds for differential and linear trails. We apply this strategy concretely to design a 256-bit permutation with an efficient inverse and strong trail bounds. Our permutation design uses a number of ideas that are of independent interest and allows a fast bitsliced implementation that compares quite well with other established ciphers and permutations.

2018

TOSC

The design of Xoodoo and Xoofff
📺
Abstract

This paper presents Xoodoo, a 48-byte cryptographic permutation with excellent propagation properties. Its design approach is inspired by Keccak-p, while it is dimensioned like Gimli for efficiency on low-end processors. The structure consists of three planes of 128 bits each, which interact per 3-bit columns through mixing and nonlinear operations, and which otherwise move as three independent rigid objects. We analyze its differential and linear propagation properties and, in particular, prove lower bounds on the weight of trails using the tree search-based technique of Mella et al. (ToSC 2017). Xoodoo’s primary target application is in the Farfalle construction that we instantiate for the doubly-extendable cryptographic keyed (or deck) function Xoofff. Combining a relatively narrow permutation with the parallelism of Farfalle results in very efficient schemes on a wide range of platforms, from low-end devices to high-end processors with vector instructions.

2018

TOSC

Sound Hashing Modes of Arbitrary Functions, Permutations, and Block Ciphers
📺
Abstract

Cryptographic hashing modes come in many flavors, including Merkle-Damgård with various types of strengthening, Merkle trees, and sponge functions. As underlying primitives, these functions use arbitrary functions, permutations, or block ciphers. In this work we provide three simple proofs, one per primitive type, that cover all modes where the input to the primitive consists of message bits, chaining value bits, and bits that only depend on the mode and message length. Our approach generalizes and simplifies over earlier attempts of Dodis et al. (FSE 2009) and Bertoni et al. (Int. J. Inf. Sec. 2014). We prove tight indifferentiability bounds for modes using each of these three primitive types provided that the mode satisfies some easy to verify conditions.

2017

TOSC

New techniques for trail bounds and application to differential trails in Keccak
Abstract

We present new techniques to efficiently scan the space of high-probability differential trails in bit-oriented ciphers. Differential trails consist in sequences of state patterns that we represent as ordered lists of basic components in order to arrange them in a tree. The task of generating trails with probability above some threshold starts with the traversal of the tree. Our choice of basic components allows us to efficiently prune the tree based on the fact that we can tightly bound the probability of all descendants for any node. Then we extend the state patterns resulting from the tree traversal into longer trails using similar bounding techniques. We apply these techniques to the 4 largest Keccak-f permutations, for which we are able to scan the space of trails with weight per round of 15. This space is orders of magnitude larger than previously best result published on Keccak-f[1600] that reached 12, which in turn is orders of magnitude larger than any published results achieved with standard tools, that reached at most 9. As a result we provide new and improved bounds for the minimum weight of differential trails on 3, 4, 5 and 6 rounds. We also report on new trails that are, to the best of our knowledge, the ones with the highest known probability.

2017

TOSC

Farfalle: parallel permutation-based cryptography
Abstract

In this paper, we introduce Farfalle, a new permutation-based construction for building a pseudorandom function (PRF). The PRF takes as input a key and a sequence of arbitrary-length data strings, and returns an arbitrary-length output. It has a compression layer and an expansion layer, each involving the parallel application of a permutation. The construction also makes use of LFSR-like rolling functions for generating input and output masks and for updating the inner state during expansion. On top of the inherent parallelism, Farfalle instances can be very efficient because the construction imposes less requirements on the underlying primitive than, e.g., the duplex construction or typical block cipher modes. Farfalle has an incremental property: compression of common prefixes of inputs can be factored out. Thanks to its input-output characteristics, Farfalle is really versatile. We specify simple modes on top of it for authentication, encryption and authenticated encryption, as well as a wide block cipher mode. As a showcase, we present Kravatte, a very efficient instance of Farfalle based on Keccak-p[1600, nr] permutations and formulate concrete security claims against classical and quantum adversaries. The permutations in the compression and expansion layers of Kravatte have only 6 rounds apiece and the rolling functions are lightweight. We provide a rationale for our choices and report on software performance.

2017

CHES

Changing of the Guards: A Simple and Efficient Method for Achieving Uniformity in Threshold Sharing
Abstract

Since they were first proposed as a countermeasure against differential power analysis (DPA) and differential electromagnetic analysis (DEMA) in 2006, threshold schemes have attracted a lot of attention from the community concentrating on cryptographic implementations. What makes threshold schemes so attractive from an academic point of view is that they come with an information-theoretic proof of resistance against a specific subset of side-channel attacks: first-order DPA. From an industrial point of view they are attractive as a careful threshold implementation forces adversaries to DPA of higher order, with all its problems such as noise amplification. A threshold scheme that offers the mentioned provable security must exhibit three properties: correctness, incompleteness and uniformity. A threshold scheme becomes more expensive with the number of shares that must be implemented and the required number of shares is lower bound by the algebraic degree of the function being shared plus 1. Defining a correct and incomplete sharing of a function of degree d in $$d+1$$ shares is straightforward. However, up to now there is no generic method to achieve uniformity and finding uniform sharings of degree-d functions with $$d+1$$ shares has been an active research area. In this paper we present a generic, simple and potentially cheap method to find a correct, incomplete and uniform $$d+1$$-share threshold scheme of any S-box layer consisting of degree-d invertible S-boxes. The uniformity is not implemented in the sharings of the individual S-boxes but rather at the S-box layer level by the use of feedforward and some expansion of shares. When applied to the Keccak-$$p$$ nonlinear step $$\chi $$, its cost is very small.

2006

EPRINT

RadioGat\'un, a belt-and-mill hash function
Abstract

We present an approach to design cryptographic hash functions that builds on and improves the one underlying the Panama hash function. We discuss the properties of the resulting hash functions that need to be investigated and give a concrete design called RadioGat\'un that is quite competitive with SHA-1 in terms of performance. We are busy performing an analysis of RadioGat\'un and present in this paper some preliminary results.

2006

EPRINT

Two-Round AES Differentials
Abstract

In this paper we study the probability of differentials and
characteristics over 2 rounds of the AES with the objective to
understand how the components of the AES round transformation
interact.
We extend and correct the analysis of the differential properties
of the multiplicative inverse in GF($2^n$). We show that AES has characteristics with a
fixed-key probability that is many times larger than the EDP. For
instance, in the case of 2-round AES, we measured factors up to
$2^{100}$.
We study the number of characteristics with EDP $>0$ whose
probability adds up to the probability of a differential and
derive formulas that allow to produce a close estimate of this
number for any differential. We show how the properties discovered
in our study can be used to explain the values of the
differentials with the largest EDP values and to construct new
distinguishers using truncated differentials.

2005

EPRINT

Distinguishing Stream Ciphers with Convolutional Filters
Abstract

This paper presents a new type of distinguisher for the shrinking generator and the alternating-step generator with known feedback polynomial and for the multiplexor generator. For the former the distinguisher is more efficient than existing ones and for the latter it results in a complete breakdown of security. The distinguisher is conceptually very simple and lends itself to theoretical analysis leading to reliable predictions of its probability of success.

2005

EPRINT

The Pelican MAC Function
Abstract

At FSE 2005 we presented a new MAC Construction called Alred and a Specific Instance Alpha-MAC. In the presentation we announced a variant of Alpha-MAC under the (working) name Beta-MAC, that can be seen as an optimized version of Alpha-MAC.
We have renamed Beta-MAC to Pelican and present its design in this paper. Pelican is based on Rijndael and a factor 2.5 more efficient than CBC-MAC with Rijndael, while providing a comparable claimed security level.

2005

EPRINT

Probability distributions of Correlation and Differentials in Block Ciphers
Abstract

In this paper, we derive the probability distributions of
difference propagation probabilities and input-output correlations
for random functions and block ciphers, for several of them for
the first time. We show that these parameters have distributions
that are well-studied in the field of probability such as the
normal, Poisson, Gamma and extreme value distributions.
For Markov ciphers there exists a solid theory that expresses
bounds on the complexity of differential and linear cryptanalysis
in terms of average difference propagation probabilities and
average correlations, where the average is taken over the keys.
The propagation probabilities and correlations exploited in
differential and linear cryptanalysis actually depend on the key
and hence so does the attack complexity. The theory of Markov
ciphers does not make statements on the distributions of these
fixed-key properties but rather makes the assumption that their
values will be close to the average for the vast majority of keys.
This assumption is made explicit in the form of the hypothesis of
stochastic equivalence.
In this paper, we study the distributions of propagation properties that are
relevant in the resistance of {\em key-alternating ciphers}
against differential and linear cryptanalysis. Key-alternating ciphers are
basically iterative ciphers where round keys are applied by an XOR
operation in between unkeyed rounds and are a sub-class of Markov
ciphers.
We give the distributions of fixed-key difference propagation
probability and fixed-key correlation of iterative ciphers. We
show that for key-alternating ciphers, the hypothesis of
stochastic equivalence can be discarded. In its place comes the
explicit formulation of the distribution of fixed-key
\emph{differential probability (DP)} of a differential in terms of
its \emph{expected differential probability (EDP)} and the
distribution of the fixed-key \emph{linear probability} (or rather
\emph{potential}) (\emph{LP}) of a linear approximation (or
hull) in terms of its \emph{expected linear probability
(ELP)}. Here the ELP and EDP are defined by disregarding the key
schedule of the block cipher and taking the average over
independently selected round keys, instead of over all cipher
keys. Proving these distributions requires no assumptions
standardly made in Markov cipher theory as perfectly uniform
behavior, independently acting rounds or the technique of
averaging over keys.
For key-alternating ciphers, we show that if the EDP is equal to
$2^{-n}$ with $n$ the block length, the fixed-key DP has a
distribution that is very close to that in a random $n$-bit
cipher. The same holds for the ELP and the corresponding fixed-key
LP. Finally we present a technique for computing bounds on the EDP
based on the distribution of probabilities of differential
characteristics and of the ELP based on the distribution of LP of
linear characteristics.

#### Program Committees

- FSE 2020
- Eurocrypt 2020
- FSE 2019
- Eurocrypt 2018
- FSE 2018
- Crypto 2016
- Crypto 2015
- FSE 2015
- FSE 2014
- Asiacrypt 2014
- Asiacrypt 2012
- FSE 2010
- FSE 2009
- CHES 2009
- FSE 2008
- CHES 2007
- Asiacrypt 2007
- FSE 2007
- CHES 2006
- FSE 2006
- FSE 2005
- FSE 2003
- Eurocrypt 2003
- FSE 2002

#### Coauthors

- Elena Andreeva (1)
- Gilles Van Assche (15)
- Guido Bertoni (6)
- Antoon Bosselaers (2)
- Craig S. K. Clapp (1)
- René Govaerts (6)
- Seth Hoffert (2)
- Ronny Van Keer (2)
- Lars R. Knudsen (1)
- Silvia Mella (1)
- Bart Mennink (3)
- Michael Peeters (5)
- Michaël Peeters (2)
- Bart Preneel (1)
- Vincent Rijmen (7)
- Ko Stoffelen (1)
- Joos Vandewalle (6)
- Erik De Win (1)