8
$\begingroup$

So let's say you had infinite time and energy. You have a hashed string of some sort. Because you have infinite time and energy, you can produce a collision(or the original value) easily enough. But, there is a problem. The hashed string was hashed an unknown amount of times. (ie, it may have been produced by sha256(sha256("foobar")) or by sha256(sha256(sha256(sha256("foobar"))))).

You were given a hint by your adversary though. They give you (say) 10 strings, of which one is the initial value that is hashed.

Is it possible to determine with absolute certainty that you chose the correct string? Is it possible that hashing "foobar" recursively an infinite amount of times will eventually yield any arbitrary hash value?

Although my question is about SHA256, I'd be equally curious of other hash algorithms as well

Improve this question
$\endgroup$
1
  • $\begingroup$ Does rehashing a hash improve security? $\endgroup$
    – Aaron Franke
    Commented Oct 21, 2018 at 23:02

1 Answer 1

Reset to default
7
$\begingroup$

Is it possible that hashing "foobar" recursively an infinite amount of times will eventually yield any arbitrary hash value?

I very much doubt it. A simple demonstration of this logic can be done through the birthday paradox. Suppose we log each successive recursive SHA-256 on "foobar" in a table. We can ask ourselves what the probability is that our next recursion will collide with any item already in the table?

Assuming SHA-256 behaves as a random function the probability will exceed 50% just after we've tried approximately $2^{128}$ recursions. However, since we know that SHA-256 is not actually a random function, as soon as a collision is found it will then fall in to a cycle. Thus, approximately 0% of the total hash value space will be covered.

The string "Foobar" would need to be a special case where each hash value is visited exactly once. I believe this property is called being a "generator" but I'm happy to be corrected on that point.

Although my question is about SHA256, I'd be equally curious of other hash algorithms as well

I'd expect that this analysis would apply to any secure cryptographic hash.

Improve this answer
$\endgroup$
7
  • 3
    $\begingroup$ A generator exists if and only if SHA-256 has a single cycle (i.e. if iterating it eventually loops around the same list of values). This is unknown (I presume) but probably false. If SHA-256 was a permutation on strings of length 256 (again, unknown, but it probably isn't), we'd expect it to have about $256 \ln 2 \approx 177$ cycles. $\endgroup$
    – Gilles 'SO- stop being evil'
    Commented Sep 4, 2013 at 17:16
  • 1
    $\begingroup$ The concept of a "random function" is normally used for a function selected uniformly at random - not for a random generator. While a random generator will not fall into cycles, a function selected uniformly at random will, just like a pseudo random function will. $\endgroup$
    – Henrick Hellström
    Commented Sep 4, 2013 at 17:18
  • 1
    $\begingroup$ Just to clarify - the term "generator" has different meaning in my comment and in Gilles comment. I use the term as it is used in e.g. RNG - random number generator. $\endgroup$
    – Henrick Hellström
    Commented Sep 4, 2013 at 17:20
  • $\begingroup$ Hmm.. interesting logic. If only the resources existed to practically test if it was true $\endgroup$
    – Earlz
    Commented Sep 4, 2013 at 17:56
  • 3
    $\begingroup$ @Earlz: You could test it on a truncated version of SHA-256. Something like, say, 24 or even 32 bits ought to be doable. (Or course, this won't prove anything about the full SHA-256 behaving the same way, but it's at least illustrative.) $\endgroup$
    – Ilmari Karonen
    Commented Sep 4, 2013 at 21:44

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