Score:3

Crypto

Analyzing the security of hash approaches

vimwitch

4/9/24, 7:05 AM

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

1 + 5

collision-resistance

fgrieu

4/9/24, 8:36 AM

Hint (lesser than the next one): what about first preimage resistance of 2 ?

Daniel S

4/9/24, 10:34 AM

HINT: There's a *very* easy second preimage attack

user2284570

7/10/24, 10:56 PM

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

Daniel S

7/11/24, 7:16 AM

@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}$.

user2284570

7/11/24, 9:52 AM

@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 ?

Score:1

Crypto

vimwitch

4/9/24, 3:02 PM

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.

+ 2

fgrieu

4/9/24, 5:29 PM

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.

Daniel S

4/10/24, 5:22 AM

There’s an even easier first pre-image attack. Consider the hash of $k$ copies of $x$.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Analyzing the security of hash approaches

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.