Attacking Transposition Ciphers

In this entry, I'll talk about brute-force attacks against Transposition ciphers. A brute-force attack is one where the attacker simply tries all the possible combinations (or keys) to decipher a message. Generally, brute-force attacks are impractical as they do not use any analysis to round down unlikely candidate keys or combinations.

In order for an attacker to decipher this message, they must first guess the size of the groupings (reasonable values might be from 4 to 10). Next, they have to guess the order in which the letters were scrambled. This type of scrambling described above is called a permutation. We can figure out how many different permutations there are by noting the following:
1. For the first letter position you pick, you get to select from all positions (so in our example, there are 7 possible choices.)
2. For the next letter position you pick, you have one less than the whole group (so 6 choices)
3. This continues until your last pick which is limited to 1 character position (whatever position is left).
Thinking about this, for 7 characters, the number of permutations is:
7 * 6 * 5 * 4 * 3 * 2 * 1 = 5040.

So even if the attacker knows the letters are in groups of 7 characters, they have to try as many as 5040 orderings to unscramble them. On the average, we can expect to have to try about half that many combinations or about 2520.
But again, the messages creator could have selected a different goruping size. That means that we would have the following numbers of permutations to try if we were pretty sure the group size was between 4 and 10:

4 - 24 permutations
5 - 120 permutations
6 - 720 permutations
7 - 5040 permutations
8 - 40320 permutations
9 - 362880 permutations
10 - 3628800 permutations

You can see how quickly the number of permutations groups each time we add 1 to the size of the grouping. The work of cracking a cipher like this by hand becomes intractable very quickly. With the help of software that could generate permutations quickly, you are left with a long set of character strings to read. So brute-force methods are still difficult to perform. The best brute-force method would involve having software generate the permutations and then look for common patterns from the english language. The software can 'score' each string according to how many patterns match. Then it can present the most likely candidates to a human cryptanalyst to examine in detail.