THE CODEBREAKERS

by DAVID KAHN

  Yet where personal factors are less strongly engaged, cryptanalysis must assert itself as one of the most useful of intelligence sources. Its intermingling with other sources makes it difficult to gauge its own particular value to the American government. The message that by itself leads to results as spectacular as those of a Zimmermann telegram or a Yamamoto flight schedule must be exceedingly rare. The impact of cryptanalysis must come in the way that the falling of many snowflakes, each one imperceptible to the ear, adds up to make an audible hiss in a wood.

  Occasionally, however, instances occur in which the importance of cryptanalysis has been made manifest. One such case was Hamilton’s referring to “the letter in which Henry Cabot Lodge, then the American ambassador to the United Nations, expressed his appreciation to members of ALLO for information about the instructions sent by the Near East governments to their U.N. missions.” Another—which showed the unsung workers at N.S.A. that the highest official in the land appreciates their work—came on March 2, 1966, when career cryptanalyst Frank B. Rowlett received the National Security Medal in a White House ceremony from the hands of the President of the United States himself.

  What about other countries? Many of them do have cryptanalytic bureaus, particularly the older ones. Britain of course does; her General Communication Headquarters lies within her Foreign Office. Germany’s is likewise within her Foreign Office. France’s appears to be within her Ministère des Armées. It seems likely that about two thirds of the Latin American countries have codebreaking agencies, but few of the new nations of Africa do. Some Arab nations must have them, perhaps started by German cryptanalysts who went to the Near East after the war (but have reportedly since returned home). In Scandinavia, Sweden’s agency remains active. In the Far East, the cryptanalytic unit within Japan’s Naikaku Chosashitsu (“Cabinet Investigation Board”), a general intelligence agency, solved the codes of South Korea and exploited the information in political negotiations early in the 1960s so effectively that when South Korea found out, it stopped cabling messages to its negotiators and sent instructions by diplomatic pouch instead.

  But none of these can compare with N.S.A.—any more than the countries themselves can compare with the United States in any other field. It comes down, as always, to a question of economics. Though these smaller countries are usually chiefly interested in the cryptograms of their neighbors, they cannot maintain the worldwide intercept facilities that would give them different encipherments of circular messages that are often essential for modern cryptanalysis. They cannot get enough messages to make it likely that one of them will contain an encipherer’s error. They cannot support the large cryptanalytic organizations that alone can build the experience and resources to solve today’s machine ciphers. In many of these countries, the cryptanalysts are more gifted amateurs than professionals. Their governments are hard-pressed to build schools and irrigation systems. They do not have the money to buy electronic computers for their codebreakers. In cryptology, as elsewhere, success breeds success.

  Where, then, is the science headed? Are there any trends that can be foreseen? For there are fashions in cryptology as in other things. The onetime pad, very popular after World War II, has fallen out of favor. More popular now seem to be rotor machines—with from three to eight rotors—and Hagelin machines. For airplane and front-line messages, small codes seem to be common.

  Future developments may be foreshadowed by a U.S. Air Force statement that

  One of the primary Air Force communications security objectives is total security of AIRCOMNET [the basic wire and radio teletype network] at the earliest date. It is intended to accomplish this by means of link encryption. This is a system which is integral to the communications system and which automatically secures all links of the communications system by on-line synchronous devices. When total security of AIRCOMNET is achieved, two distinct advantages will occur:

  (1) Unclassified common-user traffic introduced into AIRCOMNET will not be vulnerable to unfriendly intercept and analysis. U.S.A.F. Security Service has repeatedly revealed, through analysis of clear text unclassified traffic now being handled over AIRCOMNET, vital information regarding the Air Force order of battle, disposition and employment of combat air power, functions of key personnel, and similar data.

  (2) It will be possible to introduce classified messages up to and including SECRET into AIRCOMNET, without first resorting to off-line processing.

  This is part of a more basic Air Force aim of a communications complex that will “provide full protection for information flowing within Air Force communications channels, including the exclusion of unauthorized entry into the systems. This goal will be approached, first, by providing COMSEC protection to each of the individual communications networks and later by providing total end-to-end encryption throughout the complex.”

  The Air Force drive toward total end-to-end encipherment carries with it a tendency toward a single all-purpose cipher, for such encipherment can most easily and most safely be applied by such a cipher. A single all-purpose cipher, simple enough for the lowest echelon, secure enough for the highest, variable enough to nullify the danger of capture or compromise, would eliminate or reduce many of the problems produced by the present multiplicity of systems—the need sometimes to reencipher a message in a system the ultimate recipient holds, the difficulties of storing, distributing, and accounting for half a dozen different sets of ciphers instead of for just one.

  One possible form of this ideal cipher—perhaps the most likely—is that of a system using a long, quasi-random key generated by mathematical methods and “added” to the plaintext, either numerically as with the one-time pad or electrically as with the Vernam method. A special-purpose computer might produce such a key from a few key digits, some of them common to the whole communications net and changing at fixed intervals, some chosen at random by the encipherer for each message and inserted at a prearranged place in the cryptogram.

  Many generating methods are possible. The simplest is chain addition. Successive digits of the priming key are added together and the sum tacked onto the end of the keynumber, forming part of it, and the process repeated with these digits. For example, with the priming key 3 9 6 4, 3 and 9 are 12, which is listed as 2, since all addition is noncarrying and tens digits are dropped; 9 and 6 are 5, and 6 and 4 are 0. These three figures join the key at its tail: 3 9 6 4 2 5 0. The process is then continued with 4 and 2, making 6, which is put on after the 0, with 2 and 5, making a 7 which is put on after the 6, and so on:39642506756321…. More complex methods are possible. The computer might multiply a base keynumber for the day by a message keynumber to ten places, then multiply the product by the basic key to ten places, that product again by the basic key to ten places, and so on, each time extracting the last four digits of each product as the final key.

  These systems are not unbreakable. Recovery of any portion of a chain-added key will yield the entire key, assuming the length of the priming key is known, or one of several possible keys, assuming that the priming-key length is not known. In more complicated systems, a probable word could yield a fragment of possible key which mathematical analysis could extend forward and backward for tests and possible solution.

  Nevertheless, if the key generation system could be made both sufficiently flexible and sufficiently complex, such a cipher might attain sufficient security. A computer the size of a transistor radio could produce a stream of digital pulses or numbers. Plugged into an ordinary teletype or a front-line pulse-code modulation scrambler, it could provide an on-line encipherment of sufficient security. This might be the cipher of the future, and thus cryptology would return in a more sophisticated way to a universal system, from which it has been divorced since the telegraph destroyed the nomenclator.

  But what about the field as a whole? The growth of political cryptology has been exponential since it began 4,000 years ago. Will new methods like lasers, which provide hard-to-intercept line-of-sight communications, reverse that t
