A partial preimage attack on (double) SHA-256, done by brute force.


It is not a matter of solving the nonce value.  The nonce is meaningless, in and of itself; that is why it’s called a nonce.  Or perhaps it may be said, the nonce is meaningfully meaningless.  The only means of bruteforcing a hash (partial) preimage is to repeatedly change the input until you get the desired output.  The nonce is the part which gets changed; it is really a sort of a throwaway value, only there to provide arbitrarily changeable input bits.

SHA-256 is assumed (or pretended, depending on whom you ask) to have the properties of a random oracle.  Simply for the sake of understanding, pretend that for each increment of the nonce, you are generating a random number.  If target difficulty requires an unbroken string of x zeroes in the highest digit positions, then imagine how many times you’d need to generate a 256-bit random number before you have the luck to draw one which starts with x zeroes.  Alternatively, think of it as a 256-bit string of coin flips with H=0 T=1.  How long will it take you by random chance to get a string starting with x heads in a row?

(Question for anybody:  Would the probability equal that of simply flipping x heads in a row, or would you need to repeatedly flip whole 256-bit strings of flips until you get one which starts with x heads in a row?  I seem to have temporarily confused myself here.  Checked in in alpha state.  May be patched.)

Another interesting way to look at it:  If SHA-256 has good avalanche (as we suppose), then for a single-bit flip in its input, each bit of output has a 50% probability of flipping.  Implications for bruteforcing a partial preimage are left as an exercise to the reader.

(I used several basic/intermediate level cryptography terms of art here.  I tried to pinpoint those in boldface so you can look them up if you’re unfamiliar with them.)