International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

John Black

Affiliation: University of Colorado, Boulder

Publications

Year
Venue
Title
2010
JOFC
2009
JOFC
2009
FSE
2007
EPRINT
On the Impossibility of Highly-Efficient Blockcipher-Based Hash Functions
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
FSE
2006
FSE
2006
EPRINT
MAC Reforgeability
John Black Martin Cochran
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
EUROCRYPT
2005
JOFC
2005
EPRINT
The Ideal-Cipher Model, Revisited: An Uninstantiable Blockcipher-Based Hash Function
John Black
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
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
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
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
CRYPTO
2002
EUROCRYPT
2002
EPRINT
Black-Box Analysis of the Block-Cipher-Based Hash-Function Constructions from PGV
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
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
John Black Phillip Rogaway
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
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
John Black Phillip Rogaway
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.
2000
CRYPTO
1999
CRYPTO

Program Committees

FSE 2014
Eurocrypt 2012
FSE 2011
PKC 2011
Crypto 2009 (Program chair)
FSE 2008
Crypto 2008
Crypto 2005
Eurocrypt 2004
Crypto 2004