Code Warriors
Page 39
It was a system ripe for intellectual corruption for NSA to have so much influence in the highest circles of power without the responsibility for how its wares were used by its eminent customers, and its entrenched bureaucratic managers did not always have the integrity or courage to resist the temptation to place the agency’s interests above loyalty to the truth. From the cover-up of its mishandling of the Tonkin Gulf intercepts it was an evolution of degree but not of kind to the more serious political distortions of signals intelligence that occurred in the Reagan administration, when the White House simply edited out portions of intercepted air-to-ground voice communications of a Soviet fighter pilot who shot down a Korean airliner that had strayed into Soviet airspace in 1983, eliminating from the publicly released transcript evidence that the pilot had attempted to signal and warn the aircraft before opening fire; and then to the more egregious manipulation and out-of-context use of signals intelligence by the George W. Bush White House in falsely attempting to make the case that Saddam Hussein’s regime possessed weapons of mass destruction prior to the United States’ launching its invasion of Iraq in 2003.2
More subtly but perhaps of more lasting consequence, the Cold War froze in place expedients adopted to respond to the unprecedented demands of World War II that few imagined would ever become the normal way of business for the government of the United States, with its deeply rooted traditions of moral principle, openness, and the rule of law in international diplomacy, and of personal liberty and the right to privacy at home. What had been acceptable in wartime but anathema in peacetime became the norm for peacetime, too. Eisenhower in the middle of his presidency once tried to reassure himself that in adopting the methods of its adversaries America could still preserve its traditional beliefs in “truth, honor, justice, consideration for others, liberty for all”; he wrote a note to himself in which he suggested the way out was that “we must not confuse these values with mere procedures.”3 But procedures, after decades of repetition, tend to become values, like it or not. NSA’s unflagging technologically driven pursuit to “get everything” in the teeth of the Fourth Amendment principle that the burden of proof lies upon the government to establish particularized probable cause for a search; its self-justifying assurance that its business was always too secret to be disclosed to, much less judged by, the people of the democracy that employed it; its reflexive defensiveness that rejected outside criticism as thus inherently uninformed (or, worse, an attack on the honor of its employees)—all showed how far the Cold War calculus had reshaped assumptions.
No one contemplating the crimes of the Communist regimes against their own peoples, the repression of the human spirit that sacrificed generations to an abstract ideological belief, could doubt the worth of the victory gained. In the shadowy four-decade struggle, the Cold War offered little opportunity for moments of glory or exultation that World War II abounded with; the greatest victory was not getting the world blown up along the way so that it was possible for the peaceful end to come when it at last did. The cryptologic struggle that took place in the shadows behind the shadows was as morally ambiguous as everything about the Cold War, and if the breaking of the Russian one-time-pad systems in the 1940s was an echo of the soaring intellectual triumphs of the World War II codebreakers, most of what followed was a far more subdued achievement of quotidian and collective persistence rather than individual inspiration. But the American cryptologists of the Cold War deserve as much credit as anyone for the fact that Americans, Russians, and the rest of the world were never vaporized in a cloud of radioactive ash; without them it is hard to see that containment would have lasted long enough to matter.
Sir Francis Walsingham, the principal secretary to Queen Elizabeth I, who practiced the profession of intelligence long before it became a routine part of modern statecraft, remarked that “knowledge is never too dear.” If nothing else, NSA’s Cold War success stories—and they were many alongside the undeniable lapses—proved the wisdom of that maxim.
APPENDIX A
Enciphered Codes, Depths, and Book Breaking
Enciphered codes, whether they use one-time pads or books of additive key, are all based on the same simple and robust principle. Security is afforded by two steps that considerably complicate the task of cryptanalysis.
First, the message is encoded using a codebook that provides a (usually) four-or five-digit number for each word. In a one-part code, the words are numbered sequentially in their alphabetical order, which allows for the same codebook to be used for encoding (looking up the word to find its numerical equivalent) and decoding (looking up the number to find its linguistic equivalent). In a two-part, or “hatted,” code (because it is as if the words have been drawn out of a hat when assigning their numerical equivalents), the order is random, requiring separate codebooks for each operation: one in numerical order, the other in alphabetical order.
In the second step, which ensures that the same numeral does not stand for the same word in subsequent messages—thereby confounding any straightforward efforts by a codebreaker to guess the meaning of any particular numerical group—a series of four-or five-digit numerals is taken from a book or pad of randomly generated numbers distributed in advance to the sender and recipient, and these are used as additive (commonly, though loosely, also referred to as “key”) to obscure the code group values.
So, for example, to encipher the message MEET AT FOUR PM TUESDAY, the code clerk would first look up each word in his codebook and write down the code group numbers that stand for each of the words:
He would then choose a one-time-pad page, or a starting point in the additive book, and write out below the code groups the series of additive digits drawn in sequence from the page:
Finally, he would add together (digit by digit, in modulo 10, noncarrying addition) the code and key to yield the completed, enciphered message to be transmitted:
For transmission by telegram, it was the convention to convert the numerals to letters; cable companies charged less for messages containing letters, which were easier to check for accuracy and also avoided the more cumbersome and lengthy Morse code characters for numbers when transmitted manually (for example, U in Morse code is . .—, A is .—, while 2 is . .———, and 8 is ———. .). It was also customary to break the text into five-letter “words.” Using the substitution 0 = O, 1 = I, 2 = U, 3 = Z, 4 = T, 5 = R, 6 = E, 7 = W, 8 = A, 9 = P, the cipher text in the example becomes:1
The recipient would reverse the process: first subtracting off the additive key, then looking up the meanings of the underlying code groups in the codebook.
The first step in breaking an enciphered code is to locate depths; that is, two or more messages enciphered with the same stretch of additive key. In a true one-time-pad system, there will be no depths to be found: the pad pages are used but a single time, then destroyed, so no two messages are ever enciphered with the same key. But in additive book systems, or one-time-pad systems that contain accidentally duplicated pages, as was the case with the Soviet messages read in the Venona project, depths can sometimes be found through laborious machine-aided searches. The method used in World War II against the many Japanese army and navy enciphered codes and at the start of the Venona project involved IBM punch card runs to look for so-called double hits. The idea was that if the same pair of numerical groups occurred the same number of groups apart in two different messages, this was unlikely to be chance, but could indicate that the two messages contained the same pair of words enciphered with the same run of additive key. (A single hit by contrast did not mean much, as chance alone dictated a one-in-four probability that any two fifty-group messages would have one four-digit numeral in common: in one message 4998 might stand for the code group 1235 plus the additive group 3763, in another it might stand for the code group 7723 plus the additive 7275.)
The still-laborious IBM method used in the 1940s involved punching a card containing the first five or so cipher groups of each of tens of thousands of messages (the
opening groups were the most likely to contain stereotyped phrases such as addresses, message numbers, and the like), running the cards through a sorter to place them in numerical order by the first group, then printing out indexes hundreds of pages long which would be scanned by eye to see if any two messages that shared the same first group also had another group in common in another position. The whole process was then repeated with the cards reordered according to the second code group, another index printed, and again scanned by eye.
From two messages in depth, it was possible to calculate the differences in values between the underlying code groups, since subtracting two messages enciphered with the same key eliminated the key from the equation altogether. For example, from two messages placed in depth on the basis of a double hit (of the cipher groups 8596 and 1357):
Then other message pairs placed in depth could be examined to see if any of those same differences occurred in them, too, which would suggest that the same pair of words appeared there as well. Commonly occurring words like STOP, TO, or FROM, and special code groups standing for numerals or indicating “start spell” or “end spell” were the most likely candidates to be identified first. In a one-part code, the book breaker’s job was made considerably easier by the fact that the numerical value of a code group relative to other recovered words greatly narrowed the range of alphabetical possibilities of words to consider. But in any case the task required deep familiarity with grammar and usage in the target language. The Jade codebook used with the 1944 and 1945 NKGB one-time-pad messages (also known as Code 2A by Arlington Hall) was a one-part code, and was recovered entirely through Meredith Gardner’s book breaking without ever seeing the original. Code 1B, the NKGB codebook that the Russians called Kod Pobeda and which was used from 1939 to November 1943, was a two-part code, and the recovery of a copy of most of the original book by TICOM Team 3 played a significant part in the effort at NSA beginning in the mid-1950s to break most of the 1943 messages.2
APPENDIX B
Russian Teleprinter Ciphers
Captured TICOM documents on the German cryptanalysts’ work on the Russian teleprinter cipher (known to the Germans as Bandwurm and to the British as Caviar or the Russian Fish) mentioned that the machine appeared to be similar to the “left portion” of the Germans’ SZ40 teleprinter scrambler. It employed a system of five cipher wheels, each of which corresponded to one of the five bits of the Baudot code, to produce a random sequence of marks and spaces as it rotated through each successive position.1 The output of this bank of key-generating wheels thus corresponded to a single Russian letter in the Baudot code. When that key letter was combined, by noncarrying binary addition, with the plaintext letter, it produced the enciphered letter that was transmitted.
Because the wheels moved to a new position as each letter was sent, the resulting cipher was polyalphabetic: the letter Я might stand for Ш at one position of text, but could stand for И, Н, Л, or any other letter at any another position. The brilliant part of the system was that because noncarrying binary addition is the same as subtraction, exactly the same setting of the machine could be used for both enciphering and deciphering: adding plaintext to key yields cipher text; adding cipher text to key yields plaintext. The basic rules for this noncarrying, modulo 2 addition are the same as the logical exclusive—or:
• + • = •
• + X = X
X + • = X
X + X = •
Thus the bit-by-bit addition of text and key works the same forward and backward; for example:
For the same reason, any number added to itself in modulo 2 addition equals zero. So if two messages are in depth—enciphered with the same sequence of key—then adding the two streams of cipher text together zeroes out the key altogether, leaving a string that is the combination only of the two underlying plaintexts:
A report prepared by one of the captured German cryptanalysts for the TICOM investigators provided a table showing the letter produced by adding (or subtracting) any two other letters in the Russian Baudot code; using the table, it is a straightforward matter to find the sum of two streams of cipher text in depth:2
A cipher square produced by captured German cryptologists, showing the rules for adding (or subtracting) letters in the Russian Baudot teleprinter code.
The next step is to try a piece of likely plaintext—a “crib”—for one message and see if it yields a plausible word (or portion of a word) in Russian in the corresponding message, again using the addition table to combine the plaintext with the stream of summed cipher texts. For example, trying в москву (“to Moscow”) at the start of one message:
yields очень cpo in the second message, which could be the start of the phrase очень сроно (“extremely urgent”); filling out the rest of the letters of the phrase and then working back to the first message:
reveals additional letters in the first message—номе, which looks like the start of the word номе, “number.” By continuing this seesawing back and forth between the two texts, it is possible with a bit of luck and knowledge of the language to decipher the complete texts of both messages.
Finally, by combing the recovered plaintext of either message with its original cipher text, the actual sequence of key the machine generated to produce the encipherment can be established:
With enough recovered key, the next step would be to look for repetition cycles in the sequence of marks and spaces in the key stream to begin to reconstruct each cipher wheel and its movement pattern. Once the key-generation system is solved, a general solution of traffic is then possible by using special-purpose analytical machinery or a digital computer to “slide” an intercepted cipher text against all possible key sequences to find the setting that produces likely plaintext or other statistical measures of a correct placement: this was the method the British GC&CS developed for the special-purpose electronic comparator Colossus to implement in its successful breaking of the German Tunny teleprinter cipher during World War II.3
APPENDIX C
Cryptanalysis of the Hagelin Machine
Unlike the unpredictable cipher alphabets generated by rotor machines such as the Enigma, the Hagelin machine’s encipherment rules followed a simple pattern. The twenty-six different cipher alphabets it employed were generated by simply sliding the letters of an alphabet in reverse Z-to-A order against another alphabet in A-to-Z order.
That meant that if one knew the plaintext equivalent for a cipher letter at a given position of the machine, one automatically knew what every other cipher letter at that same position stood for (which was emphatically not the case with the Enigma). The Hagelin’s encipherment formula could be written arithmetically as a simple subtraction rule, where the key is a number from 0 to 25 and the letters of the alphabet are given by A = 0, B = 1, C = 2, D = 3, etc.:
cipher = key – plain (modulo 26)
plain = key – cipher (modulo 26)
(In modulo 26 arithmetic, the resulting number always remains in the range 0 to 25; so, for example, –1 modulo 26 equals 25; –2 equals 24.)
If two messages were in depth—enciphered with the exact same key sequence—then subtracting one from the other eliminated the key from the equation altogether (just as was the case with the example of the Russian teleprinter cipher in appendix B), leaving only the difference between the plaintext values of each:
The twenty-six cipher alphabets employed by the Hagelin M-209 machine. The letters inside the grid are the cipher text equivalents of the plaintext letters across the top of the table for each key value from 0 to 25.
Because of the strict alphabetical order followed by the Hagelin’s cipher alphabets, this meant that for two messages in depth, the plaintext letters of each had to be the same distance apart in the alphabet as were the corresponding cipher text letters at that same position. (For example, if the cipher letters of two messages in depth were A and D at a given position, the plaintext letters they stood for had to be four letters apart as well, such
as B and E, C and F, or Z and C.) The final step in breaking two such paired messages was to “drag” a crib of likely plaintext through every possible position in one message and see if it produced readable plaintext in the matching message. In breaking some Dutch Hagelin traffic in 1944, U.S. Army codebreakers, for example, located two messages in depth whose cipher texts included these sequences:
J E Y M C P A
X H J S T C K
Converting the letters to their numerical values and subtracting, modulo 26, to eliminate the key yielded the following differences between the two strings of plaintext values:
14 3 11 6 17 13 10
Thus, if the first plaintext letter of one message was N, the corresponding letter of the second message would have to come 14 letters earlier in the alphabet, or A. The cryptanalysts found that trying the word LETTERX in this location (“letter” is as good Dutch as it is English, and X was commonly used to represent a space following each word) produced good plaintext in the matching message: