3
$\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? Would it be $\sum\limits_{i=1}^{128} 2^{2^i}$, or something else?

$\endgroup$
5
$\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$
  • $\begingroup$ I totally forgot that it can take a zero-length message, d'oh! $\endgroup$ – forest Jul 18 '19 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$ – Richie Frame Jul 18 '19 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$ – SAI Peregrinus Jul 18 '19 at 17:30
  • 1
    $\begingroup$ @SAIPeregrinus Which itself is much smaller than $\operatorname{Rayo}(10^{100})$... $\endgroup$ – forest Jul 20 '19 at 6: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.