THE CODEBREAKERS

by DAVID KAHN

  He went back to the original 18 intercepts of the day, sliced them into 20 segments, and matched segment 5 to segment 8 in all of them. Sixty letter-pairs resulted from this juxtaposition, and Painvin took a frequency count of them—so many AA’s, SO many AD’s, so many AF’s, and so on. To his delight the count showed all the characteristics of a monalphabetic substitution. This indicated that the two columns indeed belonged together in the transposition block, for placing two wrong segments side by side would have resulted in a flattish count. It verified his original system assumptions as well as his transposition rough-out.

  He made a similar test with the 12-20 combination, and found an equally monoalphabetic count. The most frequent pair was DG, with a frequency of 8, probably representing plaintext e. But DG in the 5-8 coupling had a frequency of zero—impossible for German e. On the other hand, GD had a frequency of 8. Since Painvin did not know the order of the columns within each pairing, his arbitrary 5-8 order for the frequency count had probably reversed the letter-pairs respective to 12-20. To correlate them, Painvin reversed 5-8 into 8-5, turning its GD into DG, which, with its frequency of 8, was a much better candidate for e. The former DG became GD, frequency zero. Painvin could now set up a skeleton checkerboard—which he did on the basis that the coordinates would be taken in the order side-top—and could insert his plaintext values in it as he recovered them:

  How could the rest of the transposition block be reconstructed? Since the coordinates were taken repeatedly in the order side-top, side-top, side-top, and since the block had 20 columns, all the side coordinates would have fallen into the 1st, 3rd, 5th,… 19th positions during encipherment, and all the top coordinates into the even positions, thus:

  If, Painvin thought, the side coordinates could be separated from the top ones, this would separate the odd positions from the evens. The coordinate separation might be effected on the basis of frequency characteristics. The frequency of the side coordinate D should differ from that of the top coordinate D because the total frequency of the five letters in the D row should differ from the total frequency of the five letters in the D column. The same should hold true for the other coordinates. Hence the top coordinates should manifest a different frequency profile than the side coordinates.

  Painvin’s frequency counts showed that the columns of the cryptograms indeed separated into two groups: one with D as its maximum and G as its minimum, the other group with G as its maximum and F as its minimum. The first group, which included column 12, turned out to stand in the odd positions. Painvin then determined which odd went with which even by matching one with another; only correct pairings showed monalphabetic distributions. Simultaneously he began solving for actual plaintext and building up his checkerboard, and, after 48 hours of incredible labor, Painvin had cracked the first messages in the toughest field cipher the world had yet seen.

  His feat shows the cryptanalytic mind at its finest. Painvin spotted opportunities that many would have missed, and when he worked with one, he did not leave it until he had wrung it dry. This technique of extracting every drop of information from each phase of solution before moving on served well, for the cipher prickles with many defenses. Most stem from its fractionating nature—the breaking-up of a plaintext letter’s equivalent into pieces, with the consequent dissipation of its ordinary characteristics. The transposition then scatters these characteristics in a particularly effective fashion, while the dissipation, in turn, dulls the clues that normally help reconstruct the transposition.

  It is not surprising, therefore, that the Allies never developed a general solution for the ADFGVX. Cryptanalysis nearly always depended on the finding of two messages with identical beginnings or endings or some other quirk. This explains the apparent anomaly that although only ten keys covering as many days were ever recovered on the Western Front, approximately half the ADFGVX messages ever sent were solved: solutions were achieved only on the days of heaviest traffic. From the German point of view, the system was quick and easy, involving only two simple steps. Messages were doubled in length, but this disadvantage was somewhat offset by the presence of only six different letters in the cryptograms, making transmission faster and more accurate.

  By the time Painvin had achieved his first solution, the first German offensive had spent its force, and the volume of traffic had diminished. He rummaged through the piles of intercepts to find others with common endings or beginnings and began working on the messages of March 29, which were relatively abundant. On April 26, after three weeks of work, he finally broke through. Meanwhile the Germans again struck with surprise and forced the English back almost to the sea. But Painvin was now getting his feet on the ground, and the subsequent key recoveries came with increasing speed. It took only nine and a half days to discover the key for the April 5 messages. On the morning of May 29, he started to work on the messages of the day before, and two days later had their key. He took up the messages of the 30th at 4 p.m. on May 31 and was reading them at 5 p.m. the next day.

  By then the French had been dealt two unpleasant blows—one military, one cryptographic. Ludendorff had again managed to conceal the time and place of a major assault. Fifteen of his divisions fell by surprise on seven. A gray flood of Germans inundated the French positions in the heights of the Chemin-des-Dames and surged forward irresistibly until it lapped the banks of the Marne only 30 miles from Paris, almost submerging the Allied cause. At the same time, Painvin suddenly saw, on June 1, the ADFGX message complicated by the addition of a sixth letter, V. Probably the Germans expanded their checkerboard to 6 × 6. But why? For homophones to further blunt the frequency clues? Or to insert the ten digits? Painvin did not know.

  “In short,” he said, “I had a moment of discouragement. The last two keys of the 28th and the 30th of May had been discovered under conditions of such rapidity that their exploitation was of the greatest usefulness. The offensive and the German advance still continued. It was of the greatest importance not to lose [cryptanalytic] contact and in my heart I did not want to brusquely shut off this source of information to the interested services of the armies, which had become accustomed to counting on its latest results.”

  He opened his assault on the cryptograms of June 1 at 5 p.m. Three messages of that date all bore the same time group (00:05) and had all been sent from a transmitter with call-sign GCI. Painvin compared two of them, one to call-sign DAX, the other to DAK, that had almost identical texts of 106 letters each. But aside from indicating a keylength of 21, they led nowhere: they were too similar. He then compared the DAX cryptogram with the third from GCI, a message of 108 letters to DTD that closely resembled the others. These he cut into column segments as he had done with the messages of April 1. He obtained two roughed-out transposition blocks, whose key-order he still did not know.

  Painvin assumed, however, that the two plaintexts were the same except for the addition of a single element to the internal address of the DTD message. This would have pushed the identical portion two notches further back in the DTD block than in the DAX one. He had only to seek an arrangement of columns that would produce such a result. Within an hour he had found it:

  6 16 7 5 17 2 14 10 15 9 13 1 21 12 4 8 19 3 11 20 18

  The solution of the checkerboard followed quickly:

  The DAX plaintext read: 14 ID XX Gen Kdo ersucht vordere Linie sofort drahten XX Gen Kdo 7 (“14th Infantry Division: HQ requests front line [situation] by telegraph. HQ 7th [Corps]”). The DTD text was identical except for its being addressed 216 ID.

  Painvin completed his solution at 7 p.m. on June 2, and sent it at once to G.H.Q. By then the French had managed to halt Ludendorff’s push, but they teetered precariously on the brink of defeat. The Germans were shelling Paris from 60 miles away with their long-range guns. The great German successes of March and May had driven two vast salients into Allied territory. They pointed like daggers at Paris. And the great question recurred: Where would Ludendorff strike next? The thin Allied lines could not hold against a
