| M-209 homepage |
IntroductionIs it possible to find a M-209 key by exhaustive search? To answer this question we must know the number of different keys. In an article, James Reed made some calculations. According to them there are 6*(10**52) different keys (176 bits). For now (in 2015), with the help of a huge number of computers, an exhaustive key search is limitted to about 70 bits.In comparison, Dirk Rijmenants said there are (only) 10**23 (77 bits) possible keys for a three rotors Enigma. The James Reed's calculationExcerpt of "Entropy Calculations and Particular Methods of Cryptanalysis", by James Reed (1977)The Hagelin M-209 cipher machine has three keyed elements: each of 131 pins on the six pin wheels can be set in one of two positions; each of lug bars can be set in any one of 22 cryptographically inequivalent positions; and the six pin wheels can be set in any one of 17*19*21*23*25*26 = 101 405 850 starting positions. As far as the encipherment of a single cryptogram is concerned, the wheel starting positions are redundant: all possible encipherments of a single message are produced by varying the pin and lug settings alone. There are clearly 2**131 different pin settings; we show below that there are C(48, 21) cryptographically inequivalent lug bar settings.
{ Author's remark:
C(k, n): The number of k-combinations from a given set S of n elements
C(k, n) = n! / (k!(n-k)!)
}
Each individual lug bar carries two lugs. Both lugs can be inactive; one
lug can be inactive and the other set in any of six active positions;
or both may be active, set in two out of the six active positions. This
makes C(6,0) + C(6,1) + C(6,2) = 1 + 6 + 15 = 22 cryptographically
inequivalent ways of setting an individual lug bar. For the lug bar
mechanism as a whole, the only thing that matters is how many of the
27 lug bars are set in each of the 22 possible ways. Thus, the overall
number of inequivalent lug bar settings is equal to the number of
nonnegative integer solutions x1 + x2 + ... + x22 = 27.
Elementary cominatorial analysis gives the number of solutions - -and hence of lug bar settings -- as C(27+21, 21) = C(48, 21) Thus, for the encipherment of a single message, the number of possible keys is
K = (2 ** 131) * C(48,21) = 6.07 * 10 **52
The Beker & Piper's calculationExcerpt of "Cipher Systems", by Henry Beker & Fred Piper:"...The numbers 26, 25, 23, 21, 19 and 17 were carefully chosen so that no two of them have a common factor, and an extension of the above argument shows that the six wheels do not simultaneously return to their original positions until 26*25*23*21*19*17 rotations, i.e. until 101,405,850 rotations. ...The key to the machine is, essentially, the pin and lug settings. The six wheels together have 26+25+23+21+19+17=131 pins. Each of these pins can be made either active or inactive and the setting of each pin is obviously independent of the others. Thus, since there are 131 pins and two possible settings for each, the number of pin settings is 2**131. (** = power, 2**5=32) Having counted the number of pin settings, we now turn our attention to the lugs. Each individual bar of the lug cage carries exactly two lugs. Each of these lugs must occupy one of eight positions; two of which are non-effective while six correspond to the wheels. We first count the number of ways in which a particular bar may be set up, and then look at the ways of arranging all 27 of them. The first possibility is to have no effective lugs at all on the bar. There is certainly only one way in which this can occur. If, however, a bar is to have exactly one effective lug that lug may occupy any of the six wheel positions. Thus there are six ways of having exactly one effective lug. If we wish to count the number of ways we can arrange for a bar to have two effective lugs then we must enumerate the number of ways of occupying two positions out of six. But this is precisely the binomial coefficient C(6,2), and is equal to (6!)/(4!*2!) = 15. Thus there are 1+6+15=22 ways of setting a given bar. We must now determine the number of different ways in which the 27 bars can be set up. But since, during any encipherment, the cage makes a complete revolution, the order in which the various settings occur will not affect the outcome. Thus, for the lug cage setting as a whole, all that relevant is how many of the individual bars are set in each of the 22 possible ways. But this means that counting the number of 'different' cage settings is equivalent to counting the number of ways in which 27 objects can be placed in 22 cells This is a well known combinatorial problem and the answer is C(48,27)=(48!)/(27!*21) ~ 2.23*(10**13) ... Since we can take any pin setting with any lug setting, the total number of key is (2**131)*2.23*(10**13) ~ 6*(10**52)... trying the keys individually is out of the question. Lasry, Kobal & Wacker's calculationsExcerpt of "Ciphertext-Only Cryptanalysis of Hagelin M-209 Pins and Lugs", by George Lasry, Nils Kobal and Arno Wacker (2015)Lug Settings Keyspace... We need to distribute k = 27 indistinguishable elements (the bars) into n = 21 distinguishable buckets (the 21 distinct possible lug settings per each bar). Hence, according to the "bars and stars" formula, the number of cryptographically distinct lug settings is as follows:C(n+k-1,k) = C(21+27-1,27) = 47! / (20!.27!) ~ 2 ** 43 Additional Constraints on the Lug Settings KeyspaceThe keyspace for the lug settings is further reduced by operating procedure constraints....We compute here an upper-bound for the size of the keyspace of the lug settings, when applying the constraints derived from the 1942 version of the operating instructions. From Appendix A.1, we can see that there may be only 2, 4, 6, 8, 10, or 12 overlaps. ... Hence, the upper limit for the number of possible lug settings for all bars, with v overlaps, is as follows: C(15+v-1,v).C(6+(27-v)-1,27-v)In Table 5 we show the number of possible settings for each one of the allowed overlap values. The total number - an upper limit for the number of possible lug settings, is about 2**38, compared to 2**43 without operating procedures constraints.
Number of Overlaps v Possible Key Lug Settings
2 17 100 720 224
4 300 736 800 228
6 2 549 632 800 231
8 13 591 504 080 233
10 51 647 715 504 235
12 149 732 980 800 237
Total 217 839 670 704 238
Table 5: Number of Possible Key Lug Settings per Number of Lugs Overlaps
Combined KeyspaceThe full, cryptographically relevant, keyspace of the Hagelin M-209 is therefore the combined keyspace for the wheel pin settings and for the lug settings, i.e. approximately:(2 ** 131) * (2 **38) = 2 ** 169. Churchouse's calculationsIn his book, Robert Churchhouse talks about the number of keys of an Hagelin cipher machine, but without overlaps. Excerpt:...Since some cages are obviously very 'bad' (that is, weak from the cryptographer's point of view) this raises the questions:
number of possible cages = the number of representation of 27
as the sum of six non-negative integers.
and although there is no simple formula for calculating this number
we can use a nice mathematical identity and a computer to discover
that the number is 811. If we insist that each wheel must have at
least 1 lug opposite to it, ..., the number reduces to 331...
We must remember however that since the
six number of a cage may be permuted and so generate different key
streams, ... Thus, in the case of 27 lugs, there are 201376
possibilities, not 811.
How many of these 331 distinct possible cages are 'good'?
A 'good' cage is one that generates all possible keys in the
range of 0 to 25.
Then, we can use a computer to find how many of the 331 do this. The
answer is 113. Permuting the cage makes no difference to its quality.
{Author's note: I have written a program which verify these calculations and print all cages (ordered or not)} References
|