One-time pad

Example of a one-time pad (here with the 26 capital letters of the Latin alphabet )

The one-time pad (abbreviation: OTP , German: one- time encryption or one-time key method , literally one-time block , not to be confused with the one-time password method ) is a symmetrical encryption method for secret message transmission . It is characterized by the fact that a key is used that is (at least) as long as the message itself. The OTP is information-theoretically secure and demonstrably cannot be broken - provided it is used as intended.

history

Joseph Mauborgne

The method was proposed for the first time by the American cryptologist Frank Miller (1842–1925) in 1882, before it was applied for a patent - 35 years later - by his compatriot Gilbert Vernam (1890–1960). The American Joseph O. Mauborgne (1881–1971) implemented this idea and called the process One-Time Pad (German: one-time block ). Shortly afterwards, the Germans Werner Kunze, Rudolf Schauffler and Erich Langlotz also worked on this method. In 1921 they proposed using blocks printed with randomly generated digits to encode the diplomatic codes of the time, and referred to them as the i-worm (individual worm). This method was actually used by the diplomatic service of the Weimar Republic .

This method has been used from that time to the present day, especially during the Cold War . For example, the “ hot wire ” (also known as the “red telephone”), the highly secure direct telex connection between the American president and the Soviet general secretary , was protected by a one-time key procedure.

Procedure

One page of an agent's OTP (here with columns of digits)

description

The one-time pad is one of the polyalphabetic substitution methods , in which the individual letters (or characters) are converted ( encrypted ) into other letters (or characters) . The distinguishing feature of one-time encryption is the one-time use of a random key which is (at least) the same length as the message to be encrypted.

With the one-time pad, the plain text as well as the key and the cipher are strings of the same length. While modern implementations of the OTP are based on bits and bytes , the OTP can also be used "classically", for example with the help of the usual 26 capital letters of the Latin alphabet . If necessary, this can easily be expanded with lowercase letters , numbers or special characters . For encryption, the key is combined with the plain text character by character. The type of combination is arbitrary and does not have to be kept secret. When using bits, an exclusive-or operation (XOR) of plain text and key bits is common because this is particularly easy to implement. Alternatively, a different link, for example a character-by-character addition (without carryover), can also be used. If you use manual methods and only capital letters , addition is recommended. For this purpose, the letters are usually numbered according to their position in the alphabet, often numbering from 0 to 25 (A = 0, B = 1, ... Z = 25) or from 1 to 26 (A = 1, B = 2, ... Z = 26) takes place. You can also choose any other assignment. This has no fundamental influence on the method or its safety.

safety

The basic requirements for the security of the one-time key procedure are: The one-time key must

be at least as long as the message

are chosen randomly evenly distributed ,

stay secret and

may not be reused, not even partially.

The one-time key procedure thus fulfills Kerckhoffs' principle , according to which the security of a cryptosystem must not depend on the secrecy of the algorithm, but only on the secrecy of the key, in an ideal way. The four conditions of the key selection together with the description of the procedure ensure that the following conditions are met:

There are as many keys as there are possible ciphers,
For each plaintext / cipher pair there is exactly one key which, when applied to the plaintext, results in the cipher.

Under these conditions, the method is theoretically secure (also called perfect security ) and cannot be broken with any amount of computing effort . The ciphertext can only be decrypted with knowledge of the key. It is impossible to guess this or to infer it in any other way, since every possible key can occur with the same probability. In addition, there is no way to find out whether a key was guessed correctly or not. If the key were not chosen randomly, as was assumed above, but instead, for example, text passages were used, then this property would not be given.

Related to the one-time pad, the stream cipher , with the key pseudo-randomly from a shorter key, a PIN is generated, or a passport or password. Other historical and also current cryptographic methods use keys that are usually much shorter than the length of the plain text to be encrypted . In contrast to OTP, none of these procedures have perfect security.

The one-time key method is well suited for a machine implementation. In contrast to many modern cryptographic methods (such as DES , PGP or AES ), which rely on computers because of their complexity, the One-Time-Pad is just as suitable for manual encryption and decryption.

example

A simple manual method for encryption is, for example, the letter- by- letter addition of plain text and key. To do this, you first replace the letters of the plaintext alphabet with numbers using any substitution table . In the simplest case, the 26 capital letters of the Latin alphabet are assigned numbers that correspond to their position in the alphabet. In other words, you number the alphabet like this:

A B C D E F G H I J  K  L  M  N  O  P  Q  R  S  T  U  V  W  X  Y  Z
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

