One-Time-Pad

The One - Time Pad (abbreviation: OTP, German: Once encryption key or one-time process, literally one- block, not to be confused with the one-time password method) is a symmetric encryption method for secret transmission of messages. It is characteristic that a key is used, the (at least) as long as the message is itself the OTP is information-theoretically secure and can not be broken demonstrably - provided it is used as intended.

  • 3.1 spying the key
  • 3.2 CryptoLogic insecure key
  • 3.3 Multiple use of the session key
  • 3.4 side-channel attacks
  • 4.1 advantage
  • 4.2 disadvantages

History

The process goes back to the American cryptographer Gilbert Vernam (1890-1960), who has expressed the idea for it in 1918. The American Joseph O. Mauborgne (1881-1971) sat around this idea and called it, "One - Time Pad " ( German: one- block ). Shortly afterwards, the Germans Werner Kunze, Rudolf Schauffler and Erich Langlotz worked on this method. They proposed in 1921 before, blocks that were printed with randomly generated numbers to use for over coding of former diplomatic codes, and designated it as i- worm (individual worm). This method has actually been used by the diplomatic service of the Weimar Republic.

Since that time to the present day, especially during the Cold War, this method is employed. For example, was the "hot wire " (also known as the " Red Phone " known ), ie the highly secure direct telex connection between the American president and the Soviet General Secretary, protected by a single key - method.

Method

Description

The One -Time Pad comes to be the polyalphabetic substitution method, in which the individual letters ( or characters) in each of the other letters (or characters ) are converted ( encoded ). A distinguishing feature of the one-time encryption is the unique use of a random key, the ( at least ) has the same length as the message to be encrypted.

Closely related to the one- time pad is the stream cipher in which the key is generated pseudo-randomly from a shorter key, a PIN or pass or password. Other historical and current cryptographic algorithms use keys that are usually much shorter than the length of the plaintext to be encrypted.

Both the plaintext and the key and the ciphertext are the One- Time Pad strings of length. In modern cryptology The amount of characters used, also called alphabet, usually the amount of bits in classical cryptography, the set of all uppercase letters. To encrypt the key one character added modulo the alphabet size on the plaintext. When using the bits of an exclusive OR (XOR ) of each bit corresponds. When using uppercase letters are added as in the Caesar cipher. For this they are first mapped to the integers from 0 to 25, then added modulo 26 ( it is subtracted from the result 26 if it is greater than 25) and the result is converted back to characters.

Basic requirements for the security of the session key process are: the one key must

  • Be at least as long as the message,
  • Distributed uniformly chosen at random,
  • Remain secret and
  • Must not be re-used, even partially.

This satisfies the one-time key method 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.

The session key method is well suited for machine implementation. Unlike many modern cryptographic methods (such as DES, AES or PGP ), which rely on computers because of their complexity, the one- time pad, however, is equally suitable for manual execution of encryption and decryption.

Security

The four conditions of key election ensure, together with the description of the procedure that the following conditions are met.

  • There are as many keys as possible cryptograms.
  • Are available for each plaintext - ciphertext pair exactly one key, which applied to the plaintext, the cipher results.

Under these conditions, the process of information-theoretically secure (also called perfect security ) and can not be broken even with arbitrarily high computational effort. Alone with knowledge of the key of the cipher text can be decrypted. This guessing is practically impossible, since each possible key is selected with equal probability. There is no way to find out if a key was guessed correctly or not. In another key choice, such as the use of text passages, this property would not be given.

Example

A simple hand method for encryption, for example, the letters, addition of plaintext and key. For this purpose, first we replace using any substitution table, the letters of the plaintext alphabet by numbers. In the simplest case, one assigns the 26 capital letters of the Latin alphabet to numbers that correspond to their position in the alphabet. In other words, you numbered the alphabet as follows:

ABCDEFGHIJKLMNOPQRSTU VWXYZ 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 Write letters, addition is easy. For example, results in the addition of A and F the letter G, in accordance with their seat numbers 1 6 = 7 If the sum should not exceed the value of 26, so we simply subtract 26 from ( modulo operation ) and gets so again one of the 26 alphabet letters. For example, X plus U is numerically 24 21 = 45, according to deduct 26 results 19 and thus the letter S, so X U = S.

The relationships in the addition of letters can be in the following table, the similarity has recta with a classic tab, clear presentation of:

