SHA-256 and the avalanche effect (FIPS 180-2, 2002)

SHA-256 became the standardized hash behind Bitcoin’s block hashes, addresses, and Merkle trees. A good hash behaves like a random function: flipping one input bit flips each output bit with probability one half.

What to look for

Flip every bit of a message in turn. The number of changed output bits clusters around 128 of 256, following a Binomial(256, 1/2) distribution. This is useful intuition, not a proof of collision or preimage resistance.

The history behind this experiment: Breakthroughs in Cryptography. See Exercises: cryptography for a worked solution to the exercise.

import blockchainkit as bk
from blockchainkit.crypto.visualizers import plot_hamming_distances

message = b"blockchainkit: a reproducible experiment"
digest = bk.crypto.sha256(message)
assert digest.hex() == bk.crypto.merkle_damgard_sha256(message).hex()
distances = []
for bit in range(len(message) * 8):
    flipped = bytearray(message)
    flipped[bit // 8] ^= 1 << (bit % 8)
    distances.append(bk.crypto.hamming_distance(digest, bk.crypto.sha256(bytes(flipped))))
mean = sum(distances) / len(distances)
assert 120 < mean < 136
print("Mean changed digest bits:", mean, "out of 256")

Mean changed digest bits: 127.66875 out of 256

ax = plot_hamming_distances(distances)
ax.figure.tight_layout()

Exercise

Hash only the first byte of each digest and find collisions. Compare the number of trials to the birthday estimate. Why is this not an attack on the full SHA-256 output?