3
$\begingroup$

Let's say we have 1000 files and 1000 already computed cryptographic hashes for those files. Now we want to derive a single hash that authenticates all of them. Is there a more efficient way to do this than just hashing the concatenation of all those hashes (and thereby presumably calling the hash round function about 1000 times), without sacrificing security? What about also verifying the sequence?

$\endgroup$
2
  • 1
    $\begingroup$ If the files are in defined order, we can hash the concatenation of their hashes, in that defined order; otherwise we should sort the hashes (e.g. by increasing value) before computing the final hash, which adds to the cost. For many common hashes, the number of hash round functions required is significantly less than the number of files, since blocks are larger than hashes by a factor of 2 (SHA-256, SHA-512) or more, e.g. 3.2 (SHA-1), 4 (SHA-512/256), ≈4.57 (SHA-512/224). $\endgroup$
    – fgrieu
    Jun 1, 2016 at 12:06
  • $\begingroup$ @fgrieu Even if the block size is larger than the hash, the point is to have a method where the number of calls to the round function doesn't depend on the number of hashes you need to combine, maybe I should have clarified that in the question. $\endgroup$
    – cooky451
    Jun 1, 2016 at 14:20

2 Answers 2

1
$\begingroup$

What you're looking for is called a Merkle tree. BLAKE2b, a modern hash and an evolution of one of the SHA-3 finalists (BLAKE), supports tree hashing natively.

Edit: This may or may not actually be what you're looking for. Initially hashing the tree will take more work ($\mathcal{O}(n\log(n))$ operations) than just hashing the set of hashes, but subsequent partial updates will take less work ($\mathcal{O}(\log(n))$ operations). If you're ever updating the list, a Merkle tree is probably more efficient.

$\endgroup$
6
  • 1
    $\begingroup$ A Merkle tree requires more work than hashing the concatenated list, however. $\endgroup$
    – otus
    Jun 1, 2016 at 4:10
  • $\begingroup$ Ah yes, good point. Only for the first time, though. After that, subsequent updates to part of the tree can be computed with $\mathcal{ O}(\log(n))$ hashes. $\endgroup$ Jun 1, 2016 at 5:08
  • 1
    $\begingroup$ Please note well: BLAKE2 was not running for SHA-3. It was BLAKE which was running there. $\endgroup$
    – SEJPM
    Jun 1, 2016 at 9:00
  • $\begingroup$ Also note that, in practice, hashing a single block of sequential data tends to be more efficient than hashing multiple separate strings, since the latter has more overhead from repeated hash function calls, and also accesses memory in a less efficient pattern. This means that optimal performance (even for single-leaf access / update) is generally achieved with a $k$-ary hash tree, where $k \gg 2$ (and, on a modern CPU, I wouldn't be surprised if $k > 1000$). $\endgroup$ Jun 1, 2016 at 9:37
  • $\begingroup$ I hope that's not what I'm looking for considering it's slower than just hashing the list. ;) $\endgroup$
    – cooky451
    Jun 1, 2016 at 16:42
0
$\begingroup$

If the number of files is fixed, then concatenating the hashes (in a well-defined order) constitutes a hash function. Inverting it requires inverting the hash of one of the files, so if the per-file hash function is a cryptographic hash, then so is that 1000-file hash.

If the number of files is variable, then the natural way to combine the hashes would be to hash them. That's a very cheap operation, and I don't understand why you hope to find something cheaper. You do have to process all of the hashes after all, it's an $\Omega(k)$ operation where $k$ is the number of files.

$\endgroup$
2
  • $\begingroup$ I'm interested in not hashing them because I want to know if it would be possible, given a suitable round-function, to design a CTR-like hash function that'd be perfectly parallelizable for most of the work, which would imply you ending up with a lot of "sub-hashes" that'd need to get efficiently combined. Apparently this isn't possible, or at least there doesn't seem to be a well known method to set this up even with a suitable round-function. $\endgroup$
    – cooky451
    Jun 1, 2016 at 23:37
  • $\begingroup$ @cooky451 You can parallelize by doing exactly what you're doing: compute the hashes of the files in parallel, and finally compute the hash of the list which is very quick. $\endgroup$ Jun 1, 2016 at 23:39

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.