ABCDEFGHIJKLMNOPQRSTU VWXYZ ABCDEFGHIJKLMNOPQRSTU VWXYZA BCDEFGHIJKLMNOPQRSTUV WXYZAB CDEFGHIJKLMNOPQRSTUVW XYZABC DEFGHIJKLMNOPQRSTUVWX YZABCD EFGHIJKLMNOPQRSTUVWXY ZABCDE FGHIJKLMNOPQRSTUVWXYZ ABCDEF GHIJKLMNOPQRSTUVWXYZA BCDEFG HIJKLMNOPQRSTUVWXYZAB CDEFGH IJKLMNOPQRSTUVWXYZABC DEFGHI JKLMNOPQRSTUVWXYZABCD efghij KLMNOPQRSTUVWXYZABCDE FGHIJK LMNOPQRSTUVWXYZABCDEF GHIJKL MNOPQRSTUVWXYZABCDEFG HIJKLM NOPQRSTUVWXYZABCDEFGH ijklmn OPQRSTUVWXYZABCDEFGHI JKLMNO PQRSTUVWXYZABCDEFGHIJ KLMNOP QRSTUVWXYZABCDEFGHIJK LMNOPQ RSTUVWXYZABCDEFGHIJKL MNOPQR STUVWXYZABCDEFGHIJKLM NOPQRS TUVWXYZABCDEFGHIJKLMN OPQRST UVWXYZABCDEFGHIJKLMNO PQRSTU VWXYZABCDEFGHIJKLMNOP QRSTUV WXYZABCDEFGHIJKLMNOPQ RSTUVW XYZABCDEFGHIJKLMNOPQR STUVWX YZABCDEFGHIJKLMNOPQRS TUVWXY ZABCDEFGHIJKLMNOPQRST UVWXYZ In the italicized upper row and the first column on the left edge, the two summands to be added are indicated. In the crossing point within the table the sum can be read, so the result of the summation of plain text letters and letters of the keyword. This is the corresponding letter in the ciphertext.

For encryption, you will use a random key, which is fittingly also composed in this example case from the 26 capital letters and its length (at least) equal to the length of the plaintext to be encrypted. It is crucial for the security of the encryption that the individual character of the key are truly randomly distributed, are unpredictable and communicate with each other in any context. As an example of a random key, the following sequence of letters is:

S = WZSLXWMFQUDMPJLYQOXXB The key S in this example is quite short, it contains only 21 letters, and is "used up" very quickly if used properly, that is already on the encoding of a text from 21 letters.

For example, the following plaintext K should be encrypted:

K = ANGRIFFIMMORGENGRAUEN For encryption plaintext key K and S, as explained above, letter by letter added. As a " sum " (K S = G) is obtained by the so- conducted once encryption the ciphertext C:

G = XNZDGCSODHSEWOZFIPSCP The obtained results in the ciphertext G is indistinguishable from a random text and can in principle be with any of the most kind cryptanalytic attack method ( either now or in the future) deciphered. Only the knowledge of the key S allows to regain from the ciphertext G by subtracting the key plaintext K. Without the key, you can basically " construct " all possible and more or less meaningful combinations of letters of 21 letters. Theoretically you could try this one attacker. He would then get a ton of records that would announce any information in any language, for example,

S '= AEOUQXOFCBJQSJLIZXLHV This key S ' satisfies the condition that the letter by letter sum of it with the above generated (fake) plaintext K' exactly the same ciphertext obtained as the sum of the real ones, but the attacker unknown key S with the real ones, but the attacker also unknown plaintext K. Thus, the attacker can construct an immense wealth of possible plaintext key pairs, which all give the same real ciphertext ( letter wise ) sum. However, he has no way to infer from it the real plaintext. Even brute force, ie, the exhaustive search on all possible keys does not lead to success. Although the attacker can so - even without even knowing the ciphertext - generate all possible texts with 21 characters, among which, of course, the original will be. There are, however, to decide which is from the plethora of quite meaningful texts of the actual plaintext no clues. As long as it does not fall into the hands of the key, the plaintext remains forever a mystery.

In order not to compromise this safety, the session key should be destroyed forever after normal use.

Of attack

With the correct application of the one-time key method is OTP, as the American scientist Claude Shannon showed in the 1940s, proven to be safe and can not be broken. In practice, however mistakes can happen that make a slump possible. This is due to the violation of basic safety measures.

Spying the key

One possible error is to exchange the session key is not secret between the transmitter and receiver so that it can be spied out by others. Also a safe storage of the key is essential. Unlike passwords, or passwords to a single key can hardly remember. He must on any media, be it paper, data disk, CD -ROM or USB stick can be stored. Such a medium - and with it the key - can be easily copied. Likewise, do not forget to destroy the session key after use hardrive. If it is possible for the attacker to find the key later, or to restore, the communication is no longer a secret.

CryptoLogic insecure key

