18
$\begingroup$

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"?)

$\endgroup$
  • 1
    $\begingroup$ The identity function is a permutation for which one would get $\: n = 1 \;$. $\;\;\;\;$ $\endgroup$ – user991 Mar 25 '15 at 8:29
  • 1
    $\begingroup$ With a blockcipher (which is a permutation), the cycle length would be around $2^{255}$ with a hash the cycle length is around $2^{128}$. But of course these are just statistical values and both shorter and longer cycles exist. $\endgroup$ – CodesInChaos Mar 25 '15 at 9:35
  • $\begingroup$ Not specifically asked, but if you want to prevent cycles with such a construction, you can concatenate a 256-bit representation of n with the previous hash value at each iteration. So $$\text{SHA256}^n(v) == {SHA256}(n_{256}||{SHA256}^{n-1}(v))$$ $\endgroup$ – rmalayter Mar 25 '15 at 15:11
  • 1
    $\begingroup$ Your other question about collisions on 256-bit strings is answered here (for SHA-512 but the principle is the same). $\endgroup$ – Gilles 'SO- stop being evil' Mar 25 '15 at 21:07
  • 4
    $\begingroup$ Those loops are called cycles. Cycles are generally very large. $\endgroup$ – Maarten Bodewes Aug 4 '16 at 0:45
24
$\begingroup$

$\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.

graph of an iterated random function of 7 bits, with points belonging to cycles in red

$\endgroup$
  • 1
    $\begingroup$ Great. This reminds me of the work of Philippe Flajolet unfortunately missing many years ago. I attended one of his lecture about analytic combinatory. $\endgroup$ – Robert NACIRI Mar 25 '15 at 21:18
  • 1
    $\begingroup$ Flajolet Odlyzko was the first to look at this in a crypto context in a paper in the 1980s (either CRYPTO or Eurocrypt) $\endgroup$ – kodlu Jun 25 '17 at 8:28
  • $\begingroup$ Overall, does rehashing a hash improve security? $\endgroup$ – Aaron Franke Oct 21 '18 at 23:05
  • $\begingroup$ @AaronFranke It may improve security by thwarting length extension attacks, or it may hurt security for different reasons. Need more details to say! Out of scope for this question but if you have more details you can open a new question. $\endgroup$ – Squeamish Ossifrage Mar 31 at 19:40
9
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Let me correct my question: How many attempts, on average, would this take? $\endgroup$ – Richard M. Stroup Aug 4 '16 at 2:19
  • 1
    $\begingroup$ @otus : ​ For that, it would depend on whether "times" refers to "evaluating the hash" or "choosing an original text". ​ ​ ​ ​ $\endgroup$ – user991 Aug 4 '16 at 8:16
  • $\begingroup$ @RickyDemer, sorry, yeah I read the question a bit quickly - it's asking both. So, to complete the answer: the above is the time until you fall into a loop, but it is not necessarily one that includes the initial value (as the second code is looking for). $\endgroup$ – otus Aug 4 '16 at 8:24
7
$\begingroup$

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!

$\endgroup$
2
$\begingroup$

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

$\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.