9
$\begingroup$

In theory, there are infinite inputs, that you can hash with SHA-256. So theoretically it would be possible that one hash string would read 0xaaaaaaaa...

But would that also be possible practically, or do the algorithms check that this is not happening?

Improve this question
$\endgroup$
11
  • 7
    $\begingroup$ "In theory there are infinite inputs, that you can hash with SHA256" - nope; there are only $2^{2^{64}}-1$ allowed inputs to SHA256, which is rather less than "infinite". $\endgroup$
    – poncho
    Apr 29, 2021 at 20:16
  • 6
    $\begingroup$ I think 000000… would have been a better example. The current (2) answers don't seem to interpret your question the same way as I do. $\endgroup$
    – pipe
    Apr 29, 2021 at 22:01
  • 8
    $\begingroup$ That’s a verbose way of saying “Can a hash be a specific value?” $\endgroup$
    – Константин Ван
    Apr 30, 2021 at 16:12
  • 1
    $\begingroup$ At first glance, just looking at the title, I thought this was asking about “Is there a message that hashes to itself?”. $\endgroup$
    – Константин Ван
    Apr 30, 2021 at 16:20
  • 1
    $\begingroup$ @HeatfanJohn: actually, it's simpler than that. SHA256 inputs are limited to $2^{64}-1$ bits (or less). There are $2^{2^{64}-1}$ possible inputs of that length, $2^{2^{64}-2}$ for one bit less, $2^{2^{64}-3}$ for two bits less, etc. If you sum them all together (down to the 0 bit input), you get a total of $2^{2^{64}} - 1$ total possible inputs $\endgroup$
    – poncho
    May 3, 2021 at 20:43

6 Answers 6

Reset to default
21
$\begingroup$

First of all, the output of SHA-256 is binary and consists of 32 bytes (256 denotes the output size in bits). What you are talking about is apparently the hexadecimal encoding of these bytes.

The possibility that you are talking about is called (1st) pre-image resistance (Wikipedia):

Given a hash value $h$, it should be difficult to find any message $m$ such that $h = \text{H}(m)$.

("difficult" is a non-technical term here, generally we use "computationally infeasible", obviously there will be messages that map to any hash value, the difficulty is finding them for a one-way hash)

No, the algorithms do not check this explicitly, because the algorithm by itself needs to be resistant against it. Furthermore, the repetition of certain bits is not that special all by itself. It would be unclear what you would need to test for.

