Seven-Property-Preserving Iterated Hashing: ROX
Nearly all modern hash functions are constructed by iterating a compression function. At FSE’04, Rogaway and Shrimpton [28] formalized seven security notions for hash functions: collision resistance (Coll) and three variants of second-preimage resistance
- PDF / 685,026 Bytes
- 17 Pages / 430 x 660 pts Page_size
- 74 Downloads / 182 Views
SCD-COSIC, Dept. of Electrical Engineering, Katholieke Universiteit Leuven {Elena.Andreeva,Gregory.Neven,Bart.Preneel}@esat.kuleuven.be 2 D´epartement d’Informatique, Ecole Normale Sup´erieure 3 Dept. of Computer Science, Portland State University [email protected] 4 Faculty of Informatics, University of Lugano
Abstract. Nearly all modern hash functions are constructed by iterating a compression function. At FSE’04, Rogaway and Shrimpton [28] formalized seven security notions for hash functions: collision resistance (Coll) and three variants of second-preimage resistance (Sec, aSec, eSec) and preimage resistance (Pre, aPre, ePre). The main contribution of this paper is in determining, by proof or counterexample, which of these seven notions is preserved by each of eleven existing iterations. Our study points out that none of them preserves more than three notions from [28]. As a second contribution, we propose the new Random-Oracle XOR (ROX) iteration that is the first to provably preserve all seven notions, but that, quite controversially, uses a random oracle in the iteration. The compression function itself is not modeled as a random oracle though. Rather, ROX uses an auxiliary small-input random oracle (typically 170 bits) that is called only a logarithmic number of times.
1
Introduction
Cryptographic hash functions, publicly computable maps from inputs of arbitrary length to (short) fixed-length strings, have become a ubiquitous building block in cryptography. Almost all cryptographic hash functions are iterative: given a compression function F that takes (n + b) bits of input and produces n bits of output, they process an arbitrary length input by dividing it into b-bit blocks and iterating F appropriately. The widely used Strengthened MerkleDamg˚ ard (SMD) construction [21,11] is known to yield a collision-resistant iterated hash function if the underlying compression function is collision resistant; in other words, SMD preserves collision resistance of the compression function. Unfortunately, designing collision resistant compression functions seems quite hard: witness the recent collision attacks on several popular hash functions by Wang et al. [33,32]. One way out is to aim for a weaker security notion for the compression function, but not so weak as to make the resulting hash function useless in practice. A natural question to ask is whether these weaker proper
Extended abstract; we refer to the full version [1] for more details and proofs.
K. Kurosawa (Ed.): ASIACRYPT 2007, LNCS 4833, pp. 130–146, 2007. c International Association for Cryptology Research 2007
Seven-Property-Preserving Iterated Hashing: ROX
131
ties are also preserved by SMD. For example, does it preserve second-preimage resistance? One may think so, because SMD preserves collision resistance, and collision resistance can be shown to imply second-preimage resistance, but this says nothing about what happens if you start with a compression function that is only second-preimage resistant. Lai and Massey [16] claimed that finding
Data Loading...
