How to Build a Hash Function from Any Collision-Resistant Function
Recent collision-finding attacks against hash functions such as MD5 and SHA-1 motivate the use of provably collision-resistant (CR) functions in their place. Finding a collision in a provably CR function implies the ability to solve some hard problem (e.g
- PDF / 623,059 Bytes
- 17 Pages / 430 x 660 pts Page_size
- 89 Downloads / 231 Views
Dept. of Computer Science & Engineering, University of California San Diego 9500 Gilman Drive, La Jolla, CA 92093-0404, USA [email protected] http://www-cse.ucsd.edu/users/tristenp 2 Dept. of Computer Science, Portland State University Room 120, Forth Avenue Building, 1900 SW 4th Avenue, Portland OR 97201 USA [email protected] http://www.cs.pdx.edu/∼teshrim 3 Faculty of Informatics, University of Lugano Via Buffi 13, CH-6900 Lugano, Switzerland [email protected] http://www.inf.unisi.ch/
Abstract. Recent collision-finding attacks against hash functions such as MD5 and SHA-1 motivate the use of provably collision-resistant (CR) functions in their place. Finding a collision in a provably CR function implies the ability to solve some hard problem (e.g., factoring). Unfortunately, existing provably CR functions make poor replacements for hash functions as they fail to deliver behaviors demanded by practical use. In particular, they are easily distinguished from a random oracle. We initiate an investigation into building hash functions from provably CR functions. As a method for achieving this, we present the Mix-Compress-Mix (MCM) construction; it envelopes any provably CR function H (with suitable regularity properties) between two injective “mixing” stages. The MCM construction simultaneously enjoys (1) provable collision-resistance in the standard model, and (2) indifferentiability from a monolithic random oracle when the mixing stages themselves are indifferentiable from a random oracle that observes injectivity. We instantiate our new design approach by specifying a blockcipher-based construction that appropriately realizes the mixing stages.
1
Introduction
Background. SHA-1, a Merkle-Damg˚ ard style [24, 15] iterated function, is provably collision resistant under the assumption that its underlying compression function is collision resistant. But the recent collision-finding attacks against SHA-1 (and related hash functions) [37, 38] have made clear the point that assumptions of collision resistance are often unfounded in practice. Rather than assuming collision resistance outright, several works [12, 22, 26, 33, 14] build functions for which the guarantee of collision resistance rests, in a K. Kurosawa (Ed.): ASIACRYPT 2007, LNCS 4833, pp. 147–163, 2007. c International Association for Cryptology Research 2007
148
T. Ristenpart and T. Shrimpton
provable way, on the hardness of some well-studied computational problem. As a simple example, consider the function H(m) = xm mod n where x is some fixed base and n is a (supposedly) hard-to-factor composite [26, 33]. This function is (what we shall call) provably CR since there exists a formal reduction showing that the ability to find collisions in H implies the ability to efficiently factor n. But such a collision-resistant function is not a hash function, at least not when one attempts to define a hash function by its myriad uses in practice1 . For example, hash functions are frequently used as a way to compress and ‘mix-up’ strings of bits in an ‘unpredict
Data Loading...
