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?


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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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