M-209

From Wikipedia, the free encyclopedia

In cryptography, the M-209, designated CSP-1500 by the Navy (C-38 by the manufacturer) is a portable, mechanical cipher machine used by the US military primarily in World War II, though it remained in active use through the Korean War. The M-209 was designed by Swedish cryptographer Boris Hagelin in response to a request for such a portable cipher machine, and was an improvement of an earlier machine, the C-36.

The M-209 is about the size of a lunchbox, in its final form measuring 3.25 by 5.5 by 7 inches (83 by 140 by 178 mm). It represented a brilliant achievement for pre-electronic technology. It used a wheel scheme similar to that of a telecipher machine, such as the Lorenz cypher and the Geheimfernschreiber.

[edit] Basic operation

Key wheels, typewheel, and indicating disk from an M-209. Although aligned on the same axle, the key wheels turn independently of the typewheel and indicating disk.

Basic operation of the M-209 is relatively straightforward. Six adjustable key wheels on top of the box each display a letter of the alphabet. These six wheels comprise the external key for the machine, providing an initial state, similar to an initialization vector, for the enciphering process.

To encipher a message, the operator sets the key wheels to a random sequence of letters. An enciphering-deciphering knob on the left side of the machine is set to "encipher". A dial known as the indicator disk, also on the left side, is turned to the first letter in the message. This letter is encoded by turning a hand crank or power handle on the right side of the machine; at the end of the cycle, the ciphertext letter is printed onto a paper tape, the key wheels each advance one letter, and the machine is ready for entry of the next character in the message. To indicate spaces between words in the message, the letter "Z" is enciphered. Repeating the process for the remainder of the message gives a complete ciphertext, which can then be transmitted using Morse code or another method. Since the initial key wheel setting is random, it is also necessary to send those settings to the receiving party; these may also be encrypted using a daily key or transmitted in the clear.

Printed ciphertext is automatically spaced into groups of five by the M-209 for ease of readability. A letter counter on top of the machine indicated the total number of encoded letters, and could be used as a point of reference if a mistake was made in enciphering or deciphering.

The deciphering procedure is nearly the same as for enciphering; the operator sets the enciphering-deciphering knob to "decipher", and aligns the key wheels to the same sequence as was used in enciphering. The first letter of the ciphertext is entered via the indicator disk, and the power handle is operated, advancing the key wheels and printing the decoded letter on the paper tape. When the letter "Z" is encountered, a cam causes a blank space to appear in the message, thus reconstituting the original message with spaces. Absent "Z"s can typically be interpreted by the operator, based on context.

An experienced M-209 operator might spend two to four seconds enciphering or deciphering each letter, so operation was relatively fast.

[edit] Internal elements

[edit] Overview

Inside the casing of the M-209, a much more complicated picture emerges. The six key wheels each have a small movable pin aligned with each letter on the wheel. These pins may each be positioned to the left or right; the positioning of these pins affects the operation of the machine. The left position is ineffective, while the right position is effective.

An intermediate gear unit (center) meshes with gears adjoining each key wheel. Visible at the bottom of the image are the paper tape and typewheel that print out messages and ciphertext.

With the key wheels and intermediate gear removed, the guide arms are visible. On the right side is a spring-arm mechanism that steps the intermediate gears by one notch after each encoding.

An inactive pin (red) on the bottom of the left key wheel (light blue) pulls the guide arm (green) back. No pin is blocking the right guide arm, so a spring tilts that guide arm forward.

The left guide arm is prevented from interacting with the lugs (purple) on the drum (blue), while the right guide arm is in an effective position, and will push to the left any bars with a lug in that position.

Each key wheel contains a different number of letters, and a correspondingly different number of pins. From left to right, the wheels have:

• 26 letters, from A to Z
• 25 letters, from A to Z, excepting W
• 23 letters, from A to X, excepting W
• 21 letters, from A to U
• 19 letters, from A to S
• 17 letters, from A to Q

This discrepancy is chosen to give the wheel sizes a coprime nature; the end result is that the wheels only align the same way once every 26×25×23×21×19×17 = 101,405,850 enciphered letters (also known as the period). Each key wheel is associated with a slanted metal guide arm that is activated by any pins in the "effective" position. The positions of the pins on each key wheel comprise the first part of the internal keying mechanism of the M-209.

