An interesting discovery

Every 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.

My 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.

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.

Werftschlüssel and Rasterschlüssel '44

It is now time for the second and third of my promised favorite ciphers. And, just to let you know, I am now planning on creating an entry for Vic cipher and some of the other very elaborate spy ciphers of the cold war. Operationally Vic and its cousins were not effective for the field -- requiring too much precision, time, and care and training for a field radio operator or cipher clerk who may well be working under fire. The importance of ensuring that ciphers can realistically be used in field conditions sometimes escapes the notice of the experts charged with developing cipher systems. As we will see, this weakness played an important role in undermining one of the ciphers planned for study today. ADFGVX, on the other hand, certainly can be implemented under field conditions.

I feel I proved this when I wrote my last crypo blog entry -- the examples were all typed while riding the bus!

The Werftschlüssel is more generally known by its anglicized name "Dockyard Cipher" or just "Dockyard." It was the standard mid-grade code used by the German navy during WW2, a companion to the famous Enigma machine that was better suited to auxiliary vessels, small units, and others situations where the expensive and valuable Enigmas could not reasonably be issued. Dockyard is best known for the role it played in routine breaking of Enigma ciphers. Always ready to help out their foes with some bad practice, the German navy would often send identical (or at the very largely similar) messages in the two systems. The easier-to-break Dockyard would yield the known-plaintext crib that was necessary for the folks at Bletchley Park to break that day's Enigma settings.

Dockyard was simple to implement -- the plaintext was written out in five columns (apparently there were specially printed tables to help with this process).

Using the plaintext "It was the best of times, it was the worst of times" would set up columns like this:

I T W A S
T H E B E
S T O F T
I M E S I
T W A S T
H E W O R
S T O F T
I M E S X

Each vertical pair of letters (or digraph) would be encrypted together according to one of a set of tables published on a monthly or bimonthly basis. IT would be looked up and replaced with its cipher pair, TH with its pair, WE with its, and so on. Each column would be enciphered with using the keypairs from a separate table. These columns were selected from the book of 20 or 30 columns mentioned earlier -- I don't know if the procedure was to use a daily set of columns or for the operator to select five for each message and somehow communicate that in an indicator group.

The idea of using 20 or 30 different digraph substitutions was an interesting one -- presumably intending to reduce the amount of traffic that was generated for each. The seriation step also helped break up common digraphs (e.g. the "ch" that is as common in German as the "th" is in English). Digraphic substitution is a nice way of diffusing the statistical predictability of language -- no single digraph has the same obvious statistical dominance as "e" for example. There still are trends, and with a large enough sample, they are noticeable.

The seriation of Dockyard works to further diffuse the common elements of language, but the resulting digraphs still do not have a random distribution, much as we might think that they would. The statistical frequency of individual letters and certain patterns of letter use still result in digraphs appearing more often than others. The EE pairing is more common than any other, for example, because there are simply more e's going around to possibly end up stacked on top of each other.

As a result, the Naval Section at Bletchley could slowly compile up a key for each of the tables in a set. Using the statistical procedures discussed together with some guesses about message content (all the tools of classical cryptanalysis), the tables would be recovered. Once the tables were recovered, identifying which five were in use on a given message was a relatively simple matter of frequency counts. From all of this, the Dockyard cipher was probably the greatest source of intercept information to the Allies about German naval movements -- particularly considering its role as a source of Enigma plaintext cribs. From 1941 to 1945, about 33,000 dockyard messages were intercepted. 90% of them were read the same day they were intercepted...

The second cipher of the day, Rasterschlüssel '44, was not quite as thoroughly broken by the Allies, but more because of its late arrival than because of its security. An unfortunate example of the distance between field operators and back-room-thinkers, RS44 was issued with ambiguous instructions and a complicated operational procedure that resulted in frequent resending of messages, slow operation, and frustrated cipher clerks. And since frustrated cipher clerks have been known to violate procedure and just send the damn thing in the clear once in a while, RS44 ended up as its own worst enemy.

Though I titled this thread of blogging "My Favorite Cipher," and I am a big fan of ADFGVX and find something nifty about the simple tables of Dockyard, I don't particularly like the Rasterschlüssel. It is a transposition cipher alone -- something which a certain truthiest superstition tells me can't possibly be as secure as a mix of transposition and substitution (remember -- diffusion and confusion) as used by ADFGVX. How can it be, I just feel, that a cipher that preserves all the right letters can have the security of one that changes them? Just move then around -- like a big word scramble!

