Score:1

Preimage attack on sum of two Hash functions modulo 2

cn flag

If a hash function $H$ is defined as $H(x_1,x_2) = H_1(x_1) \oplus H_2(x_2)$ for two n bit good hash functions $H_1$ and $H_2$ then how can we construct a preimage attack on $H$ that is of $O(2^\frac{n}{2})$ given some y ?

Here, are we allowed to query $H_1$ and $H_2$ ?

I would really appreciate some hints.

Patriot avatar
cn flag
You might want to vote up the answer that you accepted.
cn flag
@Patriot Yes, I tried to. I need at least 15 reputation for it to show.
Patriot avatar
cn flag
OK, you are almost there.
Score:2
in flag

This seems like home work so I will stop short of a full solution. Yes you are allowed to query the functions $H_1$ and $H_2$ it's almost the only thing you can do. So you can collect a pool of input output pairs for each. And then what can you do with two such collections of input output pairs? You may want to index one one of them for efficient lookup.

cn flag
I can choose a query set of size 2^(n/2) and query H_1(x) and H_2(x) on that set. Then I will need to compare the values y+H_1(x) and H_2(x) using the queried ones to find a collision. Is that right?
Meir Maor avatar
in flag
yes that is a reasonable method.
cn flag
Thank you so much
mangohost

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.