Breaking a cipher with no key: letter counts reach 43%, letter order reaches 100%
Counting letters recovers 43% of a scrambled message and you still cannot read it. Counting which letters follow which recovers all of it in under a second.
Somebody hands you a page of nonsense. You have no key, no crib, no idea what language it is in beyond a guess, and nobody to ask.
There is a method for this and it is eleven hundred years old. Al-Kindi, writing in Baghdad in the ninth century, noticed that letters appear at stable rates in any long text, so you can count the symbols in the cipher, rank them, and line that ranking up against the rank order of the language. E is the most common letter in English. Whatever symbol is most common in the cipher is probably E.
I wanted to know how far that actually gets you, and what has to replace it when it fails.
The only thing the codebreaker is allowed to know
Everything here is built from counting, and the counting is done on a real book: the public-domain text of The Adventures of Sherlock Holmes, 446,804 letters after stripping everything that is not a letter. Fittingly, one of the stories in it is itself a frequency-analysis crack.
From that book alone, with no dictionary and no word list, the program learns two things.
First, how often each letter appears. It comes out at E 12.3 percent, T 9.1, A 8.1, O 7.8, I 7.0, which is the familiar opening of the canonical order. The rest of my ranking disagrees with the textbook version by a single swap, H and S trading places, which is what you get for measuring one author rather than reciting a table.
Second, and this is the part that does the work, how often each run of four letters appears. There are 456,976 possible four-letter runs and English uses a small fraction of them heavily. THER is everywhere. QZXV is nowhere.
That table of four-letter runs is the entire knowledge the codebreaker carries into the problem. It never sees a plaintext.
Road one stops where you cannot read
I enciphered a paragraph with a random one-to-one substitution. There are 26 factorial possible keys, which is about 4 followed by 26 zeros, so trying them all is not a plan.
Al-Kindi’s method, run on the ciphertext: 43 percent of the characters land correctly, and 23 percent of the key.
Here is what 43 percent looks like:
TOEDENSAIHRLNLEATOATAIPUESSACEOHFEVEDTAICRELSTNRRMADDNESTOESOAWEHKTOYou can see it is not random. A few short words surface. And you cannot read a word of it, which is the honest state of the method: right often enough to feel close, wrong often enough to be useless.
That happens because the letters in the middle of the frequency table are all within a percentage point of each other. Their true order in any particular paragraph is essentially noise, so ranking them is a coin flip repeated fifteen times.
Road two reads the whole thing
The second method never looks at how often a letter appears. It looks at what each letter sits next to.
Take a guess at the key, decrypt with it, and score the result by how English the four-letter runs look, using the table built from the book. Then swap two letters of the key, rescore, and keep the swap if it improves. Do that a lot, with enough randomness early on to avoid getting stuck.
The staircase is the interesting shape. The search sits on Al-Kindi’s floor for a long stretch, because most single swaps make the score worse. Then it finds one that lands a cluster of common words at once, and the score jumps. A few jumps in, the whole thing falls over.
It recovers 100 percent of the characters. Six tenths of a second, on a search space of 4 times 10 to the 26.
There is a detail in the result I like more than the headline. The recovered key is only 85 percent correct, and every single character of the message is right anyway. The 15 percent of the key that is wrong is exactly the letters this paragraph never uses: J, Q, X, Z. Structure cannot pin a letter that never appears, and it does not need to.
The defense that kills road one, and still loses
There is a classical answer to frequency analysis and it is a good one. Give the common letters several symbols each, so E might be enciphered as any of six different marks chosen at random. Now every symbol in the ciphertext appears at roughly the same rate.
It works exactly as advertised against the first road. The tallest bar in the plaintext is E at 14.8 percent. After the defense, the tallest symbol is 3.8 percent, and all sixty symbols sit near 1.7. Ranking them gives you nothing at all.
The second road recovers 100 percent of the message anyway.
The reason is one sentence: a mask changes what a letter looks like, and not what it likes to sit beside. You can flatten how often E appears. You cannot flatten the fact that whatever stands for T is followed by whatever stands for H far more often than chance allows. The transitions leak, and the transitions are where the meaning lives.
This is the same family of attack that broke the Zodiac 340 in 2020, after fifty-one years.
The failure that taught me the most
My first attempt at the harder cipher stalled at 54 percent and would not move.
The search had collapsed into a degenerate solution. With many symbols free to map to any letter, the highest-scoring cheat is to map almost everything to E, T, H and S, which manufactures a huge number of THE and HER patterns without the decryption being remotely correct. The score goes up. The message stays hidden.
The fix was not more search time. It was to stop letting the search choose how many symbols become each letter. I fixed the letter multiplicities to an English-shaped distribution up front, so six symbols must become E and one must become Z no matter what, and let the search only decide which symbols those are.
That is a prior on the language, not on the secret, and it is legitimate. The second run recovered everything.
The general shape is worth keeping: when a search finds a cheat, the repair is usually a constraint on the space rather than a bigger budget.
What was found this way, and what still resists
Al-Kindi gave the world the first road. Champollion cracked Egyptian hieroglyphs in 1822 with a bilingual key, the Rosetta Stone, which is the easy case.
Michael Ventris, in 1952, deciphered Linear B with no bilingual at all. He built a grid of which signs share a consonant and which share a vowel, purely from where they appear in words, and the language underneath turned out to be Greek five hundred years older than anyone expected.
Linear A, the Indus script and Rongorongo are still unread. The methods have not gotten worse. The honest limit is that structure alone runs out when you do not know the language underneath, and no amount of counting recovers meaning that nothing anchors.
What I re-ran before writing this
The whole chain, two months later. 446,804 letters of corpus. The frequency order coming out of the counts. 43 percent of characters and 23 percent of the key from frequency analysis. 100 percent of characters and 85 percent of the key from the structure search. The defense cutting the tallest bar from 14.8 percent to 3.8, and the structure search reading the message anyway.
Looking at the plates turned up a problem nothing in the toolchain could catch. That folder’s hand-rolled font has no percent sign and no greater-than sign, and a character the font lacks was drawn as a blank rather than raising an error. So every number on those two figures had been rendering without its percent sign, including the one that says the search recovered 100 percent of the message, and the axis label ending in an arrow had lost the arrow.
The characters are in the font now, and the font raises rather than dropping anything it cannot draw.