← Back to all writing
Cryptography

Periodicity Is a Vulnerability: Statistical Cryptanalysis of Repeating-Key Ciphers

2026-07-22 · Saketh Motakatla

You have a blob of ciphertext. No key. No algorithm name. Nothing but the bytes.

Most people's instinct is brute force. That instinct is wrong, and understanding why is the entry point to real cryptanalysis.

Brute force treats the keyspace as opaque: try everything, hope the space is small. Statistical cryptanalysis treats the ciphertext as the thing worth examining, and asks a different question. What structure did the encryption fail to destroy?

Encryption is a promise that the output looks like noise. Every practical break in the history of the field comes from that promise failing somewhere: a distribution that isn't quite flat, a period that repeats, a timing difference measured in nanoseconds.

This post walks a complete attack against a repeating-key cipher. The vehicle is Vigenère, broken since Kasiski published in 1863. The method is not historical. The three-stage pattern (detect hidden periodicity, decompose into independent subproblems, score candidates against a reference distribution) is the same shape as breaking repeating-key XOR in a malware config blob, detecting AES-ECB from block repetition, or exploiting nonce reuse in a stream cipher.

The cipher is a toy. The reasoning is not.

Code: github.com/mlsaketh/classical-crypto-attacks

Quantifying "This Looks Like English"

Caesar shifts every letter by the same amount, c = (m + k) mod 26. Twenty-six keys, breakable by hand. It matters here only because it's the atomic unit Vigenère is built from.

The naive break decrypts under all 26 keys and lets a human pick the English one. The human is doing something mechanical, and that recognition is what we need to turn into a number.

English letter frequencies are violently non-uniform. E lands around 12.7%, Z around 0.07%, a factor of 180 between them. Random noise sits flat at 1/26. So measure how far a candidate's distribution sits from English, using Pearson's chi-squared statistic:

chi2 = sum over letters of (observed - expected)^2 / expected

Three decisions are embedded in that formula.

The difference is squared so overshoot and undershoot both register as error rather than cancelling.

The result is divided by the expected count. This is the part people skip, and the part that makes it work. Being off by 5 occurrences of E (expected ~13 per 100 letters) is noise. Being off by 5 on Z (expected 0.07) is a screaming anomaly. Dividing normalises each letter's error against its own scale.

Lower is better. The statistic measures badness of fit. The winner is the minimum.

def chi_squared_score(text: str) -> float:
    counts = letter_counts(text)
    N = sum(counts.values())
    if N == 0:
        return float('inf')

    total = 0.0
    for letter, freq in ENGLISH_FREQ.items():
        observed = counts.get(letter, 0)
        expected = freq * N
        total += (observed - expected) ** 2 / expected
    return total

The caveat matters more than the code. Chi-squared needs sample size. Against KHOOR it confidently returned key 14 and the plaintext WTAAD, a wrong answer the scorer was perfectly happy with. Not a bug. Five letters is not enough evidence.

Why Vigenère Defeats That

Vigenère cycles through several shifts instead of one. The key is a word, each key letter supplies a Caesar shift, and the key repeats.

c[i] = (m[i] + k[i mod L]) mod 26

plaintext:   H   E   L   L   O
key:         L   E   M   O   N
shift:      11   4  12  14  13
ciphertext:  S   I   X   Z   B

The consequential detail is in those two Ls. The first becomes X, the second becomes Z. The same plaintext letter maps to different ciphertext letters depending on position.

In Caesar, E's entire 12.7% mass lands on one ciphertext letter, so the distribution keeps its silhouette and merely slides. In Vigenère with a length-5 key, that mass splits five ways, and every other letter is doing the same thing simultaneously. The English spike doesn't move. It dissolves. In my test run, 589 letters of English scored 0.0662 on the statistic below; the same text under a length-5 key dropped to 0.0398, indistinguishable from noise.

The Structural Flaw

The weakness isn't in the arithmetic. It's in the repetition.

position:  0   1   2   3   4   5   6   7   8   9  10  11
key:       L   E   M   O   N   L   E   M   O   N   L   E

Positions 0, 5, 10, 15 all receive the identical shift. The ciphertext is not one cipher. It is five independent Caesar ciphers interleaved, and Caesar is a solved problem.

Slice by stride L and every slice becomes a pure Caesar cipher of English. The only thing standing between an attacker and full recovery is knowing L.

Stage One: Recovering the Key Length

Draw two letters at random from a text. What's the probability they're identical? In peaked text, high. In flat text, low. That probability is the Index of Coincidence, a direct measurement of distributional peakedness.

IC = sum of n[i] * (n[i] - 1)  /  N * (N - 1)

Pure combinatorics: to draw a matching pair of letter i, pick one of its n occurrences then another of the remaining n-1. Sum across the alphabet, divide by total ordered pairs. English prose sits near 0.067, uniform random near 0.038.

