Score:3

Crypto

Will XORing two bad hashes lead to a collision resistant hash?

Dniel BV

12/1/23, 4:57 PM

I'm reading the fourth edition of "Cryptography: Theory and Practice" by D.R. Stinson and M.B. Paterson. In the book, they have mentioned the concept of "collision-resistant hash" and I've stumbled upon the following question from another source:

Is there a collision resistant hash function $h(x)=h_1(x)\oplus h_2(x)$ so that $h_1$ and $h_2$ are not collision resistant?

It seems interesting to think about it, but I couldn't find any relevant answers for this topic…

173

1 + 7

xor

collision-resistance

Daniel S

12/1/23, 5:31 PM

HINT: Consider a 256-bit hash function where the last 128-bits of output are all set to zero.

Dniel BV

12/1/23, 6:47 PM

Nice solution :) Thank you!

JAAAY

12/1/23, 8:55 PM

@DnielBV Considering answering the question yourself using the hint.

Maarten Bodewes

12/2/23, 12:24 PM

@JAAAY This is considered a homework question, so we only provide hints in comments, see [our current homework policy](https://crypto.meta.stackexchange.com/q/1115/1172)

JAAAY

12/2/23, 1:08 PM

@MaartenBodewes This is the reason I tagged OP in order to answer the question if he managed to figure out the solution and I didn't tag Daniel that provided the hint.

Maarten Bodewes

12/2/23, 1:18 PM

@JAAAY Oh, OK, but that would kind of defeat the purpose of only providing hints. That's not so much for the OP's purpose, but more for not answering exercises. A lot of these questions are only useful as part of an exercise.

Polytropos

12/4/23, 7:30 AM

It is worth noting that the current hint gives a quite inefficient example, in terms of the work factor to produce new collisions for the component hashes. One can construct examples where generating collisions for the components is essentially free (hint: think about preimages of zero).

Score:2

Crypto

Meir Maor

1/3/24, 8:27 AM

Let $g$ be a collision-resistant hash. We build $h_1$ to be $g$ with the first half replaced with all zeros, and $h_2$ to be $g$ with the second half replaced with all zeros. Neither are collision-resistant as both have effectively half the bit strength they should. Yet their XOR is exactly $g$ we assumed to be collision resistant.

+ 0

Elon Musk

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

EN: Will XORing two bad hashes lead to a collision resistant hash?

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.