## CryptoDB

### John Black

#### Affiliation: University of Colorado, Boulder

#### Publications

**Year**

**Venue**

**Title**

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.

2006

EPRINT

MAC Reforgeability
Abstract

Message Authentication Codes (MACs) are central algorithms deployed in virtually every security protocol in common usage. In these protocols, the integrity and authenticity of messages rely entirely on the security of the MAC; we examine cases in which this security is lost.
In this paper, we examine the notion of reforgeability for MACs. We first give a definition for this new notion, then examine some of the most widely-used and well-known MACs under our definition. We show that for each of these MACs there exists an attack that allows efficient forgeries after the first one is obtained, and we show that simply making these schemes stateful is usually insufficient. For those schemes where adding state is effective, we go one step further to examine how counter misuse affects the security of the MAC, finding, in many cases, simply repeating a single counter value yields complete insecurity. These issues motivated the design of a new scheme, WMAC, which has a number of desirable properties. It is as efficient as the fastest MACs, resists counter misuse, and has tags which may be truncated to the desired length without affecting security (currently, the fastest MACs do not have this property), making it resistant to reforging attacks and arguably the best MAC for constrained environments.

2005

EPRINT

The Ideal-Cipher Model, Revisited: An Uninstantiable Blockcipher-Based Hash Function
Abstract

The Ideal-Cipher Model of a blockcipher is a well-known and widely-used model dating back to Shannon and has seen frequent use in proving the security of various cryptographic objects and protocols.
But very little discussion has transpired regarding the meaning of
proofs conducted in this model or regarding the model's validity.
In this paper, we briefly discuss the implications of proofs done
in the ideal-cipher model, then show some limitations of the model analogous to recent work regarding the Random-Oracle Model.
In particular, we extend work by Canetti, Goldreich and Halevi,
and a recent simplification by Maurer, Renner, and Holenstein,
to exhibit a blockcipher-based hash function that is provably-secure in the ideal-cipher model but trivially insecure when instantiated by any blockcipher.

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

How to Cheat at Chess: A Security Analysis of the Internet Chess Club
Abstract

The Internet Chess Club (ICC) is a popular online chess server with more than 30,000 members worldwide including various celebrities and the best chess players in the world. Although the ICC website assures its users that the security protocol used between client and server provides sufficient security for sensitive information to be transmitted (such as credit card numbers), we show this is not true. In particular we show how a passive adversary can easily read all communications with a trivial amount of computation, and how an active adversary can gain virtually unlimited powers over an ICC user. We also show simple methods for defeating the timestamping mechanism used by ICC. For each problem we uncover, we suggest repairs. Most of these are practical and inexpensive.

2003

EPRINT

Building Secure Cryptographic Transforms, or How to Encrypt and MAC
Abstract

We describe several notions of ``cryptographic transforms,''
symmetric schemes designed to meet a variety of privacy and
authenticity goals. We consider goals, such as replay-avoidance and
in-order packet delivery, that have not been fully addressed in
previous works in this area. We then provide an analysis of
possible ways to combine standard encryption and message
authentication schemes in order to provably meet these
goals. Our results further narrow the gap between
the provable-security results from the theoretical community and the
needs of developers who implement real systems.

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.

2001

EPRINT

Ciphers with Arbitrary Finite Domains
Abstract

We introduce the problem of enciphering members of a finite set $M$
where $k=|M|$ is arbitrary (in particular, it need not be a power
of two). We want to achieve this goal starting from a block cipher
(which requires a message space of size $N=2^n$, for some $n$).
We look at a few solutions to this problem, focusing on the case
when $M=[0, k-1]$.

2001

EPRINT

OCB Mode
Abstract

This paper was prepared for NIST, which is considering new
block-cipher modes of operation. It describes a parallelizable
mode of operation that simultaneously provides both privacy
and authenticity. "OCB mode" encrypts-and-authenticates
an arbitrary message $M\in\bits^*$ using only $\lceil |M|/n\rceil + 2$
block-cipher invocations, where $n$ is the block length of the
underlying block cipher. Additional overhead is small.
OCB refines a scheme, IAPM, suggested by Jutla [IACR-2000/39], who
was the first to devise an authenticated-encryption mode with minimal
overhead compared to standard modes. Desirable new properties of
OCB include: very cheap offset calculations; operating on an arbitrary
message $M\in\bits^*$; producing ciphertexts of minimal length;
using a single underlying cryptographic key; making a nearly optimal number
of block-cipher calls; avoiding the need for a random IV; and rendering it
infeasible for an adversary to find "pretag collisions". The paper
provides a full proof of security for OCB.

2001

EPRINT

A Block-Cipher Mode of Operation for Parallelizable Message Authentication
Abstract

We define and analyze a
simple and fully parallelizable block-cipher mode of operation
for message authentication.
Parallelizability does not come at the
expense of serial efficiency: in a conventional, serial
environment, the algorithm's speed is within
a few percent of the (inherently sequential) CBC~MAC.
The new mode, PMAC, is deterministic,
resembles a standard mode of operation
(and not a Carter-Wegman MAC),
works for strings of any bit length,
employs a single block-cipher key,
and uses just max{1, ceiling(|M|/n)}
block-cipher calls to MAC any string M using an
n-bit block cipher.
We prove PMAC secure,
quantifying an adversary's forgery probability
in terms of the quality of the block cipher as a
pseudorandom permutation.

#### Program Committees

- FSE 2014
- Eurocrypt 2012
- FSE 2011
- PKC 2011
- FSE 2008
- Crypto 2008
- Crypto 2005
- Eurocrypt 2004
- Crypto 2004

#### Coauthors

- Mihir Bellare (1)
- Martin Cochran (8)
- Ryan Gardner (1)
- Shai Halevi (1)
- Trevor Highland (1)
- Tadayoshi Kohno (1)
- Hugo Krawczyk (1)
- Ted Krovetz (2)
- Adriana Palacio (1)
- Phillip Rogaway (11)
- Thomas Shrimpton (8)
- Martijn Stam (1)