Английская Википедия:Clock (cryptography)
Шаблон:Cipher Bureau Шаблон:EnigmaSeries In cryptography, the clock was a method devised by Polish mathematician-cryptologist Jerzy Różycki, at the Polish General Staff's Cipher Bureau, to facilitate decrypting German Enigma ciphers. The method determined the rightmost rotor in the German Enigma by exploiting the different turnover positions. For the Poles, learning the rightmost rotor reduced the rotor-order search space by a factor of 3 (the number of rotors). The British improved the method, and it allowed them to use their limited number of bombes more effectively (the British confronted 5 to 8 rotors).
Method
This method sometimes made it possible to determine which of the Enigma machine's rotors was at the far right, that is, in the position where the rotor always revolved at every depression of a key.[1] The clock method was developed by Jerzy Różycki during 1933–1935.[2]
Marian Rejewski's grill method could determine the right-hand rotor, but that involved trying each possible rotor permutation (there were three rotors at the time) at each of its 26 possible starting rotations. The grill method tests were also complicated by the plugboard settings. In contrast, the clock method involved simple tests that were unaffected by the plugboard.[3]
In the early 1930s, determining the rotor order was not a significant burden because the Germans used the same rotor order for three months at a time. The rotor order could be determined once, and then that order could be used for the next three months. On 1 February 1936, the Germans changed the rotor order every month. On 1 November 1936, the Germans changed the rotor order every day.[4]
Różycki's "clock" method was later elaborated by the British cryptologist Alan Turing at Bletchley Park in the development of a cryptological technique called "Banburismus."[5]
Background
The Cipher Bureau received German radio intercepts enciphered by the Enigma machine. With about 60 messages, the Bureau could determine Marian Rejewski's characteristic structure for the message key encoding.[6] By exploiting poor message keys, the Bureau could determine the message key encoding. At that point, the cryptanalysts may know only the message keys and their ciphertext. They may not know the other secrets of the daily key such as the plugboard setting, the ring settings, the rotor order, or the initial setting. With such little information and some luck, the Poles could still determine which rotor was the rightmost.
In the daily traffic, there might be about a dozen message pairs whose message key starts with the same two letters.[7] That means the left and middle rotors are in the same position.
There are two ways to align the ciphertexts of the message pair.[8] Both alignments are tried; one of the alignments will use an identical polyalphabetic substitution. From that, the cryptanalyst can determine the rotor turnover happened within a particular range of letters.
The rotors had different turnover positions. The British used the mnemonic "Royal Flags Wave Kings Above", which meant Rotor I turned over at R, Rotor II turned over at F, Rotor III turned over at W, Rotor IV turned over at K, and all other rotors turned over at A.
If the message pairs cooperated, the Poles could narrow the window where the turnover happens to include only one rotor. One message pair might say the turnover happened in the window B to U; that meant rotors I (R), II (F), and IV (K) were viable. A second message pair might produce a window of M to C; that meant rotors I (R), III (W), V+ (A) were viable. Only Rotor I satisfies both message pairs, so Rotor I is the right-hand rotor.
Machine settings
The Enigma cipher machine relied on the users having some shared secrets. Here are the secret daily settings from a 1930 Enigma manual:[9][10]
Daily settings (shared secret): Rotor 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)
The daily settings told the code clerks how to configure the machine so message could be exchanged. Initially, the machine had three rotors that could be arranged in any order (the wheel order or rotor order).[11] Each rotor had a ring with numbers or letters on it, and that ring could be in any of 26 positions. A plugboard interchanged additional characters.
For each message, the operator would choose a three-letter message key to encrypt the body of the message. The intention was for this key to be random, and using a random key for each message was a good security practice. The message key needed to be communicated to the recipient so the recipient could decrypt the message.
Instead of sending the message keys in the clear, the message keys would be encrypted with the Grundstellung (ground setting). In a grave procedural mistake, the Germans encrypted the message key twice. If the message key were "ABL", then the Germans would encrypt the doubled key "ABLABL" and send the result ("PKPJXI"). Sending the message key twice allowed keys garbled in transmission to be recovered, but the cryptographic mistake was encrypting the doubled key rather than sending the encrypted key twice (e.g., "PKPPKP"). The doubled key gave the Poles an attack. If there were sufficient message traffic using the same daily key (about 70 messages) and the code clerks used weak keys (such as "CCC" or "WER"), then the Poles could use Rejewski's method of characteristics to determine all the day's message keys. Surprisingly, the Poles cracked the message keys without learning the substantial secrets of the daily machine settings: the plugboard settings, the rotor order, the rotor positions, or the ring settings.
The Poles had to use other techniques to get those remaining secrets; the clock method helped determine the rotor order.
Different rotors have different turnover positions
The clock method exploited the three rotors (I, II, III) having different turnover positions. The rightmost rotor moved as each character was enciphered. At a certain position on the ring, enciphering the character would also cause the next rotor to the left to move one position (a turnover). The ring position that caused the next rotor to move was different for each rotor: rotor I advanced at the Q-R transition ("royal"); rotor II advanced at E-F ("flags"); rotor III advanced at V-W ("wave").[12] If the turnover could be detected, then the rightmost rotor might be identified.
The Poles, because they cracked the message key, knew the ring positions for each message because the ring positions were the message key.[13]
With sufficient traffic, the Poles would find message keys that started with the same two characters. Say the Poles received messages with keys "AAA" and "AAT".
Message Key AAA: BQWBOCKUQFPQDJTMFTYSRDDQEQJWLPTNMHJENUTPYULNPRTCKG Message Key AAT: SRDDQEQJWLPTNMHJENUTPYULNPRTCKGFHWQJTVQROVULGDMNMX
Index of coincidence
Using the index of coincidence on a long enough message, the Poles could determine where the rotor settings coincide. That determination is statistical, but it is also subtle. It exploits the nonuniform letter frequency in a language. Consider two sentences with their letters aligned. If letters had the same frequency, then a letter in the first sentence would match the letter in the same position of the second sentence with probability 1/26 (0.038). For natural languages, characters such as "e" are much more likely, so the chance of coincidence much higher. Here's a case where there are six coincidences in the first 28 characters (much more than the expected 1.73 matches per 26 characters):
WEHOLDTHESETRUTHSTOBESELFEVIDENT WHENINTHECOURSEOFHUMANEVENTS * *** * *
The index of coincidence also holds true if the two strings being compared are encrypted under the same polyalphabetic key; if the characters are equal, then their encryptions are also equal. Conversely, if the strings are encrypted under a different polyalphabetic key, the strings will be randomized and the index of coincidence will show only random matches (1 out of 26 characters will match).
If the two strings are long enough (say 260 characters), then the index of coincidence will give an indication whether the strings were encrypted under the same polyalphabetic key (i.e., the same rotor configuration).
Rotor position and coincidence
To emphasize the index of coincidence to an absurd level, the two example messages above consist entirely of the letter "A", so the coincidences occur at every position that shares the same rotor positions (something that would not happen for normal messages). That allows the coincidence to be starkly obvious even in a short message. In practice, long messages are needed to get a good statistical indication.
The Poles searched the daily traffic to find a pair of messages whose keys started the same two letters. Example key pairs would be ("UIB", "UIW") or ("GCE", "GCX"). The chance that first two letters of a message key match another message's key is small (Шаблон:Math), but finding such a pair in a set of messages can be likely; finding such a match is an example of the birthday problem.
The Poles wanted the first two letters to match because that meant the left and middle rotors were at identical rotations and would produce the same permutation. The Poles could also align the two messages to account for the differing third letter of the key. Given the ("AAA", "AAT") example pair from above, the Poles knew there were two possible ways the messages could be aligned so that the messages shared a common key (common rotor rotations). The two cases reflect whether the turnover (movement of the middle rotor) happens between "A" and "T" or between "T" and "A".
A T right rotor pos: ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ Message Key AAA: BQWBOCKUQFPQDJTMFTYSRDDQEQJWLPTNMHJENUTPYULNPRTCKG Message Key AAT: SRDDQEQJWLPTNMHJENUTPYULNPRTCKGFHWQJTVQROVULGDMNMX Coincidence: =============================== Conclusion: same key, so no turnover in A-T.
T A right rotor pos: TUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRS Message Key AAT: SRDDQEQJWLPTNMHJENUTPYULNPRTCKGFHWQJTVQROVULGDMNMX Message Key AAA: BQWBOCKUQFPQDJTMFTYSRDDQEQJWLPTNMHJENUTPYULNPRTCKG Coincidence: Conclusion: different key, so turnover in T-A
The middle rotor will turnover at different positions depending upon which rotor is in the rightmost (fast) position. The change points for rotors I, II, and III are indicated by 1, 2, and 3. The position of the middle rotor is given assuming the right rotor is I, II, or III.
Message Key AAA: BQWBOCKUQFPQDJTMFTYSRDDQEQJWLPTNMHJENUTPYULNPRTCKG turnover 2 1 3 2 1 3 Right ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXY Middle(I) AAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBBBBBBBBBBCCCCCCCC Middle(II) AAAAABBBBBBBBBBBBBBBBBBBBBBBBBBCCCCCCCCCCCCCCCCCCCC Middle(III) AAAAAAAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBBBBBBBBBBCCC Message Key AAT: SRDDQEQJWLPTNMHJENUTPYULNPRTCKGFHWQJTVQROVULGDMNMX turnover 3 2 1 3 Right TUVWXYZABCDEFGHIJKLMNOPQRSTUVWXY Middle(I) AAAAAAAAAAAAAAAAAAAAAAAABBBBBBBB Middle(II) AAAAAAAAAAAABBBBBBBBBBBBBBBBBBBB Middle(III) AAABBBBBBBBBBBBBBBBBBBBBBBBBBCCC
For the language-based coincidences to occur, all three rotors must be in sync. If they are not, then the plaintext would be randomly scrambled and the language properties would not show through. Looking at the region where the coincidence occurs, some observations can be made. If rotor I was on the right, then the middle rotor never matches and the index of coincidence would not indicate a coincidence. If rotor II was on the right, then the middle rotor would also never match. Rotor III shows complete agreement. Consequently, the rightmost rotor would be rotor III.
At this point, the Poles would know the right rotor is III and the rotor order is either (I, II, III) or (II, I, III). Although they knew the message key, they did not know the ring settings, so they did not know the absolute positions of the rotors. They also did not know the plugboard settings. The Poles could use other methods to learn that information, but those methods would be simplified by knowing the right rotor.
Utility
Early on, the clock method was not very important. In 1932, the Germans kept the same rotor order for three months at a time. On 1 February 1936, the Germans changed the rotor order every month. Daily wheel order changes started 1 November 1936.[14]
In October 1936, the Germans increased the number of plugs from six to eight, and that complicated the grill method. The Poles developed the cyclometer and card catalog. Although the new method was not ready for a year, it identified the entire rotor order (not just the right rotor) with little work.[15] Unfortunately, the catalog was rendered useless on 2 November 1937 when the Germans changed the reflector; a new catalog needed to be made.
On 15 September 1938, the Germans changed their procedures so that the messages on a network did not use the same Grundstellung.[16] The change would complicate the clock method because the message key was no longer easily known.
The British codebreakers extended the clock method; see Banburismus. German naval Enigma messages used the same Grundstellung, and the British codebreakers could determine the encrypted message keys. If all but the final letter of the encrypted keys matched, then they would have the same rotor positions except for the right rotor. The problem was the British were not matching plaintext message keys (as the Poles) but rather encrypted message keys, so the last letter of the encrypted message key did not have a natural "ABCDE...WXYZ" ordering but rather an arbitrary order. Rather than looking at just two offset, the British had to look at all the possible offsets and infer enough of the third wheel order before they could determine the right rotor. Correctly guessing the last rotor could save the British a lot of valuable Bombe time.
Notes
References
- Шаблон:Citation A revised and augmented translation of W kręgu enigmy, Warsaw, Książka i Wiedza, 1979, supplemented with appendices by Marian Rejewski
- Шаблон:Citation
- Шаблон:Citation
- Шаблон:Citation
- ↑ Шаблон:Harvnb
- ↑ Шаблон:Harvnb stating, "During this period Różycki worked out a procedure he called the clock method. In a great many cases it allowed us to determine which of the three drums, I, II, or III, was drum Шаблон:Mvar on a given day; that is, which drum was on the right-hand side of the machine."
- ↑ Шаблон:Harvnb stating, "We sometimes knew which drum was at position Шаблон:Mvar as a result of * clock method, but the grid method, the only one we could now apply to the SD network, sometimes failed. It failed because on January 1, 1939, the Germans again increased the number of pairs of letters modified by permutation Шаблон:Mvar from seven to ten."
- ↑ Шаблон:Harvnb
- ↑ Шаблон:Harvnb
- ↑ Шаблон:Harvnb stating, "A sufficient number of messages from the same day were needed, around 60 specimens, for the characteristic structure AD, BE, CF to be established."
- ↑ Шаблон:Harvnb stating, "Having a sufficient quantity of enciphered material at out disposal, we usually find a dozen or so pairs of messages such that in each pair the first two letters of their keys are identical, while the third letters are different."
- ↑ Шаблон:Harvnb
- ↑ Шаблон:Cite web, 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, http://people.physik.hu-berlin.de/~palloks/js/enigma/enigma-u_v20_en.html 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.
- ↑ Later there would be more than three possible rotors.
- ↑ The British used a mnemonic to remember the turnover positions: "Royal Flags Wave Kings Above".
- ↑ The ring positions are what showed in the windows; they are not the Ringstellung (ring settings).
- ↑ Шаблон:Harvnb
- ↑ Шаблон:Harvnb
- ↑ Шаблон:Harvnb
