Cryptanalysis of Hagelin machine pin wheels

Cryptologia, Oct 2002 by Sullivan, Geoff

ABSTRACT: A ciphertext-only attack on the pin wheel patterns of the Hagelin CD-57 Cryptographer is described. The method is also applicable to some earlier Hagelin machines of the pin wheel and lug variety, for example the M-209. The only prior knowledge required is the setting of the lugs and the plain text frequency for the language of the message. The method is extended to finding the lug and pin settings of the M-209 using a longer message.

KEYWORDS: Hagelin Cryptographer, CD-57, M-209, Hillclimbing, Ciphertext-Only cryptanalysis, Genetic algorithm.

INTRODUCTION

During winter 1999 - spring 2000, I took part in The Cipher Challenge) in Simon Singh's book The Code Book . Many of those who attempted this cipher challenge used Jim Gillogly's method of `Shotgun Hillclimbing' applied to cryptanalysis of classical ciphers for the solution of one or more of the ciphers. The procedure for attacking a classical cipher is described by Gillogly as follows:

2. Generate and score each "adjacent" postion.

4. Go to 2 if there was any improvement.

Manually stop the process when it looks like natural language.

The 'Shotgun' part is the random restart. Hillclimbing is a well known search technique usually going under the name Stochastic Iterated Hill Climbing (SIHC) or Multistart Hill Climbing (MHC). This has an advantage over other genetic algorithms in that the stochastic variant will cover a much larger area to find the global optimum peak which can be the only true solution to the cipher, thus avoiding becoming trapped in a local peak. One evening, after several weeks without success, the solution to a Playfair cipher appeared on the computer screen - after about 9 minutes of run time. I'm not sure now what I changed to get success but it was great to see it working. The same procedure broke the substitution stage of the ADFGVX cipher in the challenge a few days later. There the matter rested, until I started to think about Hagelin pin and lug machines. Would the procedure work for a pin wheel machine? Since a partially correct decrypt is related to the amount of correct key it seemed worth a try. Having just produced a computer simulation of the Hagelin CD-57, this seemed a suitable candidate machine. The CD-57 [2, 31 has six pin wheels chosen from a set of twelve3 of length 25, 26, 29, 31, 34, 37, 38, 41, 42, 43, 46 and 47. The CD-57 used for this investigation is configured with wheels of length 29, 31, 37, 41, 43 and 47 pins. All wheels step by one position at each cycle. Associated with each wheel is a lug which allows the alphabet disc to rotate by an integral number of places if an active pin is presented. Each of the six lugs can be set to values between 1 and 16.

PLAIN TEXT DETECTOR

An important part of the hillclimb process is the score system used as a detector of the output plain text. It was decided to limit this investigation to test messages of a realistic size, no more than 500 characters long. A randomly set start key for the pin wheels must have around half the pins correctly set, since they can only take on one of two states. However, six wheels are used to generate six parallel bit streams, so we have no more than 0.56. correct settings from our random start. This is equivalent to no more than 8 correct alphabet shifts in a 500 character message. The plain text detector is required to detect very small increases in plain text as the process runs and we shuffle pins into their correct position. The simplest detector is the Index of Coincidence. However this proved to be unsuccessful in detecting a small increase in the correct decrypt of a 500 character message. To improve on unigram counting, bigram and trigram system were considered. Bigrams are more likely to form first and this proved to be the better detector of the two. A bigram frequency table was constructed from a sample of 50,000 characters of plain English text4 - the target language for the test messages to be attacked. A measure of the output plain text is obtained by the sum of the log frequencies of the bigrams in the output. This is the Log-liklehood or Sinkov statistic [6, p. 77].

THE HILLCLIMB PROGRAM

The original shotgun hillclimb works well for a short pattern, such as the standard alphabet, but for longer sequences some improvements are needed to reduce the computation time. The best initial start we can do is to randomly fill the pin wheels with about half the pins set to the active state. The CD-57 pin wheels are represented in memory as a single array of 228 values set to either one or zero to represent the pin states. This array size is for the selected set of wheels, it could have a maximum length of 257 for other wheel selections. All adjustments to the pin arrangements are performed on this array. Sections of the array of appropriate length (29, 31, 37, 41, 43 and 47) are used during decryption to represent the pin wheels patterns. Scoring for `each adjacent position' in the Gillogly algorithm consists of swapping all possible pin pairs, decrypting and evaluating the score after each pair swap. If a pair swap gives a score increase then it is retained, otherwise the original pair is restored. The number of possible pair swaps is 227x228/2. This dominates the cost of the attack since a full message decrypt is required after each pair swap. However around half of the swaps result in no change in the pin pattern so these can be skipped. At the end of the swapping process, we have hopefully a better arrangement of active pins. Returning to step 1 in the algorithm, randomly pick a new starting position, requires some care. If the pattern contains some correctly found new pins then we don't want to disturb these. However the process could have gone down a blind alley, so a more thorough re-start may be desirable to avoid being stuck on a false peak. A random shuffle was therefore applied to the pin array as follows, easily described using the analogy of a deck of playing cards. Cut the deck several times and remove the top card from each section. Shuffle the top cards and replace one on top of each section. Now assemble the sections back in the deck in their original order. This allows the pattern to remain substantially the same but introduces some variation - a sort of genetic variation. The swapping, scoring and random restart sequence is similar to components in genetic algorithms previously described in this journal [7]. The number of cuts applied to the card deck should be related to the total length of the pin wheels. Machines with shorter wheel length, such as the M-209, require fewer cuts to give a suitable hillclimb. It can also be an advantage to make the number of deck cuts inversely proportional to the highest score. Hence pin patterns with increasingly correct pins get fewer re-arrangement in the shuffles of the later stages of the hillclimb. For the M-209 messages, 30 pins were randomly shuffled from the start of the hillclimb. This was reduced to a minimum of 5 as the score increased. These shuffle numbers were determined by trial and error, using the first test messages, which seemed to break readily, probably due to it's letter distribution. A final refinement to the restart process is to save a copy of the array before the random shuffle. If complete pair swapping of the new pattern gives a peak score lower than that of the saved pattern, then we abandon the new pattern, restore the saved array and then continue, generating the next restart. The array save step significantly speeds up the hillclimb. A high quality random number generators of long period was used, rather than the system supplied random function, and this was seeded once at the start of the program.