International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Martin Cochran

Affiliation: Google

Publications

Year
Venue
Title
2009
JOFC
2009
FSE
2007
EPRINT
On the Impossibility of Highly-Efficient Blockcipher-Based Hash Functions
John Black Martin Cochran Thomas Shrimpton
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
Notes on the Wang et al. $2^{63}$ SHA-1 Differential Path
Martin Cochran
Although advances in SHA-1 cryptanalysis have been made since the 2005 announcement of a $2^{63}$ attack by Wang et al., the details of the attack have not yet been presented or verified. This note does just that. Working from Adi Shamir's 2005 CRYPTO rump session presentation of Wang et al.'s work, this note verifies and presents the differential path and associated conditions. Although the error analysis for the advanced condition correction technique is not verified, a method is presented which yields a two-block collision attack on SHA-1 requiring an estimated $2^{62}$ SHA-1 computations if the original error analysis by Wang et al. is correct. The differential path is presented for only the first block of the two-block attack, but the second block path likely differs from the first in only the first 10 steps and could be derived from the information presented here.
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
2004
EPRINT
On the Impossibility of Highly-Efficient Blockcipher-Based Hash Functions
John Black Martin Cochran Thomas Shrimpton
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
John Black Martin Cochran Ryan Gardner
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.