Cipher Machines

Menu


Search






    World Wide Web
    CipherMachines.com

One-Time Pad


Click here to download a Powerpoint presentation on the One-Time Pad



Manual One-Time Pad

Frank Miller
Frank Miller, one-time pad inventor
One-Time Pad
Example of miniature one-time pad

The one-time pad is the only truly unbreakable cipher. It is named for the pads of paper with random numbers or letters written on them, which are thrown away after one use. The random numbers or letters are added to the plaintext message to create the ciphertext and the receiver of the message must have the same random numbers or letters to decrypt the message. The one-time pad has three requirements; the numbers must be random, have as many characters as the plaintext message and must be used only once (hence the shorthand description, "endless and senseless"). This was a popular cipher system used by spies in WW2 and the cold war because it was secure, the pads were small enough to easily hide and it could be used with paper and pencil only. Practical considerations prevented the one-time pad from being more widely used. Distributing one-time pads was cumbersome and, if captured, was a dangerous security breech.

During WW2 and the cold war, the Soviet Union had many spies in the US supplying information on the ultra secret US atomic bomb project. Apparently, they got careless in the creation of their one-time pads and repeated whole pages for use by their spies. It is also possible they did this deliberately, in order to supply the large demand for one-time pads while opening up a very unlikely vulnerability. Incredibly, this small vulnerability was discovered and exploited by the US in a decades-long project called Venona. The decrypted messages uncovered a widespread campaign by the Russians to spy on the US and our allies, which reached the highest levels of government in the US and Britain. A total of 349 spies were identified, including Julius and Ethel Rosenberg, Alger Hiss, Harry Dexter White (second-highest official in the Treasury Department), Lauchlin Currie (personal aide to Franklin Roosevelt) and Maurice Halperin (section head in the Office of Strategic Services). This is another example of the codemaker's over-confidence in their ciphers being exploited by the codebreakers.

In keeping with cryptologic tradition, the one-time pad was originally credited to the wrong inventors. For almost 100 years, the one-time pad was credited to the 1919 co-invention by Gilbert S. Vernam and Joseph O. Mauborgne. In 2011, however, Columbia University professor Steven Bellovin discovered a little-known book written in 1882 by Frank Miller which clearly described a one-time pad cipher. The book was called Telegraphic Code to Insure Privacy and Secrecy in the Transmission of Telegrams and was primarily written as a telegraph code book and to reduce telegraph transmission costs for banks. Only a few hundred copies of this book were printed. Miller was a banker in Sacramento, California and his description of the one-time pad was clear and specific, but his book was probably never used for sending one-time pad messages and was subsequently forgotten for 130 years. The following is a quote from Miller's book describing the one-time pad:

"A banker in the West should prepare a list of irregular numbers to be called 'shift numbers', such as 483, 281, 175, 892, &c. The differences between such numbers must not be regular. When a shift-number has been applied, or used, it must be erased from the list and not be used again."
A review of Miller's background gives some clues about how it was possible for a bank president to come up with the original idea of a one-time pad. During the Civil War, Miller joined the Union Army and was wounded at the Second Battle of Bull Run. In the latter part of the war, he was a member of Colonel Henry Steel Olcott's unit, a prominent investigator of fraud and corruption during the Civil War. In this capacity, Miller was likely one of the investigators of the Lincoln assassination, among other investigations where the conspirators used secret codes. It was during this time that Miller probably became acquainted with encryption and cryptanalysis. His quotes from "Colonel Myers" in the preface refers to Col. Albert J. Myers, the first Chief Signal Officer and father of the US Army Signal Corps during the Civil War. This also shows an unusual knowledge of military signals intelligence for a banker.



Teletype One-Time Pad

In 1917, Gilbert S. Vernam, an engineer at Bell Telephone Laboratories, invented a teletype based cipher system in which a loop of perforated paper tape representing random letters was added to a plaintext message to create the ciphertext. On the receiving end, a duplicate loop would be used to subtract the same random letters from the ciphertext to re-create the plaintext message. The advantage of this system was the encipherment and decipherment was handled automatically by the teletype system without human intervention or error. In fact, this teletype cipher was the first automated cipher systme. The use of a loop of tape meant the system was not truly a one-time pad since the key tape would be reused, so it was vulnerable to enemy decryption.

Vernam was awarded US Patent #1,310,719 in 1919 for a "Secret Signaling System", which describes this automated teletype cipher. Also in 1919, it is widely thought that US Army Captain Joseph O. Mauborgne (later Maj. Gen. and Chief of the Army Signal Corps) realized the Vernam loop could be replaced with a one-time tape, creating a truly unbreakable cipher. This insight was thought to be the invention of the one-time pad, as noted above, until it was discovered to have been invented 37 years earlier, by Frank Miller in 1882. More recent investigations by Steven Bellovin, however, disputes this widely held belief. Bellovin shows convincing evidence that Vernam originally recommended the random tape in 1917 and seemed to understand the value of the randomness. This was during WW1, however, and the distribution of one-time tapes was a burden the US military did not want. It may have been Mauborgne who recommended the 2 relatively prime tapes of 1000 and 999 characters.

