Why doesn't preimage resistance imply the second preimage resistance?

Question

Let the preimage resistance be defined as »given a hash value $h$, it is hard to find any message $m$ such that $\operatorname{hash}(m)=h$«, and let the second preimage resistance be defined as »given a message $m_1$, it is hard to find any message $m_2$ such that $\operatorname{hash}(m_1)=\operatorname{hash}(m_2)$«.

Then if you are given a preimage resistant hash function $H$, what modifications could we do in order to make a hash function $H'$ that is preimage resistant, but not second preimage resistant?

Someone suggested that we could do the following:

Take a preimage resistant hash function; add an input bit $b$ and replace one input bit by the sum modulo 2 of this input bit and $b$.

But I am not sure if that will work, could anybody explain to me why that makes $H'$ not second preimage resistant?

Answer 1

Consider the function $H$ transforming a message $m$ to the SHA-512 hash of the first 1024 bits of $m$ (right-padded with $1024-n$ zero bits if the bit length $n$ of $m$ is less than 1024).

$H$ is first-preimage resistant, but not second-preimage resistant: once you have a first preimage $m_1$, it is trivial to get another $m_2$ with the same hash (e.g. append a zero bit, $m_2=m_1||0$).

Edit: what was suggested to huyichen also works: the hash function $H'$ constructed as suggested is such that for any preimage $m_1$, there is a different preimage $m_2$ with the same hash, obtained from the first by complementing the added input bit $b$, and the other input bit which is combined with $b$.