CODEWITHSUNDEEP
securitytime-complexitybig-ocryptographic-hash-function
Horsy
Horsy

Reputation: 75

What is the time complexity for cryptographic hash function?

Let say MD5 or SHA-1? What are the time complexity for both of these? I tried to find it on the internet but it is very limited and all I got is that both of them are O(n). Can anyone further enlighten me? Maybe give me a worst case and best case scenarios?

Upvotes: 1

Views: 5719

Answers (1)

templatetypedef
templatetypedef

Reputation: 372794

The MD5 and SHA-1 algorithms - both of which are not cryptographically secure and should never be used any more - are based on the Merkle-Damgard construction. This means that they're built by

  1. starting with a block cipher that takes as input fixed-width block of bits and outputs a fixed-width block of bits of the same size,
  2. padding the input up to some multiple of the block size using a cryptographically secure padding scheme, and then
  3. iteratively applying the block cipher to a combination of some number of bits of the input, plus either an initialization value or the output of the previous block cipher.

Because the block cipher works on a fixed-size block of bits, the time complexity of running it is O(1). There are a total of Θ(n) applications of that block cipher (the input is split apart into fixed-sized blocks, so there are Θ(n) of those blocks), and the cost of computing the padding bit is probably O(1) but could potentially be O(n). Overall, this means that the runtime of computing these hash functions is Θ(n), which makes sense because each bit is visited at least once and the work done per bit is constant.

Block ciphers are typically implemented in a way that cause them to take the exact same amount of time to run on any input combination of bits - or at least, something very close to the same amount of time - to try to make them resistant to timing attacks where the amount of time required to compute the block cipher is used to steal some of the bits. As a result, it would be very unusual if these hash functions took different amounts of time to complete on different inputs of the same size. So independently of the fact that the runtime is Θ(n), you shouldn't expect to see much variation in the wall-clock runtime.

Upvotes: 5

Related Questions