I'm trying to understand Merkle–Damgård construction. We can hash as many blocks of data as we want, if I understand it right. But then it looks like when input is bigger, then also time to compute hash is longer, isn't it?

So is it true that SHA-256 would also calculate the hash longer if input is bigger? Therefore are the hash function efficiency measurements (like 25 cycles per byte), made for some standard input block sizes?


1 Answer 1


That's right, and you've just stated the obvious. The processing time of Merkle-Damgaard-based hash functions are proportional to the size of the input (unless the input is too small).

That's also true of HAIFA hash functions such as BLAKE and BLAKE2, and sponge-based ones such as SHA-3.

  • 2
    $\begingroup$ Addition: hash function efficiency measurements, when expressed in cycles per bytes, are the elapsed time divided by the input size in byte, for large input (more precisely: the limit of that ratio as the input size goes to infinity), typically discounting the time it takes to bring what's need to be hashed in memory, or cache memory. Independently: there exist tree hash function such that the elapsed time can (in theory) be made logarithmic with the input size, however the computation effort remains linear with the input size. $\endgroup$
    – fgrieu
    Sep 4, 2022 at 13:45
  • $\begingroup$ I think this answer needs to include that, take SHA-256 with 512-bit block size, with length appending part of the padding is removed, the last block provides at most 447 bit for the last block. Therefore ( considering only the last block) there is almost 446/8*25 cycle overhead.... $\endgroup$
    – kelalaka
    Sep 6, 2022 at 0:08
  • $\begingroup$ I'm all in, fgrieu, kelalaka. If you guys see fit, please don't hesitate to edit in relevant information. $\endgroup$
    – DannyNiu
    Sep 6, 2022 at 2:03

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.