Frank Rubin

January 13, 1997

There are two eternal verities in cryptography: the only absolutely secure cipher is the one-time pad, and the one-time pad cannot be achieved in practice. The goal of this paper is to show how the one-time pad can be accomplished.

The term "one-time pad" refers to any method of encryption where each byte of the plaintext is enciphered using one byte of the key stream, and each key byte is used one time then never used again. The key stream for a one-time pad must be a true-random stream, meaning that every key byte can take any of the values 0 to 255 with equal likelihood, and independently of the values of all other key bytes. By contrast, in a pseudo-random key stream the value of each byte after the first several is mathematically derived from the values of a few preceding bytes.

The practical difficulty of using a one-time pad is that the key bytes cannot be reused. This means that even for a two-way exchange of messages, each party must have a sufficient supply of key material on hand so that they cannot run out before more key stream can be furnished. For N-way exchanges, the amount of key required increases quadratically.

Many papers on cryptography assume that the only possible way out is for the key to be generated by some mathematical algorithm, and then expend a great deal of cleverness in finding an algorithm that adequately approximates the properties of a true-random key. The paper [1] gives a broad survey of such methods. The weakness of such methods is that determining a portion of the key stream will allow an opponent to reconstruct the entire key stream using the same mathematical algorithm.

This paper presents a solution intermediate between a pure random key and a pure mathematical generator.

One-time pad encipherment can be denoted as

C

where E is the enciphering operation, P

For efficiency, it is good practice to start each message near the position following the key byte used for the last character of the previous message. This eliminates the need to keep track of which portions have been used, and removes the danger that a message will be longer than any of the remaining segments.

Although the term

In principle, the encipherment E can be achieved by simple look-up in a 256·2

The reason that no portion of the key stream may be reused is that an opponent can detect reuse by the simple Index of Coincidence statistical test. Once the opponent finds two or more portions of messages enciphered with the same part of the key, it becomes possible to decipher those portions.

Suppose that two parties wish to correspond in secret over potentially compromised channels. They could communicate using a one-time pad, as above, provided that they could obtain a sufficient supply of key stream bytes, or that they could resupply themselves with key bytes at a rate fast enough to prevent ever running out. Note, however, that the total amount of key used over time equals the total amount of message material. One byte of key for each byte of message. So, if they had a secure way of resupplying the key, perhaps they could send their messages this way, and skip encryption altogether.

Suppose, then, that the parties do not have an endless supply of key bytes, but a limited supply, at least enough for the longest possible message, but perhaps only enough for one day or even one hour of communication. The question is: how can their supply be stretched to last a week, or a year, or until new key material can be distributed?

There are many ways to generate a new sequence from a given sequence. Indeed, this is precisely the problem that cryptography addresses. Even such a simple expedient as adding a constant value to each key byte K

Autokey is a very simple and fast method of encipherment. It has the valuable advantage that each byte of the new key stream has no correlation or fixed relationship with the corresponding byte in the original key stream. Let A and B be two independent simple substitutions. The new key stream L is given by

L

L

where the addition is modulo 256, and n is the length of the old key stream.

Greater strength can be obtained by repeating the autokey two or more times in order to "cover its tracks." This assures that in the final iteration none of the original bytes of the K key stream participate. It is important that the two substitutions A and B are strongly non-linear in the sense that there is no

Since this autokey can be inverted, or reversed, the resulting L key stream will also be true-random. If it were not, then the inversion process would be a deterministic algorithm for producing true-random numbers from nonrandom numbers, which is impossible. By definition, random numbers generated by a deterministic algorithm are pseudo-random.

There must be sufficiently many choices of A and B to prevent the correspondents from ever running out of keys. If A and B are determined by permuting the values 0 to 255 using a pseudo-random number generator, and this generator has a 40-bit seed, then there are 2

A new key stream may be generated in bulk fashion using the entire K key stream, or it may be generated as needed using just the portion of the key stream required for the next message. For very long messages, the autokey can be applied to one block of the K stream at a time as it is retrieved from secondary storage, provided that message keys are not restricted to block boundaries.

Since the K key stream is true-random, no method of cryptanalyzing L to recover K would work except exhaustive trial. In order to decide whether 2

Assume that an opponent has a copy of the encryption device or software, and therefore knows the E operation. Suppose, further, that the opponent knows both the ciphertext and plaintext for some given message. This means that the E encipherment can be stripped off, yielding a portion of the L key stream. It is not feasible for an opponent to try all 2

Imagine that the messages sent today will be of value 20 or even 30 years hence, when it might be possible to try 2

The autokey method allows a relatively small amount of true-random key material to stretch a long, long way. Hamburger helper.

One warning is necessary: the one-time pad method still depends on the opponent not knowing where in the key stream the key for a specific message begins. The key stream needs to be long enough to make this non-trivial. If P is the peak amount of message material expected during the time period when an L key is in use, Q is the maximum length of any message, R is the maximum number of messages expected during the period, and G the average gap left between messages in the key stream, then a good rule of thumb would be to make the key stream at least P+Q+RG+10

This technique can be extended to N-way communications by using a layered approach. Suppose that there are N parties (people or stations) that wish to communicate, and that all possible pairs of parties may potentially need to exchange messages at some time.

It is not sufficiently secure simply to supply all of the participants with the same true-random key stream, and let them apply the autokey method above to generate more key material. Two different parties may use exactly the same key and autokey, thus creating two messages with the same effective key. Such messages will begin appearing when the number of L streams that have been used reaches about 1.4x2

One solution is to control carefully which keys each pair of correspondents use to generate their L streams. This poses a huge administrative burden if the number of users is high, especially if users frequently join and leave the system. Worse, if the range of keys alloted to a particular user pair becomes known, then exhaustive trial of that limited set may be feasible, perhaps even easy.

A better solution is to use a layered approach. Each pair of correspondents could have a unique autokey used to produce their L key stream, then they would apply a second autokey to produce the key stream for a specific time period. This way, neither the K key stream itself nor any derived L key stream is ever used as the key of a message.

If the K stream were discovered by espionage, that would not compromise the communications of any pair. Similarly, no individual with legitimate access to the K stream could eavesdrop on any of the other parties.

If the L stream for a particular pair of parties, or even for several pairs were discovered by espionage, that would not compromise the communications of any other pair, because their L stream would not be known. Futhermore, it would not compromise the communications of the affected pairs because it would not reveal their key streams for any given time period.

Using this layered approach, a small amount of random key can serve a large number of correspondents over an indefinite period. Loaves and fishes. In fact, there are so many choices for the A and B substitutions that the key can never be exhausted, no matter how many parties join the network. Burning bush.

This paper has shown a practical method for implementing one-time pad cryptography. Starting with a limited supply of a true-random key, a simple autokey cipher is used to generate additional random key material indefinitely. Using a layered approach, the same random key can supply any number of correspondents indefinitely with message keys for use in a one-time pad. A break in the communications of one or more pairs of correspondents will not compromise the security of any other pairs.

1 | Ritter, Terry 1991. The Efficient Generation of Cryptographic Confusion Sequences. Cryptologia 15: 81-139. |