Many other cipher inventors have claimed their inventions were unbreakable, but the invincibility of the one-time pad has the advantage of being mathematically provable. It is also mathematically provable that ANY unbreakable cipher system must include the features of a random and non-reused key.

SIGTOT
Special Transmitter/Distributor for the US military SIGTOT teletype cipher,
this one was used in President Roosevelt's airplane
and is now at the NSA Cryptologic Museum, Ft. Meade, MD
There is no known connection between Frank Miller and either Vernam or Mauborgne. But there is an intriguing connection between Miller and Parker Hitt of the Army Signal Corp and a close collaborator with Mauborgne. While it is almost certain Hitt met Miller at social functions it is known they both attended, any cryptologic discussions between them is not known.

The US military SIGTOT teletype system was the first use of an automated one-time pad, or more specifically, one-time tape, used by the US military. It was introduced in 1925 and was the "Secret Signaling System" directly based on Vernam's 1919 patent. It remained in use by the US military until the 1959. The first SIGTOT teletype was based on the Teletype Model 14, with over 60,000 units manufactured over three decades. Other Teletype models were also manufactured, including 200,000 model 15s from 1930-1950s.

The SIGTOT teletype system consists of a 131-B2 mixer, a special Model 14 receiving transmitter/distributor (TD), a standard Model 14 TD, a Model 14 Keyboard Typing Reperforator (KTR) and a page printer. The receiving TD would read the one-time key tape, the standard TD would read the plaintext tape and both would be connected to the 131-B2 mixer which would combine the two tapes and send the encoded signals to a remote location via a radio or wired connection. The KTR was used to key in the plaintext tape and the page printer would print the messages in plaintext from the remote locations. None of these devices were ever classified, since the only way to break this cipher is to have access to the the one-time tape itself. The one-time tape was therefore classified as "top secret".

Incredibly, there was a vulnerability discovered in this "perfect" SIGTOT cipher system, so the US military gradually discontinued its use at great expense in 1959. This was a closely held secret and only revealed decades later in 2007, which will be explained below.

Pictured below is the heart of the cipher portion of the teletype system, the receiving transmitter distributor, which is essentially a paper tape reader. The difference between this special receiving TD and a standard TD is the receiving TD has a disk with 15 segments instead of only 7, which allows for the second plaintext tape reel to be electronically added to the random tape reel. The receiving TD also has the relays used to electronically combine the letters from the two tape reels, which are then sent to the remote teletype station.

Standard TD
Teletype Model 14 - Standard TD with 7 segments on disk
Receiving TD
Teletype Model 14 - Receiving TD with 15 segments on disk

The random tape is electronically read in the receiving TD and electronically combined with the plaintext tape, which is read on a standard transmitter distributor. The Baudot signals are combined by use of the XOR function (Boolean "exclusive or" function) to create the enciphered text. Vernam did not use the term XOR in his patent, but he implemented that operation in relay logic of the receiving TD.

In the example from Vernam's patent, the plaintext letter A is added to the random key character B, which after the XOR operation results in the ciphertext letter G. The G would be sent to the remote teletype location, where the G is read in the standard TD and the key tape containing the first random character B is read in the receiving TD. After the XOR operation, the result is the original plaintext letter A which would then be printed. This example is shown in Baudot code below.
+ + - - -   Plaintext letter A
+ - - + +   Random key letter B
- + - + +   Result of XOR, ciphertext letter G which is sent to remote location

- + - + +   Ciphertext letter G
+ - - + +   Random key letter B
+ + - - -   Result of XOR, plaintext letter A
An elegant design feature of this "Secret Signaling System" is the encipherment is self-reciprical, the same XOR function will both encode or decode the message. The NSA has called this patent "perhaps one of the most important in the history of cryptography."

The enciphered messages are sent via wired or radio connection to a receiving teletype location. The receiving location would have the same random tape in the receiving TD set to the same starting character as it begins receiving the signals. So the signals through the wires or the airways would be enciphered but the messages would print out on the teletype in plaintext automatically. After the random tape was used once, it would be destroyed. Ships out at sea for many months would require large volumes of these random tapes.

The story of why the US military discontinued the use of SIGTOT is filled with cold war intrigue and deception and was a closely guarded secret until it was revealed by the NSA in 2007.

