Perfect Security With One-Time Pads

One-Time Pad Cryptography

The only way to achieve perfect security when encrypting is to use a One-Time Pad. It's very impractical, so you seldom have enough motivation to go to the trouble of using one. And if you don't use it correctly, it can be broken. But a one-time pad is the only unbreakable cipher. All other methods, what are called algorithmic cryptography, are tactical. They're only secure until your adversary has enough time to apply their resources to find your key. See Applied Cryptography for analysis of just how long that is on practical, and some impractical, systems.

A version of the one-time pad was used on what was called the POTUS-PRIME communications link between Winston Churchill and Franklin Delano Roosevelt during World War II.

The "one-time pads" in the voice system were carefully made large shellac phonograph records containing random noise. The speaker's voice signal was multiplied by that noise and transmitted across the ocean. At the other end, the received signal was multiplied by the same noise, as provided by a carefully synchronized identical record. See the Wikipedia page for some details of this AT&T voice scrambler system.

The modern One-Time Pad cipher is based on the Exclusive-OR, or XOR, operation. You have two streams of bits, the input and the key. Use them one bit at a time, the nth input bit with the nth key bit. So, the key stream must be as long as the input stream.

In words:

If the key bit is 0, the output bit is equal to the input bit.

If the key bit is 1, the output bit is the opposite of the input bit.

Or, in different words:

If the input and key are equal, the output is 0

If the input and key are different, the output is 1

Or, as math: The output bit is the modulo-2 addition of the input bit and the key bit:

Or, as a table:

Or, as an example:

A one-time pad is a sequence of random bits as long as the message to be encrypted. It's the key bitstream. The sender XOR's the message with the one-time pad and sends the result. Then — and this is where even major governments mess up — the sender must destroy the one-time pad and never ever use it again. The receiver must have an identical copy of the one-time pad. They XOR the incoming message with that.

Recreation of Winston Churchill communicating with Franklin Roosevelt from Churchill's Cabinet War Rooms in London

Voice communications gear in the Cabinet War Rooms. Telegraph messages were protected by what the U.S. called the SIGABA cipher system, also known as the M-134-C, ECM Mark II, CSP 888/889, and ASAM VI, see this page for its technical details.

Generating a Key Stream with /dev/random

Computers are deterministic. You should get the same result every time you run the same program. If not, that's usually a sign that your hardware is failing.

A typical operating system includes an entropy module which collects entropy, or randomness, from its environment. It then processes that to implement a virtual random device that can be read by the operating system itself or processes running there. Well designed random devices will only provide output when adequate entropy is available.

In most situations the operating system must collect its entropy from external events such as Ethernet packet arrival timing or from user-provided events such as keyboard and mouse interrupts.

The Raspberry Pi Linux platform contains a hardware random device. The Raspberry Pi is based on the Broadcom BCM2835 system-on-a-chip with a low-power ARM1176JZ-F processor and a hardware random number generator.

