Does collision resistance imply (or not) second-preimage resistance? 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: 


“Security Properties of Domain Extenders for Cryptographic Hash Functions”
(See the chapter "Other Domain Extenders").


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: 


http://en.wikipedia.org/wiki/Preimage_attack
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&amp;\text{if }x\text{ has }n/2\text{ bits}\\H(x)&amp;\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 &amp; 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.