by DAVID KAHN
In the first days of development, the Vernam keys took the form of loops of tape perforated with characters drawn from a hat, giving a random keytext. The engineers, who were rapidly learning about cryptology, probably from Hitt’s Manual, soon spotted the flaw in this. The Vernam system is a polyalphabetic. A 32 × 32 tableau may be set up with the 32 characters of the Baudot alphabet across the top as plaintext and down the side as keys. Because the Baudot alphabet is public information, the composition of the 32 cipher alphabets filling the body of the tableau would be known. Secrecy in the Vernam system thus resides entirely in its keys. Looped keytapes would pass through the Vernam mechanism at regular intervals, permitting a simple Kasiski solution, even though the key recovered would be incoherent. The engineers made the keytapes extremely long to increase the difficulty of such a solution. But then the keytapes became too hard to handle.
Engineer Morehouse surmounted these difficulties by combining two short keytapes of different lengths in a Vernam device as if one were enciphering the other and using the extremely lengthy output—called the secondary key—as the key for plaintext. If one loop were 1,000 characters long and the other 999, the one-character difference would produce 999,000 combinations before the sequence would repeat. Thus two tapes each about eight feet long would breed a key that would extend 8,000 feet on a single tape. This was a major practical improvement.
But Mauborgne recognized that even this system was not immune to cryptanalysis. The future Chief Signal Officer, then 36, was an extraordinary cryptanalyst. He had studied the subject at the Army Signal School with Parker Hitt, was thoroughly conversant with its techniques, had devised a solution for the hitherto unsolved Playfair, and almost certainly knew of Friedman’s Riverbank Publications, including No. 17 on solving running-key. cryptograms. He therefore saw that heavy traffic raised the possibility of a Kerckhoffs superimposition, even with the two-tape system. Moreover, probable words would enable the cryptanalyst to recover the secondary key. He could then test the various possibilities for the two primary keys at intervals of 999 and 1,000 letters, and so gradually build them up. Mauborgne demonstrated this to the A. T. & T. engineers with the keywords RIFLE and THOMAS.
Mauborgne had himself perhaps participated in work at the Army Signal School several years earlier that had concluded (before Friedman’s solution) that the only safe running key was, in Parker Hitt’s words, one “comparable in length with the message itself.” Mauborgne’s study of the A. T. & T. system brought this home to him more forcefully. Any repetition of any kind in the keys of cryptograms under analysis imperils them and perhaps dooms them to solution. It does not matter whether the repetitions lie within a single message or among several, arise from the interaction of repeating primary keys or from the simple repeating of a single long key. Repetitions in the key could not be permitted. At the same time, Friedman’s work had demonstrated that running keys could not be intelligible. To avoid the Scylla of repetition and the Charybdis of intelligibility, keys would have to be, Mauborgne realized, both endless and senseless. He therefore welded together the randomness of the key, created, perhaps almost accidentally, by Vernam, and the nonrepetition of the key, discovered by the Army Signal School cryptologists, into what is now called the “one-time system.” It consists of a random key used once, and only once. It provides a new and unpredictable key character for each plaintext character in the whole ensemble of messages ever to be sent by a group of correspondents.
And it is an unbreakable system. Some systems are unbreakable in practice only, because the cryptanalyst can conceive of ways of solving them if he had enough text and enough time. The one-time system is unbreakable both in theory and in practice. No matter how much text a cryptanalyst had available in it, or how much time he had to work on it, he could never solve it. This is why:
To solve a polyalphabetic cipher is essentially to gather all the letters that are enciphered in a single alphabet into a homogeneous group that may be studied for its linguistic traits. The techniques of this collection differ, as do the kinds of keys. Thus a Kasiski examination sifts out the identically keyed letters in a repeating key. A running key with a coherent text can be solved by reciprocally reconstructing the plaintext and the keytext. A running key with a random text used in two or more messages succumbs to a simultaneous reconstruction of the two plaintexts, one checking the other. Other polyalphabetics, such as the autokey and the two-tape system, engender specialized solutions that stem from their own peculiarities. The monalphabetically enciphered letters that are the goal of these techniques also exist in a Vernam one-time system cryptogram because the 32 available cipher alphabets are used over and over again. But the cryptanalyst has no way of sorting them out because the key in a one-time system neither repeats, nor recurs, nor makes sense, nor erects internal frameworks. Hence, his methods, all based in one way or another on these characteristics, all fail. The perfect randomness of the one-time system nullifies any horizontal, or lengthwise, cohesion, as in coherent running key or autokey, and its one-time nature bars any vertical assembly in Kasiski or Kerckhoffs columns, as in keys repeated in a single message or among several messages. The cryptanalyst is blocked.
How about trial and error? It seems as if brute testing of all possible keys, one after another, would eventually yield the plaintext. Success this way is an illusion. For while exhaustive trials would indeed bring out the true plaintext, they would also bring out every other possible text of the same length, and there would be no way to tell which was the right one. Suppose that the cryptanalyst deciphers a four-letter military message with every key, beginning with AAAA. He strikes plaintext at key AABI: kiss. Unlikely in this context. He presses on. Key AAEL yields plaintext kill. Better—but he wants to make sure. He continues through key AAEM, giving kilt, which might be an oblique reference to a Scottish maneuver, and AAER, kiln. Further down the line he reaches fast at GZBM and slow at KHIA, stop at HRIW and gogo at XSTT, hard at PZVQ and easy at RZBU. He finds when he ends at ZZZZ that he has merely compiled a list of every possible four-letter word—the hard way. He can no more pick the right solution from this list than he can from a dictionary of military terms. The key does not help in limiting the selection because, since it is random, any group of four letters is as acceptable a keytext as any other. The worst of it is that the possible solutions increase as the message lengthens. There are only three possible solutions for a one-letter cryptogram, but dozens for those of two letters, and zillions for those of 100.
A final hope flickers. Suppose that the cryptanalyst obtains the plaintext of a given cryptogram, perhaps through theft or the error of a radio operator. Can he use the key that he can recover to determine the system on which that key was built, and so predict future keys? No, because a random key has no underlying system—if it did, it would not be random.
These are empiric proofs. It is possible, however, to demonstrate a priori that the one-time system is unbreakable. This constitutes the proof that it is theoretically unbreakable.
In essence, the Vernam encipherment constitutes an addition—an addition based on the Baudot alphabet, but an addition nonetheless. Suppose then that the plaintext is 4 and the key is 5. The ciphertext will be 9. Now, given only this, the cryptanalyst has no way of knowing whether it results from the addition of 7 + 2, or 6 + 3, or −2 + 11, or 4 + 5, or any other of the 32 possible combinations. Generalized, the situation is x + y = 9. Mathematicians call this an equation in two unknowns, and a single such equation has no unique solution. Two equations with the same two unknowns are required. The onetime system prevents the cryptanalyst from ever bringing two or more such equations together. The utter absence of any pattern whatsoever within its key precludes him from finding two occurrences of a given key character by reconstructing a pattern. And the tape’s exhaustless novelty makes it impossible for him to locate these occurrences in any key repetitions. The cryptanalyst is thus denied any chance of getting additional information to delimit one of the unknowns; he is
left with all 32 possibilities for the key character, and consequently all 32 for the plaintext. True it is that in the cryptanalytic case of an equation in two unknowns, some solutions are more probable than others. Thus, there is a 12 per cent chance that the plaintext unknown is e, an 8 per cent chance that it is t, and so on down the frequency table. But this does not answer the cryptanalyst’s question, for it does not specify which of these probabilities is actually present in the individual case before him.
So the answers again evade the cryptanalyst. Formless, endless, the random one-time tape vanquishes him by dissolving in chaos on the one hand and infinity on the other. Here indeed the cryptanalyst gropes through caverns measureless to man. His quest is Faustian; who would dare it would know more than can be known.
Why, then, is this ultimate cipher not in universal use? Because of the stupendous quantities of key required. The problems of producing, registering, distributing, and canceling the keys may seem slight to an individual who has not had experience with military communications, but in wartime the volumes of traffic stagger even the signal staffs. Hundreds of thousands of words may be enciphered in a day; simply to generate the millions of key characters required would be enormously expensive and time-consuming. Since each message must have its unique key, application of the ideal system would require shipping out on tape at the very least the equivalent of the total communications volume of a war. In fact, however, considerable extra key material would have to be supplied. A group of subordinate units may possess some tape in common for intercommunication, but once one unit uses a roll of keytape, the others must cancel their identical rolls. In practice, this step is the most difficult. It is virtually impossible in the hubbub of battle to monitor the messages of a dozen other units to determine what keytapes they have used.
In general, the physical problems bar employing a one-time system in a fluid situation, such as military operations in the field. These difficulties do not hold for more stable situations, such as exist at high military headquarters, at diplomatic posts, or in a two-way spy correspondence—and in such situations one-time systems are practicable and are used. Even here, however, difficulties arise if traffic volume is heavy.
Such was the case when Mauborgne, in the first large-scale trial of the Vernam system, set up machines in Hoboken, Washington, and Newport News, and soon had as many as 135 messages a day flying between them with speed and reliability. Even with this relatively low volume, it apparently proved impossible to produce sufficient key for a one-time system. Consequently, Mauborgne fell back upon the Morehouse two-tape system as the next best thing. In May, 1918, he paved the way for the first cryptanalytic test of the several keying procedures of the Vernam system when he told Bancroft Gherardi, assistant chief engineer of the telephone company, about Fabyan’s Riverbank Laboratories.
“I am not a cipher expert,” Gherardi wrote Fabyan on June 11, enclosing seven test cryptograms, “and would not presume to say what can and cannot be done, but should you and Professor Friedman decipher messages Nos. 1, 5, 6, and 7, I shall feel that I owe you both a good dinner. I have no doubt that you can decipher Nos. 2, 3, and perhaps 4. These, however, as you understand, are not the arrangement which we propose.” Friedman was overseas in G.2 A.6, but soon after his return he solved Messages 2 and 3, and part of 4. Since all three used the same portions of a single keytape of 2,000 random characters (except that 4 ran longer), a tentative recovery in one could be tested against the others by deciphering with the resultant key. Messages 5, 6, and 7 were enciphered with the two-tape system, started at different points, and though Friedman seems not to have broken these, owing to their brevity, he did solve the messages in the tri-city traffic, which used the same system. No. 1 was enciphered in the true one-time system. It shared its random keytape with no other messages. And it, of course, was never solved.
In September of 1918, Vernam himself went down to Washington to file his patent application on Friday the 13th. The war ended without any widespread application of the system before the patent—No. 1,310,719, and perhaps the most important in the history of cryptology—was granted on July 22, 1919. But A. T. & T. also saw possible peacetime profits in the invention. On October 21, 1920, the company demonstrated it before foreign postal officials at the Preliminary International Communications Conference by radioing Vernam-system cryptograms from New York to Cliffwood, New Jersey, and wiring them back again. On the afternoon of February 9, 1926, Vernam delivered a paper and ran his machine before the midwinter convention of the American Institute of Electrical Engineers in New York.
But though the device was an engineering success, it proved a commercial failure. Cable companies and business firms, which A. T. & T. hoped would buy cipher attachments for its teletypewriters, passed it over in favor of the old-fashioned commercial codes, which substantially shortened messages, thereby cutting cable tolls, and which gave a modicum of secrecy as well. The armed forces budgets had shrunk to their peacetime tightness; cryptologically, the physical difficulties forced Army communicators back onto the two-tape system, and the demonstrated solvability of this threw the whole Vernam arrangement into temporary limbo.
At about the same time on the other side of the Atlantic, cryptologists saw things differently. Three experts in the German Foreign Office—Werner Kunze, who was strongly mathematical in his approach; Rudolf Schauffler, an all-round cryptologist who specialized in East Asian languages and later received a doctorate in mathematics; and Erich Langlotz, who had been educated as a chemist and was more involved in the practical problems than the others—were given the task of providing security for their own diplomatic communications. Enciphered code was then the customary method for diplomatic communications. Often the encipherment took the form of an additive. The numerical codegroups of a diplomatic or military code were disguised by adding to them a numerical key, usually fairly long. For example, to the placode 3043 9710 3964 3043 …, the code clerk would add the key 7260 0940 5169 4174 … by noncarrying addition (tens digits are neither written down nor carried). The result, 0203 9650 8023 7117 …, effectively conceals the repeated 3043 in the original message. Kunze, at least, was well aware of the difficulties of affording secrecy: he was then scraping a non-additive superencipherment from a French number code that employed 40 or 50 two-digit encipherment tables.* The trio studied ciphers with longer and longer additives and they eventually concluded that the only system that is absolutely unbreakable is the one with a random, nonrepeating additive key—the equation in two unknowns. Some time between 1921 and 1923 they instituted the system in the German diplomatic establishment.
It took the form of pads of 50 numbered sheets of legal-size paper, each with 48 five-digit groups distributed in eight lines of six groups each. The 240 digits were random, and no sheet duplicated any other. Each pad was entirely different from every other (except for its mate for deciphering purposes). The digits constituted the key that was added to the number groups of the German codes. Langlotz supervised the distribution of the pads, giving the embassy at Washington, say, one set for outgoing and another for incoming messages to and from Berlin, and similar double sets for communicating with all German legations. The code clerks used a different sheet for every message, tearing it off when they were through, and never using the same sheet twice. Thus, though the addition was done by hand and involved numbers as opposed to the Vernam electrical addition of pulses, the principle—and the unsolvability—was the same. It soon became known as the “one-time pad” system, the name by which systems using random, nonrepeating keys are now generally known, though the mechanical embodiment is sometimes called a “one-time tape” system. For the first time in history, the official communications of a government were absolutely secure against the prying eyes of others.
Not those of the United States, however. Though the system was invented in America, though an article by Vernam headed a convention issue of the important Journal of the American Institute of Electrical Engineers, though his talk was pi
cked up by the mass-circulation Literary Digest and the general scientific weekly Science, though Yardley brought Vernam’s device to the attention of a high State Department official, mentioned it in his sensational book, and later tried to embarrass the department into using it in a needling magazine article—despite all this, the United States remained blind to the unbreakable system.
The Army revived it in a hurry as SIGTOT when World War II loomed, but by then Vernam was well out of it. He had continued developmental work at A. T. & T. for several years. He improved his own system,* invented a device for enciphering handwriting during telautograph transmission, and came up with one of the earliest forms of binary digital encipherment of pictures—another precocious development. He was so good that he was grabbed off at a substantial raise by International Telephone and Telegraph Corporation’s cryptographic subsidiary, International Communication Laboratories, where Parker Hitt was vice president. Four months later the stock market crashed. Vernam, with no seniority, was soon out. He went to Postal Telegraph Cable Company, which merged with Western Union. His inventive spark flared from time to time, and he was granted 65 patents in all, among them such important noncryptologic items as the semiautomatic torn-tape relay system, the push-button switching systems, and finally the fully automatic telegraph switching system, all for the Air Force’s 200,000-mile domestic network.
