Clock (cryptography)

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.

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]

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."[2]

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:[3][4]

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).[5] 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.

Enigma rotors. Turnover notch can be seen in left rotor near 13. Right rotor marking near center shows it is rotor II.

Different rotors have different turnover positions

Main article: Enigma rotor details

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").[6] 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 daily key.[7]

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's based on some characters in a language (such as "e") being much more common than others. If letters were chosen randomly and uniformly, then two letters would match with probability 1/26 (0.038). For natural languages, the prevalence of characters such as "e" make 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 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. The messages can be shifted to find the alignment:

Message Key AAA: BQWBOCKUQFPQDJTMFTYSRDDQEQJWLPTNMHJENUTPYULNPRTCKG
Message Key AAT:                    SRDDQEQJWLPTNMHJENUTPYULNPRTCKGFHWQJTVQROVULGDMNMX

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
                     2           1    3        2           1    3
Right           ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXY
Middle(I)       AAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBBBBBBBBBBCCCCCCCC
Middle(II)      AAAAABBBBBBBBBBBBBBBBBBBBBBBBBBCCCCCCCCCCCCCCCCCCCC
Middle(III)     AAAAAAAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBBBBBBBBBBCCC

Message Key AAT:                    SRDDQEQJWLPTNMHJENUTPYULNPRTCKGFHWQJTVQROVULGDMNMX
                                      3        2           1    3
Right                              TUVWXYZABCDEFGHIJKLMNOPQRSTUVWXY
Middle(I)                          AAAAAAAAAAAAAAAAAAAAAAAABBBBBBBB
Middle(II)                         AAAAAAAAAAAABBBBBBBBBBBBBBBBBBBB
Middle(III)                        AAABBBBBBBBBBBBBBBBBBBBBBBBBBCCC

For the coincidence 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 did not start until 1 November 1936.[8]

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 with little work.[9] Unfortunately, the catalog was rendered useless on 2 November 1937 when the Germans changed the reflector.

On 15 September 1938, the Germans changed their procedures so that the messages on a network did not use the same Grundstellung.[10] The change would complicate the clock method because the last letter of the message key was no longer known. The British codebreakers extended the clock method; see Banburismus. Correctly guessing the last rotor could save the British a lot of valuable Bombe time.

Notes

  1. ↑ Rejewski 1984, p. 290
  2. ↑ Good 1993, p. 155
  3. ↑ http://cryptocellar.web.cern.ch/cryptocellar/Enigma/EMsg1930.html, citing 1930 "Schlüsselanleitung zur Chiffriermachine Enigma I" ["Directions for use of Keys on the Cypher Machine 'Enigma I'"]
  4. ↑ 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.
  5. ↑ Later there would be more than three possible rotors.
  6. ↑ The British used a mnemonic to remember the turnover positions: "Royal Flags Wave Kings Above".
  7. ↑ The ring positions are what showed in the windows; they are not the Ringstellung (ring settings).
  8. ↑ Rejewski 1981, p. 223
  9. ↑ Rejewski 1981, pp. 224–225
  10. ↑ Rejewski 1981, p. 225

References

This article is issued from Wikipedia - version of the Saturday, March 19, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.