2
$\begingroup$

So I have $H: \{0,1\}^* \rightarrow\{0,1\}^n$ a hash function resistant to the second preimage and to collisions. Let there be a function $H' : \{0,1\}^* \rightarrow \{0,1\}^{n+1}$ with the following properties:

$$H'(x) = \{0||x\; \text{if}\; x∈\{0,1\}^n;\quad 1||H(x) \text{ otherwise}\}$$

Is $H'$ preimage resistant $∀ x$ ?

I know that I have to find an $x$ for which this property fails, but I cannot think of one, could you please help me and explain how to demonstrate this?

$\endgroup$
1
$\begingroup$

Preimage resistance is usually defined not for all the inputs, but for all the outputs, since what you are trying to model is the inability to, given any output $y$, obtain an input $x$ such that $H(x) = y$.

I'm not going to solve the problem for you since you may be able to do it by yourself. Just try to think of the patterns in the output and if this can be related to some input.

$\endgroup$
  • $\begingroup$ well if we assume that $H'(x) = 1$ then we see that $x = 1$ therefore it's not preimage resistant ? Is that correct? $\endgroup$ – southpaw22 May 31 '16 at 8:39
  • $\begingroup$ No, actually $H'(x)$ cannot be 1, it is impossible by the definition you give, since all the outputs start with either 0 or 1, and then $n$ bits. $\endgroup$ – cygnusv May 31 '16 at 8:42
  • $\begingroup$ Try another thing: Could you guess what is $x$ if I tell you that $H'(x) = 01001001$? Look at the definition of $H'$ $\endgroup$ – cygnusv May 31 '16 at 8:44
  • $\begingroup$ $x = 1001001$ ? $\endgroup$ – southpaw22 May 31 '16 at 8:51
  • $\begingroup$ Correct! Actually, a single example is enough to say that preimage resistance is broken, but you can go further and try to define a whole family of outputs whose input you can predict. $\endgroup$ – cygnusv May 31 '16 at 8:55

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.