3
$\begingroup$

Say that I have a random oracle function $H$. This function outputs a value in $\mathbb{F}_{p}$ where $p \approx 2^{256}$. $H$ can accept either one or two inputs (outputting a single value in both cases).

I can hash two elements $x$ and $y$ using either

case 1: $H(x, y)$

case 2: $H(x) + H(y)$ (using modular addition)

How does the security of these approaches differ?

In case 1 there must be collisions because we're mapping two elements to one element. If $H$ is a random oracle then we should have collision odds $1/p$.

Is there something I'm missing with case 2? I'm assuming we get security from Schwartz-Zippel, $H(x) + H(y)$ being a multivariate linear polynomial with both variables randomly distributed in $\mathbb{F}$. Is the security the same as that of $H$? Does this significantly change based on the actual implementation of $H$ (e.g. sha256 vs poseidon vs md5 vs etc).

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ Hint (lesser than the next one): what about first preimage resistance of 2 ? $\endgroup$
    – fgrieu ♦
    Commented Apr 9, 2023 at 8:36
  • 2
    $\begingroup$ HINT: There's a very easy second preimage attack $\endgroup$
    – Daniel S
    Commented Apr 9, 2023 at 10:34
  • $\begingroup$ @DanielS sorry to ask this, but in which case is he talking about ? I don t understand the meaning of the first sentence besides I know what is a finite field. $\endgroup$
    – user2284570
    Commented Jul 10, 2023 at 22:56
  • 1
    $\begingroup$ @user2284570 Are you referring to the comment below the answer? If so the approach to find a preimage for a target $z$ in case 2 is to make two lists of length about $2^{n/2}$ one of values $H(x)$ and one of values $z-H(y)$ for random $x$ and $y$. We then look for a value that appears in both lists. Our total work is then about $2^{n/2}$. $\endgroup$
    – Daniel S
    Commented Jul 11, 2023 at 7:16
  • $\begingroup$ @DanielS I’m referring to the question itself. My case is the first one anyway. Does this question apply only to the hash result of x and y of different lengths ? $\endgroup$
    – user2284570
    Commented Jul 11, 2023 at 9:52

1 Answer 1

Reset to default
1
$\begingroup$

Ok thank you for the comments.

For an input $x$ and $y$ there's a simple second pre-image attack in case 2:

$H(x) + H(y) = H(y) + H(x)$

The same problem applies if the elements are combined with multiplication as well.

There's also a first pre-image resistance problem. If you want a hash $z$ all you need to do is find $H(x) = z / 2$, then provide $x$ as the input twice. It follows that given $H(x) + H(y) = z$ the pre-image for any hash $2(z - H(x))$ or $2(z-H(y))$ is known.

Improve this answer
$\endgroup$
2
  • $\begingroup$ That was not my idea about first preimage resistance for 2. Rather, it's that if $H$ has $n$ bits, there is a first preimage attack with expected cost like $2^{n/2}$ hashes somewhat like for the birthday problem. $\endgroup$
    – fgrieu ♦
    Commented Apr 9, 2023 at 17:29
  • $\begingroup$ There’s an even easier first pre-image attack. Consider the hash of $k$ copies of $x$. $\endgroup$
    – Daniel S
    Commented Apr 10, 2023 at 5:22

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.