# How to break a Quagmire 3 cipher?

What would be a good way to go about attacking a Quagmire 3 cipher?

I understand that it is polyalphabetic with a key and an indicator. I have started by taking the cipher text, taking every n-th letter and putting that in a string, computing the index of coincidence for the n strings I get and then averaging that. I would assume that whatever n value corresponds with the closest average index of coincident to English (0.066) would be the number of alphabets, i.e. the length of the indicator.

Where do I go from there? Or is my approach incorrect?

• Do you have a specification? If I understand it correctly it's just encrypting with vigenere and then encrypting with substitution cipher? – CodesInChaos May 11 '16 at 10:20

All the Quagmire ciphers (see e.g. here for definitions) are combinations of a Vigenère shift cipher and a keyword-based simple substitution cipher, where the substitution cipher is used to scramble the alphabet before and/or after the Vigenère encryption.

In particular, the Quagmire III cipher in effect scrambles the plaintext alphabet before doing a normal Vigènere encryption (with a key that is derived from the "indicator" by also scrambling its alphabet the same way), and then unscrambles the alphabet of the resulting ciphertext. Equivalently, we may view it as just a Vigenère cipher, but using a non-standard (and typically secret) mapping from letters to numbers instead of the usual A=0, B=1, C=2, etc.

This has a couple of notable consequences:

• All the usual methods of determining the key length for a Vigenère cipher, like Kasiski examination or calculating the index of coincidence, will work just as well for a Quagmire cipher, at least as long as they make no explicit assumptions about which letters are most common in the plaintext.

• Once you've determined the length $$k$$ of the repeating Vigenère key (a.k.a. "indicator"), you can simply take every $$k$$-th letter of the ciphertext and apply frequency analysis just as if you were attacking a simple substitution cipher (since that's effectively what you have at this point).

Furthermore, the $$k$$ different substitution alphabets corresponding to the $$k$$ different indicator letters are related in a particular way: mathematically, they are all powers of the same cyclic permutation (in the strict sense; no fixed points allowed) of the alphabet. (This is also true of the basic Vigenère cipher; in that case, the underlying cycle is simply the one-letter shift A → B → C → ... → X → Y → Z → A.) Thus, once you manage to solve one of the $$k$$ substitution ciphers, the rest should be significantly easier (and you can also compare the solutions to make sure they are correct).

Also, the cycle structure of a power of a cyclic permutation is itself somewhat restricted: it cannot have fixed points (unless it is the identity permutation) and all of its cycles must have the same length that divides the size of the alphabet. In particular, for a 26-letter alphabet, the power of a cyclic permutation always consists of either one 26-cycle (making it also cyclic), two 13-cycles, 13 two-cycles or 26 fixed points (in which case it is the identity). Of these, the first two possibilities (one 26-cycle or two 13-cycles) are by far the most likely, so if you see anything else (especially if it's not one of the remaining possibilities above), you'll know that you've made a mistake somewhere.

Given sufficient ciphertext, breaking this cipher via the methods described above shouldn't be particularly difficult. Indeed, determining the key length using the index of coincidence method doesn't even need all that much ciphertext; I tried it on the Kryptos K1 and K2 ciphertexts (using a Wilson score interval correction to reduce sampling noise for large key lengths) and it pretty clearly identified the key length of K1 (63 letters) as 5, 10 or 20 letters (actual keyword: PALIMPSEST, 10 letters) and the key length of K2 (369 letters) as most likely 8 letters (actual keyword: ABSCISSA). However, with a limited amount of ciphertext and a long key, solving the individual substitutions may require a considerable amount of trial and error.

Also, it's worth noting that this method does not automatically yield the keywords used to encrypt the text. Indeed, it cannot, since the Quagmire ciphers have many equivalent keys. However, simply considering all the possible solutions for the substitution alphabet and the shift amounts may turn up one that arises from a particularly natural pair of keywords.