"But would that also be possible practically" well, no, unless SHA-2 gets broken. Generally it is collision resistance that gets broken first. That means finding a hash where $\text{H}(m) = \text{H}(m')$ for any $m$ and $m'$. This is easier to attack because an attacker can try and find weaknesses in the algorithm that create an internal collision while controlling both $m$ and $m'$. SHA-256 is still considered secure in this regard.

Improve this answer
$\endgroup$
6
  • 9
    $\begingroup$ Note that bitcoin mining is about finding hashes that start with a certain pattern (zero valued bits if I remember correctly). The miners perform a huge amount of hashes to find one that matches; they cannot find a hash that has one specific value. Once found it is easy to verify that the input data creates the hash pattern of course. This is called the "proof of work" as finding one by accident within an assigned block of input data (just a range of numbers) is exceedingly unlikely. $\endgroup$
    – Maarten Bodewes ♦
    Apr 29, 2021 at 13:41
  • 5
    $\begingroup$ @MaartenBodewes: bitcoin mining searches for a hash that treated as a 256-bit unsigned number is less than 'target' = 2^224/difficulty where difficulty is a floating-point number computed periodically by an adaptive algorithm to try to keep the average block time near 10 minutes. Having 256-ceil(log2(target)) leading 0 bits is necessary but not sufficient. $\endgroup$
    – dave_thompson_085
    Apr 30, 2021 at 1:28
  • 2
    $\begingroup$ Yeah, OK, there are some leading zero's in that most significant bit ;) $\endgroup$
    – Maarten Bodewes ♦
    Apr 30, 2021 at 7:02
  • $\begingroup$ While I agree with the general gist, I most certainly isn't obvious that there will be messages that map to any value. It's not even necessarily true. It is not known whether SHA 256 is onto and it's certainly possible it isn't. $\endgroup$
    – DRF
    May 1, 2021 at 19:38
  • $\begingroup$ I think you mean "every value". Just like with hobbs answer and the comment below, I don't think that should influence my answer at all. Note that with the structure of SHA-256 and the not-quite-infinite-but-still-very-large input space, I would expect many messages to map to each SHA-256 value - even though we only find / use a very small % of the output space. $\endgroup$
    – Maarten Bodewes ♦
    May 3, 2021 at 7:41
15
$\begingroup$
  1. Yes, it's possible.
  2. Given the size of the input space (not actually infinite, but still very, very large), it's also likely, for any given 256-bit value, that several inputs that hash to that value exist.
  3. No, there's nothing special in the construction of the algorithm that prevents it (restricting the output space would probably be bad for security).
  4. Nonetheless, as long as SHA-256 isn't broken, there is no practical way to find an input that hashes to a given value.
Improve this answer
$\endgroup$
7
  • 4
    $\begingroup$ While the other answers give a lot more information, this answer just answers the question perfectly: The probability for each hash value should be the same, so getting 0xaaaa... should be equally probable as any other hash value. $\endgroup$
    – claus
    Apr 30, 2021 at 6:34
  • 1
    $\begingroup$ This is the only answer I see that explains why it would be bad for a hash algorithm to eliminate any of the possible outputs. ▲ $\endgroup$
    – Toby Speight
    Apr 30, 2021 at 14:48
  • $\begingroup$ The input space for the hash function doesn't matter for this question, what matters is the input space for compression function. This is a 768-bit value, which is still plenty. $\endgroup$
    – CodesInChaos
    Apr 30, 2021 at 15:55
  • 1
    $\begingroup$ This answer is not correct. It is not known whether SHA256 is onto. $\endgroup$
    – DRF
    May 1, 2021 at 19:39
  • 2
    $\begingroup$ @DRF I never said or implied it was. $\endgroup$
    – hobbs
    May 2, 2021 at 1:42
6
$\begingroup$

But would that also be possible practically, or do the algorithms check that this is not happening?

This is practically beyond anybody to find a 32-$a$'s for SHA-256 without pure luck or one need breaking the pre-image resistance of SHA-256, that is not possible.

Is it possible that a SHA256 hash has the same character 64 times?

Yes, and No. We don't know such input exists or not since we cannot try all possible inputs.

Let see what is expected in a restricted SHA-256 to input size 256-bits.

Model SHA-256 as uniform random map $F:\{0,1\}^{256} \to F:\{0,1\}^{256}$, i.e. limit the input.

There are almost certainly less than $k=2^{256}$ outputs since the number of permutation is $k!$ and the number of function is $k^k$ and $$k!/k^k\to0.$$

Now each output $y$ has $1/2^k$ chance to appear. So we have $\Pr[F(x) = y] = 1/2^k$. Since each $x$, $F(x)$ is an independent random variable then we have

\begin{align} \Pr&[\exists x. F(x) = y] = 1 - \Pr[\forall x. F(x) \neq y] \\ &= 1 - \Pr[F(0) \neq y]\,\Pr[F(1) \neq y]\cdots\Pr[F(2^k - 1) \neq y] \\ &= 1 - (1 - 1/2^k)^{2^k}. \end{align}

This is also the expected ratio of the distinct outputs by the linearity of the expectations. When we set $k \to \infty$, this will converge to $1-e^{-1} \approx 0.632$. Therefore near 3 out of 10 of the output values are not expected to occur if we limit the inputs.

When the input size is increased by more than 256 bits the expected ratio of the distinct outputs will approach 1 with the uniform random model. Even for 512 bits or more This doesn't mean that all outputs will occur. We don't know and we have no way to see that. Even we don't know that SHA-256 attends the first 64 bit integers.

In theory there are infinite inputs, that you can hash with SHA256

No, not infinite inputs, Due to the length padding this is not possible.

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

Then append the 64-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^{64}$-bit-sized input messages. This makes SHA-256 can have total $2^{2^{64}}$ different messages.

This upper limit, actually, due to the Merkle-Damgård (MD) design of SHA series. This is against the MOV attack (Handbook of Applied Cryptography; Chapter 9, Example 9.23);

Improve this answer
$\endgroup$
5
  • $\begingroup$ Why would you model SHA-256 like that? That assumes there are only $2^{256}=2^{2^8}$ possible inputs, but as you've stated there are $2^{2^{64}}$ which is rather bigger... $\endgroup$
    – psmears
    Apr 30, 2021 at 10:22
  • 1
    $\begingroup$ @psmears To show that some output may not occur more theoretically. Actually, one can go for the compression function itself to see the real expected. That is more complex than this. The first compression function uses fixed IV and input, the rest uses the previous output and new Input parts. And, the Bitcoin search less nayuki.io/res/lowest-sha512-value-by-brute-force/… that is $26^{12}$ $\endgroup$
    – kelalaka
    Apr 30, 2021 at 10:43
  • 2
    $\begingroup$ Right, I don't have a problem with modelling it as a random map, but limiting it to only inputs of exactly 256 bits is misleading - that calculation suggests that ~30% of the outputs aren't used, but if you allow the full input space that drops to virtually zero. If you're going to limit the inputs that way I think you need to justify why that is a reasonable assumption - I might just as well say "If you limit it to one-bit inputs, at most 2 outputs are ever used, which is less than 1%" - limiting to exactly 1 bit is clearly nonsense; why is limiting to exactly 256 bits so much better? $\endgroup$
    – psmears
    Apr 30, 2021 at 10:59
  • $\begingroup$ @psmears I don't say aren't used. It says expected. Drops zero? There is no proof of this. Even we don't know that SHA-256 attends the first 64 integers. Will clarify more. $\endgroup$
    – kelalaka
    Apr 30, 2021 at 11:46
  • $\begingroup$ @psmears Added some more explanation. $\endgroup$
    – kelalaka
    Apr 30, 2021 at 11:57
1
$\begingroup$

But would that be possible practically

Is it possible that the SHA-256 of some input would be a repetition of the same hex digit?

Yes, most definitely. In theory, any of the values in the output space is possible (though I don't think there's any proof that ALL values are actually possible).

Is it possible to find an input, which, once hashed with SHA-256, yields a repetition of the same hex digit?

In theory, if you had infinite time and ressources, nothing prevents it. Practically, no. There are 16 values with are the repetition of a given hex digit, so it's "only" 16 times less difficult than finding the input for a single specific output.

Let's consider for a minute that SHA-256 would be bijective between the set of 256-bit numbers and itself (i.e. that the input space is the same size as the output space, and that each value in the input space yields a different value in the output space, and of course vice-versa).

The current hash rate of the whole bitcoin network (we're talking a LOT of resources, many strongly optimised just for this task) is a bit above $170000\ Phash/s$ on the good days. That's $1.7 \times 10^{20}$ hashes per second. $2^{256}$ is $1.15 \times 10^{77}$ values. So on average it would take over $2 \times 10^{55}$ seconds to find one of the possible values. That's $3 \times 10^{47}$ years. For reference, the universe is thought to be $1.5 \times 10^{10}$ years old, so that's a very, very, very long time.

But we don't even know if SHA-256 is bijective on that space. For all we know, maybe all the inputs that yield those outputs are bit strings 1000 bits long, not 256. That could make things a lot harder.

But nothing tells us that you won't find a file tomorrow with a hash which is the repetition of a hex number, just by random chance. The likelihood of it happening is just sooooooooo tiny anyone would say it's impossible.

Improve this answer
$\endgroup$
1
$\begingroup$

In theory, there are infinite inputs, that you can hash with SHA-256. So theoretically it would be possible that one hash string would read 0xaaaaaaaa...

But would that also be possible practically, or do the algorithms check that this is not happening?

The algorithm has 2256 possible outputs.

Let us assume that you don't want the algorithm to output a hash 0xaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa ever. Ok, you could implement a check that it will never be outputted. You probably would need to do the same for the 15 other hex digits. So after these modifications, the algorithm would have 2256-16 possible outputs.

But wait! The algorithm could output 0xfaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa. There are 64 possible positions for the differing digit, 16 possible non-differing digits and 15 possible differing digits. So 15360 such hashes.

So perhaps we need an algorithm that can produce only 2256-16-15360 possible outputs?

Oops, there could be 2 differing digits. Or 3. Or 4. Or ...

Every step would reduce the possible amount of outputs that the hash function can create, making the hash function worse. It would be no longer a hash function that's a true 256-bit hash.

Why would you want to do this, to make the hash function worse?

The role of a hash function is to be unpredictable: to make it impossible to find an input that creates the hash 0xaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa. To make this problem of finding the input harder, the hash needs as many bits as it can have. By reducing the effective bit amount, the hash function becomes worse: it's easier to find an input creating the desired output.

Someday, I'm sure SHA256 will be broken. Thus, someday we will know a number of inputs that all hash to the same output: 0xaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa. That day has not arrived yet. It is possible that quantum computers could accelerate the arrival of the day SHA256 will be broken. It is also possible some mathematical weakness is found in SHA256, allowing finding an input producing the desired output.

Before that day arrives, you can safely use SHA256 knowing nobody will with a probability very close to 1 find an input producing an output having only one hex digit.

Improve this answer
$\endgroup$
-4
$\begingroup$

It is possible. However, hashes are suppose to be random and 0xaaaaaa... doesn't seem random at all. Ensure that the algorithm, software, code, etc. is working properly because it looks like a security bug.

Improve this answer
$\endgroup$
9
  • 2
    $\begingroup$ This is like saying "if you roll 5 dice and they all land on 1, your dice are probably faulty". It's a complete misunderstanding of what "random" means - besides the fact that "random" is the wrong word for the output of a hash anyway. $\endgroup$
    – IMSoP
    May 2, 2021 at 16:27
  • $\begingroup$ Say, for example, that I'm implementing my own crypto algorithm. If it repeatedly produces non-random looking results such as 0xaaaaaa... when it should, in theory, produce random-looking results, then my implementation is incorrect. Also, if a hash is non-random, then the time required to find a collision is reduced. $\endgroup$
    – fiftytwocards
    Dec 12, 2021 at 3:20
  • $\begingroup$ If the output always consisted of repeated bytes, then certainly something would be wrong. But if the output never consisted of repeated bytes, that would also be a problem, because the aim is to make every output equally likely, even the ones that look funny to a human. You can't look at a single result and say if it is "random looking"; you can only look at a large selection of results, and say if there are unexpected patterns. $\endgroup$
    – IMSoP
    Dec 12, 2021 at 12:03
  • $\begingroup$ If you have a 0.2KB-9.0KB result and you view it a text editor, it is possible to have visible patterns of bytes. Adjusting the window size can make the patterns more or less visible due to word wrapping. I have had that experience at least. A 3-5 byte sequence repeated twice in a single result is improbable, and it could indicate that something is faulty. If you have 10,000 results, and 9,999 are perfect but one has a 50 byte sequence repeated twice, it is probably a bug. Really, I think you are correct in what you are saying though. $\endgroup$
    – fiftytwocards
    Dec 12, 2021 at 16:14
  • $\begingroup$ There are nearly 42 thousand non-overlapping sets of 5 bytes in 0.2 kilobytes of data, and only 32 possible sequences they could take, so I would say it is staggeringly unlikely not to have some that are repeated. Meanwhile, given a truly random source, the 10-byte sequence "aaaaaaaaaaaaaaaaaaaa" is exactly as likely as the 10-byte sequence "a6b3782f0d9e39f5b7cb", but one feels less likely because the human brain is highly tuned for spotting patterns, and very bad at judging randomness. $\endgroup$
    – IMSoP
    Dec 12, 2021 at 17:52

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