6
$\begingroup$

Suppose I have the values $a$, $b$, and $V = H(a) \oplus H(b)$ with inputs $a \neq b$ and $H$ being SHA-224. None of these values are a secret. How secure is it to assume that no other possible values $a'$ and $b'$ (except the case of $a'=b$ and $b'=a$) can be generated that result in the same $V = H(a') \oplus H(b')$?

Are there recommended procedures to combine two hashes into a single value and meet the following properties:

  1. $V$ has same (or nearly same) size as each of both input hashes
  2. Any single unknown value ($V$, $H(a)$, or $H(b)$) can easily be deduced from two known values.
  3. Cryptographically hard to obtain different pre-images $a'$ and $b'$ with same $V$
$\endgroup$
  • 2
    $\begingroup$ If you are using SHA-224 then an attacker can find $a'$ and $b'$ in $2^{112}$ work by using a birthday attack to find $a'$ and $b'$ where $H(a') \oplus H(b') = V$ $\endgroup$ – user13741 Feb 24 '16 at 19:20
  • 1
    $\begingroup$ @user13741: your statement requires an about to become correct. In order to reach odds of success $1/2$, over $1/6$ more than $2^{112}$ evaluations of $H$ are required, even if the adversary had arbitrarily large and fast memory; and since that's not, and such huge search (much larger than all bitcoin mining done to that day) needs to be distributed, significantly more hashing is required. $\endgroup$ – fgrieu Feb 24 '16 at 20:08
  • $\begingroup$ @user13741 Would you explain more please? The values of $a$ and $b$ are fixed, so how does the birthday expected complexity hold? It is like a case of second-preimage to me. $\endgroup$ – saeedn Feb 25 '16 at 18:00
  • 2
    $\begingroup$ @saeedn A birthday attack can be used because we do not need to find a specific hash (like a preimage or 2nd-preimage), we just need to find any two hashes which have a specific xor difference. $\endgroup$ – user13741 Feb 25 '16 at 19:06
1
$\begingroup$

$ Pr(H(a) \oplus H(b) = V)$ is independent of $V$ For a good hash, as pointed out in the comments. Pick your input space to be the output space of SHA-224 so with probability $1/2$ (1) holds.

The range of $H$ is a group under $\oplus$. So (2) holds.

3 won't hold by the same group property. Another $2^{112}$ trials will likely yield $a',b'$ satisfying (3) with probability $1/2$.

$\endgroup$
  • $\begingroup$ Why do you say (3) won't hold? 112 bits is enough to be infeasible for a long time, even if not necessarily forever like the 224-bit preimage resistance (without breaks, of course). $\endgroup$ – otus Feb 26 '16 at 9:34
  • $\begingroup$ I meant different preimages are no more costly than the original preimages. $\endgroup$ – kodlu Feb 26 '16 at 22:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.