Friday, June 1, 2012

The American M-209 cipher machine

At the start of WWII the US armed forces used various means for enciphering their confidential traffic. At the lowest level were hand ciphers. Above that were the M-94 and M-138 strip ciphers and at the top level a small number of highly advanced SIGABA cipher machines.

The Americans used the strip ciphers extensively however these were not only vulnerable to cryptanalysis but also difficult to use.  Obviously a more modern and efficient means of enciphering was needed.
At that time Swedish inventor Boris Hagelin was trying to sell his cipher machines to foreign governments. He had already sold versions of his C-36, C-38 and B-211 cipher machines to European countries.

In 1940 he brought to the US a copy of his C-38 device. This was tested by American cryptologists and it was adopted by the US armed forces for their low/mid level traffic. Overall more than 140.000 M-209’s were built for the US forces.
The American version of the C-38 was called M-209 and had a few modifications compared to the original version. The M-209 had 27 bars on the drum while the C-38 had 29. Another difference was that the letter slide was fixed. During operation the text was printed automatically.





The M-209 was a medium-level crypto system.

The Germans called it  AM 1, (Amerikanische Maschine 1).
The machine was set up according to the daily ‘key’ .This specified the internal settings. There were six rotors that had pins that could be set in active or inactive position. Then the lug positions on the bars of the drum were set up.

The internal settings were changed each day and the external settings were communicated by means of a complicated indicator procedure (1). The operator had to select 6 random starting positions for the six rotors. Then he would choose a letter of the alphabet at random and encipher it 12 times. After that he would take these 12 cipher letters and use them to select new positions for each of the six rotors. Why were 12 letters needed to set only 6 rotors? Some of the rotors did not have all 26 letters of the alphabet. When the cipher letter was not available it was crossed out and the next one used. Then the operator enciphered the message and sent it together with the external indicator.
Let’s say that we choose to set the 6 rotors at positions LAREIQ. Then we select the letter J to encipher 12 times. The output is QPWOINPONMML. Now we set the rotors at the position indicated by this output. Rotor 1 will be set at Q, rotor 2 at P, rotor 3 cannot be set at W since this rotor does not have this letter. We discard that letter and move to the next. Next one is O which is available at rotor 3 so we set it at that. Rotor 4 is set up on I, rotor 5 at N and rotor 6 at P. We will encipher the message with the wheels at positions QPOINP.

The external indicator sent with the message will be the letter we encoded written twice followed by the initial position of the rotors. Also two more letters indicating the cipher net need to be added at the end. Let’s say that the net for 101st Airborne division is FK. Then the indicator for the above example would be JJLAREIQFK.
The cipher clerk who receives it will follow the same instructions to get the real position of the rotors (in our case QPOINP) but will then set his machine at decipher to decode the actual message.

These procedures should have made the M-209 very secure from cryptanalysis, however as with all the other codes and ciphers of WWII it was human error that allowed the Germans to compromise its security.

German exploitation of M-209 traffic

The M-209 was first used in combat during the Tynisia campaign of 1942-43.

The agency that first succeeded with the M-209 was the German army’s signal intelligence agency OKH/Inspectorate 7/VI. According to various reports (2) the people who were responsible for the solution of the M-209 at Inspectorate 7/VI were Steinberg and Luzius.
Dr Steinberg was a member of the mathematical research section of Inspectorate 7/VI and later became head of the USA section. In Nov 1944 he transferred to OKW/Chi where he worked on a Japanese cipher machine (the PURPLE?). Unfortunately it doesn’t seem that he was interrogated after the war.

Dr Luzius was a statistician of the Alliance insurance company before the war. In 1941 he was called up into the army and posted to OKH/in 7/VI. There he became an expert on cipher machines.
Thankfully we have a short history of the work done on the M-209 from his report TICOM I-211 ‘Preliminary interrogation of Dr Hans Peter Luzius of OKH/In 7’, p2

