Avalanche
Change one bit of the input and about half the output bits change. It is said about every hash and cipher and measured almost nowhere. It is measurable: a thirty-two bit input has exactly thirty-two single-bit flips, so for any input the whole distribution can be walked rather than sampled. This page walks it, over a fixed set of inputs, and prints the same measurement for a function that does not mix at all — because sixteen is not a number that means anything on its own.
Flip one bit and count how many come back different
1 One input, one output, and the bits that make it up
One input, and the thirty-two bits it is made of. Flip any one of them.
90 (0x0000005a)
bit 11, worth 2,048
One bit of the input is different: 0x0000005a became 0x0000085a.
2 Flip a single input bit and count how many output bits moved
The output, with the bits that moved marked. Nothing about the input said which ones they would be.
16 of 32 output bits moved. The output went from 0x43c4ae27 to 0x285d1eff, which shares 16 bits with it.
3 Every single-bit flip there is, tallied into a distribution
Every single-bit flip of every sampled input, tallied into a distribution. Not a sample of them: all of them.
| bits changed | how often | |
|---|---|---|
| 5 | 2 | █ |
| 6 | 2 | █ |
| 7 | 19 | █ |
| 8 | 27 | █ |
| 9 | 111 | █ |
| 10 | 265 | ██ |
| 11 | 533 | ████ |
| 12 | 897 | ███████ |
| 13 | 1,319 | ██████████ |
| 14 | 1,794 | █████████████ |
| 15 | 2,181 | ████████████████ |
| 16 | 2,208 | ████████████████ |
| 17 | 2,109 | ███████████████ |
| 18 | 1,880 | ██████████████ |
| 19 | 1,294 | █████████ |
| 20 | 876 | ██████ |
| 21 | 475 | ███ |
| 22 | 234 | ██ |
| 23 | 109 | █ |
| 24 | 32 | █ |
| 25 | 11 | █ |
| 26 | 4 | █ |
| 28 | 1 | █ |
| 29 | 1 | █ |
16,384 flips walked, every one of them. The mean is 15.97 bits of 32, and 10,172 of them land between 14 and 18.
4 The same count for a function that does not mix, so the difference is visible
And the same measurement on a function that adds a constant instead of mixing, so the number above has something to be compared against.
- mixer, mean bits changed
- 15.97 of 32
- adder, mean bits changed
- 1.97 of 32
- worst input-to-output pair, mixer
- 57.6 per cent
- worst pair, adder
- 100.0 per cent
Both numbers want to be 50 per cent. The mixer's worst pair is 57.6, the adder's is 100.0 — an adder carries a flipped bit upward and no further, so most of its output bits never move at all.
These ran in this browser when the page loaded. Each claim, whether it held, and the number behind it.
| claim | held | measured |
|---|---|---|
| over 16,384 single-bit flips the mixer moves 15.97 of 32 output bits on average | yes | half of 32 is 16, and this is measured over every flip of every sampled input rather than a sample of them |
| adding a constant moves 1.97, which is not half | yes | the same measurement on a function that carries rather than mixes |
| and every one of the 1024 input-bit to output-bit pairs flips between 40 and 60 per cent of the time | yes | the furthest from half is 57.6 per cent at input bit 22, output bit 3 |
| the adder fails that outright: its worst pair is 100.0 per cent | yes | a mean close to half would not have shown this; the grid does |
What is real here, and what is not
This is a mixer, not a cipher, and the page does not claim otherwise
The function is murmur3’s finaliser: five lines, no key, and completely reversible if you know it. It avalanches, which is what makes it a good subject, and it provides no secrecy whatsoever. A cipher has to resist somebody who is trying; this only has to spread.
The inputs are fixed, not random
The census walks a fixed arithmetic sequence of inputs rather than random ones, so the histogram on this page is the histogram in the test and a disagreement reproduces. It also means the sample is structured, and a function could in principle do well on this sequence and badly elsewhere — which is why the page also prints the strict avalanche grid, where a single bad input-output pair shows up regardless of the mean.
A mean of sixteen is not enough and the page says so twice
A function could move sixteen bits on average while leaving one output bit that never changes at all. That is why the fourth panel reports the worst single input-bit to output-bit pair rather than only the average: the strict avalanche criterion asks that every pair flips about half the time, and it is the question that catches what the mean hides.
Avalanching well does not prove the function is the one you meant
Replace this mixer's first multiply with an ordinary JavaScript one — which silently loses the low bits once the product passes two to the fifty-third — and 504 of the 512 sampled outputs change. Every measurement on this page stays green: the mean moves from 15.97 to 16.03 and the worst input-to-output pair from 57.6 per cent to 57.2. Diffusion is not identity. A function can be arithmetically wrong and still spread a flipped bit beautifully, so nothing here should be read as saying the code below is murmur3's finaliser; that is checked separately, and not by another measurement of spread. The two multipliers and three shifts are read out of Appleby's own C++, archived in this repository, and the function rebuilt from HIS numbers is compared with this page's on every input the census walks.
Sources
- H. Feistel, Cryptography and Computer Privacy, Scientific American 228(5), May 1973. Where the avalanche idea is set out.
- A. F. Webster and S. E. Tavares, On the Design of S-Boxes, CRYPTO '85. The strict avalanche criterion, which is the measurable form.
- A. Appleby, MurmurHash3, smhasher. The finaliser this page measures, in its author's own C++: the same two multipliers and three shifts. Cited because a page claiming to measure murmur3's finaliser should say where the reader can check that it is that function.
- Logical Art, the studio this belongs to.