jOhNCHAIN · On the Evolution of Substitution Boxes

A blockchain trying to invent the heart of a cipher

Encryption is scrambling. AES is the cipher that does most of the world's scrambling: your bank, your phone, the padlock in your browser. At the centre of AES sits a lookup table of 256 entries. Give it a byte, it hands back a different byte. That table is the substitution box, and it is the only part of AES that is not ordinary arithmetic. It is the reason the cipher cannot simply be solved backwards.

A good table is one nobody can shortcut. The table inside AES was worked out by hand and is close to the best anyone knows how to do. This chain is trying to find its own by trial and error. Every block is one attempt: candidates are scored, the strongest is kept, the rest are shuffled and tried again. There is no finishing line in the rules, so it does not stop. The figures below are amended in place while you read them.

Standing figures
Generation	—
Non-linearity	— AES 112
Differential uniformity	— AES 4
Fitness	—
Shortfall against AES	—
Generations since a gain	—
Search space	256! ≈10⁵⁰⁷

I What a good table looks like the same test, run on both

This box, generation — tallest —

cells at —

AES, published 2001tallest 4

cells at —

2 or fewer 4, a level AES also reaches 6 to 8, above anything in AES 10 or more, a spike the tallest cells, circled

Figure 1. Each plate maps how differences travel through a table. Change the input a certain way, and the output changes some way too. The plate counts how often each pairing happens. Spread thin is good. Red marks a pairing that recurs more often than any pairing in AES; blue marks a real spike, and the circles are the worst of them. A pairing that recurs is the crack an attacker widens until the cipher opens, so the counts under each plate are the whole argument: AES stops at 4, and this table does not.

Precisely: row dx, column dy counts the inputs differing by dx whose outputs differ by dy. The average is 2, so only cells above 2 take ink. AES is not the emptier plate, it is the flatter one: nearly every cell sits at 2 and none exceeds 4. The chain's table concentrates its differences into spikes instead, and those are what is burning red.

II How good it is so far sampling a random table…

Both scales are absolute. Left is where a table picked at random lands. Right is the best anyone knows how to reach. AES is in black, the chain in red.

Non-linearity how far the table sits from anything a straight line can predict. Higher is stronger.

Differential uniformity the tallest spike on the plates above. Lower is stronger.

III The table, right now

Point at any entry.

Figure 2. All 256 entries, at generation —. Read it like a street map: row x, column y holds what the table gives back for the byte xy. This is the layout FIPS 197 uses to print the AES table. An entry struck in red changed in the last generation, and the warm cast on an entry fades over the generations since it last moved, so the table carries a record of where the search has been working. Usually a winning candidate is the reigning table with two entries transposed. Occasionally the whole thing is replaced by a better line of descent, and then the record starts again.

IV Progress —

Best fitness held by the chain

AES, 11,180

A generation that beat its parent

The ledger of gains

Generation	Fitness	Gain	NL	DU
awaiting the node

1. Fitness is NL × 100 − DU × 5. AES therefore scores 11,180. The weighting is a choice, not a law: it says a point of non-linearity is worth twenty of differential uniformity.

2. 256! is roughly 10⁵⁰⁷. Sampling at random will not find a strong box in the lifetime of anything. Neither, in all likelihood, will this: the search is expected to stall short of 112 and stay there, which is the honest and more interesting result.

3. Mutation is a transposition of two entries. A permutation with two entries swapped is still a permutation, so every candidate is a valid bijection by construction and no repair step is ever needed.

4. Elitism makes the score monotone: it cannot fall. The plot in III is therefore a staircase, and the flat stretches are not stalls in the recording, they are the actual difficulty of the problem.

5. No floating point is used anywhere in scoring. This is what lets independent nodes agree: two machines that disagree by one bit of rounding would fork the chain.

6. The plot shows the generations the node still holds in state. A node that has been restarted begins its record again from the height at which it resumed.

The seven capitals spell ONCHAIN; the lowercase threads John through it.

Set in the browser's oldstyle serif. Two inks. No dependencies.