Grill (cryptology)

The grill method (Polish: metoda rusztu),[1] in cryptology, was a method used chiefly early on, before the advent of the cyclometer, by the mathematician-cryptologists of the Polish Cipher Bureau (Biuro Szyfrów) in decrypting German Enigma machine ciphers.

The German navy started using Enigma machines in 1926; it was called Funkschlüssel C ("Radio cipher C").

Initially, there were only three rotors labeled I, II, and III, but they could be arranged in any order when placed in the machine.

The message key had to be conveyed to the recipient operator, so the Germans decided to encrypt it using the day's pre-specified daily ground setting (Grundstellung).

The grill method was an early exploitation of the doubled key to recover part of the daily settings.

Frode Weierud provides the procedure, secret settings, and results that were used in a 1930 German technical manual.

When Rejewski started his attack in 1932, he found it obvious that the first six letters were the enciphered doubled key.

If pi are the (unknown) plaintext letters of the message key and ci are the corresponding (known) ciphertext letters, then The equations can be post multiplied by D, E, and F respectively to simplify the right hand sides: The plaintext values are unknown, so those terms are just dropped to leave: The above equations describe a path through the permutations.

[18] If the code clerks were choosing random message keys, then one would not expect to see much correlation in the encrypted six characters.

[21][22] Initially, Rejewski used the knowledge of permutations A B C D E F (and a manual obtained by a French spy) to determine the rotor wirings.

This characteristic notation is equivalent to the expressions given for the 1930 permutations A and D given above by sorting the cycles so that the earliest letter is first.

The guessed message key of "EEE" producing indicator "RYZOLZ" would also determine the pairing of the 10-long cycles in permutation BE.

"; checking the cycles for CF would reveal that the indicator is consistent with message key "BBB".

Rejewski assumed that the left and middle rotors did not move while encrypting the doubled key.

For the 1930 example above, are transformed to the U V W X Y Z permutations: and then multiplied to produce the five successive products: Now the goal is to find the single structure preserving map that transforms UV to VW, VW to WX, WX to XY, and XY to YZ.

The physical grill[clarification needed] was used to determine both the rightmost rotor, its initial position, and the plugboard settings.

Rejewsky observed that S is close to the identity permutation (in the early 1930s, only 12 of 26 letters were affected by the plugboard).

The top sheet would then be slid through all possible positions of rotor N, and the cryptanalyst would look for consistency with some unknown but constant permutation Q.

Rejewski states that writing down all the possible Q "would be too laborious", so he developed the grill (grid) method.

[28] "Next, the grid is moved along the paper on which the drum connections are written until it hits upon a position where some similarities show up among the several expression Q.

This process requires considerable concentration since the similarities I mentioned do not always manifest themselves distinctly and can be very easily overlooked.

The ring setting could be anything, and that meant the Poles did not know how to position the rotors for the message body.

[32] The grill method is described by Marian Rejewski as being "manual and tedious"[2] and, like the later cryptologic bomb, as being "based... on the fact that the plug connections [in the Enigma's commutator, or "plugboard"] did not change all the letters."

That left more than half of the alphabet unaffected by permutation S. The number of steckers changed 1 August 1936; then it could be from five to eight pairs of letters were swapped.

The grill method found application as late as December 1938 in working out the wiring in two Enigma rotors newly introduced by the Germans.

(This was made possible by the fact that a Sicherheitsdienst net, while it had introduced the new drums IV and V, continued using the old system for enciphering the individual message keys.

The Poles had been able to take advantage of all messages in a net using the same machine settings to encrypt the doubled key.

Now most nets stopped doing that; instead, the operator would choose his own ground setting and send it in the clear to the recipient.

[37] The grill method would sometimes fail after the Germans increased the number of plugboard connections to ten on 1 January 1939.

Consequently, the Poles could not find the needed sixty message keys encrypted under the same ground setting.