International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

John Kelsey

Affiliation: NIST, United States

Publications

Year
Venue
Title
2016
JOFC
2015
EPRINT
2015
CHES
2013
CHES
The Future of SHA-3
John Kelsey
2008
EUROCRYPT
2007
EPRINT
Cryptanalysis of a class of cryptographic hash functions
Praveen Gauravaram John Kelsey
We apply new cryptanalytical techniques to perform the generic multi-block multicollision, second preimage and herding attacks on the Damg{\aa}rd-Merkle hash functions with linear-XOR/additive checksums. The computational work required to perform these attacks on the Damg{\aa}rd-Merkle hash functions with linear-XOR/additive checksum of message blocks (GOST), intermediate states (\textbf{3C}, MAELSTROM-0, F-Hash) or both is only a little more than what is required on the Damg{\aa}rd-Merkle hash functions. Our generic attacks on GOST answers the open question of Hoch and Shamir at FSE 2006 on the security of the iterated hash functions with the linear mixing of message blocks.
2006
EUROCRYPT
2006
FSE
2005
EUROCRYPT
2005
EPRINT
Herding Hash Functions and the Nostradamus Attack
John Kelsey Tadayoshi Kohno
In this paper, we develop a new attack on Damg{\aa}rd-Merkle hash functions, called the \emph{herding attack}, in which an attacker who can find many collisions on the hash function by brute force can first provide the hash of a message, and later ``herd'' any given starting part of a message to that hash value by the choice of an appropriate suffix. We introduce a new property which hash functions should have--Chosen Target Forced Prefix (CTFP) preimage resistance--and show the distinction between Damg{\aa}rd-Merkle construction hashes and random oracles with respect to this property. We describe a number of ways that violation of this property can be used in arguably practical attacks on real-world applications of hash functions. An important lesson from these results is that hash functions susceptible to collision-finding attacks, especially brute-force collision-finding attacks, cannot in general be used to prove knowledge of a secret value
2004
EPRINT
Second Preimages on n-bit Hash Functions for Much Less than 2^n Work
John Kelsey Bruce Schneier
We provide a second preimage attack on all $n$-bit iterated hash functions with Damgard-Merkle strengthening and $n$-bit itermediate states, allowing a second preimage to be found for a $2^k$-message-block message with about $k \times 2^{n/2+1}+2^{n-k+1}$ work. Using SHA1 as an example, our attack can find a second preimage for a $2^{60}$ byte message in $2^{106}$ work, rather than the previously expected $2^{160}$ work. We also provide slightly cheaper ways to find multicollisions than the method of Joux. Both of these results are based on expandable messages--patterns for producing messages of varying length, which all collide on the intermediate hash result immediately after processing the message. We also provide algorithms for finding expandable messages for a hash function, using only a small multiple of the work done to find a single collision in the hash function.
2003
FSE
2002
FSE
2000
FSE
2000
FSE
1999
FSE
1998
CRYPTO
1998
FSE
1998
FSE
1997
CRYPTO
1996
CRYPTO
1996
FSE

Program Committees

FSE 2018
FSE 2017
FSE 2013
Eurocrypt 2012
FSE 2012
Crypto 2010
Eurocrypt 2009
Crypto 2007
FSE 2007