The Art of Secret Communication: Part 3, the One-Time Pad and the Generation of Random and Pseudorandom Numbers

Here is your preview of the story.

The only cryptographic system that is perfectly secure is the one-time pad (OTP): in essence, a system in which every plaintext message is encrypted in a different, truly random key whose length is equal to the length of the message, and which is never reused. In practice, a OTP may be implemented in a way that is not secure, i.e., because of departures from randomness or reuse of key sequences.

The OTP is mentioned at least three times in canon. In Flint, 1636: The Saxon Uprising, chapter 15, we are told that David Bartley had been "fascinated with cryptography since boyhood" and that Jeff Higgins had sent Gretchen a one-time pad designed by Bartley. In Prem, "Ein Feste Burg, Episode Twenty-Two" (Grantville Gazette 63), Zenno tells Georg that the "one-time pad" is "simple and effective," and states that it had replaced the "simple Caesar cipher," among unidentified parties. Finally, Lee, "Venus and Mercury" (Grantville Gazette 24) has a character who has gleaned, from Neal Stephenson's Cryptonomicon, "Pseudo-random number generation for one time pads by way of Riemann-Zeta functions, with suggestions how they might be computed without electronic assistance. Hints about proper generation of random numbers and other cipher keys."

While the cryptographic application of random number sequences, most notably in the one-time pad, was the initial impetus for writing this article, the generation and testing of randomness has a broader importance in society. Some randomization methods discussed here, while unsuitable for cryptographic use, may be perfectly fine for other purposes, e.g., selection of samples from a production run for quality control testing, Monte Carlo simulations of physical systems based on mathematical models that do not have an analytical solution, and of course for gambling.

One practical definition of a random number sequence is that it is a sequence of numbers which has a statistically acceptable fit to the specified distribution that the sequence was intended to exemplify, and there is no readily apparent correlation between the individual numbers, i.e., knowing one number in the sequence doesn't help predict any of the others (randomnumbers.info).

In general, for cryptographic purposes, we want a generator of uniform random numbers, that is, all possible values between the allowed minimum and allowed maximum are equally likely. For scientific purposes, we may ultimately want a different distribution, for example, a normal distribution, but there are standard mathematical methods of transforming a uniform "variate" into one of the other distributions commonly used in statistical modeling.

There are two types of one-time pads, figure (numeric code) pads (OTFPs) and letter pads (OTLPs), wherein the keys are numbers or letters respectively. I will focus on figure OTPs for now and discuss letter OTPs at the end of the article.

To use the figure OTP, the plaintext is first converted into a stream of numeric codes. Once the plaintext is in numeric form, there are two common ways of implementing the encryption.

For binary encipherment, the plaintext and key are provided as sequences of bits (ones and zeroes). The plaintext letters could be encoded by the Baudot five-bit code, or the EBCDIC or ASCII eight-bit codes. The binary exclusive or operation is carried out between the two in order to obtain the ciphertext. (Exclusive-or-ing the key with the ciphertext will restore the plaintext).

For decimal encipherment, the plaintext and key are sequences of base ten integers. One could encode each letter as two digits, 01-26, or as one or two digits (e.g., 0-6 and 70-99) through what is called a straddling chessboard (Rijmenants App. A). It is also possible that some text will be converted into a code in which words or phrases have specified codes (typically 3-5 digits). The result is sometimes called plaincode because by itself it is not at all secure. In any event, each key number is added or subtracted to the corresponding plaintext numeric code, to obtain the ciphertext number. This is usually done digit by digit without carry or borrow. (This operation, likewise, is easily inverted, by one knowing the key, to restore the plaintext.)

The OTP was first described in 1882 by Frank Miller, a banker, for use in the superencipherment of telegrams using his codebook. He told his customers to "prepare a list of irregular numbers" to be used as additives and that once a number has been used, "it must be erased from the list and not used again" (Bellovin). Unfortunately, he said nothing about how these "irregular numbers" were to be generated. Humans are not very good at mentally generating random number sequences (Schulz, but see Persaud).

Miller's contribution didn't have much impact, and the principal architects of the OTP were Mauborgne and Vernam. Vernam devised the encryption machine, essentially mixing signals from a plaintext tape and a key tape to obtain a teletype signal. It is not entirely clear which of them first recognized the importance that the key be random and not reused (Bellovin). Vernam's patent also did not explain how the random numbers were obtained.

