Breaking a cipher by counting¶

Level: 101 → 201 · for anyone starting from zero

One line: A substitution cipher has 403,291,461,126,605,635,584,000,000 keys and is broken below without trying a single one — because renaming the letters leaves every relationship between them exactly where it was.

Why this is the first thing in the library¶

Not nostalgia. This is the shortest route to three ideas that everything after it depends on, and you get them by doing rather than being told:

A large keyspace is not security. 26! is a number no search will ever exhaust, and it does not matter.
A cipher has to destroy structure, not just identity. Substitution changes what each letter is called and changes nothing about how often it appears, what it sits next to, or how long the words are.
You never rest a break on one method. Section 4 of the run below catches its own frequency guess being wrong, and corrects it from a word — which is the actual working method.

The sibling library covers the ciphers with no secret in them at all: Rotation is not encryption ↗ shows ROT13 as arithmetic on the ASCII table, with a published shift and a keyspace of exactly one, and hands the rest over to this page. The step up is real — this cipher does have a secret, and it is 88 bits' worth — and it makes no difference.

What the attack actually uses¶

Three observations, none of which requires knowing anything about the key:

Observation	Why the cipher cannot hide it
Letter counts	It renames letters one-for-one, so it permutes the counts and never changes them
The commonest three-letter word is `the`	Word lengths survive untouched, and so does word frequency
A word's repetition pattern	`letter` is `(0,1,2,2,1,3)` before and after encryption; so is `kettle`. The shape is invariant

That last one is the engine. Once a few letters are known, every ciphertext word is a constraint: it must be an English word of that length, with that shape, agreeing with what is already fixed. A word that fits exactly one candidate has just told you more letters, and you go round again.

In Python¶

Verified output of frequency_analysis_py.py — regenerated by tools/run_examples.py, never hand-typed.

1. THE KEYSPACE IS ENORMOUS, AND IT WILL NOT MATTER
   A substitution alphabet is any ordering of 26 letters, so there are 26! keys.
   26! = 403,291,461,126,605,635,584,000,000
       = 4.033e+26   -- more keys than a brute-force search will ever see
   Nothing below tries even one of them.

2. THE CIPHERTEXT, WHICH IS ALL THE ATTACKER HAS
   zit zkgxwst vozi q lxwlzozxzogf eohitk ol fgz ziqz zit atn ol ldqss wxz ziqz zit
    sqfuxqut ligvl zikgxui oz. tctkn stzztk atthl zit egdhqfn oz qsvqnl athz. zit s
   tzztk ziqz lzqfrl ygk t voss lzoss wt zit gft ngx ltt dglz gyztf qfr oz voss lzo
   ...

3. COUNT THE LETTERS: THE CIPHER RENAMED THEM AND KEPT EVERY COUNT
   cipher letter    count    share      same rank in English
        z              49     15.2%           'e'  (12.7%)
        t              39     12.1%           't'  (9.1%)
        q              25      7.8%           'a'  (8.2%)
        o              24      7.5%           'o'  (7.5%)
        i              23      7.1%           'i'  (7.0%)
   The top letter of any English text is 'e', so 'z' is probably 'e'.
   One guess, and it is only a guess -- until something else agrees with it.

4. CRIB ONE: THE COMMONEST THREE-LETTER WORD IS 'the'
   'zit' appears 9 times
   'ngx' appears 3 times
   'fgz' appears 2 times
   So 'zit' = 'the', which fixes three letters at once:
   z -> t, i -> h, t -> e
   Now check it against section 3. The crib says 't' is 'e';
   the counts ranked 't' number 2, and put 'z' first instead.
   So the frequency guess was WRONG, and the crib has just corrected it.
   In four hundred letters the counts are noisy; a word is structural.
   That is why you never rest a break on one method.

5. CRIB TWO: A ONE-LETTER WORD IS 'a' OR 'i'
   one-letter words in the ciphertext: ['q', 't']
   ['t'] the crib already named, so they are evidence, not guesses:
   a one-letter word reading 'e' is exactly what
   the crib predicted, which is one more thing that had to line up.
   ['q'] is new. Taking it as 'a' gives a fourth letter for free.

6. NOW PROPAGATE. A WORD WHOSE SHAPE AND KNOWN LETTERS FIT EXACTLY ONE
   COMMON WORD MUST BE THAT WORD -- WHICH FIXES MORE LETTERS, AND REPEATS.
   after round 1: 17 of 26 letters known
   after round 2: 18 of 26 letters known
   after round 3: 18 of 26 letters known

