# First preimage resistance check

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?

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$.
• well if we assume that $H'(x) = 1$ then we see that $x = 1$ therefore it's not preimage resistant ? Is that correct? May 31, 2016 at 8:39
• 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. May 31, 2016 at 8:42
• Try another thing: Could you guess what is $x$ if I tell you that $H'(x) = 01001001$? Look at the definition of $H'$ May 31, 2016 at 8:44
• $x = 1001001$ ? May 31, 2016 at 8:51