6
$\begingroup$

Most modern cryptographic hash functions use some form of compression function combined with a construction such as the Merkle-Damgård (MD5, SHA1, SHA2, etc), the Sponge construction (with Keccak as a notable example) and variants of these constructions in order to allow messages of indefinite length to be processed. It also happens that in order to exploit parallelism some hash functions have modes which make use of Merkle trees, such as the tree-hashing mode of BLAKE2 and ParallelHash (not a Merkle tree per-se but still).

To my knowledge there are multiple Merkle tree-like structures that provably reduce the security of the whole construction to the one of the underlying primitive (for example the one described in the Sakura paper and the one described in the Certificate Transparency RFC).

If I am not mistaken MD6 tried to use Merkle trees directly, however I am not aware of any other cryptographic hash function trying such a thing. Is there any reason why more cryptographic hash functions don't use a Merkle tree-like construction directly instead of just adding them as a way to allow parallelism to existing hash functions on top of the Merkle-Damgård or the Sponge construction?

Improve this question
$\endgroup$
6
  • $\begingroup$ KangarooTwelve use the Sakura tree and allows at worst the speed of SHA-3, but can be highly parallelized to achieve higher speed for longer input ( > 8192 Bytes ). $\endgroup$
    – Biv
    Commented Aug 20, 2017 at 15:09
  • 1
    $\begingroup$ It looks like the merkle tree structure is oriented towards hashing very large messages. There are often times tradeoffs to be made between latency and throughput; A hash that can digest huge messages quickly might take excessive time/space to hash many small messages, even if the total amount of data hashed is equivalent (i.e. hashing a single GB sized file versus hashing hundreds of thousands 16 byte files, one algorithm might be very fast at the former, but quite slow at the latter, or vice versa) $\endgroup$
    – Ella Rose
    Commented Aug 20, 2017 at 16:41
  • $\begingroup$ @Biv KangarooTwelve uses Sakura on top of the sponge construction in a way similar to ParallelHash. $\endgroup$
    – Rukako
    Commented Aug 21, 2017 at 10:01
  • $\begingroup$ @EllaRose A Merkle tree requires (about - depending on the actual construction used) the same amount of evaluations of the compression function when compared to Merkle-Damgård along with the advantage that it can optionally be parallelised. Considering that I would be interested to see how a Merkle tree could perform worse for (multiple?) short messages when compared to Merkle-Damgård. $\endgroup$
    – Rukako
    Commented Aug 21, 2017 at 10:01
  • $\begingroup$ @Rukako true but the function used inside the sponge is Keccak[1600,12] and not Keccak[1600,24]. Thus it is not using Sakura on top of SHA-3 but more a function on its own. $\endgroup$
    – Biv
    Commented Aug 21, 2017 at 10:03

1 Answer 1

Reset to default
4
$\begingroup$

Is there any reason why don't more cryptographic hash functions use a Merkle tree-like construction directly instead of just adding them as a way to allow parallelism to existing hash functions on top of the Merkle-Damgård or the Sponge construction?

The reason is that a Merkle tree comes with computation overheads that the serial hash functions do not have. Such a Merkle tree is less efficient if executed sequentially, compared to the latter. In fact, its memory usage is proportional to the height of the tree (For further information, see this paper which considers constructions on top of hash functions). Furthermore, if you want to use multithreading to provide a parallel implementation of your tree-based hash function on multi-processors/cores, you will have to cope with synchronization costs.

For software applications, it makes sense to favour general-purpose computers. If you are a cryptographer and you want to design a hash function, you will focus at first on security and sequential execution performance, and then on parallelism (as an option). Note that a sequential execution of the mode of operation does not prevent using a SIMD implementation for the iterated primitive.

To my knowledge there are multiple Merkle tree-like structures that provably reduce the security of the whole construction to the one of the underlying primitive...

Sakura coding was proposed to allow anyone to construct his own tree-based hash functions, without worrying about security. For this purpose, this coding is assumed to be sufficiently flexible.

It also happens that in order to exploit parallelism some hash functions have modes which make use of Merkle trees, such as the tree-hashing mode of BLAKE2 and ParallelHash (not a Merkle tree per-se but still).

You are considering that a Merkle tree is a classic binary tree-based hash function with depth in $O(\log n)$. Most people consider a Merkle tree as a synonym of hash tree, i.e. any "tree structure+hash of child nodes". For instance, ParallelHash and KangarooTwelve that are based on trees of height 2 can be considered as a kind of Merkle tree. They are using trees of height 2 probably for a question of resource usage (and simplicity). If you are interested in parallel hashing with a focus on resource usage trade-offs, see again these propositions.

Improve this answer
$\endgroup$
6
  • 1
    $\begingroup$ favour general-purpose computers All general purpose computers have multiple cores... $\endgroup$
    – Paul Uszak
    Commented Sep 14, 2017 at 20:31
  • 1
    $\begingroup$ @PaulUszak I have not understood your remark. Yes, they tend to have at least 2 cores, and cryptographers tend to prefer to provide a one-fits-all hash function (for all types of messages and all types of computers). Depending on the synchronization delays between threads, multithreading may be not suitable when the amount of data processed is too small. This is the reason why efficient implementations of building blocks like block cipher or permutation are optimized SIMD implementations. $\endgroup$
    – Adam54
    Commented Sep 15, 2017 at 9:44
  • $\begingroup$ "a Merkle tree comes with computation overheads" Could you elaborate on that please? A Merkle tree would require the same amount of evaluations of the compression function as Merkle-Damgård. Where does the computation overhead come from? "and the memory usage are higher" Could you also elaborate on that? To my knowledcge the memory usage of a binary Merkle tree would be the same as the modern Merkle-Damgård variants. In any case, my question still remains: why K12 or Parallelhash don't use that Merkle-like construction directly instead of using it on top of the Sponge construction? $\endgroup$
    – Rukako
    Commented Sep 15, 2017 at 14:06
  • $\begingroup$ You said it makes sense to favour general-purpose computers, yet you suggest that we must design expressly for the lowest common denominator hardware like an Arduino. Do you believe that the best security is achieved by a one size fits all solution? I wonder why computers come in different sizes and colours, yet all hashes must be the same? $\endgroup$
    – Paul Uszak
    Commented Sep 15, 2017 at 20:37
  • $\begingroup$ @PaulUszak I don't believe that we should design algorithms for the lowest common denominator. But I think there is a trade-off that can fit a large amount of computers/devices. K12 has probably been proposed in this sense. Saying that it is an one-fits-all approach is subject to interpretation. $\endgroup$
    – Adam54
    Commented Sep 17, 2017 at 21:41

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.