# One-Time Pad

The one-time pad is a very well-known stream cipher that has a very simple implementation, and is impossible to break if used correctly. This makes the one-time pad the most secure cryptographical method. It was not adopted widely due to the difficult implementation in many different situations and also because it is malleable, which I will describe at the end of this article. But appart from that, the one-time pad is used as an inspiration for other stream ciphers as well as for more complex situations such as quantum key distribution.

It consists of a message and a random key, which is usually generated using a pseudo random generator (PRG). This key must have exactly the same length as the message and the reason for that is pretty obvious once the implementation is known.

Before I describe the implementation of the algorithm, I would like to make an observation. When using the one-time pad, the key must never be reused and the PRG must be secure and use a proven random generating method.

*Now let's understand how it works...*

Imagine you have a message you want to encrypt, and a key. We'll call the message, M, and the key, K. Once you encrypt the message using your key you end up with a ciphertext which we'll call, C.

There are two methods that can be applied on the one-time pad: modular addition and XOR. I prefer to xor information since it is more useful on binary messages and perform well in any situation. When modular addition is used, it generally uses mod 26 for characters and mod 10 for digits. I'll use as an example the XOR operation for this article.

The one-time pad algorithm is as easy as shown below:

M XOR K = C

Note that for decryption the same operation works flawlessly due to the nature of XOR:

C XOR K = M

But the world is not perfect, and since it is impossible to reuse keys, it is very difficult to be used in situations where both the receiver and the sender must know the key.

There are two known vulnerabilities on the one-time pad when it is used wrong. Let's attack them!

**ATTACKS:**

**(1) Two-Time Pad**

The two time pad is a vulnerability for every situation where the same key is used more than once. Suppose you have two messages [m1,m2] and you use the same key [k]. This means you have two ciphertexts [c1,c2]. This can be seen below.

M1 XOR K = C1

M2 XOR K = C2

Since we know the nature of XOR, we can apply the two-time pad as shown below:

C1 XOR C2

Which is the same to say:

(M1 XOR K) XOR (M2 XOR K)

Hence we can eliminate the key...

M1 XOR M2

Now that I have M1 XOR M2, and both the ciphertexts C1 and C2, it is easy to analyze and find the key [k]. This shows why the same key must never be used!

**(2) Tampering**

If the pattern of the file is known, it is quite easy to manipulate data and make it look like something else. For example, if we used one-time pad to encrypt a file that always started with "foo". In such case we can always manipulate the start of the file to look like anything else, which I'll show below with pure math.

Let's suppose I'd like to make all files start with "bar". My first step would be to xor both "foo" and "bar" as shown below:

"foo" XOR "bar" = T

Let's call T the answer for the tampering that will be used on all files. Since we know that XORs can be nulified if two values are repeated, than it has been seen the potential threat of this attack. I'll illustrate the potential attack below:

"foo" XOR T

"foo" XOR ("foo" XOR "bar")

We see that "foo" is repeated and now we end up having "bar" because:

"foo" XOR "foo" = 0

Hence:

"foo" XOR "foo" XOR "bar" = 0 XOR "bar" = "bar"

So as shown above, if the attacker wants to modify data of a pattern-known file, he just have to use the technique described.

**Sources:**

[1] Dan Boneh - Cryptography 1 - *http://www.coursera.com*