16
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Are you concerned about people finding the original a and b (preimage), another a and b with the same hash (second preimage), or finding arbitrary collisions? $\endgroup$ Aug 22, 2011 at 16:33
  • $\begingroup$ One observation is that the addition variant is commutative (i.e. you can swap a and b and get the same result), while the tuple variant isn't. No idea if this is relevant at all for your protocol. $\endgroup$ Aug 22, 2011 at 16:34
  • 1
    $\begingroup$ Paulo: I'm concerned about finding another a and b. And order of a and b is irrelevant. $\endgroup$ Aug 22, 2011 at 18:58
  • $\begingroup$ If at all possible, you really want the algorithm to have the characteristic that collisions are only possible if two different inputs hash to the same output of the hash function. If there is any possible way to do it this way, do it that way. $\endgroup$ Aug 23, 2011 at 11:15

2 Answers 2

19
$\begingroup$

If I get the suggested construction correctly, it is to

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

2) add theses hashes, perhaps mod 2256;

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 20, 21, .. 2255 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 2256 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.

$\endgroup$
7
  • $\begingroup$ Thanks, very helpful. For my application, maximum number of public keys will be much smaller than the number of bits in the hash function. $\endgroup$ Aug 22, 2011 at 19:00
  • 1
    $\begingroup$ Yes, hashing a canonically-ordered concatenation seems to be the right thing to do. (Though I don't yet see how addition will really make it insecure - there is still the first hash before it.) $\endgroup$ Aug 22, 2011 at 19:14
  • $\begingroup$ Unfortunately, canonically ordering and concatenating isn't an option in this particular case. $\endgroup$ Aug 22, 2011 at 19:31
  • $\begingroup$ They're only 20 bit strings. You can sort those even in a language without loops. $\endgroup$
    – Marsh Ray
    Aug 22, 2011 at 20:03
  • 1
    $\begingroup$ @gavinandresen: If it is not a requirement that the final hash is independent of the order of the inputs, you can chain the hashes: Hash(Hash(Hash(Hash(s0)||s1)||s2)||s3) $\endgroup$ Aug 22, 2011 at 23:13
6
$\begingroup$

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.

$\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.