(Download this presentation One-Time Pad: The Only Unbreakable Cipher
or view it online)
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 destroyed 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; 1) the numbers must be
random, 2) have as many characters as the plaintext message and 3) must be used only once.
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 only
required paper and pencil. 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 breach.
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 the one-time pad cipher. The book was called, Telegraphic
Code to Insure Privacy and Secrecy in the Transmission of Telegrams, which 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 and the recipient of each copy was carefully noted.
Frank Miller (1842-1925)
inventor of the one-time pad
|
Miller was a banker in Sacramento, California and his description of the one-time pad was clear and specific, but his book was probably seldom 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. He quotes "Colonel Myers" in the preface of his book, referring 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.
Gilbert Vernam
(1890-1960)
|
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 was 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, delay or error. 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.
1919 Vernam patent
|
Gilbert Vernam was awarded US Patent #1,310,719 in 1919 for a "Secret Signaling System", which describes this automated teletype cipher. Also in
1919, US Army Captain Joseph Mauborgne (later Major General and Chief of the US 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 until it was discovered to
have been invented 37 years earlier, in 1882, by Frank Miller. More recent investigations by Steven Bellovin, however, dispute this widely held
belief. Bellovin shows convincing evidence that Vernam originally recommended the random tape and seemed to understand the value of the randomness.
In his original papers in 1917, Vernam writes, “If, now, instead of using English words or sentences, we employ a key composed of letters selected
absolutely at random, a cipher system is produced which is absolutely unbreakable.” 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 use of 2 relatively prime tapes of 1000 and 999
characters, giving 999,000 characters before the key is repeated.
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 which is as long as the message. Claude Shannon proved the one-time pad was unbreakable during WW2, saying it has the property of perfect
secrecy. His results were published in a seminal article in the Bell Labs Technical Journal in 1949.
The Vernam patent was first introduced in the teletype machine. A plaintext message is punched on tape and a second tape of random letters is
added by the Boolean “exclusive or” function. Since this function is reciprocal, enciphering and deciphering is performed in the same way.
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.
SIGTOT receiving Transmitter/Distributor
|
The US military SIGTOT teletype system was the first automated one-time pad, or more specifically, one-time
tape cipher. 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 1960s. The first SIGTOT teletype used 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 first SIGTOT teletype system consisted 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 one-time
tape itself. The one-time tape was therefore classified as "top secret."
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 plaintext tape reel to be electronically added to the random tape reel.
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.
An elegant design feature of this "Secret Signaling System" is the encipherment is self-reciprocal, the same XOR function will both encode and
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.
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 accepting the very small and unlikely vulnerability. The one-time
pads were made by typists randomly typing numbers, so extra pages by using carbon paper. Unfortunately for the Russians, a 2 or 3 time pad is
not secure. Incredibly, this small vulnerability was discovered and exploited by the US in a decades-long project called Venona, which was only
closed in 1980. 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.
Venona codebreakers, most were women
|
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 the security of their ciphers.
Another example of the perfect one-time pad being broken was during WW2 as used by the German Foreign Office for their high-level messages,
codenamed GEE. The Germans used machine generated random numbers, which means they were not truly random. The US Army Signals Intelligence
Service (later became the NSA) was able to exploit this weakness, first decrypting the German messages in 1944. This breakthrough allowed
the US to go back to earlier messages, which were decrypted back to 1925. Furthermore, the German Foreign Office continued to use the machine
generated random numbers for 10 years after WW2 and all were decrypted by the US.
The examples above of breaking the one-time pad was due to the codemaker’s mistake of using a two-time pad or using non-random, machine generated
numbers. It is therefore astonishing to discover the existence of another vulnerability in this "perfect" SIGTOT cipher system, even when
following all the rules. Because of this vulnerability, which was first discovered in WW2, the US military gradually discontinued its use at
great expense starting in 1959. This 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 the relays in all teletype machines emit electromagnetic pulses which would betray the message before
encryption took place. These pulses were faint but detectable on the signal wire, over electrical power lines, copper water pipes 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.
Later, 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 tunneled
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 was operational for 11 months before the East Germans famously and publicly displayed the dastardly acts of the US. Their
plan backfired when the Western public reaction was admiration for the technology and the daring of digging a tunnel under the Berlin Wall,
instead of outrage at the illegal trespass and wiretapping.
One-time pads are too burdensome for normal message secrecy, but continue to be used for high-level messages and for spies. It is also useful
for messages between countries, allowing them to communicate securely without disclosing their cryptographic secrets.
More Information on a Unique One-Time Tape Machine
Hagelin C-446-RT One-Time Tape Cipher Machine
One-Time Pads
from the Cipher History Museum
|
US SIGTOT Teletype Model 14 Receiving Transmitter/Distributor - 1925-59
The US military SIGTOT teletype system was the first use of an automated one-time pad, or more specifically, one-time tape. It was introduced in
1925 and was the "Secret Signaling System" directly based on Gilbert Vernam's 1919 patent. It remained in use by the US military until 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-1963.
The random tape is read in the “receiving” transmitter distributor (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.
An elegant design feature of this "Secret Signaling System" is the encipherment is self-reciprocal, the same XOR function will encode or decode
the message. Also, this automated one time system is unbreakable, prompting the NSA to call this patent "perhaps one of the most important in the
history of cryptography."
US SIGTOT Teletype model SSM-33 Daystrom Mixer - 1925-59
The SSM-33 signal interface/mixer is the device that attaches a receiving TD and a standard TD to a communication line or radio. The receiving
TD reads the random tape while the standard TD reads the plain text tape. The operator could select plain text or cipher text to transmit or
receive. The SSM-33 replaced the earlier version of the SIGTOT mixer called the 131B-2 encryption table, which was supplied with a wooden table.
The SSM-33 was replaced by the HW-19A signal mixer, which eliminated the electronic emissions prevalent in teletype machines. The SSM-33 was
manufactured by the Daystrom Electric Corp. of Poughkeepsie, NY.
US Teletype Model 15 - 1930-70s
This is a standard Model 15 teletype system manufactured by Teletype Corp. and used by Bell Telephone. It has the standard transmitter
distributor for reading punched tape and when combined with the receiving TD, provides a one-time tape encipherment. The Model 15 Teleype
system was often paired with the Model 14 Receiving Transmitter/Distributor shown above.
Hagelin C-446-RT - 1944
The Hagelin C-446-RT is a one-time tape version of the C-446 pin and lug cipher machine, which was introduced in 1944. RT stands for random tape.
The sender and receiver must have the same random tape, which is in a five bit Baudot format. The random tape is added (XOR) to the plaintext to
generate the ciphertext. Since this cipher is reciprocal, adding the random tape to the ciphertext will also produce the plaintext.
This is a manual version of the teletype one-time tape, which is an unbreakable cipher. The handling of the tapes is a burden, so it is reserved
for only the most secret messages.
The standard version of the C-446 is compatible with the US M-209 and was sold to other Allied countries. One difference was a second print reel,
allowing the simultaneous printing of ciphertext and plaintext. The C-446-RT uses the same form as the C-446 but replaces the pin and lug mechanism
with the tape reader and XOR function.
Hagelin CX-52-RT with BC-543 Keyboard - 1952
The Hagelin CX-52-RT is a one-time tape version of the CX-52 pin and lug cipher machine. The RT stands for random tape. The sender and receiver
would have the same random tape, which is in a five bit Baudot format. The random tape is added to the plaintext to generate the ciphertext, which
is then usually sent via Morse code over a radio. This is a manual version of the teletype one-time tape.
One-time tape ciphers are unbreakable, but the handling of the tapes is a burden reserved for only the most secret messages. This cipher machine
is attached to a BC-543 electronic keyboard. The combination is a BC-52-RT.
Hagelin T-55 - 1955
The Hagelin T-55 is a teletype cipher device invented in 1955 to provide online and unbreakable cipher capability. It uses the 5 bit Baudot code
and electro-mechanical relays to perform the “exclusive or” addition of the random and plaintext tapes.
The T-55 is a hybrid cipher machine, since it can be used with one-time tapes or a modified M-209 cipher machine built-in. This built-in pin and
lug cipher is used to generate a pseudo random key stream if a random tape is not available. This machine does not have the built-in M-209. To
ensure the random tape is used one time, the T-55 slices the tape in half after it is used.
One-Time Pad Calculator Disk
This is an aluminum cipher disk found in the estate of a US soldier, but is of unknown origin. It looks like a standard Vigenère disk with
the outer alphabet in the normal sequence and the inner alphabet in reverse order. It has a window for a third alphabet. There are no markings
identifying the maker or user.
This disk was not used as a Vigenère disk but as a calculator for adding the plaintext and the random letters of a one-time pad. It works
reciprocally to derive the enciphered or deciphered letter. The same result could be calculated manually, letter-by-letter, or with the aid
of a table called a Beaufort square. This 3-inch disk simplifies the process.
US KD-100 Key Tape Disintegrator - 1990-2010
The key to a one-time tape cipher is the random tape itself. The machines are not considered secret, since they play no role in determining the
key, which are set exclusively by the random tape. After a tape is used, it must be securely destroyed.
The KD-100 key tape disintegrator will feed paper, polyester or plastic tape at a rate of 13 feet per minute, the result is essentially dust.
