## CryptoDB

### Bart Mennink

#### Affiliation: Radboud University, Netherlands

#### Publications

**Year**

**Venue**

**Title**

2019

CRYPTO

How to Build Pseudorandom Functions from Public Random Permutations
Abstract

Pseudorandom functions are traditionally built upon block ciphers, but with the trend of permutation based cryptography, it is a natural question to investigate the design of pseudorandom functions from random permutations. We present a generic study of how to build beyond birthday bound secure pseudorandom functions from public random permutations. We first show that a pseudorandom function based on a single permutation call cannot be secure beyond the $$2^{n/2}$$ birthday bound, where n is the state size of the function. We next consider the Sum of Even-Mansour (SoEM) construction, that instantiates the sum of permutations with the Even-Mansour construction. We prove that SoEM achieves tight $$2n{/}3$$-bit security if it is constructed from two independent permutations and two randomly drawn keys. We also demonstrate a birthday bound attack if either the permutations or the keys are identical. Finally, we present the Sum of Key Alternating Ciphers (SoKAC) construction, a translation of Encrypted Davies-Meyer Dual to a public permutation based setting, and show that SoKAC achieves tight $$2n{/}3$$-bit security even when a single key is used.

2018

TOSC

Short Non-Malleable Codes from Related-Key Secure Block Ciphers
Abstract

A non-malleable code is an unkeyed randomized encoding scheme that offers the strong guarantee that decoding a tampered codeword either results in the original message, or in an unrelated message. We consider the simplest possible construction in the computational split-state model, which simply encodes a message m as k||Ek(m) for a uniformly random key k, where E is a block cipher. This construction is comparable to, but greatly simplifies over, the one of Kiayias et al. (ACM CCS 2016), who eschewed this simple scheme in fear of related-key attacks on E. In this work, we prove this construction to be a strong non-malleable code as long as E is (i) a pseudorandom permutation under leakage and (ii) related-key secure with respect to an arbitrary but fixed key relation. Both properties are believed to hold for “good” block ciphers, such as AES-128, making this non-malleable code very efficient with short codewords of length |m|+2τ (where τ is the security parameter, e.g., 128 bits), without significant security penalty.

2018

TCC

Towards Tight Security of Cascaded LRW2
Abstract

The Cascaded LRW2 tweakable block cipher was introduced by Landecker et al. at CRYPTO 2012, and proven secure up to $$2^{2n/3}$$ queries. There has not been any attack on the construction faster than the generic attack in $$2^n$$ queries. In this work we initiate the quest towards a tight bound. We first present a distinguishing attack in $$2n^{1/2}2^{3n/4}$$ queries against a generalized version of the scheme. The attack is supported with an experimental verification and a formal success probability analysis. We subsequently discuss non-trivial bottlenecks in proving tight security, most importantly the distinguisher’s freedom in choosing the tweak values. Finally, we prove that if every tweak value occurs at most $$2^{n/4}$$ times, Cascaded LRW2 is secure up to $$2^{3n/4}$$ queries.

2018

ASIACRYPT

Short Variable Length Domain Extenders with Beyond Birthday Bound Security
Abstract

Length doublers are cryptographic functions that transform an n-bit cryptographic primitive into an efficient and secure cipher that length-preservingly encrypts strings of length in $$[n,2n-1]$$. All currently known constructions are only proven secure up to the birthday bound, and for all but one construction this bound is known to be tight. We consider the remaining candidate, $$\mathrm {LDT}$$ by Chen et al. (ToSC 2017(3)), and prove that it achieves beyond the birthday bound security for the domain [n, 3n / 2). We generalize the construction to multiple rounds and demonstrate that by adding one more encryption layer to $$\mathrm {LDT} $$, beyond the birthday bound security can be achieved for all strings of length in $$[n,2n-1]$$: security up to around $$2^{2n/3}$$ for the encryption of strings close to n and security up to around $$2^{n}$$ for strings of length close to 2n. The security analysis of both schemes is performed in a modular manner through the introduction and analysis of a new concept called “harmonic permutation primitives.”

2018

TOSC

Key Prediction Security of Keyed Sponges
Abstract

