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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
7
  • $\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
    Commented May 31, 2016 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
    Commented May 31, 2016 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
    Commented May 31, 2016 at 8:44
  • $\begingroup$ $x = 1001001$ ? $\endgroup$
    – southpaw22
    Commented May 31, 2016 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
    Commented May 31, 2016 at 8:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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