## CryptoDB

### Thomas Shrimpton

#### Publications

**Year**

**Venue**

**Title**

2020

CRYPTO

Quantifying the Security Cost of Migrating Protocols to Practice
📺
Abstract

We give a framework for relating the quantitative, concrete security of a "reference'' protocol (say, one appearing in an academic paper) to that of some derived, "real'' protocol (say, appearing in a cryptographic standard). It is based on the indifferentiability framework of Maurer, Renner, and Holenstein (MRH), whose application has been exclusively focused upon non-interactive cryptographic primitives, e.g., hash functions and Feistel networks. Our extension of MRH is supported by a clearly defined execution model, and two composition lemmata, all formalized in a modern pseudocode language. Together, these allow for precise statements about game-based security properties of cryptographic objects (interactive or not) at various levels of abstraction, As a real-world application, we design and prove tight security bounds for a potential TLS 1.3 extension that integrates the SPAKE2 password-authenticated key-exchange into the existing handshake. (This is a problem of current interest to the IETF.)

2019

CRYPTO

Security in the Presence of Key Reuse: Context-Separable Interfaces and Their Applications
📺
Abstract

Key separation is often difficult to enforce in practice. While key reuse can be catastrophic for security, we know of a number of cryptographic schemes for which it is provably safe. But existing formal models, such as the notions of joint security (Haber-Pinkas, CCS ’01) and agility (Acar et al., EUROCRYPT ’10), do not address the full range of key-reuse attacks—in particular, those that break the abstraction of the scheme, or exploit protocol interactions at a higher level of abstraction. This work attends to these vectors by focusing on two key elements: the game that codifies the scheme under attack, as well as its intended adversarial model; and the underlying interface that exposes secret key operations for use by the game. Our main security experiment considers the implications of using an interface (in practice, the API of a software library or a hardware platform such as TPM) to realize the scheme specified by the game when the interface is shared with other unspecified, insecure, or even malicious applications. After building up a definitional framework, we apply it to the analysis of two real-world schemes: the EdDSA signature algorithm and the Noise protocol framework. Both provide some degree of context separability, a design pattern for interfaces and their applications that aids in the deployment of secure protocols.

2008

EPRINT

How to Build a Hash Function from any Collision-Resistant Function
Abstract

Recent collision-finding attacks against hash functions such as MD5 and SHA-1 motivate the use of provably collision-resistant (CR) functions in their place. Finding a collision in a provably CR function implies the ability to solve some hard problem (e.g., factoring). Unfortunately, existing provably CR functions make poor replacements for hash functions as they fail to deliver behaviors demanded by practical use. In particular, they are easily distinguished from a random oracle. We initiate an investigation into building hhash functions from provably CR functions. As a method for achieving this, we present the Mix-Compress-Mix (MCM) construction; it envelopes any provably CR function H (with suitable regularity properties) between two injective ``mixing'' stages. The MCM construction simultaneously enjoys (1) provable collision-resistance in the standard model, and (2) indifferentiability from a monolithic random oracle when the mixing stages themselves are indifferentiable from a random oracle that observes injectivity. We instantiate our new design approach by specifying a blockcipher-based construction that appropriately realizes the mixing stages.

2007

EPRINT

Seven-Property-Preserving Iterated Hashing: ROX
Abstract

Nearly all modern hash functions are constructed by iterating a
compression function. At FSE'04, Rogaway and Shrimpton [RS04] formalized seven security notions for hash functions: collision resistance (Coll) and three variants of second-preimage resistance (Sec, aSec, eSec) and preimage resistance (Pre, aPre, ePre). The main contribution of this paper is in determining, by proof or counterexample, which of these seven notions is preserved by each of eleven existing iterations.
Our study points out that none of them preserves more than three
notions from [RSh04]. In particular, only a single iteration preserves Pre, and none preserves Sec, aSec, or aPre. The latter two notions are particularly relevant for practice, because they do not rely on the problematic assumption that practical compression functions be chosen uniformly from a family. In view of this poor state of affairs, even the mere existence of seven-property-preserving iterations seems uncertain.
As a second contribution, we propose the new Random-Oracle XOR(ROX) iteration that is the first to provably preserve all seven notions, but that, quite controversially, uses a random oracle in the iteration. The compression function itself is not modeled as a random oracle though. Rather, ROX uses an auxiliary small-input random oracle (typically 170 bits) that is called only a logarithmic number of times.

