The ADFGVX residue of 1918 — twenty-two mutilated messages against known keys

01 What the list is

James Rives Childs, the American cryptanalyst attached to the French in 1918, kept a transcript of German ADFGVX traffic intercepted on the Eastern Front. In 2017 George Lasry, Ingo Niebel, Nils Kopal and Arno Wacker broke the corpus with a hill-climbing attack on the transposition and recovered 618 cryptograms under fourteen three-day keys, from September to December 1918. Lasry then gave Klaus Schmeh a list of the messages that would not decrypt under any of those keys, and Schmeh published it as “Unsolved ADFGVX messages from World War I”, with the keys attached, and later as no. 46 on his Top 50.

Lasry’s own note on that page says what the problem is: the keys are “most certainly all the keys used during the period”, so “the challenge is to understand how the cryptograms were mutilated”. ADFGVX is unforgiving about length. The columnar transposition splits the letter stream by the key length, so one lost or added letter moves every column boundary after it and turns the rest of the message into noise. A message with two garbles is no longer decryptable by the key, even though the key is known.

Between February and September 2017 the comment thread under the post did most of the work. Norbert Biermann, Armin, Thomas, Max Baertl and Lasry himself read message after message. Schmeh announced a consolidating article and never wrote it, so those readings existed only as scattered comments and no table of which messages are solved had been published. The first thing this write-up does is publish that table.

02 The keys, made machine-readable

Lasry’s list gives each key as a transposition permutation and a 36-character substitution square, the cells in row order of A D F G V X. Three of the fourteen squares contain runs of hyphens for cells never recovered, and the text layer of the PDF collapses those runs into en- and em-dashes, leaving squares of 34 or 35 characters. Expanding each dash back to the run length that makes 36 repairs all three. All fourteen are in keys.json.

The key numbers admit two readings. Either perm[i] is the column emitted i-th, or it is the position at which column i is emitted. Both round-trip self-consistently, so an encrypt-decrypt test cannot tell them apart. Decrypting a real message can. It is the second.

The key not on the list

On 3 May 2017 Lasry reported in the thread that a two-part message, the FFVXV cryptogram of 13 November and the AFAFF fragment that continues it, decrypted jointly under a key that was in none of the fourteen periods: transposition word CMBLAKOHIDENFJGP, length 16. He gave the joint plaintext, 173 letters, and noted that his program had needed all 356 ciphertext letters to recover a length-16 key. The substitution square was not published. It is rebuilt here by aligning the untransposed bigrams of the two cryptograms with his plaintext, Norbert’s corrections applied: 24 of 36 cells, with the digits and the letters M, Q and Y unrecovered because the message never uses them. It is the fifteenth entry in keys.json and the repo’s notes call it the CHI key, after the header of the message it enciphered.

03 The table nobody published

The thread, all 70 comments, read in full. Page numbers are Childs’s transcript pages as Schmeh printed them; two messages carry no page number on the list. Letter counts are of the received ciphertext, with the gaps marked in the printed transcription counted separately. The reading is by the person who first posted it.

Nine solved, three partly read, ten never read. One further transcript page, 187 as printed (SELLV…, “Stellv. Gen. Kom. 9 AK Breslau”), was a message the Kassel team had already solved and does not belong on the list; Lasry said so in the thread. The two CHI messages were listed as unsolvable under the published keys, which is true; they were solved by finding a key that was not published.

04 Norbert’s method, reimplemented

Norbert stated his method in one sentence: add or remove up to five characters at two different positions, exhaustive search, an n-gram value function to rank the results. blocks.py does exactly that. For each of the fifteen keys, and each choice of up to two block edits of one to five letters, inserted or deleted at the five-letter group boundaries of the transcript, it decrypts and scores the result with a German quadgram model built from 3.6 million letters of Gutenberg German (lm_de.py). Windows that contain a digit or an unrecovered cell cost a floor; windows that cross an X separator cost less than junk and more than text. German prose scores about −3.3 nats per window on this model, and random letters about −7.

Given no hint of the plaintext, the search re-derives pages 105, 109, 146 and 171, the “missing 10 letters” message of page 176, and the two CHI messages. On page 146 the five-letter block that Norbert inserted before group 10 comes out as (45, 5). On the page-176 message the two five-letter blocks come out as (10, 5), (130, 5). Page 100 falls to the same search with one two-letter insertion. The search also finds the Nov 22–24 partial of the unnumbered VGADA message. Where the printed transcription marks gaps, gaps.py restores them to their groups and anneals the residual single-letter losses; on page 132 it lands on Norbert’s text unprompted.

The scores of the re-derived pages, from the run log, against the best any of the open messages achieves:

The solved pages are recognisable German at a glance even where the block edit is not quite right, and the residual garbles are the single-letter losses that a second pass repairs. The 105 and 109 lines score lower than the others because the two-block search only approximates their mutilation; both texts are nevertheless readable in the raw output and both agree with Norbert’s 2017 readings.

05 The ten open messages, tested

Two block edits, fifteen keys

Every one of the ten was run against all fifteen keys with up to two block edits. The best result for each, from blocks_out.txt:

Nothing clears −6.7. The solved messages come out between −4.4 and −6.0 on the same run, and random letters at about −7.3. So none of the ten is one of the fifteen keys with two or fewer block mutilations, which is exactly the boundary the 2017 readers reached and stopped at. A digit-heavy output is the usual sign of a wrong key: real traffic here is mostly letters, and a wrong square scatters bigrams across the digit cells.

The CHI key on the two page-153 messages

In September 2017 Norbert suggested, without testing it, that the two page-153 messages might belong to the CHI key, since they are of the same period. Direct decryption with parity repair, and the block search, both return noise for both messages. Either a further unlisted key, or losses heavier than two blocks.

A key-free attack, and why it fails

If some of the open messages were enciphered under a key not in the corpus, the key would have to be recovered from the ciphertext alone. keyless.py tries: anneal the column order at each candidate length on the index of coincidence of the letter pairs the untransposition produces, since a correct untransposition pairs the bigrams of a monoalphabetic substitution, then solve the 36-symbol substitution with the German model. Before running it on the open messages it was run on a planted control: 224 letters of German enciphered under a length-19 key of the same design.

The true length does not stand out: the peak at 19 is beaten by 21, 22 and 23, and the substitution stage does not converge at any length. The control is not recovered. Lasry’s own program, built for this purpose, needed 356 letters to recover a length-16 key. The ten open messages are 84 to 240 letters long. A key-free recovery is therefore out of reach at these lengths, with one exception: two or more open messages that share an unknown key could be solved jointly, as the two CHI messages were. Nothing in the ciphertext marks which those would be, and the two page-153 messages, the natural candidates, give nothing when tried together.

06 Status, and what would change it

The residue is nine solved, three partly read, ten open, and the ten are open for a reason that is now measured rather than assumed. Three things would change it.

Until one of those arrives, the useful products are the table above, the fifteen keys in machine-readable form with the three damaged squares repaired and the CHI square rebuilt, and a decoder that reproduces the 2017 solutions blind.

07 Files