Behind the row of six key wheels is a cylindrical drum consisting of 27 horizontal bars. Each drum bar is affixed with two movable lugs; the lugs can be aligned with any of the six key wheels, or may be placed in one of two "neutral" positions. An effective pin causes its guide arm to tilt forward, contacting the drum. The positioning of the lugs comprises the second part of the internal keying mechanism. Owing to the complexity of setting the internal keying mechanism, it was altered relatively infrequently; changing internal keys once a day was common in practice.

When the operator turns the power handle, the cylindrical drum makes a complete revolution through all 27 bars. If a lug on one of the bars contacts the guide arm of an active key wheel, that bar is slid to the left; lugs in neutral positions, or which do not contact a guide arm, do not affect the position of the bar. All bars that are slid to the left comprise a variable-toothed gear, which in turn shifts the letter to be encoded; the shift is equal to the number of bars protruding to the left. The resulting ciphertext letter is printed onto the paper tape.

After the rotation is complete, a retractor pushes the protruding bars back into place. A set of intermediate gears advances the key wheels by one position, and a locking arm latches into the drum to prevent a second encoding until the indicator disk is adjusted for the next letter.

This system allowed the offset to change for each enciphered letter; without this facility, the enciphering scheme would resemble a very insecure Caesar shift cipher.

[edit] Example configuration

Prior to encoding anything using the M-209, the operator must set the machine according to a preset configuration. This configuration includes the settings for each pin on all six of the key wheels, and the position of each lug on the rotating drum; these were typically specified by tables in a secret system publication given to both sender and receiver. The rotational alignment of the key wheels could be chosen by the sender at random, and provided to the receiver via a secure channel of communication.

Each letter on each key wheel is associated with a pin that can be set either to the left or right. A table specifying the setting of these pins might resemble the following:

Letters that are present in the table for a given key wheel should have their corresponding pin set to the right, or "effective", position. Absent letters, represented by a dash, are set to the left, or "ineffective", position.

The rotating drum has 27 bars, each with two lugs. These lugs can be set to any position 1 through 6, in which case they are aligned with the corresponding key wheel, or they may be set to one of two "0" positions, in which case they are ineffective. A table indicating the lug settings for the drum might look like this:

Bar 1 would have its lugs set in the "3" and "6" positions, bar 2's lugs in the "0" and "6" positions, and so on. Any lug in the "3" position, for example, will be pushed to the side by a guide arm when the currently active pin on key wheel 3 is in an "effective" position.

Finally, the external key is set by rotating the key wheels to either a specific or random sequence of letters. In testing the internal key settings of the M-209, it is customary for the operator to set the key wheels to "AAAAAA", and proceed with encoding a message consisting of nothing but the letter "A." The resulting ciphertext is then compared with a long check string to verify that all of the internal settings have been performed properly. The check string for this particular configuration is:

T N J U W A U Q T K C Z K N U T O T B C W A R M I O

Key wheel pins come into play when they reach the lower part of the key wheel during rotation; it is here that they may contact or release the guide arm that deflects the lugs to the left. The active pin is offset by a particular amount from the letter currently being displayed on the front of the key wheel; when "AAAAAA" is showing on the key wheels, the pins that are in play are those associated with the letters "PONMLK", from left to right.

[edit] Example encoding

After the M-209 is configured according to the settings above, the machine is ready to encode. Continuing with the example of a known check string, the first letter to be encoded is "A". The operator sets the indicating disk to the letter "A", and turns the power handle.

Since the key wheels are set to the string "AAAAAA", the active pins are "PONMLK"; according to the settings above, pin "P" is ineffective on the first key wheel, pin "O" is effective on the second key wheel, "N" is effective on the third, "M" is effective on the fourth, "L" is ineffective on the fifth, and "K" is effective on the sixth. The guide arms associated with effective pins will tilt forward and contact the rotating drum; in this case, guide arms 2, 3, 4, and 6 will be effective.

Any bar on the drum with a lug in any of those positions will be slid to the left, and that bar will participate in the variable-toothed gear driving the output of the machine. According to the given settings, bars 1, 2, 3, and 5 through 21 will be slid to the left, for a total of 20 bars, or 20 "teeth" on the variable-toothed gear. The encoding for this letter will use a shift of 20.

