Why this function isn't preimage resistant?

Question

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.

Answer 1

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})$