5
$\begingroup$

This is the situation: I have a list of hashes where each hash is always the SHA-256 of the one above it.

If I keep going down the list it must at some point loop since there can only be $16^{64}$ possible SHA-256 hashes. So at some point the hash I get has already been in the list before.

The problem is that the algorithms behind SHA-256 is above what I can currently comprehend (I'm only 17 and a part free programmer for 3 years). But on here there seem to be a lot of geniuses so my question is:

Is SHA-256 designed to loop after exactly $16^{64}$ hashed hashes, or is there a chance it will do so before that point?

Also: If so, it would probably do multiple times.

I saw the post on $\operatorname{Hash}(x)=x$ with $p=1-\frac1e$ answered by User fgrieu, saying that we don't yet know. But if this is determined by probability is my question also answered by probability? Please let me know if I'm thinking the wrong way or give me an answer if you have one.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ If you detect a loop then you likely have found a collision. You expect this to happen after $2^{128}$ inputs. Also see chapter 2.1.6 of the HAC $\endgroup$
    – SEJPM
    Feb 27, 2016 at 19:35
  • 4
    $\begingroup$ Hint: we can approximate SHA-256 restricted to 256-bit input to a random mapping. Then, the classical results of Philippe Flajolet, Andrew M. Odlyzko Random mapping statistics apply, and allow to answer quantitatively (under such approximation). You can also experiment with a computer simulation, e.g. by studying SHA-256 restricted to its lowers 32 or 40 bits. $\endgroup$
    – fgrieu ♦
    Feb 27, 2016 at 19:50
  • 1
    $\begingroup$ Note that if you need a guarantee a hash will never loop, the easiest method is also adding a counter (e.g. $X_{n+1} = \operatorname{SHA-256}(X_n || n)$ , this is the way HKDF basically works. $\endgroup$
    – Daan Bakker
    Feb 28, 2016 at 16:30

1 Answer 1

Reset to default
2
$\begingroup$

Is SHA-256 designed to loop after exactly $16^{64}$ hashed hashes, or is there a chance it will do so before that point?

SHA-256 behaves more or less like a random function. You can expect it to loop after approximately $\sqrt{2^{256}} = 2^{128}$ iterations due to the birthday paradox

Improve this answer
$\endgroup$
3
  • $\begingroup$ It looks like you misquoted the OP. ​ ​ $\endgroup$
    – user991
    Feb 28, 2016 at 9:21
  • $\begingroup$ @RickyDemer Oops. The Latex formatting didn't copy. Thanks. $\endgroup$
    – user13741
    Feb 28, 2016 at 15:45
  • $\begingroup$ Are you sure that the Birthday paradox implies a loop? To loop I would expect the entire sequence to repeat itself exactly, not just get a random collision pair with a 50% certainty. $\endgroup$
    – Paul Uszak
    Apr 10, 2018 at 15:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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