Cryptology Cryptanalytic Approaches to Rotor Machines

a7Hzq .#5r< kÜ\as TâÆK$ ûj(Ö2 ñw%h: Úk{4R f~`z8 ¤˜Æ+Ô „&¢Dø

Cryptanalyzing rotor machines is a complex task and essentially depends on the details of the machine. Here we depict only some general ideas:

• Superimposition
• Meet-in-the-middle
• Isomorphs

Superimposition

The method of superimposition applies when the cryptanalyst has several ciphertexts that are encrypted with the same key. He aligns the texts below each other, and gets monoalphabetically encrypted columns.

In practice the operator tries to avoid this by using different keys with each message, that is by changing the initial position of the rotors. But even then—if the traffic is high—there will occur sections in different messages that are encrypted with identical rotor positions. The coincidence index will find these sections reliably.

This approach works without known plaintext and without knowledge of the encryption algorithm. Here is an example.

Known Plaintext Attack: Isomorphs

Assume that the set of rotors is known but not their actual choice. Assume further that we know or guess a piece of plaintext, say a probable word. An essential step is finding text chunks in intermediate encryption results with identical numerical patterns, also called isomorphs. Therefore this attack is known as method of isomorphs. More generally looking at an intermediate step of an encryption algorithm from both sides, is called meet-in-the-middle.

Identification of a Fast Output Rotor

Assume that the last rotor at the output side steps by one position with each letter, and that the other rotors move infrequently. If for a section of plaintext only the last rotor moves, then for this section all the other rotors together effect only a monoalphabetic substitution. We identify a fast rotor by simple pattern comparisions: Try all possible (single) rotors in all possible step positions and decrypt the ciphertext into an intermediate text. Check if the intermediate text shows the same numerical pattern as the known plaintext.

Here is an example.

Identification of a Fast Input Rotor

Known plaintext also allows the identification of the fast rotor for a reverse odometer control where the left rotor is the fast one. In this case we consider the situation of the following graphic.

Here the intermediate text b (between rotors 1 and 2) is a monoalphabetic image of the ciphertext c.

Therefore the cryptanalyst tries all rotors with all initial positions until she finds identical numerical patterns for b and c.

Continuation of the Attack

As soon as the fast rotor is identified we can strip off its effect like a superencryption. In this way the intermediate ciphertext extends to a ciphertext that is the result of encrypting the plaintext by a much simpler machine.

If for example the rotors move like an odometer, and if the ciphertext is long enough, then in a similar way we can identify the next rotor and strip off its effect.

One also might first try to find the locations were the second rotor moves.

Ciphertext-Only Attack: Coincidence Index

The identification of a fast output rotor also works in a weaker form even when the attacker has no known plaintext. Instead of looking for isomorphs she calculates coincidence indices. She tries all possible (single) rotors in all possible step positions and checks the intermediate texts for monoalphabetic encryption with help of the coincidence index.

• If the rotor or the position is incorrect, the intermediate text will look like random text.
• If the choice is the correct one, the coincidence index of the intermediate text will resemble the typical coincidence index of the plaintext language.

Thus by a reduced exhaustion the cryptanalyst might identify the fast rotor and its position.

Here is an example.

More details on this method are in the mathematical part of this section. Note that the power of this test is quite low.

Remarks

1. In principle the method works at each position of the text. Therefore the very beginning of the text is worth a try.
2. In the unfavourable case one of the other rotors moved during the encryption of the plaintext section. Then the intermediate ciphertext consists of two different monoalphabetic pieces. With a bit of luck this also leads to a somewhat conspicuous coincidence index.