Abstract:
In this paper we present concrete collision and preimage attacks on a large class of compression function constructions making two calls to the underlying ideal primitives. The complexity of the collision attack is above the theoretical lower bound for constructions of this type, but below the birthday complexity; the complexity of the preimage attack, however, is equal to the theoretical lower bound.
We also present undesirable properties of some of Stam’s compression functions proposed at CRYPTO ’08. We show that when one of the n-bit to n-bit components of the proposed $2n$-bit to $n$-bit compression function is replaced by a fixed-key cipher in the Davies-Meyer mode, the complexity of finding a preimage would be $2^{n/3}$. We also show that the complexity of finding a collision in a variant of the $3n$-bits to $2n$-bits scheme with its output truncated to $3n/2$ bits is $2^{n/2}$. The complexity of our preimage attack on this hash function is about 2^{n}. Finally, we present a collision attack on a variant of the proposed $m+s$-bit to $s$-bit scheme, truncated to $s-1$ bits, with a complexity of O(1). However, none of our results compromise Stam’s security claims.
Keywords: Cryptographic hash functions, Information-theoretic security, Permutation-based hash functions.