In 1943, AT&T engineers discovered that teletype machines emitted electromagnetic pulses which would betray the message before encryption took place. These pulses were detectable on the signal wire, over power lines, copper water lines or even in the air. These signals could be tapped as far as 20 miles away and still be amplified and read without the sender knowing his message has been compromised.

This electromagnetic pulse was discovered to emanate from any electromagnetic device, including modern computers. A program code-named Tempest was created to combat this ubiquitous security threat. This capability to tap into encrypted communications before the encryption takes place was exploited in East Berlin in 1955. The US tunnelled under the Berlin Wall to tap into the phone and teletype lines in Berlin, which was the hub for all communications between Moscow and Eastern Europe. This tunnel we operational for 11 months before the East Germans famously and publicly displayed the dastardly acts of the US. Their plans backfired when the Western public reaction was admiration for the technology and daring for digging a tunnel under the Berlin Wall.



Cipher Machine One-Time Pad

Cipher Machine One-Time Pad
Hagelin Cipher Machine C-446-RT One-Time Pad
The one-time pad was also incorporated into traditional cipher machines by the Hagelin company. They had a "pin and lug" mechanical cipher device called the C-446 which was similar to the M-209 cipher machine they sold to the US during WW2. The C-446 used the same cryptologic technology as the M-209, including the use of pin and lugs with 6 rotor wheels and both were based on the prior C-38 cipher device. The M-209 was introduced in 1943 and the C-446 was introduced in 1944. The main difference between the two devices was the M-209 used one paper tape roll to print either the enciphered text or the deciphered text while the C-446 had two tape rolls and could print both enciphered and deciphered texts simultaneously. The C-446 was compatible with the C-38, the M-209, the BC-38 and the later BC-543.

The C-446 was available in a commercial gray color or a military green color. It was known to be used by the Dutch and Norwegian militaries into the 1960s when they were replaced with the later and more powerful CX-52s. These machines were then kept in storage for several decades for possible backup use. Since they were entirely mechanical devices, they would continue to operate even after a nuclear blast may render other electro-mechanical cipher devices inoperable.

The C-446-RT (Random Tape) was a special version of the C-446 which did not have rotor wheels but used a paper tape reader to automatically encipher and decipher the message. This device was not compatible with the other Hagelin cipher machines. The tape reader replaced the function of the rotor wheels, as you can see in the picture below. The random tape was a teletype paper tape using the 5 bit Baudot code and would advance a character at a time as the lever is depressed to encipher or decipher each character of a message.

Cipher Machine One-Time Pad
Hagelin Cipher Machine C-446-RT on left compared to standard C-446
Photo courtesy of Paul Reuvers and CryptoMuseum.com

The random tape used for the C-446-RT was the same as the tape used for the SIGTOT teletype cipher above but the SIGTOT converted the paper tape into electrical impulses to be XOR'ed and then sent via wired or radio connections. The C-446-RT is entirely mechanical so the paper tape is read a letter at a time to then be XOR'ed and printed on the roll of paper tape in the C-446. There are two print reels, one for the plaintext and the other for the ciphertext.

Compared to the SIGTOT teletype system, this is a much more manual process and similar to the use of other manually operated cipher devices. After enciphering each letter of a message, the message would normally be sent in morse code via radio. The receiver of the message would have a duplicate random tape set to the same starting position and then decode the message a letter at a time. After the random tape was used once, it would be destroyed.

Hagelin made other traditional pin and lug cipher machines into random tape machines, including the CX-52-RT and CD-57-RT. Hagelin also manufactured a traditional teletype one-time tape machines, called the T-52 and the T-55. These machines had the option of incorporating the pin and lug of the CX-52, so it could exchange messages with the CX-52 or use the psuedo number generator of the CX-52 instead of using random tapes. Using the T-52 or T-55 in this fashion would not be unbreakable, since this would not be true random tapes.




See the Entire Collection of Cipher Machines

One-Time Pad Cipher
See detailed pictures of the US Air Force SIGTOT Teletype Cipher and the Hagelin C-446-RT Cipher Machine.


While the one-time pad provides a secure cipher, it also requires the use of large volumes random paper tape reels. Producing and transporting these random tapes was cumbersome and a security threat if captured, so the use of one-time pads was limited to the most secure messages. Both the SIGTOT Teletype cipher and the Hagelin C-446-RT are rare cipher devices. They were sold exclusively for military use and most were destroyed instead of being made surplus and available for resale.

The SIGTOT receiving TD is a US Air Force Model 14 Teletype device, which is the first device manufactured to the specifications of the original Vernam one-time pad patent of 1919. The Hagelin C-446-RT was used by the Dutch Navy until it was made surplus in the late 1990s, by mistake, and removed from the surplus market after only one day. Only a few were already sold and the rest were destroyed. Some of these devices were also given to retiring Dutch Navy personnel as mementos. Only a small number of these remaining devices are of the special Random Tape variety.