The Linux bcm2709_rng kernel module detects and handles the hardware random number generator, creating device node /dev/hwrng. The rngd random number generator daemon can then feed this hardware device's output into the kernel's entropy engine for the /dev/*random devices. See my page on UNIX-family random devices for details.

Generating Additive Key Streams

To get you started, here is an additive stream, a dangerously weak way to generate a pseudorandom sequence (looks random but it isn't) from a relatively short seed or key:

1: Make the seed a multi-digit base-10 sequence. For example, my old telephone number:
7657430769
In this example we are using a 10-digit seed.

2: Generate the next digit by adding the first two digits modulo 10:
(7 + 6) mod 10 = 13 mod 10 = 3
76574307693

3: Now shift one position to the right:
(6 + 5) mod 10 = 11 mod 10 = 1
765743076931

4: And just keep going:
(5 + 7) mod 10 = 12 mod 10 = 2
7657430769312
(7 + 4) mod 10 = 11 mod 10 = 1
76574307693121
(4 + 3) mod 10 = 7 mod 10 = 7
765743076931217
(3 + 0) mod 10 = 3 mod 10 = 3
7657430769312173

When you have enough digits, convert them into bits somehow. Maybe one bit per digit — 0 if even and 1 if odd. Or maybe discard any digit of 8 or 9, and generate 3 bits per remaining digit by converting octal to binary.

Some seeds may be better or worse than others, but all of them will eventually lead the sequence into a loop. And see the table below, adding digits to the seed may generate a shorter unique sequence. Most 3-digit seeds produce 168-digit sequences, although a few produce 4-, 24-, and 28-digit sequences. Click here for a C++ program that lets you experiment with these.

And of course, if an attacker suspects that an additive stream might be used, it is pretty easy to figure out if that is the case, and in the process, discover the precise sequence and thus key stream!

Building Your Own One-Time Pad Key Generation System

So how do you make a one-time pad? Rely on physics, any attempts to generate random sequences with computers will fail.

One method would be digitize the output of a radio receiver tuned to a radio frequency spectrum completely uncontaminated with the correlated signals generated by man-made sources and even some natural sources. For a simple version, place a circuit that looks like the one at right in a very well-shielded case.

What you're measuring here is the time since the output of the noise generator changed slightly. When the comparator output goes high, indicating an ADC state change, you accept the low-order output of the counter as a valid OTP bit. Once that is done, reset the counter to zero, and take the current ADC low-order bit value as the new internal state. The counter must run several orders of magnitude faster than the bandwidth of the high-gain amplifier and the ADC. All power circuits must be well-regulated and battery powered (no 50/60 Hz bias to our output!). You'll need lots of internal shielding, don't let the noise generator (diode and resistor) pick up any noise from the counter clock. Put the battery, diode, resistor, and high-gain amplifier in one shielded case, and put that case and the ADC in another shielded case.

Collect statistics on the output — your output may not exhibit adequate entropy. In other words, it may not be adequately random. You will have to be patient and accept low output bit rates. Run the counter faster, put a low-pass filter after the amplifier, or increase the amplifier gain. Start building your one-time pad early, and make sure to compress your message before encrypting it.

CAUTION RADIOACTIVE MATERIAL Am 241 1.0 uCi 3/kBq MAXIMUM P40-83-12

As a dangerous alternative that you must never ever do, disassemble a smoke detector. It will contain a small amount of radioactive Americium-241 in a small ionization chamber used to detect combustion products. Look in the well shielded case with all the warnings against tinkering around like this.

As we're warned on the Wikipedia page, "Alpha emission from  ²⁴¹Am is approximately three times that of radium. Gram quantities of  ²⁴¹Am emit intense gamma rays which creates a serious exposure problem for anyone handling the element." Don't collect too much in one place: "Americium is also fissile; the critical mass for an unreflected sphere of  ²⁴¹Am is approximately 60 kilograms."

However, all you're likely to find in one smoke detector is one microcurie's worth, or 0.28 microgram, as we're warned on the package shown above, Doing the math, critical mass would require:
(60 kg) × (1,000,000,000 μg/kg) / (0.28 μg/detector) = 214,285,714,286 smoke detectors

Anyway, radioactive decay is a nicely random process. So, use an alpha particle detector to time decay events for your radioactive sample, and base your one-time pad on those times. Something like the low-order bit of the time in microseconds since the previous decay event would serve nicely.

The half-life of  ²⁴¹Am is 432.2 years. So after 19 years about 3% has decayed to ²³⁷Np or Neptunium-237, and about 5% has decayed after 32 years. With a much longer half-life of 2.14 million years, the Neptunium is effectively non-radioactive (for our purposes), so if you have any unusual requirements for high randomness over long periods of time....

Typical AC-powered smoke detector with Americium-241 unit at upper left.

Typical smoke detector with Americium-241 unit at left.

As a somewhat less dangerous alternative to the above, which you should never do yourself (although perhaps you could have your attorney do it on your behalf), substitute Coleman lantern mantles for the smoke detector Americium. Yes, lantern mantles are also radioactive material that mere citizens can purchase on the open market. They have a lot of thorium in them, in the form of thorium dioxide, ThO₂. The thorium produces the dazzling white light. It's an alpha emitter, so your skin should stop it but do not eat the lantern mantles.

There is also some Mexican pottery out there with bright orange glaze containing uranium oxide. The "problem" with these lantern mantle and crockery sources is that they are less radioactive and thus the output of your one-time pad generator must be much slower.

Be extremely careful! You don't want to end up like David Hahn, known as the Radioactive Boy Scout for his overly enthusiastic experiments with radioactive material.

Next ❯ Cipher Strength and Key Length