It is now easy to add letters by letter. For example, adding A and F results in the letter G , corresponding to their location numbers 1 + 6 = 7 . If the sum should exceed the value 26, you simply subtract 26 ( modulo operation) and you get one of the 26 alphabet letters again. For example, X plus U is numerically 24 + 21 = 45, after disconnection from 26 results 19 and thus the letter S , so X + U = S .

The relationships between the addition of letters can be clearly shown in the following table, which is similar to a classic tabula recta :

  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z A
B C D E F G H I J K L M N O P Q R S T U V W X Y Z A B
C D E F G H I J K L M N O P Q R S T U V W X Y Z A B C
D E F G H I J K L M N O P Q R S T U V W X Y Z A B C D
E F G H I J K L M N O P Q R S T U V W X Y Z A B C D E
F G H I J K L M N O P Q R S T U V W X Y Z A B C D E F
G H I J K L M N O P Q R S T U V W X Y Z A B C D E F G
H I J K L M N O P Q R S T U V W X Y Z A B C D E F G H
I J K L M N O P Q R S T U V W X Y Z A B C D E F G H I
J K L M N O P Q R S T U V W X Y Z A B C D E F G H I J
K L M N O P Q R S T U V W X Y Z A B C D E F G H I J K
L M N O P Q R S T U V W X Y Z A B C D E F G H I J K L
M N O P Q R S T U V W X Y Z A B C D E F G H I J K L M
N O P Q R S T U V W X Y Z A B C D E F G H I J K L M N
O P Q R S T U V W X Y Z A B C D E F G H I J K L M N O
P Q R S T U V W X Y Z A B C D E F G H I J K L M N O P
Q R S T U V W X Y Z A B C D E F G H I J K L M N O P Q
R S T U V W X Y Z A B C D E F G H I J K L M N O P Q R
S T U V W X Y Z A B C D E F G H I J K L M N O P Q R S
T U V W X Y Z A B C D E F G H I J K L M N O P Q R S T
U V W X Y Z A B C D E F G H I J K L M N O P Q R S T U
V W X Y Z A B C D E F G H I J K L M N O P Q R S T U V
W X Y Z A B C D E F G H I J K L M N O P Q R S T U V W
X Y Z A B C D E F G H I J K L M N O P Q R S T U V W X
Y Z A B C D E F G H I J K L M N O P Q R S T U V W X Y
Z A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

In the top line in italics and in the first column on the left, the two summands to be added are given. The total can be read off at the intersection within the table, i.e. the result of the summation of plain text letters and key letters. This is the corresponding letter of the ciphertext.

A random key is used for encryption, which in this example is also composed of the 26 capital letters and whose length corresponds (at least) to the length of the plain text to be encrypted. It is crucial for the security of the encryption that the individual letters of the key are really randomly distributed, are unpredictable and have no relation to one another. The following sequence of letters serves as an example of a random key:

S = WZSLXWMFQUDMPJLYQOXXB

In this example, the key S is quite short, it only comprises 21 letters and is “used up” very quickly when used as intended, namely after encrypting a text made up of 21 letters.

For example, the following plain text K should be encrypted:

K = ANGRIFFIMMORGENGRAUEN

For encryption purposes, plain text K and key S are added letter by letter, as explained above. As the "sum" (K + S = G) after the one-time encryption, the ciphertext G is obtained:

G = XNZDGCSODHSEWOZFIPSCP

The ciphertext G obtained as a result can not be differentiated from a random text and in principle cannot be deciphered with any type of cryptanalytic attack method (neither now nor in the future) . Knowledge of the key S alone makes it possible to obtain the plain text K from the ciphertext G by subtracting the key. Without the key you can in principle "construct" all conceivable and more or less meaningful letter combinations from 21 letters. In theory, an attacker could try this. In this way he would receive a vast number of sentences that would convey any information in any language, for example

K' = WIKIPEDIAFINDENWIRGUT

with the "matching" key, which corresponds to the difference between ciphertext G and the constructed pseudo-plaintext K '(S' = G - K '):

S' = AEOUQXOFCBJQSJLIZXLHV

This key S 'fulfills the condition that the letter-wise sum of it with the (false) plain text K' generated above results in exactly the same ciphertext as the sum of the real, but unknown to the attacker, key S with the real one, but also to the attacker unknown plaintext K. In this way, the attacker can construct an immense wealth of conceivable plaintext key pairs which all add up (letter by letter) to the same real ciphertext. However, he has no way of inferring the real plaintext from this. Even brute force , so the exhaustive trying all possible keys does not lead to success. The attacker can generate all conceivable texts with 21 letters - even without even knowing the ciphertext - including the original one, of course. However, there are no indications whatsoever to decide which of the multitude of quite meaningful texts is the actual plain text. As long as the key does not fall into his hands, the plaintext remains a secret forever.

