5 ms·
how long would the cycle last before it starts repeating?
by em3rgent0rdr 5y ago
how long would the cycle last before it starts repeating?
- tromp 5y agoOn 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.
- MayeulC 5y agoThen 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...
- tromp 5y agoIt 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.
- pbsd 5y agoSHA-256 is not a permutation; the expected cycle length is ~2^128. It's how collisions are (generically) found.
- colejohnson66 5y agoPigeonhole principle?
- pbsd 5y agoEach new output value i can collide with output 1, 2, ..., i-1. So the collision probability of iteration i is (i-1)/2^256. Adding all of the iterations up you have 1/2^256 + 2/2^256 + ... + (i-1)/2^256 = 0.5 i (i-1)/2^256 which approaches 1/2 as you get to 2^128. In reality you use some variant of Rho which does not store every previous value but uses something like Floyd's cycle detection or distinguished points and requires minimal storage, at the cost of some extra hash computations but still on the order of 2^128.
- dragontamer 5y agoThis situation calls for Birthday paradox, not pigeon hole.
- deleted 5y ago[deleted]