Although the Swiss firm founded by Boris Hagelin has manufactured, and continues to manufacture, many kinds of cipher machine, the words "Hagelin machine" will normally inspire thoughts of their unique lug and pin based machines.
The basic principle of a Hagelin lug and pin machine is easy enough to describe. In the C-38, used by the U.S. Army as the M-209, six pinwheels, with 17, 19, 21, 23, 25, and 26 positions on them, can be set by the user with an arbitrary series of pins that are active. For every letter enciphered, all the pinwheels rotate one space.
The combination of active and inactive pins is presented to a cage with 27 sliding bars. Each bar has two sliding lugs on it, which can be placed either in a position where it is inactive, or in a position corresponding to any of the pinwheels, so that it will slide the bar to the left, if the pin currently presented by that pinwheel is active.
In this section, we will examine how messages sent on the original C-38 machine could be cryptanalyzed, in the simplest case. That is, I will assume that a large number of intercepts for a given day (or whatever period intervenes between key changes) are available, and that the message indicator, giving the initial positions of the pinwheels, is not encrypted (or, which is the same thing in practice, any method of encryption used for the pinwheel position has been revealed to the cryptanalyst by some other method of intelligence).
The first thing to do is to find a pair of messages that have pinwheel settings that overlap. To find overlaps, the first step is to convert a pinwheel setting into a number in the sequence of pinwheel positions that the machine experiences. (Note that when the machine was improved to have an irregular pinwheel motion, this approach could not be used; overlaps could still be found, but then one would have to perform kappa tests on every pair of messages, a tedious process requiring automated assistance.)
Such conversion relies on the Chinese Remainder Theorem: given a series of integers, such as a, b, and c, which are all relatively prime to one another, the remainder of a number after division by a, b, and c is sufficient to uniquely identify that number if it is known to be within a range of length a times b times c.
Thus, for example, the numbers 1 through 15 have different remainders modulo 3 and modulo 5:
1 | 1 1 6 | 0 1 11 | 2 1 2 | 2 2 7 | 1 2 12 | 0 2 3 | 0 3 8 | 2 3 13 | 1 3 4 | 1 4 9 | 0 4 14 | 2 4 5 | 2 0 10 | 1 0 15 | 3 0
How can we quickly convert a pair of remainders to the number it is associated with, without performing a table lookup? Basically, we can take one remainder as is; the remainder modulo 5 tells us something we will need to know to find the number. But we then want to use the other remainder, the one modulo 3, to tell us how many times a whole 5 needs to be added to this remainder.
How might we do this? Looking at the way the groups of five numbers start, it seems that the difference between the two numbers might be considered. That difference is:
1 | 1 1 0 6 | 0 1 -1 11 | 2 1 1 2 | 2 2 0 7 | 1 2 -1 12 | 0 2 -2 3 | 0 3 -3 8 | 2 3 -1 13 | 1 3 -2 4 | 1 4 -3 9 | 0 4 -4 14 | 2 4 -2 5 | 2 0 2 10 | 1 0 1 15 | 3 0 3
From this, it can be seen that if we take the difference modulo 3, it nicely separates the numbers into three groups of five, but we have to shift to starting with 0, as is only to be expected, since the remainders modulo 15 run from 0 to 15.
Since 5 modulo 3 is 2, the difference increases by 2 for each group of 5.
Thus, the rule, which can be applied repeatedly to convert a group of several remainders to a remainder modulo their product, is:
Given two prime numbers, A and B, where A is less than B, and the remainders modulo those primes, a and b, of an unknown number, the remainder of that number modulo AB is determined as follows:
Once we have found two overlapping messages, the second step is to solve for the plaintext of those messages over the extent of the overlap. Because the machine produces successive shifts of a known alphabet, we know that the distance between two ciphertext letters at a given position corresponds to the distance between the two plaintext letters they represent, so for each position, we have only 26 out of 676 possibilities to consider for two letters. (Remember, the plaintext alphabet and the cipher alphabet are the normal alphabet and the reversed alphabet, and the distances between letters must be considered in their own alphabets.) Eliminating pairs which have an uncommon letter in either position narrows down the possibilities for each letter in each message.
For a machine like the Sigaba, which produces a different alphabet for each letter, an attack at a "depth of two" is probably impossible without much additional information.
Having some plaintext and corresponding ciphertext, we can derive from that the series of displacements generated by the operation of the lugs and pins over the part of the sequence of pinwheel positions in question.
At this stage, one can apply sophisticated techniques, which have been described elsewhere, to attempt to reconstruct the lug and pin settings of the machine. In order that different combinations of active and inactive pins will tend to produce different numbers of shifted lugs (different displacements of the alphabet), the lugs need to be distributed among the positions corresponding to pinwheels in a manner that assigns different weightings to the different pinwheels, resembling, but not identical to, the weighting of binary numbers (16, 8, 4, 2, 1). Thus, if one looks for large displacements and how they alternate with small ones, one may find a pattern that indicates where the lugs are on at least one pinwheel.
The third step is to find messages which have an almost overlap. A list of all the pinwheel positions in the overlap will help with this; it can be compared to the start and end pinwheel positions of other messages (and middle positions, if the other messages are long enough, and the overlap is short enough). An almost overlap is a span of letters in a message where the positions of five of the six pinwheels have matching positions to the pinwheels enciphering the (full) overlap sequence with which it is being compared.
Since each pinwheel contributes only a single bit of input to the cage which determines the displacements (note that for a computer version of this type of cipher, which XORed together whole bytes in lists of differing length as input to an S-box, this would not work), half the time, the displacement would match that of the displacement in the message with which the almost overlap exists. So, a trial decipherment can be made using those displacements, and it should not be hard to pick out the half of the letters that are right. This gives information on whether a pin in one position on a pinwheel has the same active or inactive state as a pin somewhere else.
Multiple almost overlaps involving the same odd pinwheel allow reconstruction of the pinwheel; so does the fact that an extra active pin results in an increased displacement (although there are exceptions to that rule once the cage has more than 25 lugs in it).
Constructing a table with 64 entries (corresponding to the combinations of active and inactive pins) giving displacements is sufficient to read messages, although it is doubtless possible to reconstruct the lug settings from the displacement table.
Next
Chapter Start
Skip to Next Section
Table of Contents
Home Page