22
$\begingroup$

I've seen contradictory results. Sometimes hash functions are collision-resistant but not necessarily second-preimage resistant. I've seen this kind of things in papers from Bart Preneel:

How that can be possible ?

We have theorems that say that if a hash function is collision-resistant then it is second preimage resistant as well:

$\endgroup$
2
  • 2
    $\begingroup$ Please provide a link to the claim that there are collision resistant but not second-preimage resistant hashes. $\endgroup$ Commented Jun 28, 2014 at 10:27
  • 5
    $\begingroup$ The only thing I can think of is that we usually expect $2^n$ second pre-image resistance, whereas collision resistance is limited to $2^{n/2}$. So from collision resistance we can only prove $2^{n/2}$ second preimage resistance, not the stronger bound we'd like. $\endgroup$ Commented Jun 28, 2014 at 10:29

1 Answer 1

26
$\begingroup$

With the definitions that a function $F$ is

  • collision-resistant when a [computationally bounded] adversary can't [with sizable odds] exhibit any $(a,b)$ with $a\ne b$ and $F(a)=F(b)$;
  • first-preimage-resistant when, given $f$ determined as $F(a)$ for an unknown random $a$, a [computationally bounded] adversary can't [with sizable odds] exhibit any $b$ with $F(b)=f$;
  • second-preimage-resistant when, given a random $a$, a [computationally bounded] adversary can't [with sizable odds] exhibit any $b$ with $a\ne b$ and $F(a)=F(b)$

yes, collision-resistance implies second-preimage resistance. Proof by contraposition: assume the property for second-preimage-resistant does not hold. Repeatedly pick a random $a$, perform the attack that exhibits a $b$ with $a\ne b$ and $F(a)=F(b)$, until it succeeds. By our assumption, that requires a feasible amount of work. Once exhibited, that pair $(a,b)$ proves that the property collision-resistant does not hold.


However, as pointed by CodesinChaos in his comment, the answer is no for definitions of collision-resistance and preimage-resistance that quantify the difficulty of finding a collision or (respectively) preimage, to roughly $2^{n/2}$ or (respectively) $2^n$ evaluations, where $n$ is is the number of bits in the output.

Proof by counterexample: for even $n$, assume a hash function $H:\{0,1\}^*\to\{0,1\}^n$ that behaves as a random function. Now construct $F:\{0,1\}^*\to\{0,1\}^n$ as $$F(x)=\begin{cases}x||x&\text{if }x\text{ has }n/2\text{ bits}\\H(x)&\text{otherwise}\end{cases}$$ $F$ has the collision-resistant property (when $a$ and $b$ are both $n/2$ bits, $a\ne b\implies F(a)\ne F(b)$; when neither $a$ nor $b$ are $n/2$ bits, collision resistance is that of $H$; when a single of $a$ or $b$ is $n/2$ bits, the other must have a hash with two equals halves, and it takes effort about $2^{n/2}$ hashes to exhibit such input). However the following algorithm breaks the second-preimage resistance property for $F$ at cost comparable to $2^{n/2}$ hashes, much less than required: if the random $a$ is not of size $n/2$, compute $H(a)$, and if its two halves are equal (which is expected to occur after $2^{n/2}$ hashes), let $b$ be that bitstring of $n/2$ bits; it holds that $a\ne b$ and $F(a)=F(b)$.


In summary: a function's second-preimage-resistance is always at least as strong as its collision-resistance; but it can be not much stronger, rather than quadratically stronger, which is the theoretical ideal. So depending on definition, collision-resistance implies second-preimage-resistance.. or not! That's true when we keep the same security level (effort and odds of success of adversary) to assess the two properties. That's false when we expect a security level consistent with the property and the function's output size.


Addition following comments: The question links to a paper by Elena Andreeva, Bart Mennink, and Bart Preneel Security Properties of Domain Extenders for Cryptographic Hash Functions. That highly technical paper considers various proposed extension methods to iterate the core building block of a hash function over much larger input than the core block accepts; and if security properties of that core are conserved in the extended construction, to comparable level (work for attack and odds of success).

As any good paper should, that paper gives its specific definitions, and for some established ones refers to its reference [15]: P. Rogaway & T. Shrimpton Cryptographic Hash-Function Basics: Definitions, Implications, and Separations for Preimage Resistance, Second-Preimage Resistance, and Collision Resistance. All these quantitative definitions stay fully consistent with the classical result that for any given level (work for attack and odds of success), collision-resistance implies second-preimage-resistance.

The paper shows that some extension methods demonstrably (mostly) preserve the level of collision-resistance but do not demonstrably (mostly) preserve the level of second-preimage-resistance. That is entirely consistent with the above rule.

For example, starting from a core block assumed collision-resistant to $\mathcal O(2^{n/2})$ effort and second-preimage-resistant to $\mathcal O(2^n)$ effort, some extender might construct a hash that is collision-resistant to $\mathcal O(2^{n/2})$ effort and second-preimage-resistant to $\mathcal O(2^{2\cdot n/3})$ effort. The less-than-perfect extender conserved the level of collision-resistance, but not the level of second-preimage-resistance. Yet, for the hash built using that extender, collision-resistance to some effort level still implies second-preimage-resistance to that effort level.

$\endgroup$
13
  • 1
    $\begingroup$ A sponge with capacity $n$ is another example. This one is important since NIST considered having SHA-3 with only $2^{n/2}$ preimage resistance. $\endgroup$ Commented Jun 28, 2014 at 21:04
  • $\begingroup$ @CodesInChaos: Following your comment, I've been trying to construct a sponge-based hash with capacity $n$, an argument of collision-resistance with effort about $2^{n/2}$, and an explicit second-preimage attack with effort $2^{n/2}$ (rather than a proof of security to effort $2^{n/2}$); but failed. Am I missing the obvious, or is that worth a separate question? $\endgroup$
    – fgrieu
    Commented Jun 30, 2014 at 10:53
  • 1
    $\begingroup$ If you have a two block message you can run a meet-in-the-middle attack since the primitive function is invertible. This should break (second) preimage resistance with cost $2^{c/2}$ where $c$ is the capacity. (I didn't look into the memory requirements, they might be unrealistically large) This is the reason why SHA-3 uses $c=2 n$. $\endgroup$ Commented Jun 30, 2014 at 11:04
  • $\begingroup$ Thanks @fgrieu. "So depending on definition, collision-resistance implies second-preimage-resistance, or not." Such a different definition is implicit in this kind of paper ? $\endgroup$
    – Dingo13
    Commented Jun 30, 2014 at 17:42
  • $\begingroup$ @Dingo13: No, in this kind of paper dealing with theoretical aspect of security, definitions of security are explicit, or at least given by an explicit reference. In the quoted paper a great number of subtly different definitions of security are given in 2.2, with two pages and a half devoted to that. $\endgroup$
    – fgrieu
    Commented Jun 30, 2014 at 18:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.