Broken SHA hashes and cryptocurrency

The SHA hash used in Bitcoin is iterated, or re-applied to its output.

H=\mathrm{SHA256}(\mathrm{SHA256}(I))

When a hash function is iterated for a second time in this manner, the size of its range is reduced by an approximate factor of 1-1/e by random collisions.

The iterated hash function itself can also be iterated, and we may estimate the range reduction asymptotically.

\left|\mathrm{SHA256}^{2^k}(R_0)\right|\approx\left(1-\frac 1 e\right)^k|R_0|,

where R_0 is the range of the original SHA256 (or other hash) function. Or let N=2^k for the number of times the original hash function is iterated.

\left|\mathrm{SHA256}^{N}(R_0)\right|\approx\left(1-\frac 1 e\right)^{\log_2 N}|R_0|

I am attempting here to estimate the reduction in strength of a hash function that occurs when it is iterated, as a reduction in size of its range, by purely information-theoretical arguments.

Leave a comment

Your email address will not be published.