The keyed sponge is a well-accepted method for message authentication. It processes data at a certain rate by sequential evaluation of an underlying permutation. If the key size k is smaller than the rate, currently known bounds are tight, but if it exceeds the rate, state of the art only dictates security up to 2k/2. We take closer inspection at the key prediction security of the sponge and close the remaining gap in the existing security analysis: we confirm key security up to close to 2k, regardless of the rate. The result impacts all applications of the keyed sponge and duplex that process at a rate smaller than the key size, including the STROBE protocol framework, as well as the related constructions such as HMAC-SHA-3 and the sandwich sponge.

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

CRYPTO

2017

TOSC

Efficient Length Doubling From Tweakable Block Ciphers
Abstract

We present a length doubler, LDT, that turns an n-bit tweakable block cipher into an efficient and secure cipher that can encrypt any bit string of length [n..2n − 1]. The LDT mode is simple, uses only two cryptographic primitive calls (while prior work needs at least four), and is a strong length-preserving pseudorandom permutation if the underlying tweakable block ciphers are strong tweakable pseudorandom permutations. We demonstrate that LDT can be used to neatly turn an authenticated encryption scheme for integral data into a mode for arbitrary-length data.

2017

TOSC

Understanding RUP Integrity of COLM
Abstract

The authenticated encryption scheme COLM is a third-round candidate in the CAESAR competition. Much like its antecedents COPA, ELmE, and ELmD, COLM consists of two parallelizable encryption layers connected by a linear mixing function. While COPA uses plain XOR mixing, ELmE, ELmD, and COLM use a more involved invertible mixing function. In this work, we investigate the integrity of the COLM structure when unverified plaintext is released, and demonstrate that its security highly depends on the choice of mixing function. Our results are threefold. First, we discuss the practical nonce-respecting forgery by Andreeva et al. (ASIACRYPT 2014) against COPA’s XOR mixing. Then we present a noncemisusing forgery against arbitrary mixing functions with practical time complexity. Finally, by using significantly larger queries, we can extend the previous forgery to be nonce-respecting.

2017

TOSC

Optimal PRFs from Blockcipher Designs
Abstract

Cryptographic modes built on top of a blockcipher usually rely on the assumption that this primitive behaves like a pseudorandom permutation (PRP). For many of these modes, including counter mode and GCM, stronger security guarantees could be derived if they were based on a PRF design. We propose a heuristic method of transforming a dedicated blockcipher design into a dedicated PRF design. Intuitively, the method consists of evaluating the blockcipher once, with one or more intermediate state values fed-forward. It shows strong resemblance with the optimally secure EDMD construction by Mennink and Neves (CRYPTO 2017), but the use of internal state values make their security analysis formally inapplicable. In support of its security, we give the rationale of relying on the EDMD function (as opposed to alternatives), and present analysis of simplified versions of our conversion method applied to the AES. We conjecture that our main proposal AES-PRF, AES with a feed-forward of the middle state, achieves close to optimal security. We apply the design to GCM and GCM-SIV, and demonstrate how it entails significant security improvements. We furthermore demonstrate how the technique extends to tweakable blockciphers and allows for security improvements in, for instance, PMAC1.

2016

EUROCRYPT

2016

TOSC

Security Analysis of BLAKE2's Modes of Operation
Abstract

BLAKE2 is a hash function introduced at ACNS 2013, which has been adopted in many constructions and applications. It is a successor to the SHA-3 finalist BLAKE, which received a significant amount of security analysis. Nevertheless, BLAKE2 introduces sufficient changes so that not all results from BLAKE carry over, meaning new analysis is necessary. To date, all known cryptanalysis done on BLAKE2 has focused on its underlying building blocks, with little focus placed on understanding BLAKE2’s generic security. We prove that BLAKE2’s compression function is indifferentiable from a random function in a weakly ideal cipher model, which was not the case for BLAKE. This implies that there are no generic attacks against any of the modes that BLAKE2 uses.

2015

EPRINT

2015

EPRINT

2015

ASIACRYPT

2010

EPRINT

Towards Side-Channel Resistant Block Cipher Usage or Can We Encrypt Without Side-Channel Countermeasures?
Abstract

