1
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$
    – kelalaka
    Jan 24, 2021 at 15:38
  • $\begingroup$ 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. $\endgroup$
    – Paris
    Jan 24, 2021 at 15:51
  • $\begingroup$ Could you provide the source? $\endgroup$
    – kelalaka
    Jan 24, 2021 at 15:52
  • $\begingroup$ 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. $\endgroup$
    – Paris
    Jan 24, 2021 at 15:55

1 Answer 1

Reset to default
0
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$
    – Paris
    Jan 24, 2021 at 18:32
  • $\begingroup$ Why doesn't it has secondary image resistance? $\endgroup$
    – kelalaka
    Jan 24, 2021 at 18:36
  • $\begingroup$ What do you mean by 'fails only two-bit resistance by leaking the LSB'? $\endgroup$
    – Paris
    Jan 24, 2021 at 18:41
  • $\begingroup$ 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. $\endgroup$
    – kelalaka
    Jan 24, 2021 at 18:46

Your Answer

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

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