International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Bruce Schneier

Publications

Year
Venue
Title
2015
EPRINT
2005
EUROCRYPT
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
2000
FSE
2000
FSE
1999
FSE
1998
CRYPTO
1998
FSE
1998
FSE
1997
CRYPTO
1997
FSE
1996
CRYPTO
1996
FSE
1994
FSE
1993
FSE

Program Committees

PKC 2002
FSE 2001
FSE 2000 (Program chair)
Eurocrypt 1999
FSE 1999