In order not to endanger this security, the disposable key should be irretrievably destroyed after it has been used as intended.

Attack opportunities

If the one-time key method is used correctly, OTP is demonstrably safe and cannot be broken , as the American scientist Claude Shannon showed in the 1940s. In practice, however, mistakes can occur that make a break-in possible. The reason for this is the violation of basic safety measures.

Commercially available data carriers for storing one-time keys

Spy on the key

A possible mistake is not to exchange the one-time key secretly between the sender and recipient so that it can be spied on by third parties. Safe storage of the key is also essential. In contrast to passwords or passwords, a one-time key can hardly be remembered. It must be saved on any medium, be it paper , data disk , CD-ROM or USB stick . Such a medium - and with it the key - can easily be copied. It is also important not to forget to safely and irretrievably destroy the disposable key after use. If the attacker succeeds in subsequently finding or restoring the key, the communication is no longer secret.

Cryptologically insecure keys

A cardinal error is not to use a random sequence of letters as a one-time key, but a passage of text. Even if the text used is unique and is not known to anyone (apart from the two communication partners), letter sequences that come from a "meaningful" text, in contrast to random letter sequences (random texts), show statistically evaluable dependencies that can make decryption possible .

So that the original cannot be reconstructed from the encrypted text without a key, the key must be cryptologically secure , i.e. it must not be distinguishable from a genuinely random sequence of numbers or letters. If this is not the case, an attacker may be able to decrypt the text using cryptanalysis , even without knowing the key.

In the ideal case, a physical random number generator is used to generate a cryptologically secure key , since only such a key delivers genuinely random, i.e. non-deterministic, values.

In principle, a generator for pseudo-random numbers can also be used. In this case, however, the key must not be so long that one could infer the internal state of the generator from it, otherwise all subsequent values could be predicted. With simple generators (such as congruence generators ) this is the case after just a few values. In the case of cryptographically secure generators , this can be considerably longer, but they are also deterministic and can theoretically be cracked.

Multiple use of the one-time key

A mistake often made in practical use (examples: Lorenz key machine and Venona ) is to produce and distribute more than just the two copies of the one-time key intended solely for the sender and recipient or to use the key more than once for encryption. Using a one-time key twice is enough to successfully attack the communication.

The attacker starts from the following point of view: Assuming that the sender (accidentally) used the same key for both encrypted messages, the attacker can analyze the difference between the two encrypted texts. In contrast to random texts, plain texts and consequently also differences from plain texts show a number of abnormalities that can be statistically evaluated and used for deciphering. The letter frequency of differential texts shows just as characteristic abnormalities as, for example, that of plain texts or of monoalphabetic encrypted texts.

The following table shows the relative frequencies of the letters in ‰ ( per mille ) as the result of counting the difference between two German texts consisting of one million letters each . With an even distribution , one would expect each of the 26 letters to have a frequency of 1/26, i.e. 38.5 ‰.

A.	B.	C.	D.	E.	F.	G	H	I.	J	K	L.	M.	N	O	P	Q	R.	S.	T	U	V	W.	X	Y	Z
43	31	33	48	34	30th	33	31	42	39	37	37	50	38	38	39	44	30th	33	32	33	44	32	32	41	77

In the case of difference texts - if they come from two plain texts or from two ciphertexts encrypted using the one-time key method with an identical key - the letter Z dominates with around 77 ‰, which is due to the coincidences of identical letters in both plain texts and thus also (if the same one-time key is used twice ) occurs in both ciphertexts. A secondary maximum occurs with the letter M with 50 ‰. This is due to the coincidences of the letters E and R or R and E, which are common in German-language texts, and both have the same difference, namely 13. If the attacker discovers these abnormalities in the difference text, this confirms his suspicion of multiple use of a one-time key (see also: coincidence index ). Based on further statistical dependencies and with the help of special difference text bases as well as suitable trigram, tetragram and pentagram tables (see N-grams ) and computer-aided analysis of the various cases, the ciphertexts can now be attacked with promise.

In this way, the theoretically unbreakable one-time key procedure can suddenly be broken if errors occur in practical use.

Side channel attacks

If the length of the encrypted messages or the rate of message exchange varies, conclusions can be drawn about the content regardless of the encryption method. A tried and tested antidote to this are " filling spells " which simulate radio activity for the opponent, even where no messages are exchanged.

Summary

disadvantage

The one-time pad requires a key that is just as long as the message itself. For example, to encrypt the entire data on a hard disk drive , a second hard disk drive (of at least the same size) is required to store the key.

