Cracking Columnar Transposition Ciphers: Key-Length Detection and Column Reordering

Why This Matters

Columnar transposition ciphers were standard operational tools for military field communications through both World Wars, and variants of transposition encoding still appear in CTF challenge design as a testbed for permutation-recovery reasoning. Beyond competitions, the attack methodology — factoring message length to determine grid dimensions, then using n-gram statistics to score column orderings — transfers directly to analysing structured binary formats where a permutation has been applied to byte blocks, and to certain obfuscated malware loaders that reorder code segments before execution. Understanding permutation-recovery is also prerequisite to attacking the double transposition used in the ADFGVX cipher and similar compound schemes.

Core Concept

A columnar transposition cipher writes plaintext into a rectangular grid of W columns row by row, then reads the ciphertext column by column in a key-determined order. Formally: given plaintext of length n, grid width W (the key length), and a permutation π over {0, 1, …, W−1}, the ciphertext is produced by concatenating columns π(0), π(1), …, π(W−1) in that order. Padding characters (commonly X or null bytes) are appended if n is not a multiple of W.

The violated invariant is that transposition ciphers preserve letter frequencies exactly — every frequency-analysis statistic that depends on individual letter counts is unchanged. What they disrupt is positional co-occurrence: adjacent plaintext characters are scattered across the ciphertext. The cryptanalytic lever is therefore not single-character frequency but bigram and trigram frequency: the correct column ordering is the one that maximises the occurrence of high-frequency English bigrams (TH, HE, IN, ER, AN, RE, ON, EN) and trigrams (THE, AND, ING, ION) at column boundaries.

Attack preconditions: ciphertext-only. The attacker must know or correctly guess W — the number of columns. The key insight for recovering W is that the ciphertext length n = R × W (where R is the number of rows), or n = R × W − slack for incomplete last rows. Therefore, valid W values are the divisors of n (or of n + 1, n + 2, … up to W − 1 for short padding). This limits candidates: for a 100-character ciphertext, W ∈ {2, 4, 5, 10, 20, 25, 50}.

Anagramming columns (also called multiple anagramming) is the core attack: once W is fixed, the ciphertext is split into W columns of length R (or R±1 for ragged grids). The correct ordering of these columns is the permutation π⁻¹ that produces maximal plaintext bigram score. The search space is W! which for W ≤ 7 is at most 5040 — easily exhausted by brute force. For W ≥ 10, hill-climbing (swap two columns, accept if bigram score improves) reaches the correct permutation efficiently.

Double transposition applies columnar transposition twice with possibly different keys and grid sizes, dramatically increasing the search space. The practical attack requires first recovering the inner key width, then the outer, using the same bigram-scoring methodology but nested.

Technical Deep-Dive

from itertools import permutations
from collections import Counter

# Top English bigrams and their approximate frequencies
BIGRAMS = {
    "TH":0.0356,"HE":0.0307,"IN":0.0243,"ER":0.0200,"AN":0.0199,
    "RE":0.0185,"ON":0.0176,"EN":0.0175,"AT":0.0149,"ES":0.0145,
    "ED":0.0145,"TE":0.0135,"TI":0.0134,"OR":0.0128,"ST":0.0125,
}

def bigram_score(text: str) -> float:
    text = text.upper()
    score = 0.0
    for i in range(len(text) - 1):
        bg = text[i:i+2]
        score += BIGRAMS.get(bg, 0.0)
    return score

def split_columns(ct: str, width: int) -> list[str]:
    """Split ciphertext into columns assuming row-major write."""
    rows = [ct[i:i+width] for i in range(0, len(ct), width)]
    cols = []
    for c in range(width):
        cols.append("".join(row[c] for row in rows if c < len(row)))
    return cols

def crack_columnar(ct: str, width: int) -> tuple[str, tuple]:
    """Brute-force all column permutations; return best plaintext and its column order."""
    cols = split_columns(ct.upper().replace(" ", ""), width)
    best_score, best_pt, best_perm = -1, "", ()
    for perm in permutations(range(width)):
        candidate = ""
        row_count = max(len(cols[c]) for c in range(width))
        for r in range(row_count):
            for c in perm:
                if r < len(cols[c]):
                    candidate += cols[c][r]
        score = bigram_score(candidate)
        if score > best_score:
            best_score, best_pt, best_perm = score, candidate, perm
    return best_pt, best_perm