5. The strip cypher gradually faded out, and was replaced by the M-209 Hagelin at the beginning of the African campaign. This was a better version of the French C-36, which had been solved in the early part of the war; he could give no details as this was before his time. The C-36 had five wheels, whereas the M-209 had six. Here again, solution was purely analytical, and depended upon getting two messages with the same indicators, or a mistake in encipherment. The first break was achieved as the result of a message which was subsequently re-sent with the same indicators but slightly paraphrased, so that the words in the text were slid against each other; their task of diagnosis was also made easier in this case, because, contrary to the instructions which laid down 250 letters as maximum length of a message, this message was over 700 letters long. They began by guessing a word in the first text, and then trying it out on the second text, utilizing the fact that the slide between the two cypher letters would be the same as that between the clear letters. In this way, they could read the text, and work out the cycle and behavior of the wheels, which enabled them to derive the relative setting. The solution of the absolute setting, which would enable them to read the remaining messages on the day's key, was a more intricate process, and he was unable to recall details, beyond the fact that it was always possible.
With practice, they were able to break the relative setting given a minimum of 35 letters of text, although normally they required 60-70 letters. It took them about two hours to derive the absolute setting, after they had broken the initial messages.

6. This was the only method of solution known to them; they could never solve traffic unless they had a depth. The work was done entirely by hand, except that the indicators were sorted by Hollerith. He was unable to say what percentages of keys were read, but thought that it might be about 10%.. The only occasion when traffic could be read currently was when they captured sane keys in advance in Italy, which continued to be used. Them was a theoretical method of solution an one message given at least 1000 letters in a message, but this had never occurred and he did not remember the details.
7. He was then asked whether they had achieved any other successes with this type of machine. He recalled that the Hagelin had been used by the Swedes, in a form known as BC-38. This was similar to the M-209, but with the additional security feature that, whereas with the American machine in the zero position A = Z, B = Y, etc., In the Swedish machine the relationship between these alphabets could be changed. He could not remember whether it had changed daily or for each message. He himself had worked on this machine and had solved a few messages. It had been an unimportant sideline, and he could not remember details; he thought that it had been done by the same method, when two messages occurred with the same indicators. This had only happened very rarely.

According to the war diary of Inspectorate 7/VI, the German Army’s codebreakers investigated this traffic from US troops in N.Africa and Britain in the first half of 1943, ascertained that it was a Hagelin type device and found ways of solving it by using two messages ‘in depth’ (enciphered with the same internal and external settings). By retrieving the internal settings they were able to decode the entire day’s traffic.

The first messages were solved in May ’43:

Investigations continued in June and in July reports based on decoded AM-1 messages were issued by Referat 1.

The Germans would continue to solve messages till March ’45. Information on some of the solved ‘keys’ can be found in TICOM report DF-120, for example:

The July ’43 report of Referat 1 says that the AM-1 device was judged to have adequate security since without mistakes in encipherment and messages in depth solution was deemed to be impossible. The Germans suspected that the US authorities had taken notice of their use of the Enigma machine and that is why they introduced their own cipher device.


Methods of solution

German methods of solution were based on finding messages that had been enciphered with the same internal and external settings. These would have the same external indicator meaning the starting position of the rotors would be the same for both messages.

When these messages on the same net with the same external settings were identified the cryptanalytic attack involved running ‘cribs’ (suspected plaintext in the ciphertext). A ‘crib’ used on these messages was ZPARENZ (3).
If it was not possible to find messages with the exact same indicator then there was also the possibility to use messages whose indicator differed by one or at most two letters. Another method was to look for messages where the indicators (wheel positions) differed by one or two letters equally on all wheels (4). 

The German cryptanalysts developed several methods for identifying if messages were in ‘depth’, regardless of the indicator (5). The most elaborate method used clear text and cipher text trigram analysis.

The trigram technique is described in TICOM report DF-120 (6) and was similar in concept to Friedman's Index of Coincidence and Turing's Bamburismus (7):

