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.

I have an arbitrary long list of hashes (e.g. git tree hashes), and I'm wondering by how much I am increasing the risk of hash collisions by condensing them into a single hash, like so:

import hashlib
...
rehash(list_of_hashes):
    return hashlib.sha224("".join(sorted(list_of_hashes))).hexdigest()

My feeling is that it doesn't increase the odds by an amount I need to worry about, but wouldn't mind confirmation by experts.

share|improve this question

migrated from stackoverflow.com Aug 27 at 9:46

This question came from our site for professional and enthusiast programmers.

    
I do need rehash() to return the same result regardless of the order in which the hashes are listed. I will code to avoid duplicates, but if I can't guarantee it, then I'll consider adding code into rehash() to skip over duplicates. –  Christian Goetze Aug 26 at 18:40
4  
There is one common pitfall: In hashtrees you often need to tag leaves and inner notes differently, to ensure an unambiguous tree structure. You didn't include enough context to know if this applies to your scheme as well, but I suspect that you need to use different prefixes when hashing a list of hashes and when hashing a plain file. –  CodesInChaos Aug 27 at 10:01
    
If you are really worried about collisions, use a larger size hash, eg SHA-512 –  Richie Frame Aug 28 at 0:28

1 Answer 1

up vote 5 down vote accepted

What you are describing is essentially the same things as a hash list. A hash list is a sequence of hashes over which another hash is calculated. Your scheme does the same thing after sorting. The sorting won't matter for the security of the scheme; it won't increase the chance of collisions.

Hash lists are also used for a well known structure called a Merkle tree, which allows for hashing data in parallel. Aggregating hashes using another hash is also performed in a meriad of protocols, including PKIX protocols (digital certificates, Cryptographic Message Syntax etc.). In those protocols the final hash is usually used within digital signature generation.

share|improve this answer
1  
This is helpful, but it doesn't actually list the bottom-line answer: does this increase the risk of collision? I think the bottom-line answer is no, it's safe -- and it might help to add that to your answer. –  D.W. Aug 27 at 17:59
    
Unless I'm missing something, sorting will trivially increase chance of collisions since $H(h_1, h_2)$ becomes equal to $H(h_2, h_1)$. –  otus Aug 28 at 9:26
    
By 'trivial' above I meant that it's a trivial fact, not that the increase is trivial. Whether the increase is trivial is itself not entirely trivial, and should therefore be a part of a good answer. –  otus Aug 28 at 9:34
    
@otus Git hashes over a set of files. I presumed in my answer that the order is not significant, otherwise sorting would not make sense in the first place. Of course, after sorting, the initial bits of the hash value in the sequence are convergent, but that shouldn't matter for reasonably sized hashes. Unfortunately I'm not sure if I can easily express that mathematically. –  owlstead Aug 28 at 13:06
    
Oh, I missed the part where it was git hashes. In that case, yes, order likely won't matter. –  otus Aug 28 at 16:06

Your Answer

 
discard

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