Sunday, July 6, 2008

An interesting discovery

51EJ2XMYMEL._SL500_AA240_.jpgEvery so often an old interest gets dragged up out of the background and brought into the light again. And in that background-to-light-dragging process, I always find that I learn something new about that area of interest or am able to attack it with some new perspective.

Well over the past few weeks, I've rediscovered the world of "crypto" with a certain enthusiasm. And as I've come back to visit those old friends, ADFVGX, NEMA, Dockyard, and the SX-52, I've looked at some of them with a new light. And I've discovered new companions (even if I don't like them very much) like the Rasterschlüssel'44.

And here is another new one -- one that has been known about since the mid-1990's but that I never paid attention to: the Reihenschieber. It translates as "series slide" and both the word and the device bear a noticeable (and noteworthy) relationship with slide rules (Rechenscieber). This interesting device was developed during the 1950's, put into use in the German armed forces in 1957, and used for a decade or so to encrypt information described as "up to top-secret." Since cipher technology of the cold war tends to be much harder to learn about than that of the second, this device holds a lot of potential to see how cryptographic thinking advanced in a decade or two.

Note that the Reihenschieber was developed before the revelations about British cryptanalytic success during the war were made public in 1977 -- and therefore may not embody the full state of the art that the agencies privy to that information had at hand. It was also an artifact of the early Bundeswehr, and so developed under some significant restrictions as imposed by the allied powers.

Note that in this article I'm choosing, unusually, to analyze the cipher and perform my back-of-the-envelope cryptanalysis first, rather than opening with a description of the device and its operation. I'm working primarily from John Savard's excellent description which, never the less, contains some areas of ambiguity on the actual use of the cipher. I haven't yet decided to spring the $35 for a reprint of the 1996 Cryptologia article that is the definitive source of Reihenschieber information and until then, my knowledge of its implementation may remain a little sketchy.

The result of these advances and constraints is an interesting device -- half mechanical crypto and half classical. It is a mechanical series of rods that generate a (hopefully) pseudorandom number sequence. This pseudorandom sequence is in turn used to select which column (from one of ten) and which table (one of two) is to be used to perform a simple substitution of each letter in the plaintext.

Does this sound familiar? A polyalphabetic substitution where the cryptographic strength lies in the fact that the alphabets change frequently? Think about how an Enigma machine works -- or any other machine of the period for that matter. At any given point, it consists of a single arrangement of input letters to output letters. Press a key, your input letter gets enciphered according to that arrangement, and then a new arrangement is selected for the next letter using a very complex mechanical (or electro-mechanical) scheme.

Effectively, this is the exact same method used by the Reihenschieber. Instead of a series of wheels, pins, cams, and wires that generates an ever-changing series of substitution alphabets from a vast menu (in the case of some of the machines the number of possible alphabets could be 26! or more -- 4.032914611266057x10^26 if you like), the Reihenschieber select one of twenty pre-generated alphabets according to a complex (but nothing like Enigma or its friends) series of sliding rods.

This is also similar the Dockyard cipher as described in an earlier post. Dockyard also used twenty (or in later versions thirty) substitution tables, but only five of them at any time and they were combined with an interesting fractionation step. Note that fractionation is very out of favor by this point -- apparently the statistical camouflage it offers was finally found to be more illusory than effective once a sufficiently large amount of traffic was generated (though some fractionation is used in the great Soviet spy ciphers).

It might seem that this new cipher would be more like Dockyard than the machines by virtue of its more limited pool of alphabets. This may not be true, however. First off, the 20 alphabets are all in play at any given point, not just five per day. And since the selection of alphabet does vary in a pseudorandom fashion (rather than repeating cyclically through out the message) it will be much more difficult to amass the required traffic in each alphabet that is necessary for a break. Given that a new substitution table is issued monthly, given good precautions the tables may not themselves be broken in time.

The real security in any such cipher, however, depends not on the simple substitution that takes place for each letter, but on the process by which the alphabet varies from letter to letter. And here is where another offsetting advantage might play into the hands of the Reihenschieber. Machine based systems generate both their alphabets and their alphabetic sequences on the fly, in the field, according to a pre-determined algorithm. Even the most secure such systems have historically possessed flaws, unknown or accepted by the designers, that result in patters, repeats, or other notable variations from the truly random.

The American SIGABA was probably the high point of this era, largely because it separated the process of varying the alphabet from the process of creating that alphabet. But I get ahead of myself. Musings on the amazing SIGABA and the equally amazing William Friedman will have to wait for a different day, one probably embodying bourbon and not coffee.

2423PH702C.jpgMy thought, returning to our cipher-du-jour, is that the alphabets used by the Reihenscieber have the potential to be much more carefully selected and vetted than those created internally by the rotor machines. Similarly, the combinations of numbers on the rods that arrange to select the alphabet tables are selected in an office back home -- and therefore have the potential for considerably more algorithmic complexity and analysis to eliminate weak combinations. Heck, in 1957, they might have even used one of those new computers to do some of the work!

Quality over quantity, in other words.

That said, the Reihenschieber did not have a flawless mechanism for generating the pseudorandom sequence that governed substitution table selection. And now, at last, we must with our imperfect understanding, attempt to actually analyze the device.

RS.jpg


As you can see, we have a series of ten imprinted rods (I can't help but picture them as chopsticks!). These rods are arranged according to a procedure (and here we hit the point where my information sources break down) that involves a daily key assigned by HQ (or whomever the responsible cryptographic agency would be) and an area key that is either similarly assigned by HQ or else is selected by the cipher clerk much in the manner of a message indicator. Given the name "area key" I also wonder if it might not be a centrally assigned key, but one that is assigned based on regional sectors, communications nets, or levels of security. In other words the daily key remains constant for the entire Bundeswehr for a given 24 hour period but quartermasters operating near Bonn would have a different area key than artillerymen operating in the Rhineland.

In any case, the daily key consisted of ten letters A-Z that governed the selection of ten sticks out of 26 and the order in which they were placed in the frame (the ten chopsticks were labeled, as you can probably guess, A-Z). The area key, combined with a second numeric portion of the daily key, to specify which of the four sides of each stick was placed to the front as well as the lateral position of each stick relative to its peers.

The exact method remains obscure, but involves the group of lower case letters towards the left side of each stick. They were aligned to a sequence generated, somehow, by a combination of the puzzling area key and the ten digit numeric daily key. This sounds complicated, but I can picture the process taking but a few seconds for an experienced operator. Its the kind of simple operation that can be performed in the field, by flashlight, in the middle of the rain. Notice that this system has no electrical requirements and no "moving parts" in a mechanical sense?

After these alignments, the small grid section would be slid along the large table of numbers that was produced by the arrangement of the sticks. At each stopping place, the digits visible in the windows would be used, in pairs, to select the encipherment table. One digit would be used to select one of the ten columns in a given table, the second digit would select between one of two tables (0-4 = table one, 5-9 = table two). Note that (other than the first and last digit of the sequence) each digit was used twice: once to select a table and then for the next letter to select the table.

Unfortunately, I don't yet have access to the full details of this system that are often as revealing as are the details of the algorithm. How were indicators created and transmitted? How were numbers handled? Were there provisions for using separate codewords for common names (much like RS'44?). I'm particularly interested in the question of message indicators and the actual role of the area key. Since the analysis of this sort of cipher tends to depend on getting a "depth" of multiple messages enciphered with identical alphabets, were there provisions to prevent this from happening? There are a staggering number of ways to arrange the sticks (I haven't done the math on that yet) so there should be an ability to support some sort of message variable key.

In any case, this cipher is an interesting hybrid. It really is a "paper Enigma" -- a non-mechanical attempt to mirror the sort of cipher scheme that was used by rotor machines. I suspect that, despite the vulnerabilities of rotor machines, they were well understood and that the national security agencies of the infant West Germany liked the well understood security that they offered. It is almost a paper-and-pencil cipher, but has the potential to offer much more security than anything else of that era. We shall see.

No comments: