Odd and even in the K4 cribs

The pattern

The ciphertext is the standard 97-letter transcription. The cribs are EASTNORTHEAST at positions 22–34 and BERLINCLOCK at positions 64–74, counting from 1. At each crib position, take the cipher letter’s number (A = 0, B = 1, …, Z = 25) and add the position. In the table, the cipher letter is in brackets after its number.

That is 13 pairs of matching plaintext letters, and all 13 agree. They are not 13 separate tests: a letter seen three times gives two independent comparisons, so there are 11 independent checks. The letters fall into two groups: B, E, H, I, O, R, S on the odd side and A, C, K, L, N, T on the even side.

The usual conventions make no difference. Counting positions from 0, or numbering the alphabet from A = 1, flips every answer at once, so the pairs still agree.

A fair first objection is that the two EASTs are nine positions apart, so their positions already differ between odd and even. That is exactly why it is a test. For E to keep the same total, its cipher letter has to switch too, and it does (F = 5, then G = 6). All four letters of EAST do: FLRV are all odd (5, 11, 17, 21) and GKSS are all even (6, 10, 18, 18).

Why it is about the key

In the cipher families most often proposed for K4, each plaintext letter is shifted along the alphabet by a key letter. Vigenère, Beaufort and variant Beaufort differ only in the direction of the shift. In all three, whether the key plus the position is odd or even is fixed by two things: the same odd-or-even answer as in the table, and the plaintext letter. Within a pair the plaintext letter is the same, so it cancels. The pattern therefore says: at the crib positions, whether the key plus the position is odd or even depends only on which plaintext letter is being enciphered.

Going round the end of the alphabet does not disturb this, because 26 is even: taking away 26 never changes whether a number is odd or even.

One of the 13 pairs was already known. R at positions 28 and 66 is enciphered as P both times, so the key is the same at those two positions. That is the key equality Richard Bean recorded in his 2021 paper (he counts from 0, so it appears there as positions 27 and 65). Colin did not find the odd-and-even pattern across the other pairs stated there or elsewhere.

key = C − P   (Vigenère)
key = C + P   (Beaufort)
key = P − C   (variant Beaufort)        all counted mod 26

parity(key + i) = parity(C + i) + parity(P)       in every case, mod 2

same plaintext letter P at positions i and j:
  parity(Ci + i) = parity(Cj + j)   exactly when   parity(keyi + i) = parity(keyj + j)

How unusual it is

“How likely is this by chance?” has more than one honest answer, depending on what is allowed to be random. All three below are exact counts, not estimates.

• If the cipher letters at the crib positions were random: 13 letters have odd numbers and 13 have even ones, so each of the 11 checks is a fair coin. All 11 coming out the same way has odds of exactly 1 in 2,048.
• If K4’s own 97 letters were shuffled into a random order: 1 in 1,996. This keeps K4’s actual mix of odd and even letters, so the pattern is not a side effect of which letters K4 happens to use. Colin’s original check, 2,000,000 random shuffles with 994 hits, agrees with it.
• If the alphabet were numbered in a random order instead of A to Z, with the carved letters left where they are: 1 in 433. This is lower because two of the 11 checks pass under any numbering at all. R is enciphered as P at both of its positions, so that pair always agrees. And the S pair (positions 24 and 33) and one T pair (29 and 34) use the same two cipher letters, R and S, in the same roles, so they agree or disagree together. Only 9 checks are left to chance.

Then there is how the pattern was found. Colin came across it while computing about ten different statistics on the cribs, and also tried the KRYPTOS-keyed alphabet, where the pattern does not appear (6 of 13 pairs agree). His own allowance for that search puts a fair overall figure at roughly 1 in 100 to 200. That allowance is a judgement, not a calculation, and it is the honest headline: interesting, not proof.

What it says about how K4 was built

Suppose K4 combines a letter-for-letter substitution (a mixed alphabet) with a shifting key. If the pattern comes from the method rather than luck, it means the pattern would hold whatever key had been chosen. Under that assumption, which the proofs state openly, the order of the two steps matters:

