# Why this function isn't preimage resistant?

Prove that the function

$$G(z) = \mathcal{H}(z) \, || \, \text{LSB}(z)$$

(where $$\mathcal{H}$$ is a collision resistant hash function, $$||$$ is concatenation and $$\text{LBS}$$ is the least significant bit of $$z$$) is not preimage resistant.

Obviously, if $$z = 0^n$$ then from the output $$G(z)$$, one can extract $$z$$ from the last bit. That also can be said about the case $$z = 1^n$$.

But is this enough to prove $$G$$ is not preimage resistant?

Pre-image resistance: given a hash $$h$$ it should be hard to find any message $$m$$ such that $$h=hash(m)$$. This concept is related to that of the one-way function. Functions that lack this property are vulnerable to pre-image attacks.

• It has $\mathcal{O}(2^{n})$ pre-images instead of $\mathcal{O}(2^{n+1})$. Show that if there is a pre-image oracle for $G$ then it can be used to find preimages for $H$, too. What is the origin of this question? – kelalaka Jan 24 at 15:38
• It's a hash function proved to be safe for proof-of-work, but lacks the property of collision resistance (even preimage resistance), but I couldn't get this without a formal proof. – Paris Jan 24 at 15:51
• Could you provide the source? – kelalaka Jan 24 at 15:52
• There's no actual (official) source, it was a claim of a professor of mine and I'm interested in checking if it's true and why. – Paris Jan 24 at 15:55

Let $$O$$ be an oracle that provides pre-images for $$G$$ that is given $$y$$ it produces a pre-image $$z$$ such that $$G(z) = y$$. Now expand this to $$y = H(z)||LSB(z).$$ Therefore, given the oracle $$O$$ one can find the pre-images of $$H$$ by asking $$x||0$$ and $$x||1$$ to the oracle and test the result. As a result, if $$G$$ is not pre-image resistant then $$H$$ is not. too. This implies that $$H$$ is pre-image resistant then $$G$$.

In the details; the $$O$$ will produce $$x_0$$ and $$x_1$$ such that $$G(x_0) = H(x_0)||0 = x||0$$ and $$G(x_1) = H(x_1)||1 = x||1$$. As we can see that this may also produce collisions for $$H$$.

$$G$$ fails only two-bit resistance by leaking the LSB. If a hash function is failing its pre-image resistance by leaking LSB, then it has some serious problems. Consider that, one provides you the LSB of the pre-image for SHA256, can you find the pre-image easily?

To see the loss bits of resistance; let $$H(z):\{0,1\}^* \to \{0,1\}^n$$ be a collision resistant hash function. Then is has $$\mathcal{O}(2^n)$$ pre-image and secondary pre-images resistances, and $$\mathcal{O}(2^{n/2})$$

If $$G(z):\{0,1\}^* \to \{0,1\}^{n+1}$$ with $$G(z) = H(z) \mathbin\|\text{LSB}(z)$$ then it has $$\mathcal{O}(2^{n-1})$$ pre-image and secondary pre-images resistances instead of $$\mathcal{O}(2^{n+1})$$

• So, just to confirm I understood your answer, $G$ is preimage resistant, but it's not second preimage resistant, that is: given $x$ it's hard to find another $x' \neq x$ s.t. $G(x) = G(x')$. Is this the case? – Paris Jan 24 at 18:32
• Why doesn't it has secondary image resistance? – kelalaka Jan 24 at 18:36
• What do you mean by 'fails only two-bit resistance by leaking the LSB'? – Paris Jan 24 at 18:41
• This is why I asked you the definition, does it say 2 bits? it should be hard to find or better wording is computationally infeasible. What if you say in the definition of $G$ that it is designed for $\mathcal{O}(2^{n-1})$ pre-image resistance? Of course, this is just an example to discuss, and in the real-world we consider even such amount a successful attack if it using less area-time resrouces than the brute-force. – kelalaka Jan 24 at 18:46