# Papers

S. Mella, J. Daemen and G. Van Assche, New techniques for trail bounds and application to differential trails in Keccak, IACR Trans. Symmetric Cryptol., 2017

This paper present techniques to scan the space of low-weight trails in bit-oriented ciphers. By representing two-round trails as lists of units we arrange them in a tree where we can efficiently lower bound the weight of each descendant of a node based on that node alone. Moreover, we present techniques for extending trails to more rounds. Generating all trails up to some weight can then be done by traversing the tree of two-round trails and extending the found candidates to the desired number of rounds. We used these techniques to the generate all 3-round differential trails up to weight 45 of the 4 largest Keccak-p permutations.

G. Bertoni, J. Daemen, S. Hoffert, M. Peeters, G. Van Assche and R. Van Keer, Farfalle: parallel permutation-based cryptography, IACR Trans. Symmetric Cryptol., 2017

This paper introduces 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. On top of the inherent parallelism, Farfalle instances can be very efficient because the construction imposes less requirements on the underlying primitive than other constructions. We specify simple modes on top of Farfalle for authentication, encryption and authenticated encryption, as well as a wide block cipher mode. As a showcase, we present Kravatte, a Farfalle instance based on Keccak-p[1600] and formulate concrete security claims against classical and quantum adversaries. We provide a rationale for our choices and report on software performance.

J. Daemen, B. Mennink and G. Van Assche, Full-State Keyed Duplex With Built-In Multi-User Support, Asiacrypt, 2017

In this paper, we present a generalization of the full-state keyed duplex that natively supports multiple instances by design, and perform a security analysis that improves over the previous ones in terms of a more modular security analysis and a stronger and more adaptive security bound. Via the introduction of an additional parameter to the analysis, our bound demonstrates a significant security improvement in case of nonce-respecting adversaries. Furthermore, by supporting multiple instances by design, instead of adapting the security model to it, we manage to derive a security bound that is largely independent of the number of instances.

As a countermeasure against differential power analysis (DPA), threshold schemes come with an information-theoretic proof of resistance against first-order DPA. Such schemes require correctness, incompleteness and uniformity. The former two properties are straightforward, but up to now there is no generic method to achieve uniformity. In this paper, we present a simple and relatively cheap method to find a correct, incomplete and uniform $d+1$-share threshold scheme for any S-box layer consisting of degree-$d$ invertible S-boxes.

G. Bertoni, J. Daemen, M. Peeters, G. Van Assche and R. Van Keer, KangarooTwelve: fast hashing based on Keccak-p, IACR Cryptology ePrint Archive, 2016

This paper contains the specification and design rationale of KangarooTwelve, discusses implementation aspects and reports on some performance measurements.

G. Bertoni, J. Daemen, M. Peeters, G. Van Assche and R. Van Keer, CAESAR submission: Ketje v2, CAESAR competition (round 3), 2016

This paper contains the specification and design rationale of Ketje and its underlying mode MonkeyDuplex.

G. Bertoni, J. Daemen, M. Peeters, G. Van Assche and R. Van Keer, CAESAR submission: Keyak v2, CAESAR competition (round 3), 2016

This paper contains the specification and design rationale of Keyak and its underlying mode Motorist.

G. Van Assche and R. Van Keer, Structuring and optimizing Keccak software, SPEED-B – Software performance enhancement for encryption and decryption, and benchmarking, 2016

In this paper, we discuss some aspects of the software implementation of Keccak-based algorithms, including techniques to optimize the Keccak-p family of permutations and the structure of the Keccak code package.

E. Andreeva, J. Daemen, B. Mennink and G. Van Assche, Security of Keyed Sponge Constructions Using a Modular Proof Approach, Fast Software Encryption, 2015

In this paper, we reconsider variants of the keyed sponge and derive improved bounds in the classical indistinguishability setting as well as in an extended setting where the adversary targets multiple instances at the same time. These bounds contain a term called multiplicity that is a characteristic of the data available to the attacker. It is at most twice the data complexity, but will be much smaller in practically relevant attack scenarios. We take a modular proof approach, and our indistinguishability bounds are the sum of a bound in the PRP model and a bound on the PRP-security of Even-Mansour type block ciphers in the ideal permutation model, where we obtain the latter result by using Patarin's H-coefficient technique.

