0
$\begingroup$

hash(a) + hash(b) = hash(c)

When adding 2 hashes values can it be equal to another hash value? Is it unlikely for this to happen? If so why?

$\endgroup$
4
  • $\begingroup$ If we assume that a cryptographic hash function takes all output values, then can you see the result? $\endgroup$
    – kelalaka
    Commented May 13 at 18:56
  • $\begingroup$ And, we know that SHA3 hashes can take on all values (no assumption needed) $\endgroup$
    – poncho
    Commented May 13 at 19:56
  • $\begingroup$ I get that it can happen but how likely is it really? $\endgroup$
    – randomdude
    Commented May 14 at 15:33
  • 1
    $\begingroup$ First of all, there is a problem, since you add $hash(a) + hash(b)$ then the output can be larger than the hash output, which means that there can be no c. Secondly, if this is not the case, the result depends on the hash function and the input size. See the coupon collector problem... $\endgroup$
    – kelalaka
    Commented May 14 at 21:29

2 Answers 2

0
$\begingroup$

Yes, as we assume for most hash values that the output is well distributed within the group.

Normally we do assume modular addition over $2^h$ though where $h$ is the output size of the hash function. Otherwise the result may require an additional bit, which would mean that the hash function could not generate some of the resulting values.

Although the result will very likely be the hash output of many messages, finding such messages is of course hard because the hash function is supposed to offer pre-image resistance. The result of the addition won't help with that. If it wasn't the hash function would not be pre-image resistant as anybody can calculate the hash over a different message and perform addition.

It doesn't really matter if you've calculated an impossible output value though; for most hash values it is impossible to prove that they are the output of any message due to the pre-image resistance.

If you really want to you could define a hash function where the result of a specific modular addition is never outputted by simply adding 1 to the output if it matches. That's still reasonably well distributed. I don't see the point of that, but it shows it can be done.

$\endgroup$
0
$\begingroup$

A trivial example is the hash function SHA-256 but keep only the two first bits. We now want to satisfy the equality:
hash(a) + hash(b) = hash(c)
We know that hash(x) is a two bit number, i.e. a number from zero to three. Assuming a perfect hash function, we can calculate the portion of a's, b's and c's that satisfy the equality. There's only one way to sum two different two bit numbers to zero, 0+0, and two ways to sum to one,1+0, 0+1, etc. This results in:
satisfactory cases/total number of cases = (1+2+3+4)/(4*4*4) = 10/64
This can be generalised to:
(1+2+...+n)/(n^3) = (n(n+1)/2)/(n^3)
for a hash function with n possible output values. This function approaches zero for larger n and since common hash functions have very large n, such as SHA-256 at n = 2^256, the chance that three randomly chosen a, b, and c would satisfy the initial equality is negligible.

$\endgroup$

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.