7
$\begingroup$

I came across this Answer stating (just a line from the answer):-

The input space is "infinite" and thus it has an infinite amount of values that will collide into a single hash

And in the comments of this answer, there exists a comment of @poncho stating:-

Technically, the input space for the SHA-1 and SHA-2 hash functions is not "infinite"; SHA-1 and SHA-256 inputs are limited to $2^{64}−1$ bits; SHA-512 is limited to $2^{128}−1$ bits

In reply to the above comment, the answer'er does accept the above fact. But, I can't seem to understand why?

As there exists a large number of answers, like this who loosely use the term infinite with the input space of hash functions. I tried to resolve the ambiguity via Wikipedia page of MD5 and SHA1, this is the definition of both:-

In cryptography, SHA-1 is a cryptographic hash function which takes an input and produces a 160-bit hash

The MD5 message-digest algorithm is a widely used hash function producing a 128-bit hash value

In both the definition, there exists no mention of input size (in bits) of the algorithms.

QUESTION:- Does hashing algorithms have an upper bound in the input space?

P.S.:- If the upper bound does exists, then can anyone tell me why isn't the hashing algorithm able to work on input size above the upper bound?

$\endgroup$
  • 2
    $\begingroup$ Not all hash functions but the universe have a limit on the data to store. $\endgroup$ – kelalaka Jul 20 at 15:43
20
$\begingroup$

Does hashing algorithms have an upper bound in the input space?

They can, but they don't have to and it depends on their specification.

  • All Merkle-Damgård based hash functions do have an upper limit, because appending the message length simplifies the security proof and the backdoor-resistance of the function and they usually use a fixed-length encoding of the length.
    • Though it appears that MD5 (Spec RFC) kindof just ignores this and indeed accepts message of infinite length. The encoded length in this case are the low 64 bits (so it's reduced $\bmod 2^{64}$; Thanks to forest for making me actually check).
  • SHA-3 (Spec PDF) does not have such a limit as it's based on the sponge-construction.
  • Skein (Spec PDF) does have a limit of $2^{96}$ bytes.
  • Blake2b (Spec PDF) has a limit of $2^{128}$ bytes.
$\endgroup$
  • 1
    $\begingroup$ Oh, Thanks (+1). I totally forgot the fact that during the process of computing message digest of a message (in MD5 and SHA1), it's original length in bits is appended to the padded bits. Therefore, if we use message length > that length, we won't be able to append the actual length of the original message (as it would either result in overflow or would get truncated using a modulo operation which would lead to incorrect length). $\endgroup$ – Vasu Deo.S Jul 20 at 15:15
  • $\begingroup$ BTW could you please tell me why answers like this still refer to the input space be infinite in length? $\endgroup$ – Vasu Deo.S Jul 20 at 15:18
  • 6
    $\begingroup$ @VasuDeo.S probably because for most purposes "infinite" is a good approximation of "messages shorter than 2^64 bit" (which is > 1 million terabyte). $\endgroup$ – SEJPM Jul 20 at 15:44
  • $\begingroup$ Are you sure MD5 has an upper limit? I seem to recall that the length field was modular and that there was no hard limit, something which Peter Green's answer reinforces. $\endgroup$ – forest Jul 22 at 6:22
  • 1
    $\begingroup$ @forest I checked and indeed MD5 just uses the lower 64-bit. $\endgroup$ – SEJPM Jul 22 at 8:45
2
$\begingroup$

It depends on how exactly the hash function is defined.

Typically the first step of a hashing function is to convert the input from a series of bits or bytes to a series of blocks using a padding scheme. Many such padding schemes include the length of the input in the padding as it makes the security arguments easier. Typically the length is encoded as a fixed-size integer.

So the question becomes what happens when the range of that fixed size integer is exceeded. There are two main possibilities.

  • The integer is allowed to wrap around (this seems to be the case for MD5)
  • The hash function is only defined for messages shorter than a threshold (this seems to be the case for SHA1 and SHA2)

However you are likely to find this is a case where practical implementations of the algorithm don't enforce the specification. For example the first result for "sha1 reference implementation" I found on on google ( https://github.com/clibs/sha1/blob/master/sha1.c ) did not enforce any limit on input size.

$\endgroup$
  • 1
    $\begingroup$ Thanks for sharing this info (+1) $\endgroup$ – Vasu Deo.S Jul 22 at 3:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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