Based on re-keying techniques by Abdalla, Bellare, and Borst [1,2], we consider two black-box secure block cipher based symmetric encryption schemes, which we prove secure in the physically observable
cryptography model. They are proven side-channel secure against a strong type of adversary that can adaptively choose the leakage function as long as the leaked information is bounded. It turns out that our simple construction is side-channel secure against all types of attacks that satisfy some reasonable assumptions. In particular, the security turns out to be negligible in the block ciphers block size n, for all attacks. We also show that our ideas result in an interesting alternative to the implementation of block ciphers using different logic styles or masking countermeasures.

2010

EPRINT

On the Indifferentiability of the Gr{\o}stl Hash Function
Abstract

The notion of indifferentiability, introduced by Maurer et al., is an important criterion for the security of hash functions. Concretely, it ensures that a hash function has no structural design flaws and thus guarantees security against generic attacks up to the exhibited bounds. In this work we prove the indifferentiability of Gr{\o}stl, a second round SHA-3 hash function candidate. Gr{\o}stl combines characteristics of the wide-pipe and chop-Merkle-Damg{\aa}rd iterations and uses two distinct permutations P and Q internally. Under the assumption that P and Q are random l-bit permutations, where l is the iterated state size of Gr{\o}stl, we prove that the advantage of a distinguisher to differentiate Gr{\o}stl from a random oracle is upper bounded by O((Kq)^4/2^l), where the distinguisher makes at most q queries of length at most K blocks. For the specific Gr{\o}stl parameters, this result implies that Gr{\o}stl behaves like a random oracle up to q=O(2^{n/2}) queries, where n is the output size.
Furthermore, we show that the output transformation of Gr{\o}stl, as well as `Gr{\o}stail' (the composition of the final compression function and the output transformation), are clearly differentiable from a random oracle. This renders out indifferentiability proofs which rely on the idealness of a final state transformation.

2010

EPRINT

Security Reductions of the Second Round SHA-3 Candidates
Abstract

In 2007, the US National Institute for Standards and Technology announced a call for the design of a new cryptographic hash algorithm in response to vulnerabilities identified in existing hash functions, such as MD5 and SHA-1. NIST received many submissions, 51 of which got accepted to the first round. At present, 14 candidates are left in the second round. An important criterion in the selection process is the SHA-3 hash function security and more concretely, the possible security reductions of the hash function to the security of its underlying building blocks. While some of the candidates are supported with firm security reductions, for most of the schemes these results are still incomplete. In this paper, we compare the state of the art provable security reductions of the second round candidates. We discuss all SHA-3 candidates at a high functional level, and analyze and summarize the security reduction results. Surprisingly, we derive some security bounds from the literature, which the hash function designers seem to be unaware of. Additionally, we generalize the well-known proof of collision resistance preservation, such that all SHA-3 candidates with a suffix-free padding are covered.

#### Program Committees

- FSE 2020
- Eurocrypt 2019
- FSE 2019
- Asiacrypt 2018
- FSE 2018
- Eurocrypt 2018
- FSE 2017
- Asiacrypt 2017
- Eurocrypt 2017
- FSE 2016
- Asiacrypt 2015

#### Coauthors

- Elena Andreeva (11)
- Tomer Ashur (1)
- Gilles Van Assche (3)
- Begül Bilgin (1)
- Andrey Bogdanov (7)
- Yu Long Chen (3)
- Joan Daemen (3)
- Yuanxi Dai (1)
- Nilanjan Datta (1)
- Yevgeniy Dodis (1)
- Serge Fehr (1)
- Robert Granger (2)
- Jorge Guajardo (1)
- Anthony Van Herrewege (1)
- Philipp Jovanovic (4)
- Pierre Karpman (1)
- Eran Lambooij (1)
- Jooyoung Lee (1)
- Atul Luykx (11)
- Nicky Mouha (4)
- Mridul Nandi (2)
- Samuel Neves (5)
- Kenneth G. Paterson (1)
- Bart Preneel (8)
- Reza Reyhanitabar (2)
- John P. Steinberger (2)
- Elmar Tischhauser (1)
- Ingrid Verbauwhede (1)
- Damian Vizár (2)
- Dai Watanabe (1)
- Kan Yasuda (5)