def index_of_coincidence(text: str) -> float:
    counts = letter_counts(text)
    N = sum(counts.values())
    if N < 2:
        return 0.0

    numerator = sum(n * (n - 1) for n in counts.values())
    return numerator / (N * (N - 1))

Here is the pivot, and it's the most important observation in the post.

A Caesar shift does not change the Index of Coincidence. Shifting relabels which symbol carries which frequency but alters no counts. The spike is exactly as tall, just sitting on a different letter. IC is computed from counts alone, so it is blind to the shift.

Which gives a test requiring no knowledge of the key:

Sweep L, slice, average the column ICs, read off the spike:

L avg IC
3 0.043 flat
4 0.040 flat
5 0.066 spike
6 0.042 flat
10 0.067 harmonic

Multiples of the true length also produce internally consistent columns, so they spike too. Take the smallest, not the largest. This is a real implementation trap: selecting by maximum IC lets noise push a harmonic above the fundamental, and you recover LEMONLEMON. Threshold on the first L clearing 0.06 instead.

Stage Two: Recovering the Key

With L known the hard part is over. Each column is a standalone Caesar cipher, and chi-squared solves those.

ciphertext --+-- col 0 --> chi2 --> shift 11 --> L --+
             +-- col 1 --> chi2 --> shift  4 --> E --+
             +-- col 2 --> chi2 --> shift 12 --> M --+--> "LEMON"
             +-- col 3 --> chi2 --> shift 14 --> O --+
             +-- col 4 --> chi2 --> shift 13 --> N --+

def recover_key(ciphertext: str, L: int) -> str:
    key = ''
    for offset in range(L):
        shift = break_column(get_column(ciphertext, offset, L))
        key += chr(shift + ord('A'))
    return key

Eleven million keys reduced to five independent 26-way decisions. Not one clever insight. A decomposition.

Where the Attack Strains

Against 300 characters encrypted with LEMON, the IC sweep nailed the length at 5 and the key came back as LEFON. One letter wrong.

Nothing was broken. Three hundred characters across five columns leaves ~60 per column, and chi-squared on 60 samples is thin. The correct shift and a competitor scored within a few points, and the competitor won on noise. Feed the same code 589 characters and it returns LEMON exactly.

This is the most operationally useful lesson in the exercise, and it has nothing to do with Vigenère.

A broken cipher still requires sufficient ciphertext to break.

Every statistical attack has a data threshold below which it degrades to guessing. Linear and differential cryptanalysis are quoted in required plaintext-ciphertext pairs. Padding oracle attacks in oracle queries. Nonce-reuse attacks need enough reuse. "Theoretically broken" and "broken with the data I have" are different claims, and conflating them produces bad attacks and bad risk assessments.

Instrument it rather than trusting it. Return ranked candidates per column instead of a single argmin and inspect the margin. A near-tie is the algorithm telling you it lacks evidence.

The Part That Transfers

Detect hidden periodicity. IC exposed a key length nobody disclosed. The general form is that the ciphertext has structure it shouldn't, which is precisely how you detect AES-ECB, where identical plaintext blocks yield identical ciphertext blocks and the penguin becomes visible.

Decompose into independent subproblems. Repeating-key XOR, the byte-level descendant of Vigenère and a common find in malware config blobs, obfuscated firmware strings, and lazy "encrypted" mobile app fields, breaks under the identical decomposition. Hamming distance substitutes for IC, single-byte XOR scoring for the per-column Caesar break.

Score candidates against a reference distribution. Chi-squared answered "is this plaintext?" without a human reading it. That primitive sits underneath every automated cryptanalytic search, and its descendants show up in packer detection via entropy thresholds and in every distinguisher separating real output from random.

The principle underneath all three: encryption promises the output looks random, and every break is a place where that promise leaked. When you approach unknown ciphertext, the productive question is never "how do I try every key." It's "what did this fail to destroy?"

Vigenère fails because the key repeats. Extend the key to the message length, never reuse it, and you have a one-time pad, which is information-theoretically unbreakable. Every practical cipher since is an engineering compromise on that axis: how do you get one-time-pad-like output from a key short enough to manage? Stream ciphers, block modes, nonces, IVs, key derivation, all of it is machinery for not repeating yourself.

You don't build intuition for why nonce reuse is catastrophic by reading that nonce reuse is catastrophic. You build it by breaking something with your own hands, then recognising the same silhouette in something modern.

Code

Four standalone scripts, standard library only, no imports between them.

File Contents
caesar_encrypt.py Caesar encryption
caesar_break.py Frequency analysis, chi-squared scoring, automated break, ranked candidates
vigenere_encrypt.py Vigenère encryption
vigenere_break.py Index of coincidence, key-length sweep, per-column attack, full break

github.com/mlsaketh/classical-crypto-attacks

Encrypt something, hand the ciphertext to the breaker, watch it recover a key it was never given. Then hand it 100 characters and watch it fail. That failure is the more instructive run.

References