G. Bertoni, J. Daemen, M. Peeters and G. Van Assche, Sakura: A Flexible Coding for Tree Hashing, ACNS, 2014

In this paper, we propose a flexible, fairly general, coding for tree hash modes. The coding does not define a tree hash mode, but instead specifies a way to format the message blocks and chaining values into inputs to the underlying function for any topology, including sequential hashing. The main benefit is to avoid input clashes between different tree growing strategies, even before the hashing modes are defined, and to make the SHA-3 standard tree-hashing ready.

G. Bertoni, J. Daemen, M. Peeters and G. Van Assche, Sufficient conditions for sound tree and sequential hashing modes, Int. J. Inf. Sec., 2014

A sponge function processes input in a sequential way. It can however be used as a component in a tree hashing mode. This article gives a set of four practical, simple-to-verify, conditions under which a sequential or parallel hashing mode is sound. For such a mode, it proves that the differentiating advantage over a random oracle is upper bounded by $q^2/2^n$, with $q$ the number of queries to the underlying hash function and n the length of the chaining values. In other words, it shows that it is easy to design a tree or parallel hashing mode whose generic security is not worse than the (in)ability to generate internal collisions. This paper provides a unifying treatment of both tree and sequential hashing modes and, as a by-product, provides insight into classical fixed-input-length compression function based constructions by placing them in a wider context. As for modes that call a sponge function, we show in this paper that a tree or parallel hashing mode takes advantage of its arbitrary output length for optimizing efficiency.

G. Bertoni, J. Daemen, M. Peeters and G. Van Assche, The Making of Keccak, Cryptologia, 2014

The structure and components of Keccak are quite different from its predecessors and at first sight it seems like a complete break with the past. In this paper we show that Keccak is the endpoint of a long learning process involving many intermediate designs, mostly gradual adaptations but also some drastic changes of direction. We take off from our attempts at fixing the Panama hash function, resulting in RadioGatún and our insights on trail backtracking applied to generalizations of these functions. We explain how we originally presented the sponge construction to compactly express security claims for our proposals and how we finally decided to use it in an actual design, that would become Keccak. Then we explain the design choices made in Keccak and how some of its building blocks can be traced back to its predecessor RadioGatún and even earlier.

B. Bilgin, J. Daemen, V. Nikov, S. Nikova, V. Rijmen and G. Van Assche, Efficient and First-Order DPA Resistant Implementations of Keccak, CARDIS, 2013

In many use cases, the implementations of keyed modes of Keccak-p should be protected against side-channel attacks, preferably with a low cost. In this paper, we present threshold implementations (TI) of Keccak-p with three and four shares, based on efficient unprotected parallel and serial architectures. The implementations with four shares satisfy all requirements of the TI approach, while the versions with three shares use extra random bits to compensate for the problems with the uniformity of earlier Keccak-p implementations. We present innovative ideas to reduce the amount of random bits required for re-masking. The proposed implementations are efficient and provably secure against first-order differential power analysis.

G. Bertoni, J. Daemen, M. Peeters and G. Van Assche, A software interface for Keccak, NIST hash forum, 2013

In this note, we propose an interface to Keccak at the level of the sponge and duplex constructions, and inside Keccak at the level of the Keccak-f permutation. Since the publication of this note, this interface has evolved into what is now called SnP in the Keccak Code Package.

G. Bertoni, J. Daemen, M. Peeters, G. Van Assche and R. Van Keer, Keccak implementation overview, SHA-3 competition (round 3), 2012

This document gives technical details on the implementations of Keccak, for software, hardware and protection against side-channel attacks. It also gathers a bunch of implementation techniques, such as the bit interleaving technique (e.g., how to implement Keccak$-f[1600]$ in $32$ bits) or the in-place processing to minimize memory usage. It is a must-read for anyone wishing to optimize his/her implementation.

J. Daemen and G. Van Assche, Differential Propagation Analysis of Keccak, Fast Software Encryption, 2012