I know, it is wrong, but I can't help but feel that way...

RS 44 was a fairly complex table based transposition. The grid above was specially issued -- one per day -- to all units using the cipher. The clerk would randomly select a square to start in and begin filling in the message in the open spaces, working from left to right, wrapping down columns and back up to the beginning if the message ran off the bottom of the printed grid. The grid was printed on cardboard and was placed behind a thin "flimsy" printed with a grid that let the light and dark squares show through. That way the clerk knew what spaces could be filled in and what couldn't. Once the message was filled in, taking off began.

Using a complex and troublesome formula, the cipher clerk would then determine the column to begin taking the message text off. This process would proceed from top to bottom, moving from left to right as each column was completed. Once the leftmost column was transcribed off, the process would start at the rightmost and work through until the message was done. Indicator groups would indicate both the starting position of the message and the column from which the taking off to the final cipher text began.

That's it. This has been described as the ultimate hand field cipher -- but I can't help but feel a certain "that's it?" at the end of the procedure. But yeah, that's it. I suspect that we see another case of the "possibly combinations" fallacy. Based on the formula that created the daily grid tables, there was an absurdly large number of possible combinations. More, in fact, than rotor settings on the Enigma machine.

And again, German cipher designers let themselves be overwhelmed by the mathematical possibilities of a system and ignore implementation details.

I look back on these two, on Dockyard and RS'44, and can't help that they lack the certain elegance of ADFGVX. RS'44 in particular relies on the tired old misconception that a larger number of possibilities equates with increased security. Dockyard has the cleverness to use multiple keys within each message -- effectively decreasing the traffic in each substitution key. Unfortunately, it still generates a significant amount of traffic in each table. The designers of Dockyard probably thought that each combination of tables would effectively constitute an entirely new key (and picking 5 of 20 tables yields 1,860,480 possibly combinations, 5 of 30 yields 17,100,720).

