Cryptography/One time pads

A One Time Pad (OTP) is the only potentially unbreakable encryption method. Plain text encrypted using an OTP cannot be retrieved without the encrypting key. However, there are several key conditions that must be met by the user of a one time pad cipher, or the cipher can be compromised.

• The key must be random and generated by a non-deterministic, non-repeatable process. Any key generated by an algorithm will not work. The security of the OTP relies on the randomness of the key. Unfortunately, the randomness of a key cannot be proved.
• The key must never be reused. Use of the same key to encrypt different messages, no matter how trivially small, compromises the cipher.
• The key must not fall in the hands of the enemy. This may seem obvious, but it points to the weakness of system in that you must be able to transmit large amounts of data to the reader of the pad. Typically, one time pad ciphers are sent via diplomatic pouch.

One way of using this method is by generating a key the same length as the plaintext. XOR the plaintext with the key to create the ciphertext. To decrypt the ciphertext, XOR it with the original key. The system as presented is thus symmetric. Other functions (e.g., addition modulo n) could be used to combine the key and the plaintext to yield the ciphertext, although the resulting system may not be symmetric.

If the key is random and never re-used, an OTP is provably unbreakable. Any ciphertext can be decrypted to any message of the same length by using the appropriate key. Thus, the actual original message cannot be determined from ciphertext alone, as all possible plaintexts are equally likely. This is the only cryptosystem for which such a proof is known.

However, there are limitations. Re-use the key and the system becomes extremely weak; it can be broken with pencil and paper. Try to build a "one-time-pad" using some algorithm to generate the keys and you don't have a one-time-pad, you have a stream cipher. There are some very secure stream ciphers, but people who do not know one from a one-time pad are probably not able to design one. It is unfortunately fairly common to see weak stream ciphers advertised as unbreakable one-time pads.

Also, even if you have a well-implemented OTP system and your key is kept secure, consider an attacker who knows the plaintext of part of a message. He can then recover that part of the key and use it to encrypt a message of his own. If he can deliver that instead of yours, you are in deep trouble.

Example

First, an OTP is selected for the plaintext:

Preshared Random Bits = 1010010010101010111010010000101011110101001110100011
           Plain text = 110101010101010010100
   Length(Plain Text) = 21
              Key(21) = 101001001010101011101

The example indicates that the plaintext is not always the same length as the key material. This can be handled by methods such as:

• appending a terminator to the plaintext before encryption, and terminating the cyphertext with random bits.
• prepending the length and a preamble terminator to the plaintext, and terminating with random bits.

Such signaling systems (and possibly the plaintext encoding method) must be designed so that these terminators are not mistaken for plaintext. For this example, therefore, it is assumed the plaintext already contains endpoint/length signaling.

For increasingly long plaintext/key pair lengths, the cross-correlation gets closer to zero.

Encryption

Key(21)    = 101001001010101011101
Plaintext  = 110101010101010010100
$\oplus$bitwise    |||||||||||||||||||||
cyphertext = 011100011111111001001

For increasingly long plaintext/cyphertext pair lengths, the cross-correlation also gets closer to zero.

Decryption

Preshared Random Bits = 1010010010101010111010010000101011110101001110100011
           cyphertext = 011100011111111001001
           $\oplus$bitwise    |||||||||||||||||||||
           Plain text = 110101010101010010100

An astute reader might observe that the decryptor needs to know the length of the plaintext in actual practice. This is done by decrypting the cyphertext as a bitstream (i.e. xor each bit as it is read), and observing the stream until the end-of-plaintext ruleset is satisfied by the signals prepended/appended to the plaintext.

Key Exchange

In order to keep this algorithm secure each party must exchange or generate the same random key their are many solutions to this problem but they are not perfect. One such method is the satellite method. Where a satellite streams random numbers that are then sampled by the users at a specified interval unknown to the attacker to get the key. Another method is for both users to have identical devices that generate the same semi random numbers on the same intraval. This is vulnerable to some one stealing a devise.