Just Enough Cryptography — One-Time Pads

One-Time Pad Cryptography

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.

All algorithmic cryptography is tactical. It's only secure until the Bad Guy 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.

However, there is a completely different form of cryptography that cannot be broken — use a One-Time Pad.

A version of this 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 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:
    0 + 0 = 0
    0 + 1 = 1
    1 + 0 = 1
    1 + 1 = 0

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.

             +-----+                                      +-----+
message ---> | XOR | ---> transmitted over the clear ---> | XOR | --> message
             +-----+                                      +-----+
                ^                                            ^
                |                                            |
               OTP                                          OTP
             copy #1                                      copy #2

        Firefox users may find that "monospace" isn't really a constant-width
        font, and Courier works much better for ASCII art.

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
   
5. When you have enough digits, convert them into bits somehow. Maybe:
   • One bit per digit — 0 if even and 1 if odd.
   • Skip any digit of 8 or 9, and generate 3 bits per remaining digit (converting octal to binary).
6. Some seeds may be better or worse than others, but all of them will eventually loop. And see the table below, adding 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 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 below in a very well-shielded case:

                   High gain
                   Amplifier
                         |\
                         | \    +-----------+         high-order
     zener  +------------|  >---|  A-to-D   |=======> bits discarded
     diode  | resistor   | /    | converter |-----+
  +----|<|--+--VVVVV--+  |/     +-----------+     | low-order bit only
  |                   |          +----------------+---------+
-----                 |          |                          |
 ---                  |          |      +----------+        |
----- battery         |          |in1   |in2       | out    | in
 ---                  |        +------------+  +-----------------+
  |                   |        | Comparator |  | Sample-and-hold |
  +-------------------+        +------------+  +-----------------+
                                     |out               |clock
                                     +------------------+
                                     |
                                     +----------------------> CLOCK
                                     |
                                     |reset
                                +---------+
  fast, and not +-------+       |         |----> discard the
    necessarily |       |out    |         |----> high-order
         stable |  /\/  |------>|  fast   |----> bits
     oscillator |       |    in/| counter | ...
                +-------+  clock|         |-----------------> OUTPUT
                                +---------+

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

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

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 

Typical smoke detector with Americium-241 unit at left.

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 neptunium-237, and about 5% 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....

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.

All the way back to the start Terminology Symmetric and Asymmetric Ciphers One-Time Pads Next — Cipher Strength and Key Length Diffie-Hellman Key Negotiation and Secret Sharing Cryptographic Hash Functions Digital Signatures and Certificates Cultural Cryptography Further Reading

Back to the Security Index

Home Unix/Linux Networking Infosec Travel Technical Radio Site Map Contact