* The race between codemaker and codebreaker accelerated in World War I, with combatants devising ever more devious ciphers, and their adversaries cracking them. Codebreaking ended up having a strong influence on the course of the war. In fact, code-making and code-breaking proved so important that by the end of the war, cryptologic organizations were no longer small groups of back-room "boffins", but large bureaucracies increasingly integrated into normal military practice and operations.
The First World War also led to the development of a cipher, the "one-time pad", that was provably impossible to crack by analytic methods. However, this cipher also had drawbacks that made it too clumsy for most practical use at the time.
* At the beginning of the 20th century a new invention, wireless telegraphy, made the need for such ciphers all the more urgent. If intercepting telegraph traffic was simple, with wireless it was almost unavoidable. Messages were broadcast over the airwaves, and anybody could pick them up. In fact, before wireless, one of the problems in cryptanalysis was intercepting enough messages to permit reasonable analysis. After wireless, the problem was sorting through the flood of messages that poured in over the airwaves. World War I essentially created the field of "signals intelligence", or the art of reading an enemy's radio traffic.
Despite the lack of security, there was often no alternative to wireless, since it allowed governments to communicate with warships at sea and armies on the move. When the First World War broke out in 1914, all the major combatants were using wireless. Unfortunately, the lack of really secure ciphers made wireless transmission risky. Codes, which were regarded as generally more secure than ciphers, became standard for navies, since distributing and protecting codes was easier with naval vessels than with armies on the move. Naval codes were generally bound in volumes with metal plates bound into the covers, so they could be thrown overboard in an emergency, with assurance that they would go to the bottom.
For the moment, however, armies on the ground had to rely on ciphers, and the Germans proved unusually vulnerable to interception of their wireless transmissions and cracking of their ciphers. This was partly because the Germans had advanced into Belgian and French territory where telegraph lines had been cut, forcing the invaders to rely on wireless. The French and British, in contrast, only absolutely needed to use wireless to communicate with ships at sea. Furthermore, on the first day of the war, a British ship had dragged up Germany's transatlantic telegraph cables and cut them. From that time on, the Germans had to use radio links or telegrams sent through neutral nations, and both methods left them open to interception.
At the outbreak of the war, Britain had no formal codebreaking operation. The British Admiralty's signals intelligence stations began to intercept German wireless messages and soon recognized the need for a formal cryptanalysis organization. An organization was put together by Sir Alfred Ewing, the Admiralty's director of naval education, a polymath Scotsman whose interests included cryptology.
Volunteer codebreakers were found in the country's naval colleges, the most able among them being Alistair G. Denniston and Dilwyn "Dilly" Knox. Knox did his best work in the bathtub. The group was formally known as "Intelligence Division 25 (ID 25)" and originally operated out of Ewing's office in the Admiralty. The group grew rapidly, and to obtain more space and improve security, Ewing moved them to Room 40 of the Admiralty Old Building. The codebreakers would grow to other rooms, with Dilly Knox acquiring Room 53 and installing a bathtub in it, but they would simply be known as the "Room 40" group.
Room 40 acquired a legendary status, partly because of the remarkable feats of codebreaking accomplished by its members, and partly because of its members itself -- a thoroughly un-military collection of linguists, classical scholars, and crossword puzzle fanatics. They were able to perform extraordinary feats of cryptanalysis, though they were assisted, at least in the case of German naval ciphers, when the Russians recovered the body of a German signals officer after the wreck of the German light cruiser MAGDEBURG in the Baltic. The dead man was carrying cipher books in his pockets, and the Russians cooperatively turned the books over to the British.
The Room 40 codebreakers were able to provide useful intelligence on German naval movements, and made significant contributions to the actions of the Royal Navy at the inconclusive Battle of Jutland at the end of May 1916. The British and German fleets were not quite able to come fully to grips with each other and the British got somewhat the worst of it tactically, but the Kaiser's fleet never tried to directly challenge the Royal Navy again. Ironically, one of the results of the Battle of Jutland was that the Royal Navy acquired a certain distrust of Room 40 intelligence, since the codebreakers had provided some information that proved erroneous. In fact, the codebreakers had correctly deciphered the German messages, but the Germans had broadcast a few erroneous orders that confused their own captains along with the British.
* With the German surface fleet bottled up in port, the Germans shifted their naval strategy to "U-boats" -- submarines. Room 40 now focused on decrypting U-boat codes, an activity that was assisted by a hard-helmet sea diver named Shipwright E.C. Miller, who made several deep dives to rescue code books from sunken U-boats full of corpses and feeding scavengers.
The group had grown to the extent that Ewing no longer felt he was essential to them, and he left in October 1916 to take up a senior academic position at the University of Edinburgh in Scotland. The codebreakers came under the control of Captain, later Admiral Sir, Reginald Hall, known as "Blinker" because he had a facial twitch and tended to blink rapidly when excited. Hall was a sharp, energetic, and respected leader.
Hall expanded the domain of the codebreakers to focus on German diplomatic codes. The British Foreign Office resented this intrusion into their domain, but Hall was able to invoke military secrecy to block interference in his work. This allowed the Room 40 group to score one of the greatest intelligence coups in history.
In January 1917, one of Hall's codebreakers, the Reverend Montgomery, was handed a telegram that the Germans had sent over Swedish and American transatlantic cables. Both these cables were routed through Britain, and the British naturally tapped them. The Reverend Montgomery was a translator of German theological works turned codebreaker. He enlisted the help of Nigel de Grey, a publisher on loan to the military. The two men quickly realized that the telegram was encrypted in a high-level German diplomatic cipher, suggesting that it was important.
Room 40 already had a handhold on that cipher, and in a few hours the two men had deciphered chunks of the telegram. It was in fact an important message. It was from the new German Foreign Minister, Arthur Zimmermann, to the German embassy in Mexico City, and it outlined a scheme that the British could not have imagined in their wildest dreams.
In an attempt to blockade Britain and bring the country to its knees, the Germans had declared "unrestricted submarine warfare" in early 1915, based on what amounted to a "shoot on sight & without warning" policy in which any vessels in the war zone would be liable to attack. Unsurprisingly, such indiscriminate attacks by submarines on merchant shipping gave Germany very bad press, particularly in America, reaching a peak when the Cunard liner LUSITANIA was torpedoed in April 1915. Almost 1,200 people died, including 128 Americans, and led to cries in America for a declaration of war on Germany.
US President Woodrow Wilson didn't want America to become involved in the bloody European conflict and, much to the disgust of the British, calmed the public down, but given further provocations such restraint would neither be possible nor desireable. In the fall of 1915, the Germans abandoned unrestricted submarine warfare. The war dragged on, however, and in the fall of 1916 the Germans revived the practice. Some German officials believed the Americans would refuse to become involved in the European war, no matter how great the provocation -- while others felt that even if the Americans did declare war, Germany would be able to strangle Britain before the US could intervene in any serious way.
Arthur Zimmermann wanted to take more active measures to deal with American intervention. The telegram was a proposal to the Mexican government suggesting that Mexico invade the United States to reclaim territories lost in the 1848 war between the US and Mexico. Germany was prepared to provide military assistance. By this means, the Americans would be too busy fighting on their own soil to help Britain and France. Germany also wanted Mexico to contact the Japanese, who fought on the side of the Allies in World War I, to suggest they invade the American West Coast at the same time.
The scheme was completely crackbrained. Mexico didn't have the material capability to take on the United States at the best of times, and since Mexico was in the middle of a violent revolution, the whole notion was simply unthinkable. All it amounted to was a potential provocation to the Americans, and now the British had it in their hands.
Although Montgomery and de Grey hadn't completely deciphered the message, they knew it was explosive, and passed the partially deciphered message to Blinker Hall. Hall remained calm, even if his constant blinking suggested otherwise, and placed the message in a safe and asked the two men to complete the decryption. The German scheme was so preposterous that Hall suspected that the partial decryption was being misunderstood. Even if that wasn't the case, handing such a message over to the Americans required some finesse, since it was so preposterous that it was likely to be judged a clumsy hoax. Besides, Hall didn't want the Germans to realize that the British were reading their messages.
Two weeks later, Montgomery and de Grey gave Admiral Hall the fully decrypted message, which confirmed the foolish German plot. By that time, Hall had figured out the best way to pass the decrypted telegram on to the Americans without compromising security, by having a British agent obtain a decrypted copy of the telegram at the Mexican end. That was easy, since the British agent knew exactly what he was after.
The "Zimmermann Telegram", as it came to be known, was handed over to the American ambassador to Britain on 23 February 1917. It raised a storm of outrage in America, compounded when Zimmermann bizarrely admitted that the telegram was valid, and did much to lead to the US declaration of war on Germany in April. Hall further covered the tracks of Room 40 by planting stories in the British press, criticizing the sloppy work of British intelligence in almost letting the telegram slip through their hands. This provoked a small national controversy, leaving the Germans completely duped.
* The results of the codebreaking game between the British and the Germans were by no means one-sided. German efforts in codes and codebreaking during World War I are somewhat obscure, mostly because of the later destruction of records in the Second World War. The Germans had a signals intercept system in operation before the end of 1914, and had also been able to crack Royal Navy ciphers -- giving German U-boats a leg up in their attacks on Allied shipping.
German cryptographers were then able to come up with simple mechanical aids to help keep up with changes in Royal Navy and Allied maritime cryptosystems. They were also helped by the usual idiot failures of "cryptographic discipline" by the enemy, such as repeating a message sent in a new cipher that hadn't been understood using an old cipher, in effect simply handing the Germans the new cipher on a platter. Like the Allies, the Germans had their star codebreakers, particularly Ludwig Foeppl, in civilian life a professor of mathematics, who performed many impressive feats of codebreaking and rose high in the German codebreaking hierarchy.
By 1917, the Allies had become aware, the hard way, that their naval ciphers were being cracked. They tightened up their security, changing their ciphers more regularly, as well as obeying tighter communications and cryptographic discipline. The Germans were hard-pressed to keep up, and in the fall of 1917 consolidated their various signals intelligence operations under a single "Signals Service (Nachrichtenwesen)". However, the Germans were simply becoming overwhelmed by seemingly endless Allied resources, while Germany was increasingly scraping the bottom of the barrel. Although the Germans continued to crack Allied ciphers, they were fighting a losing battle and in fact a losing war.
Ludwig Foeppl went back to teaching mathematics after the conflict, ending up at the Munich Technische Hochschule and becoming a member of the Bavarian Academy of Sciences. He died in 1976 at age 89, respected for his academic achievements while his adventures as a codebreaker remained unknown to all who knew him. For whatever reason -- a concern for security, a simple disregard of wartime work irrelevant to his academic career, who knows? -- he never mentioned the matter, and an important chapter in the history of cryptology went to the grave with him.
BACK_TO_TOP* The relative vulnerability of ciphers had already led all the major combatants to implement codes, known as "trench codes", for field armies. A reasonably-designed code is generally more difficult to crack than a cipher, but of course suffers from the difficulty of preparing, distributing, and protecting codebooks.
However, by the middle of World War I the conflict had settled down into a static battle of attrition, with the two sides sitting in huge lines of fixed earthworks fortifications. Vast numbers of men were sacrificed in futile offensives to break these lines, with the usual result being little more than a dent of a few kilometers at best. With armies generally immobile, distributing codebooks and protecting them was easier than it would have been for armies on the move. To be sure, trench-raiding parties could sneak into enemy lines and try to snatch codebooks, but then an alarm could be raised and a code quickly changed. They were changed on a regular basis anyway.
The French began to develop trench codes in early 1916. They started out as telephone codes, implemented at the request of a general whose forces had suffered devastating artillery bombardments due to indiscretions in telephone conversations between his men. The original telephone code featured a small set of two-letter codewords that were spelled out in voice communications. This grew into a three-letter code scheme, which was then adopted for wireless, with early one-part code implementations evolving into more secure two-part code implementations. The British began to adopt trench codes as well.
The Germans started using trench codes in the spring of 1917, evolving into a book of 4,000 codewords that was changed twice a month, with different codebooks used on different sectors of the front. The French codebreakers were extremely competent at cracking ciphers but were somewhat inexperienced at cracking codes, which require a slightly different mindset. It took them time to get to the point where they were able to crack the German codes in a timely fashion.
The Americans were relative newcomers to cryptology when they entered the war, but they did have their star players. One was Parker Hitt, who before the war had been an Army Signal Corps instructor. He was one of the first to try to bring US Army cryptology into the 20th century, publishing an influential short work on the subject in 1915. He was assigned to France in an administrative role, but his advice was eagerly sought by colleagues working in operational cryptology. Another Signal Corps officer who would make his mark on cryptology was Joseph Mauborgne, who in 1914, as a first lieutenant, had been the first to publish a solution to the Playfair cipher.
When the Americans began moving up to the front in numbers in early 1918, they adopted trench codes and became very competent at their construction, with a Captain Howard R. Barnes eventually learning to produce them at a rate that surprised British colleagues. The Americans adopted a series of codes named after rivers, beginning with "Potomac". They learned to print the codebooks on paper that burned easily and degraded quickly after a few weeks, when the codes would presumably be obsolete, while using a font that was easy to read under trench conditions.
However, American codemakers were often frustrated by the inability or refusal of combat units to use the codes -- or worse, to use them properly. A soldier engaged in combat didn't always feel the need to do things "by the book" even when there were very good reasons to do so, and generals on the front line felt that they had other things to worry about. One codemaker suggested that the best way to address the problem was to publicly hang a few offenders, but he lacked the authority to do so.
The British and French were already familiar with such problems in communications discipline. They hadn't completely solved the problems either, but they had at least managed to get it through the heads of most of their signalmen that if they didn't have time to properly encrypt a message, they shouldn't bother trying, sending the message unencrypted, or "in the clear". A partially or badly encrypted message could undermine a cipher or code system, sometimes completely, which made an unencrypted message far preferable.
BACK_TO_TOP* If the German efforts at codebreaking still remain obscure, it is clear the Germans were able to put together strong codes and ciphers that were difficult to crack. They were not, however, uncrackable, and the French were particularly competent at penetrating German codes and ciphers. Unlike the British, the French actually had formal codebreaking groups, five of them, in place before the war. After the outbreak of hostilities, the French built up their "Bureau du Chiffre (Cipher Bureau)" in specific.
The Bureau du Chiffre was one of the most professional Black Chambers ever organized. It grew out of the humiliating defeat of the French in the Franco-Prussian War in 1870, and their subsequent fear of a new united Germany. The French took their inspiration from the Dutch cryptanalyst Auguste Kerckhoffs, who wrote the text LA CRYPTOGRAPHIE MILITAIRE mentioned in a previous chapter. Kerckhoffs did most of his work in France, and the French were his enthusiastic students.
The Bureau du Chiffre performed cryptanalysis on an industrial scale. A group of "stars" were put to work breaking new ciphers, while teams of experts with specialized training did the day-to-day "grunt work". One of the stars was Lieutenant Georges Painvin. The bright Painvin had not been interested in cryptanalysis before the war, but after the shooting began he ran into a member of the bureau, who recognized that Painvin had the "knack".
The Germans threw their greatest cryptological challenge at the French in the spring of 1918. The Allies became aware that the Germans were preparing to launch an offensive, in hopes of victory before American reinforcements arrived in strength and presented the Kaiser's army with certain defeat. The tipoff was increased radio traffic and the introduction not merely of new trench codes, but of a cipher as well, which became known as the "ADFGX" cipher, which went into service on 5 March 1918. The ADFGX cipher had been invented by Colonel Fritz Nebel, a communications officer of the Kaiser's army, to provide an army on the move with encryption more convenient than trench codes but still secure. In fact, the Germans believed the ADFGX cipher was unbreakable.
The ADFGX cipher was a fractionating transposition cipher and was in fact very difficult to solve. The cipher is constructed in two steps. The first step requires building a checkerboard with the rows and columns indexed by the letters ADFGX, and then randomly placing the letters of the alphabet in the grid:
: A D F G X : --------- : A f z t n i/j : D g l d s b : F y v p e a : G k c u w r : X o m x q h
The placement of the letters establishes a "substitution key" for the cipher. In this example, the substitution key leads to the cipher equivalents:
: a FX f AA l DD q XG v FD : b DX g DA m XD r GX w GG : c GD h XX n AG s DG x XF : d DF i/j AX o XA t AF y FA : e FG k GA p FF u GF z AD
For example, the message:
: urgent send more ammunition now
-- would first be enciphered into its letter pair ciphertexts as follows:
: u r g e n t s e n d m o r e a m m u n i t i o n n o w : GFGXDAFGAGAF DGFGAGDF XDXAGXFG FXXDXDGFAGAXAFAXXAAG AGXAGG : -> GFGXDAFGAGAFDGFGAGDFXDXAGXFGFXXDXDGFAGAXAFAXXAAGAGXAGG
The reason the letters ADFGX were used was because in Morse code they are very distinctive from each other, reducing the likelihood of transmission errors. At this stage of encryption, the ADFGX cipher is just a simple Polybius cipher, just another form of a monoalphabetic substitution cipher, which is of course very weak.
However, the next step involves a transposition, using a transposition keyword, say "WARTHOG", and then writing the ciphertext produced by the first step in consecutive rows underneath it:
: W A R T H O G : ------------- : G F G X D A F : G A G A F D G : F G A G D F X : D X A G X F G : F X X D X D G : F A G A X A F : A X X A A G A : G X A G G
The columns of this transposition array are then shuffled so that the letters of the key are in alphabetical order:
: A G H O R T W : ------------- : F F D A G X G : A G F D G A G : G X D F A G F : X G X F A G D : X G X D X D F : A F X A G A F : X A A G X A A : X G A G G
Finally, the letters are written out in column order to produce the ciphertext:
: FAGXXAXX FGXGGFA DFDXXXAG ADFFDAG GGAAXGXA XAGGDAAG GGFDFFAG : -> FAGXXAXXFGXGGFADFDXXXAGADFFDAGGGAAXGXAXAGGDAAGGGFDFFAG
Long messages sent in the ADFGX cipher were broken into sets of messages of different and irregular lengths. The Germans had learned that fixed-sized blocks left their ciphertexts vulnerable to multiple anagramming -- and knew that if they gave the French any fingerhold into a cipher, it would be methodically broken.
* Georges Painvin was given the job of cracking the ADFGX cipher. Of course Painvin had the powers of concentration characteristic of any good codebreaker, but the knowledge that the ciphertexts he was being handed had clues in a life-or-death game of national survival focused his concentration all the more.
Since the cipher only used five letters, it was clearly a checkerboard scheme of some sort. The first step was to eliminate the obvious. He did a frequency analysis on the letter pairs to see if they were just a simple Polybius square substitution. The result showed a "noisy" distribution of the letter pairs -- which meant, as he had expected, that the letter pairs had been split up and shuffled.
Now he assumed that the cipher was a transposition by columns of a simple monoalphabetic checkerboard substitution. A grille transposition or a polyalphabetic substitution, using different checkerboards for different letters, would have been harder to crack but also harder to use, so Painvin decided to work using a relatively simple assumption before moving on to more complicated ones.
* Figuring out the transposition scheme was very tricky. As the ciphertexts were of irregular length, the Germans were obviously not using a fixed size block, which made breaking the messages into its columns a puzzle. At first, traffic was light, making progress on the small handful of intercepts he received very difficult, all the more so because he had to assume the Germans were changing keys every day.
On 21 March 1918, the German offensive began like a thunderclap, smashing great holes in Allied lines and throwing British and French troops back in confusion. The pressure on Painvin increased accordingly, though at least now he had an increasing adequate number of intercepts to work from. Changes in the letter frequency distributions from day to day told him the Germans were in fact changing the keys every day, though the fractionating nature of the cipher ensured that his analyses told him no more than that. By the beginning of April, he was receiving enough intercepts on a single day to give him some hope of obtaining a fingerhold. On 4 April, he finally noticed that some ciphertexts sent on the same day possessed certain patterns that gave a clue to the column breakdown of the messages.
* Suppose two or more messages were encrypted with the ADFGX cipher using the same keys, and that these messages began (or ended) with the same text, giving Painvin a crib. The encryption procedure ensured that when the letter pairs for these messages were written down in an array for transposition, they would have the same text at the top of the columns. The columns would be transposed in the same way for all these messages, with the common text transposed along with them.
This meant that when the transposed columns of these messages were transmitted in sequence, they would all feature distinctive "clusters" of the same text at more or less regular intervals corresponding to the crib. Painvin could use these clusters to find clues on the column breakdown of the messages. Painvin now had a strong clue concerning the way the messages were broken down into columns, but he did not know the way in which the columns had been shuffled, or in other words he did not know the transposition key.
The fact that the ADFGX cipher did not use a fixed-size transposition block actually helped, to an extent. Most of the time, the columns would be broken down into sets of two lengths, with one set a single letter shorter than the other. In the example for the ADFGX cipher above, for instance:
: A G H O R T W : ------------- : F F D A G X G : A G F D G A G : G X D F A G F : X G X F A G D : X G X D X D F : A F X A G A F : X A A G X A A : X G A G G
-- some columns are 8 letters long and some are 7 letters long. Now recall that before the columns were shuffled we had:
: W A R T H O G : ------------- : G F G X D A F : G A G A F D G : F G A G D F X : D X A G X F G : F X X D X D G : F A G A X A F : A X X A A G A : G X A G G
-- with all the 8 letter columns to the left. If the longer columns can be identified, that gives a clue to the column shuffling.
Among the messages Painvin received on 4 April were one that was 110 ciphertext letters long and another 104 ciphertext letters long. His use of cribs suggested they were both broken down into 20 columns. Given 20 columns, a message with 120 letters would have broken down into columns that were all six letters long, while a message with 100 letters would have broken down into columns that were all five letters long. The message lengths of 110 and 104 meant that the lengths of the columns were a mix of five and six letters.
Of course, the number of five-letter columns had to be the same as the message length subtracted from 120. It's just simple logic: if there were 20 six-letter columns, the message would be 120 letters long; if 19 six-letter columns and one five-letter column, it would be 119 letters long; if 18 six-letter columns and two five-letter columns, it would be 118 letters long; and so on.
The message 110 letters long had ten columns five letters long, and ten columns six letters long, while the message 104 letters long had 16 columns five letters long and four columns six letters long. Painvin could use the crib patterns to get an idea of how to break the message down into 5-letter and 6-letter columns. He could then assume that the longer columns, with six letters, had been on the left side of the transposition array before they were shuffled.
This gave Painvin a few plausible column matches. He performed a frequency analysis on the letter pairs that resulted from them. Some yielded a noisy result, suggesting a mismatch, but others yielded a frequency distribution approximating that of German text, indicating a successful match. This not only confirmed a valid match, but his assumption that the Germans were not using a polyalphabetic substitution.
Given multiple column matches, he was able to glean a little more information on the ordering of the columns he had matched. For example, the most common pair in each analysis very likely represented "e". If the most common pair in one analysis was "DG" and the most common pair in another analysis was "GD", then obviously the column order of one of the pairs of columns was reversed from that of the other. He could switch one, and then perform a single frequency analysis on the combination of the two pairs. It didn't really matter which pair he switched; the order of the letter pairs was unimportant, as long as he was consistent for all the letter pairs.
* Painvin was able to come up with another subtle trick to help narrow down the possibilities for the transposition order of the columns. The ADFGX cipher's substitution was, as explained above, based on a grid, with the letters "ADFGX" along the side and the same letters along the top:
: A D F G X : --------- : A f z t n i/j : D g l d s b : F y v p e a : G k c u w r : X o m x q h
Painvin knew that each substitution was created with one letter taken from the left side of the grid, followed by another letter taken from the top of the grid. The reverse might have been true, but once again, as long as he was consistent, it didn't matter at all, and so we'll assume a "side:top" arrangement in this discussion.
This meant that after substitution but before transposition, the "side" letters would be the odd-numbered letters and the "top" letters would be the even-numbered letters. Going back to the ADFGX example above, the initial conversion of plaintext into letter pairs gave:
: GFGXDAFGAGAFDGFGAGDFXDXAGXFGFXXDXDGFAGAXAFAXXAAGAGXAGG : ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ : "side" letters : : GFGXDAFGAGAFDGFGAGDFXDXAGXFGFXXDXDGFAGAXAFAXXAAGAGXAGG : ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ : "top" letters
Now, remember this would be written out in row order before being transposed by columns. If there were an even number of columns, then the columns would be composed entirely of "side" letters or "top" letters, and not a mix of the two. For example, if we take the list of letter pairs with the "side" letters marked above and chop it into eight columns, we get:
: G F G X D A F G : ^ ^ ^ ^ : A G A F D G F G : ^ ^ ^ ^ : A G D F X D X A : ^ ^ ^ ^ : G X F G F X X D : ^ ^ ^ ^ : X D G F A G A X : ^ ^ ^ ^ : A F A X X A A G : ^ ^ ^ ^ : A G X A G G : ^ ^ ^
One of the characteristics of frequency analysis of letters is that while the distributions of individual letters may vary widely from the norm, the law of averages dictates that groups of letters vary less. With the ADFGX cipher, each "side" letter or "top" letter is associated with five plaintext letters. Going back once again to the example:
: A D F G X : --------- : A . z . . . : D g l d s b : F . v . . . : G . c . . . : X . m . . .
-- the "side" letter "D" is associated with the plaintext letters "g l d s b", while the "top" letter "D" is associated with the plaintext letters "z l v c m". Since these two groups of five letters have different cumulative frequency distributions, then if there were an even number of columns -- which Painvin could figure out using the crib trick described above -- a frequency analysis of the "D" letter in odd-numbered columns will have a distinctively different result from those of the "D" letter in even-numbered columns.
This trick allowed Painvin to tentatively identify which columns were odd and which columns were even. He could then pair up odd and even columns and perform a frequency analysis on the pairings to see if they were noise, or real pairings that corresponded to plaintext letters. Once he had the proper pairings, he could then use frequency analysis to figure out the actual plaintext letters. The result was still transposed, but at that point all he had to do was unscramble a simple transposition. Once he determined the transposition scheme for one message, he would then be able to crack any other message enciphered with the same transposition key.
* Painvin was finally able to decrypt some ADFGX ciphertexts on days when German radio traffic was heavy. By the end of May, given enough traffic, he could crack the messages in a day. The Germans were on the move again and proving very hard to stop. Hopefully, one of the decrypts would give warning of where they intended to strike next.
Then, on 1 June 1918, the ciphertexts suddenly began to include the letter "V". The Germans had changed the cipher. Painvin had no idea if they had simply added the new letter to expand the existing system to a 6 by 6 grid, or if they had completely changed the scheme, wiping out all his hard work.
He fell into despair for a moment, then went to work. The simplest assumption was that the new cipher was just a straightforward extension of the old. As he dug into the ciphertexts, he became increasingly aware that this assumption was correct, and quickly regained confidence. Adapting his work on the ADFGX cipher to the ADFGVX cipher was straightforward. He had a solution by the evening of 2 June.
The additional "V" used by the ADFGVX cipher allowed encryption of the ten digits "0" through "9", with the following example grid:
: A D F G V X : ----------- : A 6 g e f a 3 : D k 4 c 1 9 n : F s l p 2 j r : G z f 7 x w t : V 8 h m q u i : X b 5 o y v d
The encryption scheme was otherwise unchanged, with plaintext letters converted into pairs, which were then transposed according to a keyword.
Painvin's decrypts provided Allied leadership with clues about enemy operations, though by this time the German offensive was running out of steam; stories persist that the decrypts were a critical tool in stemming the tide, but they seem to be exaggerations. In any case, as American reinforcements arrived the Germans found themselves increasingly on the defensive, and in November they would have to admit defeat.
* It is a testimony to the good security of the ADFGX / ADFGVX ciphers that the Allies never developed a general solution to them during the war. The only way to crack them was through a lucky break, such as messages enciphered with the same keys that had the same beginnings or endings. In fact, only ten keys were ever discovered, though unsurprisingly these keys were on days of the heaviest traffic and allowed the cracking of a disproportionately large amount of ciphertext.
After the war, Georges Painvin would become a prominent leader of the French business community, and granted high prestige and many honors. To the end of his days, however, he regarded the cracking of the ADFGVX cipher as his greatest distinction. He had lost ten kilograms during the exercise.
Painvin's work in cracking the ADFGVX cipher was typical of the story of cryptography during the Great War. No matter how clever a cipher or code a codemaker came up with, the codebreakers were one step ahead. Clearly something entirely new needed to be done to make codes harder to break.
BACK_TO_TOP* One of the significant achievements in cryptography in the First World War was a cipher that was, and remains, uncrackable even in principle. As is typical of magic, it had a significant catch.
As noted in the discussion of how Kasiski cracked the Vigenere cipher, cracking such a cipher becomes more difficult as the key grows in length, since the size of the sets of letters that can be sorted out grows smaller, and frequency analysis becomes more difficult. In the limit, a cipher key as long as the message could be used, making frequency analysis of the message completely impossible. Such a key is known as a "running" key, in contrast to a "repeated" key. The key could be a block of text in some common document, such as a standard edition of the Bible, or a classical novel. A hybrid scheme known as an "autokey" could also be used, using a short initial cipher key to encrypt the first letters of a message, and then the plaintext of the message itself, beginning from the first letter, to encrypt the rest.
Unfortunately, while such approaches make frequency analysis of the text impossible, the key itself becomes a weakness. For example, Holmes could assume that the key contains a crib, such as a common word like "the", and create a key that consists only of repetitions of "the". He could then decrypt the ciphertext using this key and see if he found strings that seemed to be part of words.
For example, his decryption might yield strings like "uqf" or "zhp" or "und". Only the last looks like it might be part of a real word, and so if "und" is obtained, that suggests that the key actually contains "the" at that location. Holmes can use the clue provided by "und" to guess at words that it may be associated with, such as "sunday" or "dunderhead" or whatever, and see if they provide clues to the unknown parts of the key, and then use anagramming to slowly fill in the blanks. This approach is known as the "probable word" method. Of course, only a word game from Hell would be this difficult, but the point is that a fingerhold is still available.
If a large number of messages encrypted with the same key are available, cracking them is even easier, using superimposition, as described in the previous chapter. Even if Holmes only has a few messages encrypted with the same key, he can cross-reference between the messages to identify or validate elements of the key.
* There was, however, a way to make an absolutely impenetrable Vigenere cipher. In 1918, Gilbert S. Vernam, a cryptologist working for American Telephone & Telegraph (AT&T) and Joseph Mauborgne, then a major, realized that a message encrypted with a Vigenere cipher and using a running key was absolutely secure, as along as two conditions were obeyed:
A completely random running key would defeat any "guessing games" played by Holmes to attack it. Using the key only once defeated attacking the message using superimposition or cross-referencing games. In practice, sequences of long random cipher keys could be printed on a thick pad of paper. Each random key would be used to encrypt one message, and then ripped off the pad and thrown away. As a result, this scheme is known as a "one-time pad" cipher, or sometimes as the "Vernam" cipher.
* While the one-time pad cipher clearly looks difficult to crack, what is not so obvious is that it is completely impossible to crack by any cryptanalytic method. If the key is at least as long as the message; the letters in the key are truly selected at random; and the key is never used again, then the encryptions of each letter in the message are completely random as well.
Imagine Alice has a sheet of entirely random letters, with the same number of letters as a plaintext message as she has written but having no other relationship to the plaintext. If the selection of letters is truly random, then deciphering it is a nonsensical idea. There's nothing there to decipher, it's just random gibberish, noise, with no signal to be extracted from it, just like trying to pick up a radio station out of static -- when the radio station's not on the air.
Now suppose Alice takes this sheet of random letters and then uses it as a keytext, taking its letters as shifts for a Caesar-shift cipher to convert her plaintext to ciphertext. Since the letters in the keytext are random, the encipherments of all the letters in the plaintext are random as well. This means that the ciphertext is still random, just noise, and there's no way to extract a message from it without the keytext. If there's no way to decrypt a message consisting of completely random letters, there's no way to decrypt a message consisting of letters that have been completely changed at random.
By the way, the straddling checkerboard cipher used by Red spies during World War II, with an enciphering mask taken from numbers in a standard reference book of industrial statistics, was much like a one-time pad. The numbers used for the mask were effectively random, and if the Germans didn't know how the masking numbers were generated, they had no chance of cracking messages enciphered with the scheme.
* A one-time pad cipher has an interesting property: it is not so much true that no signal can be extracted from pure noise, but that any signal can be extracted from noise. Since there's no fixed pattern in the ciphertext or the key, a key can be easily synthesized to produce every possible message that will fit into the number of plaintext letters, such as instructions to attack the enemy, a love message to a significant other, a shopping list, dirty limericks, or a personal insult to the codebreaker. Leaking such fake keys might be an amusing game. Incidentally, in some sources the ability to decipher any message out of a ciphertext encrypted with a one-time pad is used as an explanation of why a one-time pad is secure, but that's confusing an effect for a cause: a one-time pad is indecipherable because it is unpredictably random, and its randomness allows any message to be extracted from it.
Of course, there's a catch to the absolute security of a one-time pad cipher, in that it has similar weakness to that of a code. Using a code requires printing and distributing a large number of codebooks, a process that is very vulnerable to thievery or treason. A one-time pad cipher requires printing and distributing pads of keys, and the situation is even worse than with a code, since each person who uses the cipher have a unique set of keys.
* It must be emphasized how important it is to only use a one-time pad key once, and then throw it away. If a large number of messages are enciphered using the same key, of course they can be directly cracked using superimposition. However, even if only two messages are encrypted with the same one-time pad key, the ciphertexts are no longer theoretically unbreakable. The two messages could be cracked by a simple, if hideously exhausting, brute-force exercise in multiple anagramming, trying all possible arrangements of plaintext that make sense in one message, determining the key that produces that text, and then using that key to decrypt the other message and see if the result is also something that makes sense.
In practice, a much smarter approach would be used, based on the probable word method. At the very least, the messages would contain common words such as "the". Holmes could assume that one message consisted of nothing but the plaintext word "the", determine the key that would produce such a message, apply that key to the second message, and see if any strings that looked like text actually popped out. Those strings in the second ciphertext could be used to identify plausible key sequences, which would then be applied to the first message to see if any strings that look like text pop out. This is clearly another word game from Hell, but the essential point is that the messages can be now cracked in principle.
* The requirement that a key only be used once makes the logistics of a one-type pad cipher system complicated, to say the least. While recent developments in cryptography, discussed at the end of this document, have provided tools that may in principle overcome this obstacle, during the 20th century printing up large numbers of pads and distributing them made the one-time pad cipher was an overwhelming job. It was even worse than distributing codebooks, since anyone who used a code could be given the same codebook, but everyone who used one-time pads to transmit (as opposed to receive) messages had to have a completely unique pad.
There are situations where a one-time pad cipher is workable; it has often been used in high-level communications, the sort used by the leaders of nations and top military officers. In other circumstances, such as battlefield communications, a one-time pad cipher is much too clumsy. Something else is needed for practical use.
Although one-time pad ciphers are unwieldy, the Soviets did use them for diplomatic communications. Their obsession with secrecy made them willing to tolerate the overhead. Unfortunately, due to their equally characteristic lack of resources and tendency to take shortcuts, they recycled their one-time pad keys. This might not have proven fatal. Although recycling keys will undermine the theoretical security of a one-time pad cipher, the practical barriers to deciphering messages still remain enormous. For example, if thousands of messages are sent using a one-time pad cipher, it is still very hard to determine which messages are enciphered with the same key.
However, the Americans threw many resources at the problem, and eventually cracked Soviet diplomatic ciphers for the period from 1942 through 1947. This feat was all the more significant because the documents were coded as well as enciphered. The decrypted documents were part of what were known as the "Venona Papers", and were a goldmine for US intelligence. The Venona Papers are discussed in more detail later.
* As a footnote to the subject of one-time pads, it was discovered in the 21st century that the one-time pad had been invented twice. Steven Bellovin, a professor of computer science at Columbia University in New York with a background in cryptosystems, liked to collect old codebooks, and on a visit to Washington DC he decided to look up old codebooks in the Library of Congress.
While checking through the card catalog, Bellovin found a reference to an 1882 document titled "Telegraphic Code To Insure Privacy And Secrecy In The Transmission of Telegrams" by Frank Miller, a Sacramento banker in Sacramento who later became a trustee of Stanford University. Bellovin looked through the preface of the book and found to his astonishment that Miller was outlining the basic concept of the one-time pad. Bellovin looked around the internet, found no reference to Miller's work, and realized he'd stumbled on to a lost treasure.
Miller simply proposed the concept as an idea and didn't pursue its implementation; it appears that he didn't even realize that his cryptosystem was unbreakable. Nobody paid any attention to it, and it was forgotten. Or was it? Miller was a Union Army veteran and had an interest in army affairs; the society pages of THE SAN FRANCISCO CHRONICLE indicate that in 1907 Miller attended a military ball at the Presidio Army base in San Francisco -- with one of the other attendees being Parker Hitt. Could Miller have given Hitt a germ of an idea that was eventually handed on to Vernam, who finally put it into practice? Without more lost treasures coming to light there's absolutely no way of knowing, but it's an interesting thought.
* As another footnote, generating a truly random string of letters is tricky. Anyone who has ever played with a computer random-number function, for example to generate data for testing software, knows that such functions necessarily work in a predictable way. This is because a computer operates by fixed rules, and any algorithm that operates by rules isn't truly random, though the pattern may be very hard to second-guess.
Usually, a computer random-number generator function is "seeded" with some derivative of the time of day as provided by the computer's real-time clock, but this will yield a finite number of possible seeds, and so a finite number of random-number sequences. It may be very hard to second-guess any one of the sequences, but they are still not random, and are actually generally referred to as "pseudo-random" number generators.
Humans are not very good at generating random sequences, either. For example, if you ask somebody to type a sequence of random letters, they will more often than not switch back and forth between their two hands, which leads to a result that is not truly random. The only real way to generate a truly random sequence is to obtain it from unpredictable physical phenomena.
For example, a purely mechanical way to generate a one-time pad key would be to roll a pair of dice, with each die a different color so they can be distinguished -- say, one white (W) and one red (R). The results of each throw are assigned a letter as follows:
: W R : ---------- : 1 1 A : 1 2 B : 1 3 C : 1 4 D : 1 5 E : 1 6 F : 2 1 G : 2 2 H : ... : : 5 1 Y : 5 2 Z : 5 3 - : 5 4 - : ... : ----------
The two die have to be distinguishable since otherwise there would be no way to tell, say, the combination "1 2 = B" from "2 1 = G". Alternatively, one die could be thrown twice and the results listed in order of the throws. In any case, with each throw of the dice, the corresponding letter is written down to build up the one-time key. As the table shows, all throws of "5 3" and following are ignored. Since the probability of all the possible combinations is the same, discarding some throws will not skew the distribution of letters.
A more high-tech approach would be to measure the random noise voltages provided at a low level by a solid-state electronic device, and mapping the values into the letters of the alphabet.
BACK_TO_TOP
