9
$\begingroup$

If I take the sha-256 of an empty string, and apply the hash function $2^{256}!$ times, will I end up with the same hash that I started with?

Is the smallest required cycle equal to the LCM of $1$ to $2^{256}$?

$\endgroup$
24
$\begingroup$

In a uniform random function, which is a mostly reasonable model for SHA-256, you are not guaranteed that any particular element lies in a cycle: it could go $A \mapsto B \mapsto C \mapsto B$ and therefore never return to $A$.

In fact, only a tiny minority of elements are likely on cycles at all—the expected number of elements on cycles in a uniform function of $n$ elements grows with $\frac 1 2 \sqrt{2\pi n}$; for SHA-256, this is about $2^{128}$ of $2^{256}$ possible 256-bitstrings, i.e. the probability that any particular element is on a SHA-256 cycle is about $2^{-128}$.

However, if you just want to know how long you must pursue a hash chain before it cycles somewhere—not necessarily back to where you started ($A$), but somewhere you started going in circles lost in the desert trying to follow your own tracks like a pair of Belgian detectives ($B$)—the length of that chain turns out to have the same distribution as the number of elements on a cycle, with expectation $\frac 1 2 \sqrt{2\pi n}$, and the expected length of the cycle itself is $\frac 1 4 \sqrt{2\pi n}$.

So on average you'd have to follow $2^{128}$ elements before you ever come back upon your footsteps somewhere in a SHA-256 hash chain, and the average cycle length is about $2^{127}$, so you'd skip half your footsteps when you cycle back.

Here's an illustration that I stole from fgrieu of a 7-bit hash function—the vast majority of points, the grey dots, are not on cycles at all; only the red dots are on cycles:

A genuine guaranteed random mapping, courtesy fgrieu

Of course, in principle it could turn out that SHA-256 is actually a permutation of $\{0,1\}^{256}$ and is a single giant cycle, in which case you would actually have to tread $2^{256}$ steps—this, rather than the much larger $2^{256}!$, is the maximum number of steps before you are 100% guaranteed to have cycled back upon your footsteps. But it is exceedingly unlikely that SHA-256 is a permutation, let alone a cyclic permutation—this would be an astonishing development if proven.

See Harris 1960 (paywall-free) for everything you need to know about statistics of uniform random functions, permutations, and derangements.

$\endgroup$
  • 1
    $\begingroup$ This is such a wonderful answer and happily went ahead and answered what my follow up questions would be. I’m glad that others are interested enough in this topic to share their knowledge! $\endgroup$ – William May 11 at 21:03
  • $\begingroup$ It could also be a permutation with many smaller cycles. $\endgroup$ – Paŭlo Ebermann May 12 at 0:23
  • $\begingroup$ Why do you say that it is exceedingly unlikely that SHA256 is a single cycle? (I'm not challenging your claim, I'm genuinely curious) $\endgroup$ – DreamConspiracy May 12 at 1:06
  • $\begingroup$ Nice. My answer would have been similar. Unfortunately all these excellent questions pop up when it's after midnight here. $\endgroup$ – kodlu May 12 at 1:27
  • 1
    $\begingroup$ @DreamConspiracy Only about $1/e^{2^{256}}$ of all 256-bit functions are permutations, and of those, only a tiny fraction consist of a single cycle. $\endgroup$ – Squeamish Ossifrage May 12 at 2:48
5
$\begingroup$

There is a big difference between what we know for sure and what we expect. We don't know for sure almost anything, We don't know what is the cycle structure of sha256 We don't know how big any cycle is including one starting with an empty string.

We however expect sha256 to behave like a random function. So we expect it to contain many cycles. Each with on the order of 2^128 elements. The graph of random function has many different connected components each with a single cycle and a bunch of tree segments leading into the cycles. We however expect only a logarithmic number of cycles. Thus the vast majority of points are not on a cycle.

We do not know if the empty string is part of a cycle. It is likely it leads into a cycle it is not part of. It is ridiculously unlikely sha256 consists of a single cycle so that when starting with the empty string we would go through all others before returning to it. If this were the case it would hold for any starting point.It would also make sha256 a permutation. We can't currently disprove it, but we like to think of sha256 as a random function making these have probability 0 for all practical purposes.

$\endgroup$
4
$\begingroup$

If I take the sha-256 of an empty string, and apply the hash function (2^256)! times, will I end up with the same hash that I started with?

It's not guaranteed (and it would appear to be unlikely).

SHA-256 is not invertible and so while you're guaranteed to run into a cycle with at most $2^{256}+1$ iterations, that cycle might not include the initial element.

For example, SHA-256 might act like this simplified example:

SHA(0) -> 1
SHA(1) -> 2
SHA(2) -> 1

If our hash function acted like this, then it would matter how many times we iterated $SHA^n(0)$; we'd never come back to our initial 0 value.

$\endgroup$

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.