massive piledriver blow concentrated on a single point. If Ludendorff could gain the same surprise that he had so successfully achieved in each previous assault, he could puncture the Allied defenses, overrun Paris, and perhaps end the war. The Allies’ only hope of stopping him was to absorb his thrust head-on with their reserves. But to do this they had to know where to send them.

  The French discussed the possibilities. Would Ludendorff lunge out directly for Paris from the tip of one of his salients despite the danger to their flanks? Or would he first flatten out the large dent between those bulges and then drive forward from a consolidated position? If the latter, where in the huge pocket would he strike? No one knew.

  Ludendorff, meanwhile, was having troubles of his own. German military doctrine called for a sudden, intense artillery bombardment to paralyze the defenders before the infantry attacked. This saturation technique required concentrating thousands of field pieces and tons of munitions at the battle-front. At a conference early in June, Ludendorff learned that this concentration was running behind the schedule he had set for his next assault. His successes had strained his lines of transport, and he had been moving his guns and shells only under cover of night to preserve the invaluable advantage of surprise.

  And this advantage he had conserved superbly. The hints that drifted out to French G.H.Q. about his intentions were multiple, petty, and contradictory. Nothing would jell. Gloomy intelligence officers could reach no definite conclusions. Another attack was certainly in the offing, but unless they could ascertain its location, France might be lost.

  Into this dismal atmosphere on the morning of June 3 burst Guitard of the Service du Chiffre, excitedly waving an intercept. One of the G.H.Q. cryptanalysts, applying the keys that Painvin had sent there, had just read a cryptogram sent at 4:30 a.m., only a few hours earlier:

  CHI-126 FGAXA XAXFF FAFFA AVDFA GAXFX FAAAG DXGGX AGXFD XGAGX GAXGX AGXVF VXXAG XFDAX GDAAF DGGAF FXGGX XDFAX GXAXV AGXGG DFAGD GXVAX XFXGV FFGGA XDGAX ADVGG A

  Direction-finders reported that it had been transmitted by the German High Command. The addressee, DIC, was known from traffic analysis and direction-finding to be the 18th Army’s general staff in Remaugies—a town situated just above the concavity in the German lines. Its plaintext read: Munitionierung beschleunigen Punkt Soweit nicut [error for nicht] eingesehen auch bei Tag (“Rush munitions Stop Even by day if not seen”).

  Guitard and the intelligence officers recognized at once that the ammunition mentioned in the telegram was that intended for the usual German preassault bombardment, and the location of the addressee of the message told them where that attack would come. Jubilantly they communicated their information to the operations officers: Ludendorff was going to hammer out the dent, and the German sledge would crash down onto the French line between Montdidier and Compiègne, a sector about 50 miles north of Paris.

  Aerial reconnaissance confirmed the daylight transport of munitions. Deserters reported that the onslaught would take place June 7. Foch, in supreme command, shifted his reserves into position, thinned out the front lines, upon which the brunt of the cannonade would fall, and braced his secondary defenses. On the 6th, officers were told that “the offensive is imminent.” Tension mounted. The 7th passed without enemy action, and the 8th: Ludendorff had postponed the attack for two days to bring up more guns and munitions because, he said, “thorough preparation was essential to success.” The French waited tensely but with confidence. At midnight on June 9 the front from Montdidier to Compiègne erupted in a fierce, pelting hurricane of high-explosive, shrapnel, and gas shells. For three hours a German artillery concentration that averaged one gun for no more than ten yards of front poured a continual stream of fire onto the French positions—and Ludendorff’s urgent demand for ammunition became clear. But this time, for the first time since Ludendorff began his stupendous series of triumphs, there was no surprise. Painvin’s manna had saved the French.

  A little before dawn 15 German divisions charged forward. The French were ready. For five days, fighting seesawed back and forth. Initially the Germans took the little villages of Méry and Courcelles, but on June 11, General Charles Mangin counterattacked with five divisions and all the elan the French could muster. He stopped the German advance cold and then swept the gray tide out of the two villages. Again the Germans heaved forward in a great effort. They failed with heavy losses. For the first time that spring, Ludendorff suspended an operation before it had achieved its goal. Mangin, wearing his gold-brocaded képi, laughed beneath the guns of victory. Foch, who realized that other German assaults would come and that he would have to defend against them, knew at last that he would some day take the offensive. He knew then that the war was not lost, and could eventually be won. Within a few weeks, the final German thrusts did come, but they had run out of steam, and the French parried them. Soon the initiative passed to the Allies, bolstered by the Americans, and their powerful counterstrokes drove the German armies back and back until the Kaiser, his militaristic dreams wrecked, abdicated and fled while his generals signed the Armistice at Compiègne. The World War was ended.

  For Painvin, who had lost 33 pounds while simply seated at his desk, there was a long leave of convalescence. Afterwards, he engaged in an immensely successful business career, becoming president and director general of Ugine, the chemical giant of France, president of a phosphate company, vice president of a commercial credit firm, administrator of a mortgage society, honorary president of the Union of Chemical Industries and of the central committee of the electrochemical trade, and president of the Chamber of Commerce of Paris. Yet, he said, none of these achievements ever gave him the satisfaction that his ADFGVX solutions did. They left “an indelible mark on my spirit, and remain for me one of the brightest and most outstanding memories of my existence.”

  The First World War marks the great turning point in the history of cryptology. Before, it was a small field; afterwards, it was big. Before, it was a science in its youth; afterwards, it had matured. The direct cause of this development was the enormous increase in radio communications.

  This heavy traffic meant that probably the richest source of intelligence flowed in these easily accessible channels. All that was necessary was to crack the protective sheath. As cryptanalysis repeatedly demonstrated its abilities and worth, it rose from an auxiliary to a primary source of information about the foe; its advocates spoke regularly in the councils of war. Its new status was exemplified in terms clear to every military mind when both Cartier and Givierge became generals. The emergence of cryptanalysis as a permanent major element of intelligence was the most striking characteristic of cryptology’s new maturity.

  Another was the change in cryptanalysis itself. The science at last outgrew the mode of operation that had dominated it for 400 years. This was chamber analysis, in which a single man wrestles with a single cryptogram alone in his room; John Wallis epitomizes the genre. Chamber analysis began to fail the cryptanalysts in the first days of the war. The German double transposition required at least two messages of the same length for solution, but a great many messages had to be intercepted before the law of averages would hatch those two. As cipher systems grew increasingly complex, cryptanalysis relied more and more on special solutions like this, and so they required many more messages for success than the bewigged practitioners of chamber analysis would have ever thought necessary. They also depended more heavily on such auxiliary aids as traffic analysis and knowledge of surrounding events, because the more that is known about the circumstances in which messages are sent, the easier solutions by special case become. Cryptanalysts thus became much more intimately connected with the real world.

  A third characteristic of the new maturity was the evolution of fields of cryptanalytic specialization. Systems of secret communication had ceased to be so few and so homogeneous that a single expert could subdue them all. Their multiplicity and heterogeneity, plus the volume of traffic in each, bred the specialist. Such, for example, was Childs, who worked
