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.

Making one-time pads by hand

A full English-language Scrabble tile set. See Scrabble letter distributions for other languages.

One-time pads were originally made without the use of a computer and this is still possible today. The process can be tedious, but if done correctly and the pad used only once, the result is unbreakable.

There are two components needed to make a one-time pad: a way to generate letters at random and a way to record two copies of the result. The traditional way to do the latter was to use a w:typewriter and w:carbon paper. The carbon paper and w:typewriter ribbon would then be destroyed since it is often possible to recover the pad data from them. As typewriters have become scarce, it is also acceptable to hand write the letters neatly in groups of five on two part w:carbonless copy paper sheets, which can be purchased at office supply stores. Each sheet can given a serial number or some other unique marking.

The simplest way to generate random letters in the Roman alphabet is to obtain 26 identical objects with a different letter of the alphabet marked on each object. Tiles from the game w:Scrabble can be used, as long as only one of each letter is selected. Kits for making name charm bracelets are another possibility. One can also write the letters on 26 otherwise identical coins with a marking pen. The objects are placed in a box or cup and shaken vigorously, then one object is withdrawn and its letter is recorded. The object is returned to the box and the process is repeated.

Another way to make one time pads is to use dice. One can generate random number groups by rolling several w:ten-sided dice at a time and recording the numbers for each roll. This method will generate random code groups much faster than using Scrabble tiles. The plaintext message is converted into numeric values with A =1, B =2 and so on. The resulting numeric values are encrypted by adding digits from the one time pads using non-carrying addition. One can then either transmit the numeric groups as is, or use the straddling checkerboard to convert the numbers back into letters and transmit that result.

If the message is converted into two digit base-6 numbers, then ordinary six-sided dice can be used to generate the random digits in a one time pad. Digits in the pad would be added modulo-6 to the digits in the plaintext message (again without carry), and subtracted modulo 6 from the ciphertext to decrypt. For example:

Table for converting messages to base-6

PT	0	1	2	3	4	5	6	7	8	9
CT	0	1	2	3	4	5	10	11	12	13
PT	A	B	C	D	E	F	G	H	I	J	K	L	M
CT	14	15	20	21	22	23	24	25	30	31	32	33	34
PT	N	O	P	Q	R	S	T	U	V	W	X	Y	Z
CT	35	40	41	42	43	44	45	50	51	52	53	54	55

Using this table, "Wikipedia" would convert to 52 30 32 30 41 22 21 30 14. If the pad digits were 42 26 21 35 32 34 22 62 43, the ciphertext would be 34 50 53 05 13 50 52 10. (Note that 6 = 0 modulo 6).

Key Exchange

In order to use this algorithm, each party must possess the same random key. This typically involves meeting the other party in person or using a trusted courier. Other methods are sometime proposed, such as or both users to have identical devices that generate the same semi-random numbers, however these methods are essentially w:stream ciphers and are not covered by the security proof of one time pads.

Further reading

• Infoanarchy wiki: One-Time Pad Cryptosystem
• Cryptodox: one time pads
• Wikipedia: one-time pad