Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

up vote 5 down vote accepted

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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