Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this question
    
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? –  Paŭlo Ebermann Aug 22 '11 at 16:33
    
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. –  Paŭlo Ebermann Aug 22 '11 at 16:34
1  
Paulo: I'm concerned about finding another a and b. And order of a and b is irrelevant. –  gavinandresen Aug 22 '11 at 18:58
    
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. –  David Schwartz Aug 23 '11 at 11:15
add comment

2 Answers 2

up vote 17 down vote accepted

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.

share|improve this answer
    
Thanks, very helpful. For my application, maximum number of public keys will be much smaller than the number of bits in the hash function. –  gavinandresen Aug 22 '11 at 19:00
    
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.) –  Paŭlo Ebermann Aug 22 '11 at 19:14
    
Unfortunately, canonically ordering and concatenating isn't an option in this particular case. –  gavinandresen Aug 22 '11 at 19:31
    
They're only 20 bit strings. You can sort those even in a language without loops. –  Marsh Ray Aug 22 '11 at 20:03
1  
@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) –  fgrieu Aug 22 '11 at 23:13
show 2 more comments

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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