From solved M-209 messages from Africa, out of 10,000 letters the 300 most frequent clear text trigraphs ware counted (taking into account the separator letter "Z’’) and the clear text intervals of these trigraphs to each other were determined, The differences found correspond to the negative cipher intervals in messages in depth. The triple number (Zahlentripel) which arose was weighted with values built up simply from the product of the frequencies of their occurrences, since the probability that two definite clear text trigraphs will appear over each other is equal to the product of the frequency of the percentage of their occurrence.

From these differences a table was prepared which indicates for us the corresponding weight for every possible Zahlentripel. One now finds each interval triple which appears in the two cipher messages, in the upper as well as in the lower message, and adds up the weights which apply to them. The sum is then multiplied by 100 and divided by twice the number of positions being investigated. It is multiplied by 100 in order to get a relationship to 100 positions, and divided by twice the sum of the investigated positions since we have looked up each position twice - once in the upper and once in the lower message. For this reason the different sign of the intervals for the clear and cipher text has no moaning. The final result then gives us a point of departure for telling whether the messages being investigated are in depth or not. Experience has shown that values of 50,000 or more make depth probable. Values under 40,000 speak against depth, and with numbers in between 40,000 and 50,000 one can count on either possibility. Of course, in doing this, scattering (Streuungen) and coincidences must be taken into account, These things can make a considerable distortion of the picture, especially in short messages,. Nevertheless, up to now, we have, in general, been able to depend on the results, particularly In rather long messages.

At times German work was assisted by captured material. In Sicily and in Normandy key lists were captured and all messages read (8):
There were times, however, when captured lists of keys or settings made possible a quick solution of the traffic. During the campaigns of Sicily and Italy, messages of great tactical value were decoded using captured booklets containing M-209 settings. At the time of the invasion of Normandy, the M-209 keys of the 82nd and 101st Airborne Divisions which covered the critical days of June 6, 7, 8, 9, 10, 11 were captured and all traffic on those days, was read.

Operational work on the M-209 was carried out both by the USA section of OKH/In 7/VI in Berlin and NAAS 5 (Nachrichten Aufklärung Auswertestelle - Signal Intelligence Evaluation Center) in Saint-Germain-en-Laye, France. NAAS 5 was part of KONA 5 (Kommandeur der Nachrichtenaufklärung - Signals Intelligence Regiment) covering Western Europe.
The NAAS 5 section was headed by Wachtmeister Engelhardt. Under him was a group of young mathematicians (9). 

The NAAS 5 unit also cooperated with Luftwaffe cryptanalysts on the M-209 (10).
Reinold Weber and the German ‘bombe’

An interesting overview of events regarding the NAAS 5 unit is given by one of the cryptanalysts who served there named Reinold  Weber.
According to an article at Telepolis magazine by Klaus Schmeh (11), Reinold Weber was born in Austria in 1920. In April 1941 he was drafted in the German army and assigned to a signal company in the Eastern front. In December 1942 while he was in an interpreter school he took an intelligence test and scored third. His good results got him reassigned to the signal intelligence service and he was sent to Berlin for a six month course in cryptology.

In September 1943 he was sent to FNAST 5 in Louveciennes, near Paris.
In France Weber distinguished himself by solving the US TELWA code. In April 1944 the emphasis shifted to the M-209 machine. The traffic was broken sometimes several times per week, other times once in 14 days.

In April 1944 Weber came up with the idea of building a cryptanalytic device that would speed up the deciphering process. His superiors found the idea interesting and he was sent to Berlin to discuss it with specialists. The employees of the Hollerith company (Dehomag?) told him that such a machine would take two years to build.
Weber returned empty handed but did not forget his idea to build the cryptanalytic device. When his unit retreated to Giessen, Germany he finally had the chance to build the machine. Using equipment from a nearby factory he and his coworkers built the device. By the end of August they were finished and in mid September Weber used it to recover the daily settings of the M-209 in 7 hours. The message contained details on a bombing operation scheduled for several weeks time.

As Germany collapsed Weber’s unit was ordered to Bad Reichenhall in Bavaria. When Weber got there his unit was in nearby Salzburg. As the war was coming to a close he was ordered to destroy the machine. It was broken up with hammers.
Weber’s story appeared in 2004 but until this time it could not be independently confirmed. Thankfully newly released TICOM report DF-114German Cryptanalytic device for solution of M-209 traffic’ has the blueprints of this cryptanalytic device.


This proves that the Allies were not the only ones to build specialized cryptanalytic equipment for the solution of cipher machines. The Germans also had their own ‘bombe’.

Overview of German success with M-209:

US Army M-209:
The US army used it at division level and below. According to a German report it was at times used up to Corps level.

Several reports give some information on the success achieved with it:
From I-60  ‘Further Interrogation of oblt. Schubert of OKH/Chef HNW/Gen.d.NA’, p2

c) 209 CIPHER KEYS
QUESTION: How many 209 cipher keys a month were broken? Give details of personalities and units mentioned in decodes.

