Cycles in SHA-256

Question

Let's say I start with a particular 256 bit value. Call this $v$. I then hash that value, and get another 256 bit value. Call this $\text{SHA256}(v)$. I take this value and get another 256 bit value. Call this $\text{SHA256}^2(v)$. More generally, let's call the result of hashing $v$ repeatedly $n$ times $\text{SHA256}^n(v)$.

Now my question is, how big will $n$ be, such that $\text{SHA256}^n(v) = v$?

It would seem to me, that if it's a giant sort of permutation, $n$ would have to be $2^{256}$, is that correct? Is that provable, or is there any information on this? (Just curiosity, really.)

Another question I had was, do all 256 bit strings have unique SHA256 values, and is there a way to show that? (Or, stated differently, can it be shown that there are no SHA-256 collisions in the language of all "256 bit strings"?)

Answer 1

$\text{SHA256}$ is designed to behave as a random function. Under that assumption, it is expected that for most 256-bit $v$, there is no positive integer $n$ with $\text{SHA256}^n(v)$ equal to $v$. Otherwise said, most $v$ do not belong to a cycle.

To illustrate this visually, in the following picture showing iteration of a 7-bit hash, I drew the points belonging to a cycle in red.

Answer 2

For a random function with 256-bit output,
the average would be almost-exactly ​ $\sqrt{\hspace{.03 in}2\hspace{-0.05 in}\cdot \hspace{-0.04 in}\pi} \cdot 2^{127}$ .

There's not really anything we can say that's more specific to SHA-256.

Answer 3

fgrieu gives a compelling visual illustration, but we can quantify this too. From Harris 1960 (paywall-free), for a uniform random function $H$ on $\ell$ elements, the number of $q$ elements that lie on a cycle is distributed by $$p(q) = \frac{(\ell - 1)! \, q}{(\ell - q)! \, \ell^q},$$ whose expectation grows with $\frac 1 2 \sqrt{2 \pi \ell}$. If we model SHA-256 as a uniform random function (a model which breaks down when we consider length-extension attacks but largely reasonable on fixed-length inputs), we have $\ell = 2^{256}$. So the probability that any particular element is on a cycle is about $1/(2^{127} \sqrt{2\pi})$. In other words, unless you know something special about SHA-256, you will never even find an element on a cycle.

What about the distribution on cycle lengths $n$? It turns out to have the same distribution, with expected value $2^{127} \sqrt{2\pi}$ for a 256-bit function. So even if you somehow found an element on a cycle, you almost certainly wouldn't be able to confirm whether it's on a cycle or not—again, unless you know something special about SHA-256.

Pretty much everything else you need to know about these distributions for uniform random functions and permutations—and uniform random functions and permutations that never map an element to itself—is covered in the Harris paper too!

Answer 4

If a hash is modelled as a random function $H$ from input strings of length 256 to that same length output, then the probability that $H$ is in fact a permutation (which is equivalent to saying that all of the inputs have unique outputs) is negligible. So the chances are close to 0 that this is the case.

For random functions some results on the cycle lenght are known, I believe that the expected cycle length is of the order $2^{128}$, i.e. the root of the size of the input. See e.g. this paper