A cardinal mistake is to use it as a one-time key no random letters, but a passage of text. Even if the text used is unique and no one (except the two communication partners ) is known to have sequences of letters, which come from a " meaningful " text, as opposed to random letter strings ( random text ), allowing statistical analysis dependencies that can make decryption possible.

Thus again the original can not be reconstructed from the ciphertext without the key, the key must be cryptologically sure that he may not depart from a truly random numbers or letters be indistinguishable. If it is not, then an attacker may by cryptanalysis, also without knowing the key, decrypt the text.

A physical random number generator is to generate a secure key cryptologically ideally used because only those deliver truly random, ie non- deterministic values ​​.

In principle also a generator of pseudo-random numbers can be used. But then the key must not be so long that you could close out of it on the internal state of the generator, otherwise all subsequent values ​​could be predicted. Which is of simple generators (such as Congruential ) after only a few values ​​of the case. In cryptographically secure generators this can be significantly longer episodes, but they are also deterministic and can theoretically still be cracked.

Multiple use of the one-time key

An in practical applications (examples: Lorenz cipher machine and Venona ) already common mistake is to create more than just the two, intended only for the sender and receiver copies the session key and distribute or use the key more than once for encryption. Already a two-time using a session key is enough to attack the communication can be promising.

The attacker starts from the following consideration: Suppose the sender has both encrypted messages ( accidentally) uses the same key, then the attacker is able to analyze the difference of the two encrypted texts. Plaintexts and consequently differences of plain texts show that is in contrast to random texts, a number of abnormalities that can be statistically analyzed and exploited to decipher. Thus, the frequency of letters difference texts also shows characteristic abnormalities such as the plain text or by monoalphabetically encrypted texts.

The following table shows the result of a count of the difference of two German texts from each one million letters the relative frequencies of the letters in ‰ ( per mille ). In a uniform distribution, one would expect each of the 26 letters with a frequency of 1/ 26, ie 38.5 ‰.

For differential texts - if they come from two plaintexts or two after the one-time key - method with an identical key encrypted ciphertexts - dominates the letter Z with about 77 ‰, the same by coincidence of identical letters in both plain text and thus also ( in duplicate using session key ) occurs in both ciphertexts. A secondary maximum occurs at the letter M with 50 ‰. This is caused by the frequent coincidences in German texts letters E and R or R and E, which both have the same difference, namely, 13. If the attacker discovered these abnormalities at the differential text, this confirms his suspicions of the multiple use of a single key ( see also: coincidence index). Based on further statistical dependencies and using special differential text bases and matching trigram, tetragrammaton and pentagram tables and computer-based analysis of the different cases, the ciphertexts can now be attacked promising.

In this way, theoretically unbreakable one-time key method may suddenly be broken yet, if mistakes happen in the practical application.

Side-channel attacks

Varies the length of the encrypted messages or the rate of message exchange, so let that, regardless of the encryption method, to draw conclusions about the content.

Summary

Advantage

The one-time pad is information-theoretically secure and can not be deciphered, if the key is as long as the message and consists of characters that are randomly and independently, and when it is used only once for encryption. Under these conditions, the ciphertext can be decrypted only with knowledge of the key.

Other encryption algorithms ( including AES ) to achieve their safety by the immense amount of calculation of the theoretically possible decipherment, which is practically not feasible in the foreseeable future. In other words, a potential attacker lacks the necessary resources (such as computing power or time) in order to successfully carry out its decryption attempt can. The security of the one- time pad, however, is based on the unique use of the key and the random choice of the key used. It can not be broken even with arbitrarily high computational power.

Disadvantages

The one- time pad requires a key that is as long itself to encrypt as the message, for example, the data of an entire hard disk drive, a second hard drive ( with at least the same size ) for storage of the key is necessary. If you want to transmit encrypted messages with the OTP method, the key must be transmitted over a different ( secure ) channel as the message. For example, a CD with keys will be delivered by a messenger, while the so encrypted messages are transmitted over the Internet. A theoretical alternative to waive a messenger, the quantum key exchange is: It is a method that can generate a shared key secret with the spatially separated transmitter and receiver.

A more theoretical problem is that the individual characters of the key must be completely random and independently generated. Ideally, this can be achieved only by a non-deterministic physical random number generator. In practice, one often waived and shall be satisfied with more or less good random number generators.

Due to the high logistic effort, the one- time pad for encryption could not prevail in large communication networks. For the two-sided secret communication but it is in terms of safety as the first choice.

Joseph Mauborgne Alphabet (computer science) Advanced Encryption Standard Tabula recta Floppy disk CD-ROM Index of coincidence The Code Book
299184
de