ANSWER: Approx. 20 keys were broken every month. 15 men were working full time at O.K.H. on these codes. SCHUBERT cannot give any details of the texts, but he mentioned that for a fortnight during the landing in SICILY the Germans were able to read all our messages as the code had not been changed for some time. 

From I-113 ‘Interrogation of Major Dr. Rudolf  Hentze, Head of Gruppe IV (Cryptanalysis) General der Nachrichtenaufklaerung’, p2-3
(a) M.209: This was broken only on depths. His estimate of the traffic per month intercepted was 1,000 messages; in this they would find about 50 cases of depth, and break a total of about 30% of the intercepts.

From I-185 ‘Letter from Fritz Wichert on interception and reading of Allied service W/T traffic’, p2
The American cypher machine (Converter M209), originally a Swedish system which was improved for the American army, could also be read up to roughly 40%-50%.

USAAF M-209:

The M-209 was also attacked by the codebreakers of the Luftwaffe. The central department  OKL/Gen Na Fue/III (Oberkommando der Luftwaffe/General Nachrichten Fuehrer/Abteilung III) cooperated with the Army’s signal intelligence agency.
From I-112  ‘Preliminary Interrogation of Reg. Rat Dr Ferdinand Voegele (Chi Stelle, Ob.d.L.) and Major Ferdinand Feichtner (O.C. of LN Regt. 352)’, p4

4. (g) U.S. Hagelin Machine (M. 209)
The first success was achieved in March or April, 1944, On the western Front the keys were broken for 6 to 8 days per month but in the Mediterranean cypher discipline was much stronger and keys were broken on only one or two days per month.

A key chart was captured in September or October, 1944. Although in theory 22 hours should suffice for breaking, the time lag was 8 to 10 days in practice, owing to delays in the reception of raw material.
The breaking of M.209 was soon left to the Army who intercepted most of the traffic. Hagelin traffic was considered of little value as compared with Slidex which was read in bulk. Lt. Zimmerlin (a French prisoner at Tuttlingen) and Sgt. von Metzen were M.209 specialists.

In another part of the report Voegele says there was collaboration with NAAS 5 and exchange of indicators with OKH and OKM.
Voegele was the chief cryptanalyst of the Luftwaffe.

From I-109 ‘Translation of a Report by Lt. Ludwig of Chi Stelle OB.d.L, based on questions set for him at ADI(K)’, p37
A. M-209 (Small cipher machine).

German name for system : AM1 (American 1). The cipher system appeared in American army and air force networks below Army Corps or Command.
………………………………………………………………………………………………………………………………………………..

Work on the system was done simultaneously in section E at Potsdam-Wildpark and Sigint interpretation station 5 (NAAST 5) at St. Germain. As far as I remember the first messages were decoded in February, 1944, by NAAST 5. They originated from the ground networks of VIII Fighter Command (65th, 66th and 67th wing) and contained statements of an administrative nature, but also tactical indications, such as the change over to Mustangs etc.
The original of every message was sent to Potsdam, one copy to the Army. The army got better results.  Because of those results the interception of such messages was stepped up considerably, from about 50-200-300 messages a day, with priority over other tasks. On the invasion starting, the GAF cryptanalytic section too was finally moved from Potsdam to Paris (14/3 formerly W control 3) and close co-operation in cryptanalytical work was established with the army. After the start of the invasion some interesting messages about the losses of the 101st Airborne Division were decoded; apart from that the decoded messages were of greater value to the Army than to the GAF. Cryptanalysis was, as far as I remember, made more difficult later by the fact that the individual service groups (armies, commands) no longer used the same cipher setting, so that they had to be worked out separately. As far as the GAF was concerned, therefore, each individual command was monitored and worked on in turn with all available resources. Good results were achieved in the case of IX Air Defense Command (details of A.A. units) and the IX Eng. Command (extension of airfields, effect of the V 1 bombardment on Liege airfield). The monitoring of the networks of the Tactical Air Commands also brought results: e, g. the forming of the XXIX Tactical Air Command became known from a decoded message.

