Permutation Cipher — frequencies survive intact, only position is scrambled

A permutation cipher applies a fixed permutation π to the positions within each block of size n — output position i takes input position π(i) — and is the abstract core of every classical transposition cipher (columnar transposition, rail-fence); nothing is substituted, only reordered, and decryption is just applying π⁻¹.

The signal that gives it away

- Per-symbol frequency counts already match the plaintext language, letter for letter. This is the single biggest tell and the thing that separates it instantly from a substitution cipher: substitution remaps the alphabet, which shifts the frequency histogram; permutation only moves symbols around, so unigram statistics come out looking exactly like normal plaintext even though the message is unreadable. If your frequency count already "looks like English" before you've broken anything, you're looking at a permutation, not a substitution. - The message (or ciphertext) length is a clean multiple of some small integer n — that n is the block width / key length you need to recover. Divisors of the total length are your first candidates. - It also shows up as a component rather than a whole-message cipher: the "P-box" bit-shuffle stage bolted onto a toy or home-rolled block cipher alongside an S-box. Recognize the same pattern even when it's just one stage of a larger pipeline (see Block Cipher Modes of Operation — the mode carries the CTF vulnerability, not the primitive, Feistel Structure — the split-and-XOR shape that tells you which attack family applies). - Named variants you'll actually meet in challenges are this same block permutation with a specific, guessable π shape: columnar transposition (write into rows under a keyword-ordered set of columns, read out column by column) and rail-fence (zig-zag the plaintext across a fixed number of "rails," read off rail by rail). Spotting "columns," "rails," or a keyword used only to order columns (not as a key-stream) is a strong hint you're in this family, not a substitution one.

How to exploit it

1. Recover or guess the block size n. Try divisors of the message length first; for columnar/rail-fence variants the challenge usually hints at the column or rail count directly. 2. If you have a known plaintext/ciphertext pair for one block, recover π directly — no search needed: pi[j] = position in plaintext that maps to ciphertext index j. This is exact and O(n). ``python def recover_pi(pt_block, ct_block): return [pt_block.index(ct_block[j]) for j in range(len(ct_block))] ` 3. **Without known plaintext**, this is a search over the n! permutations of that block. For small n, full enumeration works: try every permutation and score the decryption with English n-gram statistics (bigram/trigram frequency counts, or a fitted quadgram log-probability model) — the correct π stands out sharply. Field-tested threshold: **past n ≈ 10, stop enumerating** (10! ≈ 3.6M and it grows factorially from there) and switch to hill-climbing instead — start from a random permutation, swap two positions, keep the swap only if the n-gram score improves, repeat until it converges. This mirrors the standard anagramming/hill-climbing approach documented for classical transposition cryptanalysis generally. 4. Decrypt by applying the recovered inverse permutation to every block: ``python def invert(pi): inv = [0]*len(pi) for i, p in enumerate(pi): inv[p] = i return inv

def apply_perm(block, pi): return ''.join(block[pi[i]] for i in range(len(pi)))

def decrypt(ct, pi): n = len(pi); inv = invert(pi) return ''.join(apply_perm(ct[i:i+n], inv) for i in range(0, len(ct), n)) ``` 5. If you're handed several ciphertexts of the same length produced under the same key/π (a "depth"), you can anagram them in parallel instead of solving π on a single message — aligning candidate rearrangements across all of them narrows the search much faster than working one message at a time. We haven't needed this in practice (single-block known-plaintext or hill-climbing on one message has always sufficed), so treat it as a documented fallback, not something we've field-verified ourselves.

What does NOT work

- Single-symbol frequency analysis, the substitution-cipher playbook (map the most frequent ciphertext symbol to 'e', build a substitution alphabet, etc.) tells you nothing here — by construction the per-symbol histogram already equals the plaintext's, so there is no substitution mapping to discover. Recognizing this early saves the hours it costs to run a full substitution attack against a cipher that was never substituting anything. - Full enumeration of all n! permutations does not scale. Our working threshold is n > 10: past that, brute force stops being a productive use of time and hill-climbing is the tool, not a longer wait on the same brute force. - Guessing the wrong block size n derails everything downstream, including hill-climbing: with the wrong n, the "blocks" being permuted aren't the real blocks, the n-gram score plateaus low, and no amount of extra hill-climbing iterations converges on readable text. If the optimizer stalls, re-check divisors of the length before suspecting your scoring function or search. - Treating it as a symbol-mapping recovery problem. Hill Cipher — a linear block cipher that known-plaintext breaks in one matrix inversion and Substitution & Shift Cipher — recovered by letter-frequency, not by algebra both require recovering a mapping over the *alphabet*; permutation cipher requires recovering a mapping over *positions* within a block. They look superficially similar (both classical, both attackable with known-plaintext or statistics) but the object you're solving for is different — don't reach for a substitution-key-recovery technique here, and don't reach for positional permutation recovery when the real problem is a symbol substitution.

Related

Hill Cipher — a linear block cipher that known-plaintext breaks in one matrix inversion Substitution & Shift Cipher — recovered by letter-frequency, not by algebra Block Cipher Modes of Operation — the mode carries the CTF vulnerability, not the primitive Feistel Structure — the split-and-XOR shape that tells you which attack family applies