Is digest=HASH(HASH(a)+HASH(b)) equivalent to publishing two digests?

Question

Is combining digests (created using a hash function) using arithmetic addition, and then hashing and publishing the result, less secure than publishing the set of digests?

Does the answer change if the outer hash function is different from the inner function?

I am working on a proposal for Bitcoin to enable m-of-n signatures for transactions, and am considering using a 160-bit digest of the public keys computed as:

digest = RIPEMD160(SUM(SHA256(public_key_n)))

The number of public keys involved will typically be less than ten, and will never be more than 20. The order of public keys is irrelevant, I am just concerned with an attacker finding another set of public keys that hash to the same digest.

Answer 1

If I get the suggested construction correctly, it is to

1) hash n values (with SHA-256);

2) add theses hashes, perhaps mod 2²⁵⁶;

3) hash the sum (with RIPEMD-160).

This would be potentially unsafe: creating a collision or even second pre-image at step 2) reduces to a knapsack problem, and this has a poor safety record; it might be workable when the number n of inputs allowed gets above some threshold, with some relation to the number of bits in the first hash.

There is a simple, safe solution: at step 2), instead of adding the hashes, sort them, then concatenate them; sorting keeps the associativity and commutativity of addition (and is otherwise unnecessary). The construction becomes essentially as resistant as the weakest of the hash functions against collision (second pre-image resistance is the weakest of that for the first hash function for n preimages, and the second hash function).

Note: I see no good reason to use two different hash functions.

-

Here is an attack against a slight modification of the proposed construct, with addition replaced by XOR. It is a second-preimage attack: the attacker has a set of valid input values, and wants another set with the same overall hash after step 3).

In a preparatory step, she generates random values (all distinct from each others and valid input values), hashes them with the first hash, until a basis of 256 hashes emerges from the accumulating hashes; that is, until each of the values 2⁰, 2¹, .. 2²⁵⁵ can be expressed as a linear combination of XOR of some of the 256 hashes in that basis. This is simply a matter of adding the newly generated hash to the basis, unless it turns out to be a linear combination of the ones already in the basis, which can be checked by Gaussian elimination. The basis is complete when it contains 256 hashes, which will happen shortly after the 256th random value.

To obtain a forgery, she performs steps 1) and 2) normally with the valid input strings. She expresses the result as a linear combinations of the hashes in her precomputed basis, again by Gaussian elimination. It will consist of the XOR of about 128 hashes from the basis. The random strings that generated these hashes form a set which is a forgery. Step 3) is not necessary. It is easy to markedly reduce the number of strings in the forgery.

If addition modulo 2²⁵⁶ is used, or worse with straight addition, things are markedly more difficult, but conceivably still manageable (with more vectors in the forgery, and in the case of straight addition more vectors in the original); it is a knapsack problem, with a nearly unlimited supply of values.

-

I do not know how safe the system is with the number of elements limited to 20 (which I now realize is part of the statement); but at any rate, the addition step potentially is a weak spot.

Answer 2

This problem (i.e. generating a second preimage) is analyzed in the paper "A generalized birthday problem"[Citeseer][Slides], by David Wagner, Crypto 2002.

If you add 8 public keys then the attack requires somewhere around $2^{64}$ hash computations, if you add 16 public keys before hashing them then the complexity is somewhere around $2^{51}$ hash computations.