US Navy M-209:
The US Navy also used the M-209 but according to report HW 40/7 – ‘German Naval Intelligence successes against Allied cyphers, prefixed by a general survey of German Sigint’ (12) the codebreakers of the B-Dienst only managed to read a few days traffic.

Misuse of the M-209:
Although the M-209 was supposed to be used up to division level some of the messages the Germans decoded were from higher levels of command (like Corps) (13).

Also Reinold Weber mentions USAAF messages containing details of upcoming bombing operations.
In these cases the M-209 was used for messages that should probably have been passed on the SIGABA cipher machine. Perhaps the limited number of secure cipher machines forced commanders to resort to the use of less secure methods.

The only other explanation is gross negligence on the part of the cipher clerks.

The Normandy invasion

In the summer of 1944 the Western Allies invaded France and after a period of hard fighting managed to defeat the German troops and liberate the entire country. Prior to the invasion the German signal intelligence agencies tried to gather as much information as possible on the location and movement of Allied units in the UK in order to find out where the landings would come.

From the war diary of Inspectorate 7/VI and the reports of NAAS 5 it is clear that in the first half of 1944 M-209 messages from US forces in the UK were solved and valuable intelligence was gathered on the groupings of US military forces. In the period February-May ’44 the USA section of Inspectorate 7/VI issued 47 reports based on 678 decoded messages. Also the report E-Bericht Nr. 3/44 der NAASt 5 (Berichtszeit 1.4-30.6.44), pages 3-8 shows that NAAS 5 solved 1.119 messages during April-May ’44 and got intelligence on the assembly of US troops.




Activity report before the invasion
…………………………………………

1). AM1:
Focused on decoding the AM1. Ten absolute settings were recovered, which brought the deciphering of 1,119 messages. This cipher-material, mostly composed by the U.S American Expeditionary Corps, gave valuable insights into the location of enemy groups.

After the Allies landed in Normandy a significant number of M-209 messages continued to be read revealing the Allied order of battle. The messages for the days of 6-9 June were solved thanks to captured cipher material.

Conclusion:
The M-209 cipher machine was used extensively by the US armed forces in the period 1943-45. German codebreakers were able to exploit this system, especially Army traffic.
By reading the messages they got tactical information and were able to identify units and build the enemy OOB.  At times the M-209 was used for high level traffic and details of future operations became known to the Germans. For example during the buildup for the Normandy invasion M-209 messages gave information on the concentrations of US forces in Britain.

Work was carried out both in Berlin by the central department of the German army’s signal intelligence agency and also from a forward unit in France. The success rate was roughly 50-50 between them.

The use of a specialized cryptanalytic machine by the Germans was a noteworthy engineering achievement.
Overall the solution of the M-209 was an important success for the German side. In 1943-45 the M-209 together with Slidex were the main sources of information for the German codebreakers in the West.

Notes:

(1). The US indicator procedure is described in TICOM reports DF-120 and I-175.

(2). ‘European Axis Signal intelligence vol4’, TICOM I-211



(5). TICOM report DF-120

(6). TICOM report DF-120, p12-14


(8). ‘European Axis Signal intelligence vol4’, p157 also mentioned in the Inspectorate 7/VI war diary and NAAS 5 reports.

(9). TICOM report I-149 ‘Report by Uffz. Karrenberg and Colleagues on'Allied  Cipher Machines’

(10). TICOM report I-113 ‘Interrogation of Major Dr. Rudolf Hentze’



(13). TICOM report DF-120

(14). US national archives - collection RG457 - Entry 9032 - box 1.024 - US COMSEC reports

(15). TICOM report IF-272 - TAB ‘D’ ‘Documents of Oberkommando des Heeres’