A physical random number generator is required to select the key, which is usually implemented in special hardware. The security of the one-time pad depends on the quality of the random number generator. A less elaborate alternative to the one-time pad is a stream cipher that works with a pseudo-random generator, but has no theoretical information security.

If you want to transmit encrypted messages using the OTP method, the key must be transmitted over a different (secure) channel than the message. For example, a CD with keys can be delivered by a messenger while the encrypted messages are being transmitted over the Internet. Due to the high logistical effort, the one-time pad for encryption could not establish itself in larger communication networks.

advantage

The one-time pad is theoretically secure against cryptanalysis and cannot be deciphered if the key is as long as the message and consists of characters that are random and independent, and if it is only used once for encryption. To ensure that the key is used once, it is advisable to permanently delete the key after it has been successfully decrypted so that a frequency analysis can be prevented. Under these conditions, the ciphertext can only be decrypted with knowledge of the key.

Other encryption methods (such as AES) achieve their security through the immense computational effort of the theoretically conceivable decipherment, which is practically impossible to implement in the foreseeable future. In other words, a potential attacker lacks the necessary resources (for example computing power or time) to be able to successfully carry out his attempt to decipher. The security of the one-time pad, on the other hand, is based on the one-time use of the key and the random choice of the key used. Used correctly, it offers unsurpassed security for two-way secret communication and cannot be broken even with any high computing power.

literature

Friedrich L. Bauer : Deciphered Secrets. Methods and maxims of cryptology. 3rd, revised and expanded edition. Springer, Berlin et al. 2000, ISBN 3-540-67931-6 .
Steven M. Bellovin: Frank Miller - Inventor of the One-Time Pad . Cryptologia . Rose-Hulman Institute of Technology. Taylor & Francis, Philadelphia PA 35.2011,3 (July), pp. 203-22. ISSN 0161-1194 .
Robert Louis Benson: The VENONA Story . Center for Cryptologic History, NSA , Fort Meade , USA ( PDF; 0.8 MB ). Retrieved January 5, 2011.
Rudolf Kippenhahn : Encrypted messages: secret writing, Enigma and chip card. Rowohlt, Hamburg 1999. ISBN 3-499-60807-3 .
Dirk Rijmenants: Is One-time Pad History? Cipher Machines & Cryptology, 2010 ( PDF; 0.1 MB ). Retrieved January 5, 2011.
Dirk Rijmenants: The Complete Guide to Secure Communications with the One Time Pad Cipher Cipher Machines & Cryptology, 2010 ( PDF; 0.2 MB ). Retrieved January 5, 2011.

Web links

Individual evidence

^ Steven M. Bellovin: Frank Miller: Inventor of the One-Time Pad. In: Cryptologia. Vol. 35, Issue 3, Rose-Hulman Institute of Technology. Taylor & Francis, Philadelphia (Pennsylvania) January 3, 2011, ISSN 0161-1194 , pp. 203-22, online at Columbia.edu, accessed January 31, 2017 (PDF; 2.4 MB).
↑ Simon Singh: Secret Messages . Hanser, Munich / Vienna 2000, ISBN 978-3-446-19873-9 , p. 178, online at DNB.de.
^ Johannes A. Buchmann: Introduction to Cryptography . Springer, New York 2001, ISBN 978-1-4419-9003-7 , chap. 4 , doi : 10.1007 / 978-1-4419-9003-7 ( springer.com [accessed January 31, 2017]).
↑ Claude Shannon: Communication Theory of Secrecy Systems (PDF; 563 kB). Bell System Technical Journal, Vol. 28, 1949 (October), pp. 656-715.

[1] Steven M. Bellovin: Frank Miller: Inventor of the One-Time Pad. In: Cryptologia. Vol. 35, Issue 3, Rose-Hulman Institute of Technology. Taylor & Francis, Philadelphia (Pennsylvania) January 3, 2011, ISSN 0161-1194 , pp. 203-22, online at Columbia.edu, accessed January 31, 2017 (PDF; 2.4 MB).

[2] Simon Singh: Secret Messages . Hanser, Munich / Vienna 2000, ISBN 978-3-446-19873-9 , p. 178, online at DNB.de.

[Buchmann-3] Johannes A. Buchmann: Introduction to Cryptography . Springer, New York 2001, ISBN 978-1-4419-9003-7 , chap. 4 , doi : 10.1007 / 978-1-4419-9003-7 ( springer.com [accessed January 31, 2017]).

[4] Claude Shannon: Communication Theory of Secrecy Systems (PDF; 563 kB). Bell System Technical Journal, Vol. 28, 1949 (October), pp. 656-715.