0
$\begingroup$

This question follows on from my answer to calculation-of-the-avalanche-effect-coefficient earlier. I have reproduced the graph for this question.

Full avalanche effect graph

Consider the red line which represents the number of bits changed for a single flipped input bit to SHA-512. This is for 100,000 random bit flips. The graph is normal, as expected for a full avalanche effect. From preparing this graph, I can say that the mean (of course) is 256 bits, which is 512 /2. As expected. (I actually get 255.5 but that could be my fault).

The standard deviation of this normal curve is approximately 11.3 obtained empirically. That's for a SHA hash with a block size of 512 bits.

Q. Is there a calculable mathematical relationship between the standard deviation and the block size, or must it always be determined empirically?

$\endgroup$
2
$\begingroup$

Q. Is there a calculable mathematical relationship between the standard deviation and the block size, or must it always be determined empirically?

This is a well studied problem in probability.

If we consider each output bit as an independent random variable (and if they're not independent, your hash function is broken), each such random variable has a standard deviation of $0.5$ (if $0$ and $1$ have equal probabilities; again, if this is not true, your hash function is broken). The sum of $N$ such independent samples will have a standard deviation of $0.5 \sqrt{N}$. In your case, $N=512$; this gives us a standard deviation of $11.3137...$, which is just what you see.

$\endgroup$
  • $\begingroup$ Note: in this answer, "hash function is broken" is considered with respect to a model of the hash as a PRF, not to other properties like collision or preimage resistance. $\endgroup$ – fgrieu Nov 23 '16 at 11:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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