This article aims to prove that low-weight differential trails in Keccak$-f[1600]$ do not exist. It does so by showing how to efficiently and exhaustively scan the space of such trails. As a by-product, it introduces new concepts that help read and understand differential trails. In particular, it elegantly characterizes the trails that exploit the kernel, i.e., the worst-case diffusion scenario where the mixing layer acts as the identity.

G. Bertoni, J. Daemen, M. Peeters, G. Van Assche and R. Van Keer, 1001 ways to implement Keccak, Third SHA-3 Candidate Conference, 2012

This note gives a short overview of the different implementation techniques. There is nothing new compared to the Keccak implementation overview document, but it provides a good summary of different implementation aspects.

G. Bertoni, J. Daemen, M. Peeters and G. Van Assche, Permutation-based encryption, authentication and authenticated encryption, Directions in Authenticated Ciphers, 2012

This article explores variants of Keccak, sponge functions and duplex objects in the scope of encryption, authentication and authenticated encryption.

G. Bertoni, J. Daemen, N. Debande, T. Le, M. Peeters and G. Van Assche, Power analysis of hardware implementations protected with secret sharing, MICRO Workshops, 2012

In this paper, we analyze the security of three-share hardware implementations against differential power analysis and advanced variants such as mutual information analysis. We present dedicated distinguishers that allow to recover secret key bits from any cryptographic primitive that is implemented as a sequence of quadratic functions. Starting from the analytical treatment of such distinguishers and information-theoretic arguments, we derive the success probability and required number of traces in the presence of algorithmic noise. We show that attacks on three-share hardware implementation require a number of traces that scales in the third power of the algorithmic noise variance. Finally, we apply and test our model on Keccak in a keyed mode.

G. Bertoni, J. Daemen, M. Peeters and G. Van Assche, The Keccak reference, SHA-3 competition (round 3), 2011

This is the document that defines Keccak. It gives the full specifications, the design rationale, the properties of the step mappings in Keccak$-f$, and our own detailed cryptanalysis. It comes with some companion files that can downloaded here.

G. Bertoni, J. Daemen, M. Peeters and G. Van Assche, The Keccak SHA-3 submission, SHA-3 competition (round 3), 2011

In this document, we define the instances that comply to the SHA-3 requirements, discuss alternate options together with their rationale, describe what can be done to adjust the safety margin or how to deal with existing usage scenarios, and link the implemented API with NIST's.

G. Bertoni, J. Daemen, M. Peeters and G. Van Assche, On alignment in Keccak, Ecrypt II Hash Workshop, 2011

This paper discusses an aspect of symmetric cryptographic primitives that we call alignment. We define this term and show that there are important differences between primitives that have strong and weak alignment. For strong alignment, the propagation of truncated differences or linear masks is predictable, and for weak alignment it is hard to predict. We show that Keccak has weak alignment with respect to rows and discuss the benefits of weak alignment for rebound attacks, trail clustering and plateau trails. The paper contains figures that can also illustrate the differential and linear propagation inside Keccak$-f$.

G. Bertoni, J. Daemen, M. Peeters and G. Van Assche, Cryptographic sponge functions, SHA-3 competition (round 3), 2011

This document gathers all the definitions, applications and properties of sponge functions in one document. It covers the sponge and duplex constructions, their applications, generic attacks, security proofs and design aspects.

G. Bertoni, J. Daemen, M. Peeters and G. Van Assche, On the security of the keyed sponge construction, Symmetric Key Encryption Workshop, 2011

(This paper is deprecated and superseeded by our Asiacrypt 2017 paper.) In this paper, we prove the generic security of the sponge construction when the input is prefixed with a secret key, i.e., when used for authentication or (authenticated) encryption. For these use cases, the net result is that one can achieve the same security level with less capacity (hence more rate) than what indifferentiability suggests. This is particularly interesting for constrained devices, where a small permutation is used.

G. Bertoni, J. Daemen, M. Peeters and G. Van Assche, Duplexing the Sponge: Single-Pass Authenticated Encryption and Other Applications, Selected Areas in Cryptography, 2011

This is the first article defining the duplex construction. The duplex construction allows for both input and output blocks for each call to the underlying permutation. Security of this construction is easy to analyze: it is shown to reduce to that of the sponge construction, hence taking advantage of all known results on sponge. The main application is an authenticated encryption mode that costs one call to the underlying permutation per block.

