One-time Pad History Rewritten

Does the discovery in an old telegraph codebook rewrites the history of cryptography? Until now, Gilbert Vernam was generally accepted as the inventor of the unbreakable one-time encryption. His teletype system was later improved by Joseph Mauborgne and paper versions of the systems later became widely used for diplomatic and military communications.

Recently, Steven Bellovin, professor of computer science at the Columbia University School of Engineering, discovered a 1882 telegraph codebook in the Washington Library of Congress. This codebook, compiled by a Frank Miller, describes a superencipherment of telegraph codes by random "shift-numbers" that should not be repeated. Did Bellovin discover the proof that one-time pad was invented 35 years earlier? Should the history of cryptography regarding one-time pads be rewritten?

Let us first explain what was actually discovered. Telegraph codebooks were used extensively in the 19th century to reduce costs of telegrams by compressing words and phrases into codewords or into a combination of letters or digits. Codebooks did not provide any cryptographic security. Therefore, the codes were sometimes superenciphered (an additional layer of encipherment over the code) with a short key to improve its security. Miller's codebook contains 14,000 words or phrases (some are blanks) with their corresponding codewords and a serial number. So far, nothing special.

The codebook also provides instructions for a superencipherment. These instructions are what makes his work extraordinary. In his preface, Miller writes: "the sender and receiver must each cancel "shift-numbers" as soon as they are used". He further states that "if the senders finds that the addition of the key (to the serial-number) produces a sum greater than the highest serial number (14,000) in this book, he must deduct said last serial number (14,000) from said sum." If the receiver finds that the enciphered word "is less than the key which is to unlock it, he must temporarily add to said serial-number the highest number in this book (14,000) and deduct the key from the sum".

Now, let us recapitulate this: to calculate the ciphertext, the sender adds a key (the shift-numbers) to the plaincode numbers (serial numbers). When the total is more than 14,000, he subtracts 14,000. To decipher, the receiver subtracts the key from the ciphertext. However, if the ciphertext is smaller than the key, he first adds 14,000 to the ciphertext and than subtracts the key. This is essentially a modulo 14,000 additive cipher.

Further down, Miller describes the shift-numbers as "a list of irregular numbers" and "the difference between such numbers must not be regular". He also explains that when a shift-number has been used, it should be erased from the list and not used again. Next, some examples are given where words are replaced by their serial-number (plaincode) and a shift-number (key) is added.

This is clearly the essence of one-time pad encryption. Text is converted into numbers, a random key is added by modular arithmetic and the key should not be used again. Moreover, Miller explains that each correspondent should wirte his own shift-numbers list in black ink in a book and the correspondent's list in red ink upon the opposite page. He clearly distinguishes the black (encipher) and red (decipher) shift-numbers. By doing so, he avoids simultaneous use of the same shift-numbers, something that could occur when both correspondents use one single list of shift-numbers.

Unfortunately, Miller falls short in explaining that each shift-number should have a value between 0 and 14,000. He neither addresses the issue of generating truly random values. This could affect the security of the cipher as the user could be seduce into selecting smaller shift-values that don't require the cumbersome modulo 14,000 calculations. The complicated modulo 14,000 might well be the reason why his system never received the attention and success it deserved. Taking the individual digits of the serial numbers as independent, and applying a modulo 10 (add without carry, subtract without borrowing) would have been much easier and faster. We can only speculate about the reason why Frank Miller's one-time encryption never became publicly know.

Steven Bellovin speculates whether Miller's work might somehow, indirectly through Parker Hitt and Joseph Mauborgne, have reached Gilbert Vernam. However, Vernam, as an electrical engineer, approached the one-time encryption from an entirely different angle and discovered a completely different solution of teletype five-bit punched paper tapes using modulo 2 on each of its five bits. Fact is that Frank Miller's work disappeared in oblivion.

