The grill method (),Marian Rejewski, Mathematical Solution of the Enigma Cipher, trans Christopher Kasparek, Cryptologia, Vol 6, Number 1, pp 1–18 at 17, January 1982 in cryptology, was a method used chiefly early on, before the advent of the cyclometer, by the mathematician-cryptologists of the Polish Cipher Bureau in decrypting German Enigma machine ciphers. The Enigma rotor cipher machine changes plaintext characters into cipher text using a different permutation for each character, and so implements a polyalphabetic substitution cipher.
Background The German navy started using Enigma machines in 1926; it was called Funkschlüssel C ("Radio cipher C"). By 15 July 1928, the German Army (Reichswehr) had introduced their own version of the Enigma—the Enigma G; a revised Enigma I (with plugboard) appeared in June 1930. The Enigma I used by the German military in the 1930s was a 3-rotor machine. Initially, there were only three rotors labelled I, II, and III, but they could be arranged in any order when placed in the machine. Polish cryptologist Marian Rejewski identified the rotor permutations by , , and ; the encipherment produced by the rotors altered as each character was encrypted. The rightmost permutation () changed with each character. In addition, there was a plugboard that did some additional scrambling.
The number of possible different rotor wirings is:
The number of possible different reflector wirings is: Take the number of ways to arrange 26 distinct letters (26!) and pair the selected letters. The paired letters interchange, so divide by 213 to account for the two orderings of each pair. The order the pairs are enumerated does not matter, so divide by the number of ways to order the 13 pairs (13!).
A perhaps more intuitive way of arriving at this figure is to consider that 1 letter can be wired to any of 25 others, leaving 24 further letters to connect. The next chosen letter can connect to any of 23 others, leaving 22 further letters to connect. Repeating this process yields:
The number of possible different plugboard wirings (for six cables) is: Take the number of ways to arrange 26 distinct letters and pair off the first 12 letters; divide by 26 because the pairs can be swapped (AB is same as BA), divide by 6! because the order of the pairs does not matter, and divide by 14! because the order of the trailing 14 characters does not matter.
To encrypt or decrypt, the operator made the following machine key settings: the rotor order (Walzenlage) the ring settings (Ringstellung) the plugboard connections (Steckerverbindung) an initial rotor position (Grundstellung)
In the early 1930s, the Germans distributed a secret monthly list of all the daily machine settings. The Germans knew that it would be foolish to encrypt the day's traffic using the same key, so each message had its own "message key". This message key was the sender-chosen initial rotor positions (e.g., YEK). 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 recipient would use the daily machine settings for all messages. He would set the Enigma's initial rotor position to the ground setting and decrypt the message key. The recipient would then set the initial rotor position to the message key and decrypt the body of the message.
The Enigma was used with radio communications, so letters were occasionally corrupted during transmission or reception. If the recipient did not have the correct message key, then the recipient could not decipher the message. The Germans decided to send the three-letter message key twice to guard against transmission errors. Instead of encrypting the message key "YEK" once and sending the encrypted key twice, the Germans doubled the message key to "YEKYEK" ("doubled key"), encrypted the doubled key with the ground setting, and sent the encrypted doubled key. The recipient could then recognize a garbled message key and still decrypt the message. For example, if the recipient received and decrypted the doubled key as "YEKYEN", then the recipient could try both message keys "YEK" and "YEN"; one would produce the desired message and the other would produce gibberish.
The encrypted doubled key was a huge cryptographic mistake because it allowed cryptanalysts to know two encipherments of the same letter, three places apart, for each of the three letters. The Polish codebreakers exploited this mistake in many ways. Marian Rejewski used the doubled key and some known daily keys obtained by a spy, to determine the wiring of the three rotors and the reflector. In addition, code clerks often did not choose secure random keys, but instead chose weak keys such as "AAA", "ABC", and "SSS". The Poles later used the doubled weak keys to find the unknown daily keys. The grill method was an early exploitation of the doubled key to recover part of the daily settings. The cyclometer and the bomba kryptologiczna were later exploitations of the doubled key.
Example message
Frode Weierud provides the procedure, secret settings, and results that were used in a 1930 German technical manual., citing 1930 "Schlüsselanleitung zur Chiffriermachine Enigma I" ["Directions for use of Keys on the Cypher Machine 'Enigma I'"]Can be checked with a simulator. For example, Select Enigma I, choose reflector A (at the time, the Germans only had one reflector), set the wheel order (II, I, III), set the rings (24, 13, 22), set the plugs (AM, FI, NV, PS, TU, WZ), activate the plugboard, and set the wheels to the ground setting ("FOL"). Typing ABLABL in the input box should produce PKPJXI as the output.
Daily settings (shared secret): Wheel Order : II I III Ringstellung : 24 13 22 (XMV) Reflector : A Plugboard : A-M, F-I, N-V, P-S, T-U, W-Z Grundstellung: 06 15 12 (FOL)
Operator chosen message key : ABL Enciphered starting with FOL: PKPJXI
Message to send and resulting 5-letter groups of clear text: Feindliche Infanteriekolonne beobachtet. Anfang Südausgang Bärwalde. Ende 3 km ostwärts Neustadt.
FEIND LIQEI NFANT ERIEK OLONN EBEOB AQTET XANFA NGSUE DAUSG ANGBA ERWAL DEXEN DEDRE IKMOS TWAER TSNEU STADT
Resulting message: 1035 – 90 – 341 – PKPJX IGCDS EAHUG WTQGR KVLFG XUCAL XVYMI GMMNM FDXTG NVHVR MMEVO UYFZS LRHDR RXFJW CFHUH MUNZE FRDIS IKBGP MYVXU Z
The first line of the message is not encrypted. The "1035" is the time, "90" is number of characters encrypted under the message key, and "341" is a system indicator that tells the recipient how the message was encrypted (i.e., using Enigma with a certain daily key). The first six letters in the body ("PKPJXI") are the doubled key ("ABLABL") encrypted using the daily key settings and starting the encryption at the ground setting/Grundstellung "FOL". The recipient would decipher the first six letters to recover the message key ("ABL"); he would then set the machine's rotors to "ABL" and decipher the remaining 90 characters. Notice that the Enigma does not have numerals, punctuation, or umlauts. Numbers were spelled out. Most spaces were ignored; an "X" was used for a period. Umlauts used their alternative spelling with a trailing "e". Some abbreviations were used: a "Q" was used for "CH".
When Rejewski started his attack in 1932, he found it obvious that the first six letters were the enciphered doubled key. stating, "The fact that the first six letters of each message formed its three-letter key, twice enciphered, was obvious, and I will not dwell on the matter."
Key encryption The daily key settings and ground setting will permute the message key characters in different ways. That can be shown by encrypting six of the same letter for all 26 letters: AAAAAA -> PUUJJN BBBBBB -> TKYWXV CCCCCC -> KZMVVY DDDDDD -> XMSRQK EEEEEE -> RYZOLZ FFFFFF -> ZXNSTU GGGGGG -> QRQUNT HHHHHH -> SSWYYS IIIIII -> WNOZPL JJJJJJ -> MQVAAX KKKKKK -> CBTTSD LLLLLL -> OWPQEI MMMMMM -> JDCXUO NNNNNN -> YIFPGA OOOOOO -> LPIEZM PPPPPP -> AOLNIW QQQQQQ -> GJGLDR RRRRRR -> EGXDWQ SSSSSS -> HHDFKH TTTTTT -> BVKKFG UUUUUU -> VAAGMF VVVVVV -> UTJCCB WWWWWW -> ILHBRP XXXXXX -> DFRMBJ YYYYYY -> NEBHHC ZZZZZZ -> FCEIOE From this information, the permutations for each of the six message keys can be found. Label each permutation A B C D E F. These permutations are secret: the enemy should not know them.
Notice the permutations are products of 13 disjoint transpositions. For the A permutation, it not only changes "A" into "P" but it also changes "P" into "A". That allows the machine to both encrypt and decrypt messages.
Augustin-Louis Cauchy introduced two-line notation in 1815 and cycle notation in 1844. at page 129 implies both notations used in 1815.
Rejewski's characteristic Rejewski made a discovery. Without knowing the plugboard settings, the rotor positions, the ring settings, or the ground setting, he could solve for all the daily message keys. All he needed were enough messages and some code clerks using non-random message keys.
The message key is three characters long, so the doubled key is six characters long. Rejewski labeled the permutations for the successive message-key characters A B C D E F. He did not know what those permutations were, but he did know that A and D permutations encrypted the same message key letter, that B and E encrypted the same letter, and that C and F encrypted the same letter. If are the (unknown) plaintext letters of the message key and 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. If is passed through the inverse of , then it produces . If that character passes through , then the result is .
Rejewski also knew that the Enigma permutations were self inverses: Enigma encryption and decryption were identical. That means that where is the identity permutation. Consequently, . Thus:
The above equations show the relationship between the doubled key characters. Although Rejewski did not know the individual permutations A B C D E F, a single message told him how specific characters were permuted by the composed permutations AD, BE, and CF.
From many messages, Rejewski could determine the composed permutations completely. In practice, about 60 messages were needed to determine the permutations.
Rejewski recorded the three permutations with a cyclic notation he called the characteristic. gives an example:
In this notation, the first cycle of permutation would map d to v, v to p, p to f, ..., y to o, and o would wrap around to d.
Marks and Weierud give an example from Alan Turing that shows these cycles can be completed when some information is incomplete. (page 3 in PDF)
Furthermore, Enigma permutations were simple transpositions, which meant that each permutation A B C D E F only transposed pairs of characters. Those character pairs had to come from different cycles of the same length. Moreover, any one pairing between two cycles determined all the other pairs in those cycles. Consequently, permutations A and D both had to transpose a and s because (a) and (s) are the only cycles of length one and there is only one way to pair them. There are two ways to match (bc) and (rw) because b must pair with either r or w. Similarly, there are ten ways to match the remaining ten-character cycles. In other words, Rejewski now knew that there were only twenty possibilities for the permutations A and D. Similarly, there were 27 candidates for B and E, and 13 candidates for C and F.
Weak keys