exclusively on ciphers, while others in G.2 A.6 attacked codes. Perhaps the most interesting specialist of all was the chief of the cryptanalytic office himself. No longer could he seclude himself in a quiet little world of letters and numbers as just the foremost among a group of cryptanalysts, like the English Decypherers. The more active cryptology of the 20th century impinged on so many more areas that the chief had to devote his energies exclusively to learning from other branches of the services what intelligence was most needed, disposing his team of codebreakers to get it, and obtaining information in the form of battle reports, cleartext intercepts, prisoner-of-war interrogations, captured documents, and the like that would help them in their special solutions. The chief had become purely an executive, who himself never picked up a colored pencil or an eraser for an actual solution, though he necessarily needed a thorough knowledge of the technique. His new responsibilities, of course, stemmed in large measure from cryptology’s upgraded position. But they also reflected the specialization now required in the burgeoning field, and this division of labor is as much a sign of maturity in cryptology as it is in a society.

  Still another sign of that maturity was the emotional apprehension of the role played by the blunders of inexperienced, indolent, and ignorant cryptographic clerks. Cryptologists had had an intellectual awareness of this danger at least since 1605, when Francis Bacon wrote that “in regards of the rawness and unskillfulnesse of the handes, through which they passe, the greatest Matters, are many times carryed in the weakest Cyphars.” But it was not until cipher key after cipher key, and code after code, had been betrayed by needless mistakes or stupidities or outright rule violations that the magnitude of the problem was borne in upon them. The problem had swollen to such proportions because so large a volume of messages had to be handled by so many untrained men—against whom were pitted the best brains of the enemy. The experts realized that to eliminate these is to strengthen cryptographic security more effectively than by introducing the most ingenious cipher. The great practical lesson of World War I cryptology was the necessity of infusing an iron discipline in the cryptographic personnel. Errors arising from ignorance can be reduced by explaining how enemy cryptanalysts take advantage of what appears to be the most trivial violation of the rules. Faults arising from laziness can be lessened by a monitoring service that finds and punishes offenders. Givierge enunciated the doctrine that must be impressed upon the cipherers: “Encode well or do not encode at all. In transmitting cleartext, you give only a piece of information to the enemy, and you know what it is; in encoding badly, you permit him to read all your correspondence and that of your friends.”