encryptionhashgpusha256cracking

How long would it take for a sha256 digest loop to reach the original hash or start cycling?


If I started with a sha256 hash such as

3f46fdad8e5d6e04e0612d262b3c03649f4224e04d209295ef7de7dc3ffd78a7

and rehashed it continuously (without salting):

i) What is the shortest time it would take before it started cycling in a loop or back onto the same value if at all?

ii) If it did cycle back on itself, could we assume that it had been cracked?

iii) How long would this take using modern GPU cracking techniques?

iv) If all the intermediary hashes were recorded in some kind of rainbow tables - presumably all the hashes within that cycle would be compromised?

v) What is to stop someone computing these cycles and offering cracks to sha256 hashes - likewise for other hashing protocols...

For Extra marks - What is the probability this question would be asked in this forum 60 billion years ago?


Solution

    1. If values generated by sha256 can be assumed to be distributed uniformly and randomly, then there exists with probability 1−1/e (about 63%) a 256-bit sequence whose sha256 hash is equal to itself. If so, the minimum sequence length is one.

    2. On the other hand, based on the pigeonhole principle, we know that the sequence must repeat after no more than 2256 iterations. This doesn't say anything about the brokenness of sha256.

    3. The maximum cycle length is 2256 ≈ 1.16×1077 iterations. If you can evaluate 1012 hashes per second, then working your way through all possible hashes would take you about 1065 seconds (about one quindecillion times the age of the earth). Even if you're fortunate enough find a loop in a tiny fraction of that time, you're still liable to be waiting for trillions of years.

    4. Good luck with that. If every atom in our galaxy was used to store a separate hash value, you would run out of space after storing less than one billionth of the total number of hashes. (Source: number of atoms in milky way galaxy ≈ 1068)

    5. See 3 and 4

    6. A similar question was asked about 9 years ago.