Analyzing the security of hash approaches

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).

• Hint (lesser than the next one): what about first preimage resistance of 2 ?
– fgrieu
Apr 9 at 8:36
• HINT: There's a very easy second preimage attack Apr 9 at 10:34
• @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. Jul 10 at 22:56
• @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}$. Jul 11 at 7:16
• @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 ? Jul 11 at 9:52

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.

• 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.
– fgrieu
Apr 9 at 17:29
• There’s an even easier first pre-image attack. Consider the hash of $k$ copies of $x$. Apr 10 at 5:22