2007

EPRINT

On the Impossibility of Highly-Efficient Blockcipher-Based Hash Functions
Abstract

Fix a small, non-empty set of blockcipher keys $K$. We say a blockcipher-based hash function is highly-efficient if it makes exactly one blockcipher call for each message block hashed, and all blockcipher calls use a key from $K$. Although a few highly-efficient constructions have been proposed, no one has been able to prove their security. In this paper we prove, in the ideal-cipher model, that it is impossible to construct a highly-efficient iterated blockcipher-based hash function that is provably secure. Our result implies, in particular, that the Tweakable Chain Hash (TCH) construction suggested by Liskov, Rivest, and Wagner is not correct under an instantiation suggested for this
construction, nor can TCH be correctly instantiated by any other efficient means.

2007

EPRINT

Building a Collision-Resistant Compression Function from Non-Compressing Primitives
Abstract

We consider how to build an efficient compression function from a small
number of random, non-compressing primitives (fixed-key blockciphers
were our original motivation). Our main goal is to achieve a level of
collision resistance as close as possible to the optimal birthday
bound. We present a $2n$-to-$n$ bit compression function based on
three independent $n$-to-$n$ bit random functions, each called only
once. We show that if the three random functions are treated as
black boxes (i.e., modelled as random oracles),
finding collisions requires $\Theta(2^{n/2}/n^c)$ queries
for $c\approx 1$. We also give a heuristic,
backed by experimental results, suggesting that the security loss is
at most four bits for block sizes up to 256 bits.
We believe this is the best result to date on the matter of building
a collision resistant compression function from non-compressing functions.
It also relates to an open question from Black et al. (Eurocrypt'05), who
showed that compression functions that invoke a single non-compressing
random function cannot suffice.

2006

EPRINT

Deterministic Authenticated-Encryption: A Provable-Security Treatment of the Key-Wrap Problem
Abstract

Standards bodies have been addressing the key-wrap problem, a
cryptographic goal that has never received a provable-security
treatment. In response, we provide one, giving definitions,
constructions, and proofs. We suggest that key-wrapâs goal is
security in the sense of deterministic authenticated-encryption
(DAE), a notion that we put forward. We also provide an alternative
notion, a pseudorandom injection (PRI), which we prove to be
equivalent. We provide a DAE construction, SIV, analyze its concrete
security, develop a blockcipher-based instantiation of it, and
suggest that the method makes a desirable alternative to the
schemes of the X9.102 draft standard. The construction incorporates
a method to turn a PRF that operates on a string into an equally
efficient PRF that operates on a vector of strings, a problem of
independent interest. Finally, we consider IV-based authenticated-
encryption (AE) schemes that are maximally forgiving of repeated
IVs, a goal we formalize as misuse-resistant AE.We show that a DAE
scheme with a vector-valued header, such as SIV, directly realizes
this goal.

2004

EPRINT

Cryptographic Hash-Function Basics: Definitions, Implications and Separations for Preimage Resistance, Second-Preimage Resistance, and Collision Resistance
Abstract

We consider basic notions of security for cryptographic hash
functions: collision resistance, preimage resistance, and
second-preimage resistance. We give seven different definitions
that correspond to these three underlying ideas, and then we work out
all of the implications and separations among these seven definitions
within the concrete-security, provable-security framework. Because
our results are concrete, we can show two types of implications,
"conventional" and "provisional", where the strength of the latter depends on the amount of compression achieved by the hash function. We also distinguish two types of separations, "conditional" and "unconditional". When constructing counterexamples for our separations, we are careful to preserve specified hash-function domains and ranges; this rules out some pathological counterexamples and makes the separations more meaningful in practice.
Four of our definitions are standard while three appear to be new;
some of our relations and separations have appeared, others have not. Here we give a modern treatment that acts to catalog, in one place and with carefully-considered nomenclature, the most basic security notions for cryptographic hash functions.

2004

EPRINT

On the Impossibility of Highly-Efficient Blockcipher-Based Hash Functions
Abstract

Fix a small, non-empty set of blockcipher keys K.
We say a blockcipher-based hash function is "highly-efficient"
if it makes exactly one blockcipher call for each message block hashed, and all blockcipher calls use a key from K. Although a few
highly-efficient constructions have been proposed, no one has been
able to prove their security. In this paper we prove, in the
ideal-cipher model, that it is impossible to construct a
highly-efficient iterated blockcipher-based hash function that is
provably secure. Our result implies, in particular, that the Tweakable Chain Hash (TCH) construction suggested by Liskov, Rivest, and Wagner is not correct under an instantiation suggested for this
construction, nor can TCH be correctly instantiated by any other
efficient means.

2004

EPRINT

A Characterization of Authenticated-Encryption as a Form of Chosen-Ciphertext Security
Abstract

In this note we introduce a variation of the standard definition of chosen-ciphertext security, which we call IND-CCA3, and prove that IND-CCA3 is equivalent to authenticated-encryption.

2002

EPRINT

Black-Box Analysis of the Block-Cipher-Based Hash-Function Constructions from PGV
Abstract

Preneel, Govaerts, and Vandewalle
considered the 64 most basic ways
to construct a hash function
$H:\{0,1\}^*\rightarrow\{0,1\}^n$ from a block cipher
$E:\{0,1\}^n\times\{0,1\}^n\rightarrow\{0,1\}^n$.
They regarded 12 of these 64 schemes as secure,
though no proofs or formal claims were given.
The remaining 52 schemes were shown to be subject to
various attacks.
Here we provide a formal and quantitative treatment of
the 64 constructions considered by PGV.
We prove that, in a black-box model, the 12
schemes that PGV singled out as secure really \textit{are} secure: we
give tight upper and lower bounds
on their collision resistance.
Furthermore, by stepping outside of
the Merkle-Damgard approach to analysis,
we show that an additional 8 of the 64 schemes
are just as collision resistant (up to a small constant) as the first group
of schemes.
Nonetheless, we are able to differentiate among the 20
collision-resistant
schemes by bounding their security as one-way functions.
We suggest that proving black-box bounds,
of the style given here, is a feasible and useful step
for understanding the security of any
block-cipher-based hash-function construction.

2002

EPRINT

Encryption-Scheme Security in the Presence of Key-Dependent Messages
Abstract

Encryption that is only semantically secure should not be used on messages that depend on the underlying secret key; all bets are off when, for example,one encrypts using a shared key K the value K.
Here we introduce a new notion of security, KDM security, appropriate for key-dependent messages. The notion makes sense in both the public-key and shared-key settings. For the latter we show that KDM security is easily achievable within the random-oracle model.
By developing and achieving stronger notions of encryption-scheme security it is hoped that protocols which are proven secure under ``formal'' models of security can, in time, be safely realized by generically instantiating their primitives.

#### Program Committees

- Crypto 2020
- Crypto 2019
- FSE 2017
- Eurocrypt 2016
- FSE 2016
- FSE 2015
- Crypto 2014
- Asiacrypt 2013
- Crypto 2012
- PKC 2011
- Eurocrypt 2011
- Asiacrypt 2010
- Eurocrypt 2009
- Crypto 2008

#### Coauthors

- Elena Andreeva (2)
- John Black (8)
- Alexandra Boldyreva (1)
- Martin Cochran (4)
- Yevgeniy Dodis (1)
- Marc Fischlin (1)
- Markus Jakobsson (2)
- Will Landecker (1)
- Anja Lehmann (1)
- Philip D. MacKenzie (2)
- Chanathip Namprempre (2)
- Gregory Neven (2)
- Onur Özen (1)
- Kenneth G. Paterson (1)
- Christopher Patton (3)
- Bart Preneel (2)
- Thomas Ristenpart (6)
- Phillip Rogaway (10)
- Hovav Shacham (1)
- Martijn Stam (5)
- R. Seth Terashima (5)
- Stefano Tessaro (1)
- Bogdan Warinschi (1)