G. Bertoni, J. Daemen, M. Peeters and G. Van Assche, Note on zero-sum distinguishers of Keccak-f, NIST hash forum, 2010

This note discusses the zero-sum distinguishers found on Keccak$-f$. It shows that the generic construction of a zero-sum set is at most a factor 2 slower than for the proposed distinguishers, which limits their impact. The note explains why we nevertheless decided to increase the number of rounds from 18 to 24 in Keccak$-f[1600]$. Note that in the meantime, zero-sum distinguishers were extended to the full 24 rounds, but due to apparent lack of impact and extreme complexity (zero-sum set size $2^{1575}$ by Duan and Lai), we decided not to further increase the number of rounds.

G. Bertoni, J. Daemen, M. Peeters and G. Van Assche, Note on Keccak parameters and usage, NIST hash forum, 2010

This note discusses different options of parameters and usage for Keccak. Except for a discussion on the width of Keccak$-f$ and on the benefits of parallel hashing on modern CPUs, this note has been integrated into the Keccak SHA-3 submission document.

G. Bertoni, J. Daemen, M. Peeters and G. Van Assche, Building power analysis resistant implementations of Keccak, Second SHA-3 Candidate Conference, 2010

This paper proposes countermeasures against side-channel attacks, and more precisely, differential power analysis and variants. A more up-to-date content can be found in the Keccak implementation overview.

G. Bertoni, J. Daemen, M. Peeters and G. Van Assche, Sponge-Based Pseudo-Random Number Generators, CHES, 2010

This article proposes a mode for pseudo-random number generation on top of a sponge function. The mode is close to the duplex construction, with feed and fetch calls, so as to allow the generator to be easily and efficiently reseedable. The resulting pseudo-random number generator is interesting for constrained platforms in that the sponge construction does not need more memory than the state. Generic security against state recovery is taken one step further ("beyond the birthday bound") than what indifferentiability directly achieves. An alternate mode based on the duplex construction can be found in Duplexing the sponge: single-pass authenticated encryption and other applications.

G. Bertoni, J. Daemen, M. Peeters and G. Van Assche, The Road from Panama to Keccak via RadioGatún, Dagstuhl Seminar on Symmetric Cryptography, 2009

In this paper, we explain the design choices of Panama and RadioGatún, which lead to Keccak. We focus on three important aspects: the role of the belt in the light of differential trails, the relative advantages of a block mode hash function compared to a stream mode one, and the design philosophy differences between Keccak and its predecessors.

G. Bertoni, J. Daemen, M. Peeters and G. Van Assche, Note on side-channel attacks and their countermeasures, NIST hash forum, 2009

This note discusses the relevance of protecting against side-channel attacks in the scope of keyed modes, and argues the high benefit of using bitwise Boolean operations, in contrast to addition-rotation-XOR (ARX) operations.

G. Bertoni, J. Daemen, M. Peeters and G. Van Assche, On the Indifferentiability of the Sponge Construction, EUROCRYPT, 2008

This article proves that the differentiating advantage of a sponge function over a random oracle is upper bounded by $N(N+1)/2^{c+1}$, with $N$ the number of calls to the underlying transformation or permutation and $c$ the capacity. In other words, it shows that the sponge construction is free of generic attacks (at least in the single-stage model) under complexity of about $2^{c/2}$.

G. Bertoni, J. Daemen, M. Peeters and G. Van Assche, Sponge functions, Ecrypt Hash Workshop, 2007

This is the first article defining and analyzing sponge functions. It is fully contained in Cryptographic sponge functions, except that our original definition allowed for non-binary input/output blocks. We sent this article also as an official comment on NIST's initial SHA-3 requirements.

G. Bertoni, J. Daemen, M. Peeters and G. Van Assche, RadioGatún, a belt-and-mill hash function, IACR Cryptology ePrint Archive, 2006

In this paper, we presented a new approach to design cryptographic hash functions that built on the one underlying the Panama hash function and gave a concrete design called RadioGatún. We later abandoned this design approach in favor of the hermetic sponge strategy. Still, Keccak has many building blocks in common with RadioGatún.