Each table in dockyard was composed along the lines of some fairly strict rules. Any given letter pair and its cipher were reciprocal -- if EH enciphered as DG then DG enciphered as EH. No letter from the plaintext pair could appear in the ciphertexext pair. For the plaintext digraph ML the cipher digraph could contain neither the letter M nor the letter L in either position. This dramatically limited the possibilities that needed to be tried and gave the cryptanalyst a few extra clues. It simplified the job of creating the tables and sped things up for the cipher clerk and helped to introduce some self-checking features into the cipher. Nice idea -- but at a cost in security. A cost that was probably accepted in light of the massive number of tables available (or rather, of the massive number of combinations of tables that might be used in any given day's key).

Since the cryptanalysts at Bletchley learned to look at each column as essentially a separate entity, they were able to aggregate samples large enough to bring statistical tools to bear. With the result, as mentioned, that Dockyard was despite good intentions one of the most well read of German wartime ciphers.

What do I collect?

My former boss, a man about whom tact and professionalism demand that I say no more, used to ask me "what do you collect?" The fact that has asked me this question at least three times during our interview process and my short ten month's tenure as his employee should have told me something about how much interest he actually had in his staff's well being, but that's water under the bridge (or whisky down the throat, if you want a more accurate image of that time).
But his question was an interesting one because, in many ways and for all his flaws, he was an astute observer of human nature and had a disturbingly accurate arsenal of stereotypes at his disposal. His question was the product of an assessment that people with my personality inevitable collect something. Typically something obscure or marginalized. So what is it?

Action figures? No, but it fits the type, doesn't it?

Slide rules?  Obscurely enough, I do own to, one a glorious Faber 2/83N arguably the finest slide rule ever produced, but I can't see myself investing in dozens, seeking out obscure models for Deitgzen, Hemi, Pickett, Aristo, or K&E.

Calculators? I thought about that one -- and I do want to get an HP-25 or an HP-67 and I'd gladly give a nut to have an HP-65 in my collection. Space (and budget) permitting, I'd love to have one of the RPN members of the HP-98XX family and an HP-9100 would be amazing... But I don't actually do these things.

Nor have I built my cryptology collection beyond the one NEMA machine. No Enigma, no little Hagelin wheel machines, just the one. There simply isn't enough on the market that is affordable to make it possible.

Books? Sure, I have hundreds, but its not really collecting. There is no purposeful seeking out of missing volumes, pride in obtaining a rare edition, etc. I love and treasure them, but as tools.
Vintage airplanes in a hangar somewhere, smelling vaguely of fuel and paint? No. I wish...but lacking Paul Allen's budget I need to keep my collecting under control. But what'd I'd give to have a half dozen classic aircraft sitting somewhere. I'd spend all my weekends lost in complex fantasies, sitting in the cockpits with a sandwich and a beer, playing with all the knobs and levers.
But wait a second (and my inductive writing style is finally reaching its almost inevitable conclusion), I can do that, only without the cockpit to sit in! I have it, the thing I collect: vintage aircraft manuals. I do carefully seek out missing spots, I genuinely feel a thrill when I get an obscure or rare item to add. I've done it for years, but with the internet, over the past three years the collection has grown from a half dozen to hundreds. Don't ask me how many.
I've got pilot's manuals or other documentation on everything from the obscure (BTD-1 Destroyer) to the pervasive (Boeing 737). From the doomsday (B-52) to the innocent (Cessna Mustang). From the complex (C-17) to the simple (Staggerwing). From the secret (F-117) to the well known (P-51). From the high performance (SR-71) to the mundane (Twin Otter).
They are fascinating for student of technology, tracing the evolution of one particular segment from almost its dawn (I don't think that Orville and Wilbur wrote a lot of documentation...) to its very cutting edge. There is plenty of potential for Walter-Mitty moments of mental digression. There is a chance to really get under the skin of some historic airplanes and, by extension, of those who designed and flew them.

Some of my favorites are from the late 1940's on through the middle 1960's. This era gave us amazing advancement in aviation -- the stimulus of the war pushed the envelope and then then period of consolidation when that amazing surge gathered itself up and pushed the electromechanical, slide rule, vacuum tube, and aluminum stage of engineering artistry to its conclusion.

It was an era when the ballpark sums of the slide rule demanded filtering through the mind of an inspired engineer. It was a time when a single gifted brain (Kelly Johnson, Edgar Schmued, Ed Heineman, Frank Whittle, Werner Von Braun, and a half dozen other titans) could shape a design from intuition and lead a project by sheer force of will. The resulting products were often bedeviled by vices and idiosyncrasies but pushed the state of the art at a pace unequaled since. And they rewarded the deft hands of a skillful pilot (and punished the ham fists of a clumsy one). It was an era when pilots were real pilots, engineers were real engineers (and let's not forget the small furry creatures from Alpha Centuri -- they were real too!).
For a variety of reasons, some of my favorites are not the actual flight manuals, the detailed collections of technical specifics and procedures, but the training manuals provided to introduce pilots to their new mounts during the 2nd World War. Thin on technical details, they never the less provide a wonderful zeitgeist. A smilingly benevolent picture of General Arnold on the inside cover, cheerful anecdotes of field successes, little humorous drawings of wayward Ensigns of Lieutenants who used too much throttle on the runup and the comic fate they suffered, and the pervasive use of all those wartime epithets of "Jap" or "Jerry" or "Hun" or whatever. The writing style is half legitimate indoctrination and half propaganda. Always positive on the friendly side, always optimistic. As I once put it in an email to a fellow collector:I love those training manuals from the 1940's and early 1950's, with their snappy and cheerful style. Phrases like "Your Corsair is a snappy flying bird!" instead of "Your Corsair will have nearly uncontrollable roll characteristics in the landing pattern!" And, if it is an AAF manual, the smiling face of Hap Arnold on the inside cover...kind of fatherly, experienced and stern yet supportive of young 2nd Lieutenants...

The drawings, moving in to the 1950's just got better for a time. The other picture above is from the pilot's manual to an F-89, an obscure 1950's all-weather interceptor. What more could I say? So overtly sexist as to be comical, aimed at the entirely male audience of military aviation. But again, there is a potentially telling look at the era and the community here.

Its not just the irony of that important information stacked buxom brunette. The technology of the late 1950's is also something I enjoy reading about. It was "chunky" in a way that made it easy to understand. You could truly look at a diagram of an airplane's

 flight control system (and the comparatively rare service manuals are the place to go for this) and understand what things did and how they worked.

Eventually things get less interesting. The Navy, in particular, starts to carve the information up into classified and non-classified sections. The aircraft, military and commercial, get sufficiently complex that the reading gets denser and denser. Still fascinating, from the airplane lover standpoint, but no longer the full retro experience on top. Thing hit their nadir, probably, in the Navy's current manual for the F/A-18, a volume so dryly procedural and simultaneously obtuse and neurotically obsessed with minutiae as to read like Tolkien's Silmarillion, only without the elves. Boeing's current commercial offerings are no better -- the 767's and 777's reading more like giant VCR manuals than the sort of in-depth technical examination that I enjoy -- and I tend to believe a qualified pilot needs. It is as if the F/A-18 manual substitutes prepared drills for every contingency for actual understanding and the 767 and 777 manuals are afraid of spilling any corporate secrets.

Part of this is increased complexity. The current generation of aircraft are incredibly complex but largely self monitoring. But, that said, Airbus actually produces significantly more interesting training documentation than Boeing does.

My favorite cipher

There is something gloriously manual about a hand cipher, a cipher using pencil, paper, and possibly a small collection of keytables or such. There is intimate connection with the message, and a comprehensible dynamic that is impossible for the oily "kerchunk" of a rotor machine or the silent algorithmic intensity of yet more modern techniques.

So, in my not-remotely-technical way, I propose a quick review of three interesting wartime hand ciphers. One from the First World War, two from the Second, all three German. I'll take a look at these three from the standpoint of a cipher clerk enciphering a message in the field and then, with a perspective as artistic as it is mathematical, at the inner workings that render reversible incomprehensibility. It'll take time, so bear with me. First one, then the rest later on. If I get into it, there might even be more than these three..

ADFGVX -- and the heroic efforts that lead to its breaking -- is at least conceptually familiar to students of 1918. In the final year of that static conflict, the French cryptographic victory helped the allies withstand the final German push to Paris (it should be noted that there are those who question this widely held view of the history).

The German designers of ADFGVX knew well that a successful cipher needed to be simple to use. This lesson, and the corollary that a complex cipher may, through laziness or simple haste, may prove self-compromising in the field, was one that would be lost between the wars, much to the relief of allied cryptanalysts who knew they could always count on sloppy German practice.

But ADFGVX itself embodied some very interesting ideas. For starters, it enciphered messages into six easily transmitted letters: A, D, F, G, V, and X. In Morse, these letters are simple to send and difficult to confuse on reception. Clear transmission (and therefore minimum repetition) improves security.

Let us suppose you have the message "It was the best of times" to encrypt. The first ingredient is a 6x6 substitution square (note that original versions of this used the letters ADFGX in a 5x5 grid and therefore could not directly encipher numbers). In the field, this would have been provided by headquarters and, probably, changed on a daily basis.

  A D F G V X
A Q 1 W E R 2
D 3 T Y U 4 I
F O P A 5 S 6
G D F 7 G 8 H
V J 9 K 0 L Z
X X C V B N M

(Note that I generated this square by typing on that irritating anachronism, the QWERTY keyboard. I don't pretend to cryptographic validity here.)

We look up each letter in the plain text in the grid and then write down the two ciphertext letters that define its coordinates (row first, column second, so "R" would be represented as AV).

Our message encrypts as:

I T W A S T H E B E S T O F T I M E S
DXDDAFFFFVDDGXAGXGAGFVDDFADDDXXXAGFV

Note that the length is now doubled -- but these are the six easiest letters to transmit (radio was effectively all Morse back then!).

We're not done, because this is just a simple monophonic substitution. That is, every letter in the plaintext corresponds to a single symbol in the ciphertext (even if that symbol consists of two letters). And a monophonic substitution is about as easy to solve as it gets.

Now we write our columns out according to a code word that we have been given. This might also change from day to day, or depending on recipient, in an effort to reduce the amount of traffic a given key setup would produce. Our code word is EDMONDS -- but we omit the second instance of any repeated letter for EDMONS. Write the intermediate encipherment out underneath this word, lining each letter up underneath the ones above it.

EDMONS
DXDDAF
FFFVDD
GXAGXG
AGFVDD
FADDDX
XXAGFV

I got lucky and my message lined up directly underneath the key word, making things look tidy and in fact more cryptographically secure.  The Germans left any blank columns unfilled but, as the tale will show, would have been better off adding random nulls at the end to fill all columns fully and equally.

Now take the letters off vertically by columns, in order of the alphabetical position of the letters in the key word. In this case, take of the D column first, then the E column, the M column, the N, the O, and finally the S. Per traditionally proper technique, we will do so in five letter groups.

XFXGA XDFGA FXDFA FDAAD XDDFD VGVDG FDGDX V

This message would then be transmitted.

Analytically, ADFGVX embodies degrees of both transposition (portions of the message are moved around -- think word scramble) and substitution (think, well, substitution). Interestingly, however, it relies on a third component for its security kicker: fractionation. This results from the step where each plaintext letter's two-part symbol is written down horizontally and then taken off vertically. Each plain text symbol is, therefor, divided (or fractionated) into two parts which are located in different portions of the ciphertext. Modern cryptography places quite a bit of emphasis on this idea -- confusion and diffusion being two sought after goals.

At first blush ADFGVX might seem extremely secure. But the reality is that there are cracks a cryptanalyst can pursue. Realize that after our first step -- the plaintext's initial transformation by substitution into the double-lenth intermediate message of digraphic symbols -- all we had was a simple monophonic substitution. Funny looking, yes, but ultimately almost entirely devoid of security. Given any message with a normal distribution of characters and statistics will quickly yield the digraph pairs that correspond to each plaintext letter. Our sample message is statistically skewed, but AG's representation of E would quickly stand out in any normal frequency count. From there, the rest follows and the message is wide open.

A cagy cryptanalyst can, then try to break back from the fractionation component of the second step. Trialing different lengths and sequences of the columnar transposition guided by the keyword in the cipher's second step is a brute force possibility. This would involve taking an intercepted message "backward" to the intermediate stage by various different keywords, then analyzing the resultant intermediate text for normal statistical distributions of digraph pairs.

Hold on, in case I lost you, think of it this way...and remember that once we reach the intermediate stage of the in-order double-lenght message, the break is effectively trivial.

Our wily cryptanalyst starts by assuming the message's keyword was four letters long. It really doesn't matter what those letters were because a four letter word can only yield 24 possible ways of taking off the columns to produce the final cipher:

1234, 1243, 1324, 1243, 1423, 1432, 2134, 2143, 2314, 2341, 2413, 2431, 3124, 3142, 3214, 3241, 3412, 3421, 4123, 4132, 4213, 4231, 4312, 4321.

The cryptanalyst now tests the intercept by transcribing the message backwards into each of these columnar orders. This, incidentally is exactly what the friendly cipherclerk on the receiving end would do, but he would know they keyword and therefore the order in which to fill in the received code. Each of these 24 possibilities is then take off (going sideways this time) to produce a candidate intermediate text. Do a statistical count on this intermediate text and see if it looks valid. If close, try to decrypt. If gibberish, try again.

Sounds easy but time consuming -- but when nations are on the line resources are usually available, and nothing so far can't be taught to any moderately apt college student. But now let's say your foe used a five letter keyword for the 2nd step. That would have 120 combinations you' have to examine. Six letters? 720. Eight letters? 5,760. Nine? 51,840. You get the idea, right? And we forgot to account for the paltry six possibilities offered by a three character keyword. The Germans, at least in the first intercepts to be broken, used 20 columns...

In the end, the French depended upon some even more clever analysis. Cryptographic genius George Painvin spent months (and lost 20 pounds) breaking this cipher just ahead of the threat of a German offensive aimed at Paris. He guessed the structure of the cipher and saw that the essential security lay in the columnar transposition. To avoid brute force, he used two messages with the identical beginnings so helpfully common to military communication to determine the number of transposition columns used (20). The identical openings resulted in the first twenty characters of the intercept being identical. After that first column, the diffusion element of the cipher intermingled the traces of the identical openings with the divergent bodies.

Knowing that there were 20 columns, he could reconstruct them. Some were longer and some shorter by one letter. Logically, the longer columns would be to the left because of the order in which they were filled in. This sorted the columns into two groups -- the long left and the short right, thinning the field a little but still leaving far too many options to try. Assuming that messages with identical beginnings might have identical endings, Painvin was able to apply his opening logic in reverse and create a few groups of pairs that he knew must be next to each other, but not which was to the left and which was to the right. But with two columns, he could afford to roll the dice and try to find statistical distributions that matched written German.

That worked, and allowed him to find the digraph pairs for a few common letters. Using this break, the rest of the columnar arrangement and the substitution square filled themselves in by turns. Statistical guesses at the substitution arrangement could guide the arrangement of the columns (arrangements that produced greater frequencies of digraphs corresponding to common letters were more likely to be correct). As more columns were arranged, more digraphs emerged, and so on, until the columnar arrangement and the substitution table were both fully filled out and all that day's traffic could be read.

It was laborious and depended on a sufficient volume of traffic. The French never read ADVGVX reliably -- only on days with sufficient traffic to generate the sort of kick start needed. The initial breaks took weeks to analyze -- rendering the effort useless from a tactical standpoint. But as experience (and traffic and poor communications practice) grew, solutions were achieved sometimes the same day the messages were sent.

All this said, I like the beauty of this cipher. It embodies both substitution and transposition, and yet is relatively wieldy. If you thought that trial example was tough, just wait until parts two and three...

There are also a few steps that could be taken to improve security. A classic step is to substitute codewords for frequently named people and places. Certain suspected patterns can help speed up the breaking of the final stage, and if an army is fighting in Verdun, for example, a cryptanalyst looking at a signal to or from that army might look for that word. Substitute FIBLA for that word (and then encrypt it) and you have an improvement. Even better, have FIBLA, GIZWA, NILMO, and QAGTL all as options for the cipher clerk to pick at random.

The second stage keyword should be long, to maximize the number of choices facing the cryptanalyst. Chose a phrase like "YOURE MY WONDER WALL" (I've had that song stuck in my head today) instead of just a few words. Take columns headed by duplicate letters off in order instead of ignoring repeats and you have a 17 letter keyword: 355,687,428,096,000 possible combinations, more than enough to prevent trial-and-error cryptanalysis as I suggested. Better yet, don't use a keyword at all (and I believe this might be how the Germans actually implemented the cipher) but a numeric sequence (11 4 7 8 3 8 6 10 1 5 2 9 12) that couldn't correspond to some word or phrase a codebreaker might recognize.

An implementation that somehow changed a portion of the key (say the keyphrase) at every message would increase security. A little recognized fact is that message length can have a lot to do with the ability of a foe to compromise a cipher system. ADFGVX is vulnerable, but only with a sufficient amount of identically keyed traffic. So embedding an encrypted version of an ever changing key phrase or selecting one from a daily sequence rather than using the same one all day long would help. One could easily see a book that contained the substitution square on the left side and a table of 50 different transposition keys on the right, each identified by an in indicator to be sent along with the message or else some sort of scheme for sequencing to govern their selection. This was a common feature of some of the better ciphers of the 2nd world war and shortly thereafter -- the amazing American SIGABA machine for one, the postwar Swiss NEMA for another -- an indicator group that specified an easily changed portion of the machine's settings was transmitted (enciphered in some manner) as part of the message header and footer. The great Soviet spy ciphers (Vic and its kin) used similarly variable portions for every message.

I think that the idea of saying "I transmit part of my cipher key IN my message?" is shocking to most. Understandably! But the countermeasure is that done properly, the indicator group is not easy to read, and the effect of reducing message traffic for any given setup more than outweighs the risks.

Naturally, all the standard weaknesses of classical error cryptography (and their potential countermeasures) are present as well. Sloppy work resulting in identical messages being sent with different keys. Sending the same message on a secure and a non-secure channel resulting in the compromise of all the message on the secure channel for that keying period. Stereotyped beginnings or entire messages -- this was the bane of actual German cryptography, with a national penchant for patriotic phrasing or "nothing to report" reports...

Interestingly, while it would considerably weaken the security of the thing, it is possible to do a ADFGVX variation with no prepared materials, using a keyphrase of sufficient length to form up the initial substitution table. Take the letters of "The sky above the port was the color of television, tuned to a dead channel" and use them to form the initial grid, alphabetically filling in the rest of the spaces.

  A D F G V X
A T H E S K Y
D A B O V P R
F W C L F I N
G D B G J M Q
V X Z 0 1 2 3
X 4 5 6 7 8 9

Of course, we'd need to come up with some scheme for the numbers -- or else use the 5x5 version. Its weaker, since an analyst could guess the arrangement once they started to get a break. But for a spy or someone forced to work with no materials and sending a very small amount of traffic, it has possibilities.

I find this cipher charming for some reason. Its balance of complexity and comprehensibility works for me. It has its vulnerabilities, but then again so does anything of this period or level of sophistication.

The accessibility of it means I can play with it in my mind, try to understand it the way I picture George Painvin did.