1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ You might want to vote up the answer that you accepted. $\endgroup$
    – Patriot
    Commented Jul 22, 2021 at 3:08
  • $\begingroup$ @Patriot Yes, I tried to. I need at least 15 reputation for it to show. $\endgroup$
    – user766787
    Commented Jul 22, 2021 at 7:43
  • $\begingroup$ OK, you are almost there. $\endgroup$
    – Patriot
    Commented Jul 22, 2021 at 9:14

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$
    – user766787
    Commented Jul 21, 2021 at 19:50
  • $\begingroup$ yes that is a reasonable method. $\endgroup$
    – Meir Maor
    Commented Jul 21, 2021 at 20:51
  • $\begingroup$ Thank you so much $\endgroup$
    – user766787
    Commented Jul 22, 2021 at 7:45

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.