In WW II and thereafter, the OTP was used primarily by spies and diplomats. I'll discuss that further below.

****

Institutions employing OTPs must assume that 1) some keys will be obtained by the enemy through bribery, blackmail, burglary, or open capture, as happened to the Germans in WW II (Waggoner 46) and 2) the system of encipherment and decipherment will become known through interrogation of agents using the system or capture of instructions for the use of the system. That includes, by the way, capture of codebooks to which a superencipherment is applied. Hence, the security ultimately rests in the randomness and non-repetition of the uncaptured keys, so that the former cannot be generated by analysis of the captured keys. Indeed, Kerchoff stated that "a cryptosystem should be secure even if everything about the system, except the key, is public knowledge."

There are three basic problems with the OTP that have seriously limited its utility:

1) generating the random key in a sufficient volume,

2) securely distributing the random key to the intended recipients and securely holding it until use, and

3) making sure senders don't reuse (or otherwise misuse) keys.

If it were easy to solve these problems in the 1632 universe, then all nations having spies in Grantville would quickly start using OTPs and cryptography would play a minimal role in stories (because the communications would be unbreakable). Thus, from a dramatic standpoint, these problems are a good thing!

****

 

Required Key Volume

 

AT&T tried to market the Vernam machine in the 1920s for commercial use, but without much success: "The production, distribution and consumption of enormous quantities of one-time tapes limited its use to fixed stations (headquarters or communications centers)" (Bellovin).

For absolute security, the key must not be reused, which means that you need as many key values as there are characters in all of the messages being sent. What is a sufficient key volume? It depends on whether we are talking about communications with military units, embassies, or spies.

If all communications with military units are written or radioed, then the number of messages will depend on the number of units at all relevant levels. In the American Civil War, the army commander (general) sent messages to the corps commanders (major generals), who gave orders to division commanders (brigadier generals), who instructed brigade commanders (colonels), who directed regimental commanders (colonels, majors and captains), who ordered company commanders. At a minimum, there would be a daily movement order down the line and status report up the line. As the army nears the enemy, communications would become more frequent. There be would scouting reports, consultations, engagement reports, and so on.

If the army relied completely on OTPs for secret communications, there would need to be, essentially, a separate OTP for each possible sender-recipient pair. And the OTP would have to contain a sufficient quantities of random numbers so you didn't have to send out a new set of OTPs too frequently.

For what it's worth, during the ACW, the US Military Telegraph Service handled some 6.5 million messages (Hochfelder). This of course doesn't fully convey the full magnitude of written ACW military communications, as some would have been in the form of letters. As to the length of a telegraph message, the first civil war military telegram I could find was 398 characters (decodingthecivilwar.org). I suspect that some were longer. Letters of course could be much longer because they don't tie up the communication channel the way a telegram does.

The forces in play in NTL Europe are smaller than those of the ACW, with fewer organizational levels, but I would suspect that the message volume would still be large enough for it to be impractical to generate and distribute enough OTPs frequently enough to encipher all military communications of the major powers.

The OTP volume requirements for diplomats and spies are substantially smaller than for military officers, and that is one reason why most actual OTP use has been by them.

Despite that, the difficulties of generating and distributing random keys were such that in WW II, the German Foreign Office adopted "economy measures for the purpose of making use of all the groups of additive left over on the sheets at the end of messages not exact multiples of 48 groups" (the number of-five digit groups on each OTP sheet) (Waggoner 29ff).

As for the actual generation of the random keys to meet the volume requirements, there are many ramifications; the discussion of these takes up the bulk of this article. Hence, I will address the other issues first.

****

 

Secure Key Distribution

 

The OTP key could be used for twentieth-century diplomatic communications, because it could be transported to the intended recipient in a diplomatic pouch, a container having diplomatic immunity from search or seizure under Article 27 of the 1961 Vienna Convention on Diplomatic Relations. That said, there have been instances in which such pouches have been opened, either openly (e.g., with the excuse that it was not properly marked as a diplomatic pouch) or surreptitiously (as in the British Triplex operation in WW II).