The M-209 uses a reciprocal substitution cipher or Beaufort scheme; the alphabet used in the plaintext message is mapped to the same alphabet in reverse:

If shifting is not considered, "A" becomes "Z", "B" becomes "Y", "C" becomes "X" and so on. Shifting proceeds in a reverse direction; for instance, a plaintext "P" maps to ciphertext "K"; shifting by three positions, to the left, gives ciphertext "N". The shift is circular, so when a shift steps off the left side, it continues again on the right. This approach is self-inversing, meaning that deciphering uses the same table in the same way: a ciphertext "N" is entered as if it were plaintext; this maps to "M" in the ciphertext alphabet, or "P" after shifting three positions, thus giving the original plaintext back.

Continuing the example above, the initial letter to be encoded was "A", which maps to "Z" in ciphertext. The shift given by the variable-toothed gear was 20; shifting to the left 20 positions gives the final ciphertext letter "T", which is the same as the first digit in the check string.

At the end of the encoding cycle, all six key wheels are advanced by one position. The key wheels will then read "BBBBBB", and the active pins will be "QPONML". A new set of guide arms will interact with the drum, resulting in a different shift for the next encoding operation.

[edit] Security

The M-209 was good for its time but it was by no means perfect. As with the Lorenz Electric teletype cypher machine (codenamed Tunny by the Allies), if a codebreaker got hold of two overlapping sequences, he would have a fingerhold into the M-209, and its operation had some distinctive quirks that could be exploited. As of early 1943, German cryptanalysts were able to read M-209 messages (see this telepolis article for details). It was, however, considered perfectly adequate for tactical use and was still used by the US Army during the Korean War.

US researcher Dennis Ritchie has described a 1970s collaboration with Jim Reeds and Bob Morris on a ciphertext-only attack on the M-209 that could solve messages of around 2000–2500 letters long.^[1]. Ritchie relates that, after discussions with the NSA, the authors were persuaded not to publish it as they were told the principle was applicable to machines then still in use by foreign governments^[1].

[edit] Production and usage

Hagelin built about 140,000 M-209 / C-38s and became quite wealthy. A WWII German cryptographer named Fritz Menzer built cipher machines based on Hagelin's designs, though no doubt Hagelin never received royalties from them. Menzer's "Schluesselgeraet 1941 / Cipher Device 1941 / SG-41" was a purely mechanical device, with an internal organization along the lines of the M-209 but larger, with a real keyboard. It was actually put into limited production, with about a thousand built for use by the Abwehr, the German intelligence service, which operated them from 1944^{[citation needed]}.

The SG-41 was supposed to have been a standard tactical cipher machine, but the Germans had only limited supplies of lightweight metals such as magnesium and aluminum, and it was simply too heavy for tactical use. Menzer also worked on two other cipher machines based on Hagelin technology, including a follow-on to the Enigma, the "SG-39", and a simple but fairly strong handheld cipher machine, the "Schluesselkasten (Cipher Box)". Neither of these machines reached production. Had the Menzer devices been put into service, they would have certainly caused trouble for Allied cryptanalysts, though they were certainly no more uncrackable than the M-209.

After the war, Hagelin came up with an improved model of the M-209, designated the "C-52". The C-52 featured a period of up to 2,756,205,443; wheels that could be removed and reinserted in a different order; and a printwheel with a mixed alphabet. However, the C-52 was one of the last generation of the classic cipher machines, as by that time new digital technology was permitting the development of ciphers that were far more powerful.

[edit] References

1. ^ ^{a b} Dennis M. Ritchie, Dabbling in the Cryptographic World — A Story, [1]

• J. Reeds, D. Ritchie, R. Morris, "The Hagelin Cipher Machine (M-209): Cryptanalysis from Ciphertext Alone", unpublished technical memorandum, Bell Laboratories, 1978. Submitted to Cryptologia.

[edit] External links

• Dirk Rijmenants' M-209 Simulator for Windows
• The 1944 M-209 Manual
• Jerry Proc's page on the M-209

This article, or an earlier version of it, incorporates material from Greg Goebel's Codes, Ciphers, & Codebreaking.