• Substitute first, then shift: the pattern follows automatically, provided the key’s odd-or-even value steps in time with the position. Each plaintext letter’s group is then simply whether the substitution sends it to an odd or an even number.
• Shift first, then substitute: the pattern can hold for every key only if the substitution keeps odd letters odd and even letters even, or swaps the two halves wholesale. The groups would then have to match the ordinary alphabet’s odd and even letters. They do not: E (4, even) and R (17, odd) are in the same group. So this order cannot produce the pattern by design.
• Two shifting keys add up to a single shifting key, so nothing on this page can tell them apart.
• A transposition as the last step adds a term that depends on where each letter moved. For a keyed columnar transposition of odd width that term is the same all the way down each column, and 38,805 of the 409,112 keys of widths 2 to 9 leave it the same at all 24 crib positions. So the pattern cannot rule a final transposition in or out.
• One method across both cribs: four of the checks link the two cribs, because E, N, O and R appear in both. If the cribs had been enciphered separately, those four would be coin flips. All four agree, a 1 in 16 coincidence on its own: mild evidence for one method spanning positions 22–74.

It also says less about the cipher alphabet than it might seem to. The pattern only fixes which letters count as odd and which as even. Any renumbering that keeps the odd letters together, or swaps the two halves wholesale, keeps all 13 pairs; swapping A and C is one example. So the pattern points to an alphabet whose odd/even split is the ordinary one, not to the ordinary order itself.

Together with the Stehle run

K4 has a second well-known oddity next to BERLINCLOCK. In the nine letters DIAWINFBN at positions 56–64, every letter is exactly five places further along the alphabet than the letter four positions before it (D to I, I to N, A to F, W to B going round from Z to A, I to N). Ferdinando Stehle pointed this out on the sci.crypt newsgroup in 2000, and Bean’s 2021 paper cites it. Allowing for the fact that both the gap of four and the place were found by looking, a run like this turns up by chance about once in 205 tries.

If both patterns are real and come from the “substitute first, then shift” method above, they combine like this:

• The key’s change across each four-letter step is even, so the key cannot supply the whole 5. Each 5 splits into an odd part on the plaintext side and an even part on the key side.
• So in positions 56–64, plaintext letters four apart always sit in opposite groups, and no plaintext letter repeats four positions later.
• Position 64 is the B of BERLIN, which is in the odd group. So position 60 is not B, E, H, I, O, R or S, and position 56 is not A, C, K, L, N or T. Letters outside the 13 grouped ones are not constrained at all.

What it cannot tell us

This is the most important result on the page. Under that method, once the substitution is fixed, a candidate plaintext is possible for some key exactly when it passes one odd-or-even test at each position. The key is otherwise free, so the method never predicts a key value. The Stehle run adds nothing beyond that test: any plaintext that passes it already has all the Stehle consequences above.

The test allows exactly 13 of the 26 letters at each unknown position once the substitution is known, and more before it is. That still leaves 13 choices for each of the 73 unknown letters before anyone asks whether the result reads as English. To show how loose it is, the proofs include a complete 97-letter plaintext that fits both patterns and both cribs and uses only A and B everywhere else. Guessing plaintext against these constraints is not a way to search. Their use is to reject proposed solutions that come from somewhere else.

What new plaintext would show

If the pattern comes from the method, it has to hold across the whole message: every plaintext letter must give the same odd-or-even answer at every one of its positions. Over 97 letters that is dozens of independent checks, which chance would essentially never pass. If more plaintext is ever published, this is a one-line check.

Any newly released crib letter that is one of the 13 grouped letters must land in its group, and each one is a fair test with an even chance of breaking the pattern. If the pattern is luck, eight such letters would all fit only about once in 256 tries.

Checked by computer

The arithmetic on this page is written as proofs in Lean, a proof assistant: a program that checks every step of a mathematical argument and refuses any step it cannot verify. The proofs start from the carved ciphertext itself, read letter by letter, and an automated test fails if that text ever differs from the repository’s reference copy. A final audit confirms that no step was taken on trust.

Four figures are exact counts made by a short Python script in the same folder rather than Lean proofs: the shuffle and random-numbering odds, the KRYPTOS-alphabet count and the transposition count. The 1-in-205 figure for the Stehle run comes from a separate script, linked below.

Reproduce

bash formal/k4_parity/reproduce.sh

Run from a clone of the kryptos repo. Needs Python 3.11+ and elan, the Lean installer. The first run downloads the Lean toolchain, the Mathlib library and its prebuilt files; allow about 11 GB of disk space. The proofs, the script and a theorem-by-theorem index are in formal/k4_parity.

How confident we are