7. THE MESSAGE
   the trouble with a substitution _i_her is not that the _ey is small but that the
    language shows through it. e_ery letter _ee_s the _om_any it always _e_t. the l
   etter that stands for e will still be the one you see most often and it will sti
   ll sit beside the letters that follow e in ordinary writing. you are not atta__i
   ng the _i_her at all. you are reading the sha_e of english through a _oat of _ai

8. WHAT IT COST, AND WHAT IS LEFT
   characters recovered: 386 of 403 (95.8%)
   letters of the key:   18 of 26
   still unknown:        ['c', 'k', 'p', 'v']
   Every one of those appears only in words the 200-word list does not
   contain, so nothing pinned it. A real attacker has a whole dictionary
   and never gets this far by hand -- and a person just reads the gaps.

   No key was tried. No key was guessed. The ciphertext told on itself,
   because a substitution cipher renames the letters and leaves every
   relationship between them exactly where it was.

Three things worth stopping on.

Section 4 is the honest part. The letter counts pick z as the likeliest e, and they are wrong — four hundred letters is not many, and this text is unusually full of the word the. The crib says the e is t, which the counts had at rank 2. Neither method is reliable alone; the break comes from making them argue. A page that had asserted "the two agree" would have been prettier and false, and the program checks rather than claims.

The word list is deliberately weak. It is roughly the 200 commonest English words — function words only, and not one content word of the message. That is why the run stops at 18 of 26 letters, leaving c, k, p and v unknown: each appears only in words like cipher, keeps, shape, every. A real attacker has a whole dictionary. This one gets 95.8% of the characters anyway, and the result is plainly readable:

Abridged from section 7 — the four unknown letters shown as _

   the trouble with a substitution _i_her is not that the _ey is small but that the
   language shows through it. e_ery letter _ee_s the _om_any it always _e_t.

Nothing tried a key. No brute force, no guessing, no search over the 4 × 10²⁶. The ciphertext told on itself.

Where this leaves classical cryptography¶

Every classical cipher fails to some version of this, and the history of the field up to about 1920 is the history of trying to hide the statistics without hiding the message:

Homophonic substitution — give e a dozen different symbols so the counts flatten. Beaten by pair statistics.
Polyalphabetic (Vigenère) — use several substitution alphabets in rotation, so e is not always the same symbol. Beaten by finding the period, then attacking each alphabet separately — Kasiski, 1863.
Transposition — keep the letters and move them. The counts are now exactly English, which gives it away instantly, and the anagram is the whole problem.

The pattern is that each fix hides one statistic and leaves another. The only cipher that hides all of them is the one-time pad, which achieves it by making the key as long as the message — and so trades the problem for an identical one. Getting out of that trap took until the 1970s, and it is chapter 7.

If you are coming from Python or ABAP¶

Python. collections.Counter is the whole frequency-analysis toolkit — Counter(text).most_common() is section 3. The shape function is four lines with dict.setdefault, and it is worth reading: seen.setdefault(c, len(seen)) assigns each new character the next index and returns the existing one thereafter, which is exactly a canonical relabelling. Nothing here needs a library.

ABAP. The counting is a hashed table keyed by the character (TYPE HASHED TABLE OF ... WITH UNIQUE KEY), and the string handling is where the friction is: iterating characters means DO strlen( lv ) TIMES with offset access lv+sy-index(1), since there is no character iterator. More to the point for a real system — if you find a homegrown substitution or XOR "encryption" in an ABAP program, this page is the entire argument for replacing it, and the replacement is cl_sec_sxml_writer or the platform's SSF, never a table of your own. (Not machine-checked — CI cannot run ABAP.)

Try it¶

cd 02_Classical_Ciphers/frequency_analysis/examples
python3 frequency_analysis_py.py

Then break it further, in the program:

Shorten the message. Cut MESSAGE to one sentence and run it again. Where does the break stop working, and which section fails first? (The counts go first; the cribs last.)
Change the key. Any ordering of the 26 letters works. The run should be identical in every respect except the ciphertext — which is the point of Kerckhoffs's principle, seen from the inside.
Add the content words — cipher, letter, keeps, every — to COMMON and watch it close to 26 of 26. That is what having a dictionary buys.

Without the machine: the ciphertext zit appeared 9 times in 403 characters. If you saw a three-letter word 9 times in an English text of that length, what else could it be?