Unfortunately, there is no international protection for diplomatic pouches in the 1632 universe. Hence, another method of transporting keys will need to be found. There might be some advantage to using an aircraft or airship for this purpose, since they are difficult to intercept (at least if the craft doesn't have to stop to refuel). While only the USE has aircraft, by NTL 1636, Denmark, the Netherlands, Spain, Russia, and the Ottoman Empire have airships.

If couriers carrying OTPs to intended recipients must travel by more conventional means, then they need to either escape detection (secret route, hidden identity, and perhaps a concealed OTP) or be traveling with sufficient escort so that they needn't worry about the OTP being taken by force.

OTPs were also transported by spies. Spies had to worry about being subject to search by local authorities, and possession of something that looked like a cryptographic tool would be evidence of espionage. Hence, OTPs had to be concealed in some way. One method was to place them inside a concealment container. The East Germans have made use of a personal car kit with a secret compartment and of a toy truck. The KGB is known to have placed an OTP inside a real walnut that was split, emptied and glued back together.

Concealment was facilitated if the OTP was printed in a reduced size so it took up less space. Of course, the agent would then need a magnifying glass in order to read the OTP.

The SOE (Special Operations Executive) had OTPs printed on silk (although it had to struggle to get enough silk because silk was needed for parachutes). The Gestapo would cordon off a street without warning and search everyone it could find. Silk could be concealed inside clothing in such a way that it couldn't be felt by a routine search. As keys were used, they could be cut out and burnt. (Marks 269). It was also possible to print keys on silk with "invisible" ink.

****

            An alert reader might ask: if the key must be as long as the message itself, and you are sure that the key can be delivered securely, then why not dispense with the key and just securely deliver the message?

The answer, I believe, is that you may only be able to deliver a communication securely at particular times. For example, during peacetime, you deliver a large number of OTPs, which are then used during wartime when the communications are no longer secure.

****

            It is common for encrypted messages to be transmitted by shortwave radio. Indeed, the radio spectrum has many mysterious stations that come and go, broadcasting strings of numbers.

Crypts may also be transmitted by fax, telex, mail, and courier.

Once the OTP is in hand, the legitimate recipient has to know which sheet to use to decipher an incoming message. One expedient is an agreement that a particular key sheet is used when the transmission is on a particular date. However, this has the problem that a sheet is wasted if nothing is transmitted on its assigned day. Also, what do you do if two messages are transmitted the same day; reuse of the key is forbidden. A date-based key selection is feasible only when the OTP is based on a pseudo-random number generator, as discussed in a later section, and even then there's the issue of whether such a selection method might unduly help the cryptanalyst.

Hence, it is routine for a key "indicator" to be transmitted, either in a separate earlier or later message, or as part of the same message. The indicator will usually be encrypted or concealed in some way.

****

 

Key Use and Misuse

 

Despite the simplicity of the OTP, its use is time-consuming. Even with a code book to reduce the number of characters, "A one page message could take two operators hours to complete." If the message had to be encrypted letter by letter, as in the case of one using foreign words not in the code book, a message of 600-700 five-digit groups could take almost two days to decrypt. (Smith).

Reuse can occur inadvertently, as a result of error either by the sender or by the provider of the OTP. "For a few months in 1942, a time of great strain on the Soviet Union, the KGB's cryptographic center . . . for some unknown reason printed duplicate copies of the "key" on more than 35,000 pages of additive and then assembled and bound these in one-time pads." The pads in turn were pouched to Soviet diplomatic missions. Most of the duplicates were used in 1942-4. The Soviet use of duplicate key pages was detected in autumn 1943, and techniques were developed for "finding duplicate pages separated in time and among different users" (Benson xv). About 29,000 messages were decrypted as a result of the duplication (193).


That is the end of the preview.
Only active subscribers can read the full story.
If you would like to, please subscribe.
We hope you enjoyed the preview.

About Iver P. Cooper

Iver P. Cooper, an intellectual property law attorney, lives in Arlington, Virginia with his wife and two children. Two cats and a chinchilla rule the household with iron paws. Iver has received legal writing awards from the American Patent Law Association, the U.S. Trademark Association, and the American Society of Composers, Authors and Publishers, and is the sole author of Biotechnology and the Law, now in its twenty-something edition. He has frequently contributed both fiction and nonfiction to The Grantville Gazette.

 

When not writing (or trying to get an “orange blob” off his chair so he can start writing), he has been known to teach swing dancing and folk dancing, or to compete in local photo club competitions. Iver adds, “I can’t get my wife to read my fiction, but she has no trouble cashing the checks.”

Iver’s story “The Chase” is in Ring of Fire II