0
$\begingroup$

Assuming we use SHA256 as hash function. In practice you see that a Merkle tree is used to concatenating multiple hashes together to one single root hash.

A Merkle tree is a binary tree which always takes two SHA256 hashes and concatenate them in a recursive manner.

My question: Is it insecure to hash more than two hashes together? Say for example you want to create a unique hash of a folder structure. Each folder can contain an huge amount of files which are separately hashed. If we now concatenate the hashes in a sorted way:

SHA256(concatenate(sort(SHA256(file 0), SHA256(file 1), SHA256(file 2), [...], SHA256(file n-1))))

Does this increase the risk of a collision?

Explanation: You can imagine that an attacker wants to prove that a file was part of the hashes (through the root hash) which it was not. So he can choose n-2 hashes freely and try to calculate the root hash (collision). Does this (dramatically) increasing the chance of a collision?

I can not find precise information about that online. My stomach feeling points me to the birthday problem. And kind of the existence of a Merkle trees is pointing in the same direction. Or am I wrong? I would be really happy for any hint. Thanks!

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

Assuming the hash is collision-resistant (which SHA-256 is believed to be), the proposed practice of hashing the concatenation of a sorted list of hash of files is demonstrably secure against collision (argument: a collision in the final result implies a collision in the last step or/and for some file); so is the practice of hierarchically hashing a binary tree. There's no meaningful difference in security (arguably, accidental collision is more likely in the later; but that's immaterial).

Notice that the proposed practice will give the same hash if files are reordered (which clearly is intentional), or if the content of two files is exchanged while they keep their name (which could be a serious security issue: two packages with the same hash, and the same filenames, can do entirely different things when run).

Improve this answer
$\endgroup$
2
  • $\begingroup$ Most real-world Merkle-tree-based systems include metadata in the hashes (e.g. filenames in Git, block indexes in ZFS, etc.). Is this intentional for protecting against the file-swap attack you mention, or accidental due to application needs? I can't seem to find a good search engine phrasing for this... $\endgroup$
    – rmalayter
    May 25, 2017 at 1:26
  • $\begingroup$ The idea was not to hash the names of the files but really the content of them. If you would modify the content of a single file this would also change the root hash (eg. if you wanna use it to protect a package as you said). Changing the name will not have an effect on the root hash. Yes, reordering is a problem. But there is no order in a folder structure as the composite pattern doesn't include ordering. $\endgroup$
    – developer346
    May 26, 2017 at 9:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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