11
$\begingroup$

Both SHA-384 and SHA-512 are limited to an input size of less than $2^{128}$ bits. Considering SHA-512 has a higher output size, couldn't it include more input data?

$\endgroup$
  • 10
    $\begingroup$ Are you actually considering computing the SHA-512 hash of an input $> 2^{128}$ bits long? Even if it were allowed, could you do it, say, before the heat death of the universe??? $\endgroup$ – poncho Dec 9 '18 at 23:15
  • 1
    $\begingroup$ Universe has approximately $10^{80} = 2^{256}$ atoms. $\endgroup$ – kelalaka Dec 9 '18 at 23:43
  • $\begingroup$ @kelalaka: what does the number of atoms have to do with it? SHA-512 computation isn't parallelizable; hashing $2^{128}$ requires $2^{119}$ successive hash compression operations; even if we could do one in a picosecond ($10^{-12}$), that'd still take over 20 quadrillion years (that is, over a million times the current age of the universe). $\endgroup$ – poncho Dec 10 '18 at 5:36
  • $\begingroup$ @poncho Yes, definitely, SHA-512 is not parallelizable. I would like to give the impression about the amount of data to be stored then processed. Bitcoin reached $2^{91}$ in one year that is $2^{119}$ is $536.870.912$ years. $\endgroup$ – kelalaka Dec 10 '18 at 7:15
  • 1
    $\begingroup$ @kelalaka It has approximately $10^{80}$ proton masses. While quite a few of its atoms are hydrogen, enough are not that there are far fewer atoms in general. Not to mention, that is only for the visible universe (one Hubble volume). If I recall correctly, the observable curvature proves that there are at least 200 Hubble volumes out there with unknown mass distribution, and possibly even an infinite number. $\endgroup$ – forest Dec 10 '18 at 9:02
16
$\begingroup$

The standard FIPS.180-4 defines a padding scheme that limits the upper input size.

Then append the 128-bit block that is equal to the number $l$ expressed using a binary representation.

Where the $l$ is the message length. Therefore, according to the standard, you can hash at most $2^{128}$-bit-sized input messages.

This upper limit, actually, due to the Merkle-Damgård (MD) design of SHA-512. MD based hash functions are vulnerable to length extension attacks and appending the length simplifies the security proof.

$\endgroup$
  • 4
    $\begingroup$ Which is an artifact of Merkle-Damgaard construct $\endgroup$ – DannyNiu Dec 10 '18 at 2:26
8
$\begingroup$

Considering SHA-512 has a higher output size

Here's where I think you're making a mistake. The space of the output of SHA-512 is $2^{512}$. However, the number of possible inputs is not $2^{128}$, but a whooping $2^{(2^{128}-1)}-1$. You will have reached all possible output spaces well before even a minuscule fraction of the input space has been exhausted.

$\endgroup$
3
$\begingroup$

This is not a question of output size (even a 16-bit CRC can handle an unlimited input) but depends on the specification. You could use the SHA-2 compression function in an algorithm with larger input size, but then it would not be SHA-512.

$\endgroup$
  • $\begingroup$ You cannot encode the length field in the final step of the hash as you must, if the input size is too large. A CRC has no such encoding so it's a false comparison... $\endgroup$ – Henno Brandsma Jul 20 at 8:59
3
$\begingroup$

The limitation is not a fault but a practical limit. A limit which does not impair it's usefulness.

"The Bug Charmer's" blog "How big is 2**128?" makes several comments about the value, here are a few:

  • "Most people realize that it’s a “big number” but don’t comprehend exactly how big. Who can blame them? Outside of a few disciplines such as cryptography and astrophysics, most people will never encounter a number this large.".

  • "$2^{128}$ is 340 undecillion - 340,282,366,920,938,463,463,374,607,431,768,211,456".

  • "How long would it take to brute-force a 128-bit key? If your PC can try $2^{40}$ keys per day, it would take you about 847,904,136,496,835,804,725,427 (848 sextillion) years in the worst case. We expect the sun to run out of hydrogen and collapse into a white dwarf in only about 5 billion years.".

  • "A computer that can try $2^{90}$ keys per day will take millions of years to guess a 128-bit key.".

  • "Storage on the order of $2^{128}$ will remain impossible. As I discussed in a previous post, storage for rainbow tables for each of $2^{128}$ salt values would require a storage device at least as large as the Earth.".

While some of those points refer to cracking and not the input text length the problem remains the same, what if the actual message was contained in the last sentence. Someone (or a computer) must create the input, it requires storage, and then there's the processing time; what if it turns out to be a compressed file?

$\endgroup$
  • $\begingroup$ If the computer has also a big space, it can also try a birthday attack, halving the bit length. If there is no more help, it is realistic around until 80 bit on a home pc. $\endgroup$ – user259412 Dec 10 '18 at 6:44
  • $\begingroup$ What if he's lucky? He could potentially guess the key in 5 seconds. I mean like super lucky, like 2^128 lucky. $\endgroup$ – Kieveli Jul 19 at 18:41

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.