It is indisputable that Frank Miller was the first to invent the one-time pad encryption, albeit less practical than in its current form. 35 years later, Gilbert Vernam invented a completely different electromechanical cipher system that incidentally had the same mathematical properties as Miller's pencil-and-paper cipher. Finally, it were the German cryptologists Werner Kunze, Rudolf Schauffler and Erich Langlotz who developed a one-time pad system for use with pencil and paper, thus re-inventing Frank Miller's encryption scheme.

We may conclude that both Miller and Vernam independently invented one-time pad, and both deserve credit for the same achievement, although in a completely different form. But ultimately, we must acknowledge Frank Miller as the first to have invented the one-time pad concept. Sadly, as far as we know, his invention did not influence the history of cryptography. Nevertheless, history rewritten! And finally, not to be forgotten, Steven Bellovin can be credited for discovering the inventor of one-time pad. Congratulations, Steven!

More details about Miller's 1882 telegraphic codebook are found in Steven Bellovin's paper on Frank Miller (direct link to pdf). The history and use of one-time pads is found on my website. More on various old telegraphic codebooks is found on my post about the Nick Gessler collection.

First Strike

U.S Titan II missile in its silo
See video footage

It is always interesting to have a retrospective view on the Cold War history (yes, that's easy with hindsight) and see how accurate, or inaccurate, the assumptions were back then, influenced by the mind set of those days.

First Strike, the 1979 PBS documentary, is a good example of how assessment of one's own capabilities and of those of the opponent can trigger an enormous arms build-up in an era where disarmament and weapons control and limitations were the words of the day.

The documentary starts with a dramatization of a Soviet surprise first strike attack, destroying nearly all Minuteman missile silos, wiping nuke carrying B-52's from their runways and sinking nuclear submarines in their ports and at see. Crippling the U.S. Strategic Forces in minutes was a daunting prospect in those days, in fact, it still is, but one can question the accuracy of this scenario, and the capabilities of the Soviets in those days. Spicy detail: actual Air Force personnel and air force installations were used to film the documentary.

The fear for such a scenario was undoubtedly real, both in the U.S. and in the Soviet Union, but fear has often been a bad counselor. In the next part of the documentary, analysts from the Defense and Strategic Studies Program, Rand Corporation, Research and Development, and other think tank experts defended their what-if theories in the documentary. Pretty scary and risky statements and conclusions! Parts of the documentary were later used in the notorious 1983 movie The Day After (which even scared the hell out of Ronald Reagan). Both documentary and movie were very good at convincing tax payers, both in the United States, in Europe... and unfortunately also in the Soviet Union. War scare at its best.

As we now know, the fear was real, the facts and the estimated treat were not (the latter paradoxically later made itself come true). If fear did achieve one thing, then it were the exorbitant defense budgets on both sides, which eventually resulted in the collapse of the Soviet economy and the disintegration of the Soviet Union. The route chosen made many on both sides poor and a few very rich. Both sides never intended to strike first, both believed the other one would do so, and no one used its nukes.

Words could have done the job just as well, and much cheaper. One can discuss ages about the sense or nonsense of Assured Mutual Destruction and yes, it did the job, but there must have surely been better solutions, with less risk of escalation.

We did have a few close encounters of the third World War kind, as you can read in 1983 - The Brink of Acopalyps. Lessons learned? Who knows? Today's analysts still have a tough job with the current military and geopolitical situation.

More on the U.S. estimates on the Soviet strategic capabilities, and how it often deviated from Soviet reality, is found on my post on US Strategic Intelligence on the USSR. In my Farewell Dossier post you can read how the defense budget itself was used as a weapon to destabilize the Soviet Union. If you want to find out more on the Minuteman missiles, you can visit the Minuteman Missile National Historic Site website, with lots of information, images and interviews with Minuteman personnel. You can pay a virtually visit to a Minuteman Missile site with spherical panoramas (click-and-drag to move around). Below the documentary First Strike.

First Strike (Full)

Igor Gouzenko - The Man Who Revealed the Cold War

Igor Gouzenko

The defection of Igor Gouzenko is probably the one single case that truly marked the beginning of the Cold War.

One month after the end of the Second World War, the Allied forces were still celebrating their victory over Nazi Germany. During the war, the Canadian forces had been part of the second - Western - front against the German forces to relief the pressure on their Russian Allies in the east. Only four months earlier, the Americans and Soviets had shaken hands when they met at the River Elbe in Germany. Many innocently believed that this ended all hostilities and that they could pick up their lives from before the war.

Inside the Soviet Embassy

Meanwhile, Lieutenant Igor Sergeyevich Gouzenko had completed his second year as a cipher clerk in the Soviet embassy to Canada in Ottawa, Ontario. Gouzenko, then 26, was a member of the GRU (Soviet Military Intelligence). After returning from the Russian front two years earlier, he received training in coding and cipher work.

 

In June 1943 he was sent to Ottawa, where he lived with his wife and baby son in a small apartment. He worked at the embassy under GRU Colonel Nikolai Zabotin, who commanded 14 GRU officers that were involved in espionage operations against Canada. Gouzenko worked in the coding room, the inner sanctum of the embassy, where he was responsible for enciphering and deciphering of secret GRU intelligence messages between Ottawa and Moscow.

In August 1945, Gouzenko was instructed to return to Russia. Having tasted of the Western individual freedoms and being disgruntled about the Soviet intelligence operations against Canada, their former ally, he decided to defect and seek asylum for him and his wife and child. On the evening of September 5, 1945, he left the embassy, carrying 109 secret documents on Soviet espionage activities in the West. 

 

A Risky Defection

He approached the media and tried to contact the Minister of Justice but was initially turned down by all of them. The next night, fearing for his life, or at least apprehension by a Soviet team, Gouzenko hid with his wife and child at a neighbour, who notified the police. After the police caught Soviet officials breaking into Gouzenko's apartment, his story was finally taken seriously.
 

On September 7, the Royal Canadian Mounted Police took over the case and Gouzenko handed over the secret documents. The Gouzenkos were placed in protective custody and Igor was interviewed by Canadian officials, Britain's MI5 and the FBI. The 109 documents that Gouzenko took along from his GRU cipher office proved to be of exceptional intelligence value. They revealed a large Soviet spy operation to obtain military, scientific, and technological information, by whatever means, in Canada, Britain and the United States.

Gouzenko in 1948 (Source: CSIS)

Information, provided by Gouzenko and his documents, lead to extensive counter-intelligence operations and resulted in the apprehension of a series of spies and people who collaborated in some way with the Soviets.

But above all, these revelations shocked the intelligence communities, politicians and public opinion. No one expected such aggressive intelligence operations against their country from the former Soviet ally, nor could they have imagined the scale of infiltration in several Western intelligence agencies and bureaucracies. Igor Gouzenko's defection also had some unexpected and devastating consequences that surfaced only three years later.

Vigilant Soviets take Measures

Already before the Gouzenko case, American Signals Intelligence eavesdropped on Soviet encrypted communications and the codebreakers in Arlington Hall broke their cryptographic systems with great easy. In the first week after his defection, Moscow warned all its intelligence posts and agents abroad that their operations were compromised. This warning however was not picked up by the Americans, as they were unable to penetrate the Soviet intelligence communications.

Once Gouzenko's information was fully exploited, the U.S. could no longer openly use covertly obtained intelligence without disclosing their eavesdropping capabilities to their new Cold War enemy. The idea developed to release and use more sensitive communications intelligence with the Gouzenko defection as a plausible cover. The Soviets didn't know exactly what information Gouzenko actually compromised, and this could give the U.S. and Britain the opportunity to use critical information without disclosing to the Soviets that their cryptographic systems were breached.

Unfortunately, just as before the Gouzenko case, they did not consider a Soviet penetration of their own intelligence community. In fact, the Soviets did have several penetration agents inside different Western intelligence agencies. The irresponsible use of sensitive info, derived from encrypted traffic, tipped off the Soviets that their cryptographic systems were insecure. By 1948, Soviet sources within the U.S. codebreaking community had reported which crypto systems were read by the Americans.

Surprise Backlash

What did the Russians do? Nothing! To the outside world it seemed business as usual. Arlington Hall happily continued to eavesdrop on their new enemy. In reality, the Soviets had quietly initiated a large research program to vastly improve their communications security. They continued using the compromised systems but undoubtedly took their precautions and no longer gave away critical information over those channels. Then, on Friday, October 29, 1948, when the British and American eavesdroppers were busy as usual on their Russian targets, they suddenly suffered a complete black-out.

Moscow had secretly planned a complete makeover of all their communications channels. From one moment to the next, they introduced complex radio callsign and frequency schedules and all high-level communications changed to the unbreakable one-time pad encryption. Every single crypto system that the U.S. had been reading went silent. Previously unencrypted channels were now encrypted, and the new systems were a mystery. They no longer used the familiar crypto system indicators, leaving the eavesdroppers with no clues about who was using which system when, and for what messages.

It was a complete and unprecedented intelligence break-down. According to NSA, the Soviet communications changeover "came crashing down like a tidal wave on the beach of Anglo-American cryptology". This so-called Black Friday was a loud wake-up call. The Soviet Union had entered the battlefield of signals intelligence, and it was an impressive entry. It took the National Security Agency six years to even begin to recover from this slap in the face.

A New Life

The Gouzenkos were granted asylum and relocated under a new identity. Igor Gouzenko, who later appeared in several television interviews, was know for the white bag over his head that protected his identity (not a luxury, given the KGB's reputation with traitors). In 1948, Gouzenko's memoirs were published under the title This Was My Choice (see Amazon). Igor Gouzenko died of a heart attack in 1982 at Mississauga, Canada and was survived by his wife Svetlana and their eight children.

More on Igor Gouzenko is found on the Canadian Camp X website. On that page you also find Gouzenko's story "Stalin sent me to Spy School", published in the Coronet magazine (direct links to each page: [1][2][3][4][5]). On Videofact you can read Gouzenko's statement from one month after his defection.

CBC Digital Archives has an interesting interview with Svetlana Gouzenko (old archive), a CBC interview with his daughter Evelyn Wilson, who is also interviewed in Gouzenko Deciphered by Canada's History. Much more video and audio are found on the CBC website by entering "Igor Gouzenko" in their search box.

More on the Black Friday communications black-out is found in NSA's National Cryptologic School - On Watch (chapt 3, p19 (pdf page 25). The Canadian Intelligence Resource Centre has some excellent papers related to Gouzenko. The Gouzenko Affair Revisited; The Soviet Perspective is an interesting document.

Cold War Conversations has an interview with Evy Wilson, the daughter of Igor and Svetlana Gouzenko and with author Andrew Kavchak. Evy Wilson talks about her father, life at the secret Camp X in Canada, and growing up in the United States under a false identity.

I recommend Andrew Kavchak's commemorative page with many press articles. For an in-depth view on Gouzenko's story, Andrew wrote the book Remembering Gouzenk (available at Amazon US, UK and other countries). Below his fascinating presentation of "The Gouzenko Affair - The Start of the Cold War".

Gouzenko Affair - History Presentation (March 21, 2019)

The National Cryptologic School - On Watch

NSA main building at Fort Meade

The National Cryptologic School On Watch, Profiles from the National Security Agency's Past 40 Years, is a 76 page document that highlights some of the key moments in the history of the National Security Agency (NSA).

The document starts with Japan's last days of war and the transition from the different American wartime cryptology efforts into one post-war agency in Arlington Hall that controlled the Army Security Agency, the Naval Security Group, and the Air Force Security Service. However, the in 1949 created Armed Forces Security Agency (AFSA) lacked the power to enforce a real centralized coordination between the individual parts of the intelligence community.

Meanwhile, the 1945 defection of GRU officer Igor Gouzenko in the Soviet Embassy of Ottawa was used by U.S. intelligence as a cover to release communications intelligence. The Soviets however knew, through a source inside Arlington Hall, that their communications were not compromised by Gouzenko but by the vulnerability of their systems.

It was the start of a Soviet research program to improve their Communications Security, which resulted in the 1948 blackout of American and British intelligence on the Soviet communications. The sudden change in radio procedures and the use of one-time pads for all Soviet high level traffic was a disaster that took six years to overcome.

In 1949, AFSA codebreakers discovered the double use of one-time pads in old Soviet intelligence traffic, giving them various clues on Soviet infiltration of U.S. intelligence services. This initiated several counter-intelligence operations. The results of this operation, now called VENONA, eventually unveiled the Cambridge spy ring (Phylby, Maclean, Blunt and Burgess), atom bomb spy Klaus Fuchs and many other agents (see also VENONA Declassified).

AFSA's successor, the National Security Agency, was created in 1952. The United States finally had its centralised cryptologic intelligence agency.  The Korean War was NSA's trial of fire, which resulted in a dearly needed reorganisation of its communications capabilities. The explosion of the French-Vietnamese conflict and fear for Soviet expansion initiated a major SIGINT buildup in Southeast Asia in the early 1960's. It was soon followed by thousands of U.S. military advisors. In the 1964 Gulf of Tonking incident, USS Maddox, a destroyer on DESOTO patrol (SIGINT missions in hostile waters), was attacked by North Vietnamese torpedo boats. It would be the prelude to a complete involvement of American armed forces and intelligence in Vietnam.

NSA's SIGINT efforts would continue to play a major role in combat operation, with signals collection both on the ground and in the air, until the end of the Vietnam war in 1975. Vietnam also fueled the development of miniaturized voice encryption equipment. The secure voice system NESTOR became a widely used standard during that war. During this conflict, NSA also suffered many losses, as you can read in my Silent Warriors post.

The agency quickly outgrew its former girl's school in Arlington. In 1966, NSA relocated to its current buildings in Fort Meade to keep up with the ever growing work load. Nothing, however, could prevent the intelligence disaster that struck NSA two years later, when USS Pueblo AGER-2, a SIGINT vessel, operating near North Korean waters, was attacked and seized by the North Koreans. Loaded with SIGINT equipment and a vast amount of highly classified documents, the ship was a treasure trove for the North Koreans and their Soviet allies. The compromise of equipment, documents and knowledge effected NSA's SIGINT capabilities for many years. See also USS Pueblo Incident.

The paper has some minor redactions, but gives a good view on NSA's achievements and some of its failures. On Watch is available as document 5 at The Secret Sentry Declassified (alternative link here).

FedFlix on the Internet Archive

Fedflix is a project to digitize a large number of U.S. Government movies. It is a Joint Venture between the National Technical Information Service and Public Resource Org, which is also supported by the National Archives.

The FedFlix archive is published on the Internet Archive and it is a real treasure trove of Government movies related to intelligence agencies, espionage, the Cold War and various other subjects. There's a wide variety of historical movies, instruction movies, documentaries and interviews, and best of all, they are available as free download.

Many movies are also made available on Youtube, but at the FedFlix website you can download each movie in various video formats (MPEG4 and h.264 are the most commonly used). Just right-click the proper video format link and select "Save Target As...".

From the numerous titles, and I have selected here below a few that fit the profile of this weblog. Of course, there are many more movies, from how to fly a P-47, over Morse techniques, to atomic bombs, available on the FedFlix section of the Internet Archive. In total, there are more than 7,000 movies to discover! Select this link to view the complete list of movies and enter FedFlix AND your keyword in the search box and hit the GO! button to find your desired movies.

• A Point in Time - The Corona Story (undated)
• The Walker Spy Ring - Lessons Learned (1989)
• Defense Against the Spy (1967)
• Counter-Intelligence Special Operations (1969)
• KGB Connections - parts1 and 2 (1981)
• The Hollow Coin (1958)
• Intelligence Gathering (1947)
• Military Intelligence Specialists (1947)
• Small Town Espionage (1960)
• Soviet Active Measures (1984)
• Cutout Devices - Espionage (1953)
• Intelligence and the Cuban Missile Crisis (1992)

Enjoy watching them! If you discover any other interesting movies in the FedFlix database, please post them in the comments of this post.