4
$\begingroup$

The SHA-512 hash function accepts any message from a single bit to $2^{128}$ bits. Because the function takes into account the message length, I can't just represent every message as a $2^{128}$-bit integer. I'm sure this is a very basic question, but my math background is limited so this isn't coming easily to me.

How do I calculate the number of distinct inputs?

$\endgroup$

1 Answer 1

6
$\begingroup$

There is one zero-length message, two 1 bit long messages, four 2 bit long messages, eight 3 bit long messages, and so on. Since these messages are distinct, you can simply use the formula:

$$1 + 2 + 4 + 8 + \dots + 2^{n-1} = 2^n-1$$

Note that the maximum message length is the same as the maximum value of a 128-bit integer, ie. $2^{128} - 1$, not $2^{128}$. That makes $n-1 = 2^{128} - 1$, so $n = 2^{128}$. That makes the total number of distinct inputs

$$2^{(2^{128}-1)} - 1 $$

$\endgroup$
4
  • $\begingroup$ I totally forgot that it can take a zero-length message, d'oh! $\endgroup$
    – forest
    Jul 18, 2019 at 1:15
  • 2
    $\begingroup$ that number is so incomprehensibly large, I do not know how to adequately compare it to anything, if you had that many neutrinos packed as tightly as physics would allow, it would overflow the universe $\endgroup$ Jul 18, 2019 at 4:39
  • $\begingroup$ It's tiny as far as large finite numbers go. It's less than $f_{3}(128)$ in the Wainer hierarchy, much smaller than something like $f_{ω_{1}}(3)$, for example. Still huge in the everyday sense though. $\endgroup$ Jul 18, 2019 at 17:30
  • 1
    $\begingroup$ @SAIPeregrinus Which itself is much smaller than $\operatorname{Rayo}(10^{100})$... $\endgroup$
    – forest
    Jul 20, 2019 at 6:17

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.