# For width > 7: hill-climbing
import random
def hillclimb_columnar(ct: str, width: int, iterations: int = 5000) -> tuple[str, list]:
    cols = split_columns(ct.upper().replace(" ", ""), width)
    order = list(range(width))
    random.shuffle(order)
    def score(o):
        pt = "".join(cols[o[c]][r] for r in range(len(cols[0])) for c in range(width) if r < len(cols[o[c]]))
        return bigram_score(pt)
    best = score(order)
    for _ in range(iterations):
        i, j = random.sample(range(width), 2)
        order[i], order[j] = order[j], order[i]
        s = score(order)
        if s > best:
            best = s
        else:
            order[i], order[j] = order[j], order[i]
    return order

Cryptanalysis Methodology

1. Measure ciphertext length n — Compute all divisors of n (and n−1, n−2 up to a small slack for padding). Each divisor is a candidate column width W.
2. Filter implausible widths — Widths of 1 (trivial) or n (single row, no transposition) can be eliminated. Widths > 20 are rarely used in CTF classical challenges.
3. For each candidate W, split into W columns — Rows have length R = ceil(n / W). If n mod W ≠ 0, the last R − (n mod W) columns will be one character shorter (ragged grid).
4. Brute-force permutations for W ≤ 8 — Enumerate all W! orderings with crack_columnar(). Score each candidate plaintext by bigram frequency. The correct W and permutation yields a clear English plaintext reading.
5. Use hill-climbing for W > 8 — Run hillclimb_columnar() multiple times from different random starting permutations and take the highest-scoring result. Verify manually.
6. Confirm with trigrams — After column anagramming, verify the top candidate by counting THE/AND/ING trigrams. A genuinely decrypted English text should contain these frequently.
7. Handle double transposition — If single transposition produces a high-scoring but still garbled result, suspect double transposition. Apply the columnar attack to the intermediate result treating it as a second ciphertext.

Secure Implementation Note — Transposition alone provides no computational security. Any system requiring confidentiality should use AES-256-GCM. Transposition is sometimes combined with substitution (as in historical compound ciphers), but this still does not approach modern security standards.

Common Cryptanalysis Errors

• Trying only divisors of n — Short padding (1–3 X characters) means the true width does not divide n exactly. Always try divisors of n, n−1, n−2, and n−3 to account for padding.
• Treating the ragged last row incorrectly — When n is not divisible by W, the last row is incomplete and some columns are shorter by one character. Failing to account for the ragged column breaks the bigram scoring at column boundaries.
• Using only single-character frequency analysis — Transposition preserves letter frequencies perfectly. Sorting candidate decryptions by letter frequency will rank all permutations identically. Only bigram or higher-order n-gram scoring distinguishes the correct ordering.
• Stopping after the first hill-climbing run — Hill-climbing is a local search and can get stuck in local optima. Always run multiple restarts from different initial permutations and compare.
• Confusing row read order with column read order — Some implementations write columns and read rows (the inverse). If brute-forcing columns produces no good candidate, transpose the entire approach.
• Neglecting the key alphabet ordering — Some Columnar Transposition puzzles present the key as a word (e.g., "ZEBRA") where column order is derived by alphabetical rank (B=1, E=2, R=3, A=0? wait — A=0, B=1, E=2, R=3, Z=4). Misranking repeated letters in keyword-based keys causes incorrect column orderings.

NICE Framework Alignment

Further Reading

• Military Cryptanalysis Part I: Monoalphabetic Substitution Systems — William Friedman, Aegean Park Press reprint, 1984
• Cryptanalysis of the Double Transposition Cipher — George Lasry, Praktische Kryptographie, 2016
• Cryptanalysis (Chapter 8: Transposition Ciphers) — Helen Fouché Gaines, Dover, 1956