Security/Efficiency Tradeoffs for Permutation-Based Hashing

Authors: Phillip Rogaway and John Steinberger

Reference:Advances in Cryptology — EUROCRYPT 2008. LNCS vol. 4965, pp. 220-236, 2008.

Abstract: We provide attacks and analysis that capture a tradeoff, in the ideal-permutation model, between the speed of a permutation-based hash function and its potential security. We show that any 2n-bit to n-bit compression function will have unacceptable collision resistance it makes fewer than three n-bit permutation invocations, and any 3n-bit to 2n-bit compression function will have unacceptable security if it makes fewer than five n-bit permutation invocations. Any rate-α hash function built from n-bit permutations can be broken, in the sense of finding preimages as well as collisions, in about N1-α queries, where N=2n. Our results provide guidance when trying to design or analyze a permutation-based hash function about the limits of what can possibly be done.

Availability: pdf or ps

Rogaway's home page.