Semi-automatic analysis, ADFGVX encryption algorithm (Menu Analysis \ Symmetric Encryption (classic) \ Ciphertext-Only)

For the ADFGVX encoding method, CrypTool provides a dialog window for supporting the manual analysis (dialog Semiautomatic Analysis of the ADFGVX Cipher).

Since the substitution step of ADFGVX is based solely on the matrix which should be random, a reliable and fast automatic analysis of the cipher is not possible. While a frequency analysis can determine the letters that stand out clearly from the histogram in long enough texts, the remaining letters cannot be recognized with a high enough certainty to guarantee a correct automatic allocation.

With single messages, the analysis of the transposition step is only possible by brute force. All possible transposition keys must be applied to the ciphertext, unless the key length can be restricted (due to the condition that the password must not contain double characters in order to permit a definite alphabetical sequence and the historical restriction to the letters 'A' to 'Z', the maximum password length is 26 characters).

The size of the key space makes a problem of the transposition analysis: Since the brute force search must examine every possible combination of letters, the analysis on average covers a range of

(c:= maximum password length)

combinations, if the password length cannot be further restricted (from top or bottom).

An example:
A maximal password length of only 5 characters permits a manageable number of 1! + 2! + 3! + 4! + 5! = 153 possible combinations.
The extension of the password length by only one character already enlarges the range of combinations to 153 + 6! = 153 + 720 = 873.
A brute force analysis of the complete range of a 26 character password and thus 419.450.149.241.406.189.412.940.313 (ca. 4,2 *10^26) possible combinations should hence be avoided.

As a result of the retransposition, the ADFGVX bigrams from the substitution stage are now standing in order and can be analysed by counting their relative frequency. If the values concur roughly with a suitable reference table, the transposition password is a possible solution. Although this task can easily be automatted, there remains another problem that requires a decision by the user:
If the transposition password consists of an even number of letters, each column exclusively holds either the first or the second letter of an ADFGVX bigram. Thus it is possible to shift a pair of two matching columns without changing the bigram-frequencies of the ciphertext. So the following three transposition tables are completely identical in having the same bigram-frequencies, although there is only one correct solution:
 

M A T R I X
A F V D D X
D G X G A A
F A V X F D

 

T R M A I X
V D A F D X
X G D G A A
V X F A F D

 

M A I X T R
A F D X V D
D G A A X G
F A F D V X



One solution to this problem would be an analysis of plaintext-bigrams: each bigram of plaintext is represented by four letters of ADFGVX-ciphertext, making it possible to mark four columns as related. However, this requires a resolution of the substitution stage which cannot be accomplished without solving the transposition. In addition, the columns could still be exchanged in groups of four.

Through these considerations, it becomes apparent that the ADFGVX cascade cipher is very effective. The sole method of deciphering a single ADFGVX message is to examine all possible transposition keys for correctness by analysing the substitution step of the cipher for each possible transposition key of the message.