rend for the first time?

  Probably not. Radio’s advantage in establishing out-of-sight communication is so great that its use will probably continue to increase, just as communication and literacy itself always have. In any case, the advent of such techniques as the laser would merely shift the element of secrecy from cryptography to transmission security. It would not diminish the amount of secrecy in communication. Though in the past the amount of secrecy—the amount of cryptology, in other words—has always grown as rapidly as communication itself has, the secrecy comes not from the communication but from politics, from statecraft, from the governments who apply and seek to remove that secrecy. The future of cryptology contains many questions of technology, but the waxing or waning of the field as a whole is not among them. That question is human.

  * The Report from the Senate Committee on Armed Services recommending passage of the bill (S. 277) was submitted byLyndon B. Johnson.

  * This has led to abuses. One 17-year-old girl, trying to get a job as clerk-typist with N.S.A., was asked many over-intimate questions about her sex life.

  Sideshows

  20

  THE ANATOMY OF CRYPTOLOGY

  CRYPTOGRAPHY AND CRYPTANALYSIS are sometimes called twin or reciprocal sciences, and in function they indeed mirror one another. What one does the other undoes. Their natures, however, differ fundamentally. Cryptography is theoretical and abstract. Cryptanalysis is empirical and concrete.

  The methods of cryptography are mathematical. “It would not be an exaggeration to state that abstract cryptography is identical with abstract mathematics,” declared Dr. A. Adrian Albert. Maurits de Vries, a Dutch statistician and theoretician of cryptology, wrote of cryptography: “The transformations are generally of a simple mathematical nature. E.g. permutations in the set of primary elements (the alphabet); coordinate transformations of lattice points; addition and subtraction in finite rings; linear algebraic transformations…. A simple example of such a secrecy-transformation is: y = ax @ b, where x represents a letter of the message; y is the resulting letter of the cryptogram; a and b denote constants which determine this particular transformation. Calculations with the letters are easily carried out after defining a suitable algebra.”

  Thus the operations and results of cryptography are as universally and eternally true as those of mathematics. Within the “suitable algebra” of the ordinary 26-letter Vigenère, it would be as logically impossible to deny that plaintext b keyed with C yields D as to deny that 1 @ 2 = 3. And this holds on Mars in the 25th century as equally as in France in the 16th. Different ciphers, like different geometries, yield results that are different but equally valid.

  The situation is not at all the same with cryptanalysis. Its methods are those of the physical sciences. They rest, not upon the unchanging verities of mathematical logic, but upon observable facts of the real world. The cryptanalyst must obtain these data by experiment, by measurement. Unlike the cryptographer, who can deduce any enciphering equation in Vigenère from a few initial conditions without recourse to any further experience, the cryptanalyst cannot tell from any number of statements about English which is its most frequent letter. He has to count the letters. The facts may be constants, but they are not logical necessities. They depend upon circumstance, upon reality.

  Philosophy offers a useful distinction between statements like those of cryptography and statements like those of cryptanalysis. The statements of cryptography, whose denial would be self-contradictory, are analytic. The statements of cryptanalysis, whose denial would not be self-contradictory, are synthetic. It might even be said that cryptography deals with noumena, cryptanalysis with phenomena.

  The empirical nature of cryptanalysis appears in its operations. These consist of the four steps of what is commonly called the “scientific method,” which scientists apply in attacking problems in the natural sciences. They are: analysis (such as counting the letters), hypothesis (x might be e), prediction (if x is e, then some plaintext possibilities should emerge), and verification (they do) or refutation (they don’t, so x is probably not e), either case starting a new chain of reasoning. (This common ground of scientific method between cryptanalysis and other sciences validates such metaphorical statements as “He sought to decipher the history of the earth from layers of rock.”)

  Within this general format, cryptanalysis operates in two ways, deductive and inductive. Deductive solutions are those based on frequency analysis; they are the general solution for any cipher system. Inductive solutions are those based on probable words or on lucky occurrences, such as two cryptograms with the same plaintext; they are special solutions.

  Solutions based on frequency analysis move from a knowledge of letter frequency to an application of it to the cryptogram at hand. Reasoning that flows from the general to the specific like this is deduction. A typical syllogism in the frequency analysis of an English monalphabetic substitution would have as its major premise, “The most frequent letter in the cryptogram is probably the substitute for e,” as its minor premise, “x is the most frequent letter in the cryptogram,” and as its conclusion, “x is probably the substitute for e.” Since all languages have well-defined characteristics of letter frequency, this deductive pattern is known to apply to any cryptogram even before it is inspected. Such a solution is thus a priori in its nature. And because this kind of solution will always work, given enough text, it is the general solution.

  Inductive solutions, on the other hand, will work only when certain conditions are fulfilled. Because the cryptanalyst cannot tell whether those conditions are indeed fulfilled until after he has obtained the cryptogram and knowledge of its circumstances, inductive solutions are a posteriori in nature.

  If an enemy post radios a message just after it has been subjected to heavy fire followed by a tank assault, the cryptanalyst might well conclude that the cryptogram contains bombardment and attack in its plaintext. These are probable words, which he can use to jimmy open the cryptogram. (Common words such as the, that, and, and so on, which are probable in all texts because of their high frequency, do not constitute probable words in this sense.) The cryptanalyst’s reasoning issues from the numerous specific facts surrounding the message and crystallizes into a single conclusion concerning its plaintext. Such reasoning is inductive. So is the reasoning used in lucky-break, or special-case, solutions. Only after Painvin had noticed the identical bits and pieces of text in two ADFGX cryptograms could he assume that they both had identical plaintext beginnings and thus commence his cryptanalysis (which in this case might better be called a “cryptosynthesis”).

  Because probable words and special cases enable the cryptanalyst to bring extra information to bear, such solutions display great power and fruitfulness and are often the first to be achieved in new systems. But they are limited to particular situations, and so cryptanalysts seek the deductive general solution of frequency analysis that will always apply.

  The realization that cryptography was essentially mathematical, glimpsed by Babbage and de Viaris and Hill and others, and made explicit by Albert, afforded great insight into cryptography. It also paved ways to new solutions. In cryptanalysis, the principles of letter frequency gradually expanded to help solve ciphers that at first seemed outside their ambient (such as columnar transposition). When Friedman brought those principles within the broader field of statistics, cryptanalysts could train really powerful new guns upon ciphers. But even this great expansion of knowledge did not reach to the frontiers of cryptanalysis and there confront the phenomenon upon which cryptanalysis rests—the constancy of letter frequency. Shortly after World War II, however, a remarkable new theory emerged that has provided an explanation of that phenomenon and of the whole process of cryptanalysis itself. It has not had the practical effects that Friedman’s work has had, but it affords, for the first time, a thorough understanding of why cryptanalysis is possible.

  The astonishing stability and universality of the phenomenon of letter frequency is not often real
ized. Other activities besides cryptanalysis depend upon the fixity of letter frequency, and flouting it can cause economic losses. A demonstration of these matters leads through some amusing and little-known byways.

  In 1939, the Wetzel Publishing Company of Los Angeles issued a 267-page novel of but moderate literary merit but so distinctive that in its way it stands unrivalled by any other work in the entire history of the English language. Here is how the author summarizes his tale in his opening pages. The excerpt fairly illustrates the book’s unique feature:

  Upon this basis I am going to show you how a bunch of bright young folks did find a champion; a man with boys and girls of his own; a man of so dominating and happy individuality that Youth is drawn to him as is a fly to a sugar bowl. It is a story about a small town. It is not a gossipy yarn; nor is it a dry, monotonous account, full of such customary “fill-ins” as “romantic moonlight casting murky shadows down a long, winding country road.” Nor will it say anything about twinklings lulling distant folds; robins carolling at twilight, nor any “warm glow of lamplight” from a cabin window. No. It is an account of up-and-doing activity; a vivid portrayal of Youth as it is today; and a practical discarding of that worn-out notion that “a child don’t know anything.”