Sources: Cryptomuseum Hagelin M-209 page, European Axis Signal intelligence ,vol4 – Signal intelligence service of the Army High Command , M-209 manual , The Achievements of the Signal Security Agency in World War II,  wikipedia , German analysis of converter M-209 - POW interrogations , Telepolis article , various TICOM reports including DF-120, DF-114, DF-105, TICOM Archive, war diary of Inspectorate 7/VI, E-Bericht NAAS 5, M-209 manual - (March 1944), Special conference on M-209 security (1950), M-209: German break

Pics: M-209 pics found through Wikipedia commons user Rama

For those of you who want to actually use the M-209 check this simulator.

Additional information:

1). The US Army’s M-209 cipher machine was a powerful encryption system, even if it could sometimes be solved through mistakes in encipherment. However it seems that contrary to regulations the US troops did not always use this system in the field since it took too long to encipher their messages (14).

Report of interview with S/Sgt, Communications Section 79 Inf Div, 7th Army. (dated March 1945):

"The US Army code machine #209 was found to be something that hampered operations. It would take at least half hour to get a message through from the message center by use of this code machine and as a result the codes of particular importance or speed, for instance mortar messages, were sent in the clear."




2). The following Inspectorate 7/VI Hagelin C-38 reports were among the records recovered in 1947 by the US authorities from a camp in Glasenbach, Austria (15).

BC 38

Losung der BC 38 aus einem langen Chi-text (Berichtfragment) 1944.

2. Aktenvermerk ueber Erkennen von Phasengleichheit bei alphabetischen Spaltenverfahren. 8 Sept. 1944.

3. Aktenvermerk ueber das Erkennen der Phasereeleichheit bei alphabetischen Spaltenverfahren. 30 September 1944.

Untersuchungsergebnisse betreffend Schluesselgleichheit an franzoesisehen mit BC-38 verschluesseltem Spruchmaterial (von Ref. B2)

Aktenvermerk ueber einige Eigenschaften von Haeufigkeits-verteilungen der BC-38. 6 Sept. 1944.

Erklaerung der Z-Leiste.

Plan fuer die Bearbeitung der amerikanischen und schwedischen Maschine BC 38. 19.8.44. 

Aktenvermerk ueber Erkennen der Phasengleichheit bei alphabetischen spaltenverfahren. 8 Juli 1944,

Aktenvermerk. 1. Theoretische Chi-verteilungen der BC-38 bei verschiedenen Klarhaeufigkeiteno 2. Theoretische Chi-haeufigkeitsverteilungen der C-36.

10 Chi-Haeufigkeitsverteilungen der BC 38 mit USA-klarhaeufigkeiten.

Bericht ueber die analytischen Untersuchungen, die zur Bestimmung der amerikanischen Schluesselmaschine M-209 fuehrten. 1 Juli 1944.

Aktennotiz zur schwedischen BC-38. 13 Juni 1944.

Bericht ueber eine Methode zur Vorausscheidung der Konstanten C26 und C25 bei der absoluten Einstellung (AM 1) 27.6.44.

Erstellung des Tagesschluessels der amerikanischen Maschine M-209 bei Vorliegen von 2 Spruechen mit gleichen Kenngruppen 27 Januar 1944.

Aktennotiz zur Maschine C36. 21.1.44.

Bericht OKM/SKL/Chef MND IIIe ueber Loesungsmoeglichkeiten der Hagelin -Schluesselmaschine mit z. T. doppelten Reitern (Type BC 38). 18.11.43.

Sicherheit der Chiffriermaschine BC 38. 16 Okt. 1943.

Bericht. Ausl. Chiffrierwesen. 15 Maerz 1943.

Technische Erlaeuterung zur maschinellen Bearbeitung von AM 1 Kompromisstextloesungen auf der Texttiefe.

Betrug der Anfangsstellung eines Spruches bei Kenntnis des…. Einstellung der BC 38.

3 comments:

  1. From verbal evidence of my father, the M-209-B was still in use during the Korean War, for links between the American Marines and the Royal Navy. He was the senior NCO in communications on HMS Modeste, which was at that time the British flagship Far East, and as such the senior cryptographer.

    ReplyDelete
  2. At that time Swiss inventor Boris Hagelin...
    Boris Hagelin was born on July 2nd, 1892 in Adschikent, Russia. His Swedish father sent him to Sweden...

    ReplyDelete