On the order of 2^256 steps, if SHA-256 behaves randomly, since the largest cycle in a random permutation on N elements has expected length ~ 0.62 * N.
Then wouldn't that be 0.62*2^256, closer to 2^255 ? Not that it makes a notable difference: at 1 fs per step (1000 GHz, or 1 TH/s), that would take about 4.5e65 years to happen. The universe is only about 1e10 years old...
It would be at least that, with a smaller contribution to the expectation from smaller cycles. That's why I said "on the order of", i.e. not much smaller.
