1
$\begingroup$

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?

$\endgroup$
1
3
$\begingroup$

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

Well, strictly speaking, it's possible (albeit unlikely) that the first hash output would happen to be the initial value, and so the "shortest time possible" would be one hash.

However, lets do some analysis to see when it's likely to happen.

Let us assume that SHA-256 acts as a Random Oracle (it has no known ways it doesn't act like a Random Oracle on fixed length inputs). Then, for a hash chain of length $n$, you have $n+1$ outputs, and hence $(n+1)(n+2)/2 \approx n^2/2$ pairs of outputs, and for each pair, we have a probability of $2^{-256}$ of them happening to collide (actually, this isn't exactly correct, but it's close); hence, if $n \ll 2^{128}$, we have a probability of circa $2^{-257}n^2$ of there being a collision (again, this isn't precisely correct, because the probabilities are not independent, but it's close).

So, to get a probability of $2^{-30}$ of falling into a loop, we would need a chain of length $n$ where $2^{-30} \ge 2^{-257}n^2$ or $n \ge 2^{113.5}$ long. If your hardware can compute $2^{30}$ SHA-256 hashes per second (real hardware can't go this fast), then it'll take around 30 million times the current estimate of the age of the universe.

How long would this take using modern GPU cracking techniques?

Well, a quick Google search finds the fastest GPU doing about 3 billion SHA256 hashes per second. Let us assume that you have a GPU farm with a million of these GPUs, and let us also ignore the issue that computing a hash chain is an iterative process (and GPUs want to compute things in parallel). Then, using the above estimates, to get to a 1-in-a-billion probability of finding a collision, we get the expected time down to about 10 times the age of the universe.

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

Probability is 0; this forum didn't exist 60 billion years ago :-)

$\endgroup$

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