The one time pad and the many time pad vulnerability

The scope of this article is to present the one time pad cipher method and its biggest vulnerability: the many time pad attack.

The one time pad: what it is and how it works

The one time pad is the archetype of the idea of stream cipher. It's very simple: if you want to make a message unintelligible to an eavesdropper, just change each character of the original message in a way that you can revert, but that looks random to another person.

The way the one time pad works is the following. Suppose \(\mathcal{M}\) is the clear-text message you would like to send securely, of length \(|\mathcal{M}| = s\). First, you need to generate a string \(\mathcal{K}\) of equal length \(|\mathcal{K}| = s\). Then, you can obtain a cipher-text version of your message by computing the bitwise XOR of the two strings:

The best thing is that decoding is just the same as encoding, as the XOR operator has the property that \(\mathcal{X} \oplus \mathcal{X} = 0 \ \forall X\) (and that \(\mathcal{X} \oplus 0 = \mathcal{X} \ \forall \mathcal{X}\)). The only difference is that the cipher-text is involved in the XOR, rather than the clear-text:

Below is an example of the one time pad encoding achieved with Python, with a made-up pad string.

In the first section, result holds the XOR result. In the second part, the result and one_time_pad variables are XORed together to obtain the original plain-text message again.

Since XOR is a fundamental logical operation, and the only other element we used is the string \(\mathcal{K}\) (which is the pad the technique takes its name from), it's clear that the algorithm's strength must lie in \(\mathcal{K}\). If an attacker gains access to \(\mathcal{K}\), then it's oviously game over, as we've seen that decryption is straightforward then.

We said one requirement of \(\mathcal{K}\) is that it should be of the same size of the message, otherwise there are not enough bytes to XOR with, and part of the message is revealed. But the other, more subtle but still fundamental, requirement is that each \(\mathcal{K}\) must be used once and once only (that's where the one-time comes from). Understanding why this second requisite is important is the scope of this article.

The many time pad vulnerability

If the same key is used more than once, bad things will happen and you will go to hell. As soon as you have encoded a message with a given pad, throw it away immediately and for good! That's what makes the One-Time Pad so tricky: when keys still laid on stacks of paper in different continents, people had to be scrupulous in burning away the key sheet they had just used, to ensure their stack was always exactly in the same state as their peer's. The one time pad is simple, and yet one little bit of carelessness can break it!

Let's look at what happens if the same key \(\mathcal{K}\) is used more than once. Suppose an attacker intercepted some of the cipher-text messages, but did not have the key used to encode them. Could the attacker get something out of them, if they had been encrypted with the same key? Suppose we have two ciphertexts at our disposal:

where in the last line we have used the fact that the XOR is a commutative operator, and that \(\mathcal{K} \oplus \mathcal{K} = 0\).

But behold! Given only two cipher-text, we retrieved a combination of the original plain-text messages! We may have not recovered the original messages yet, but the way is short from here.

For the sake of simplicity, let's assume that plain-text messages are made up only of letters (both lower and uppercase) and spaces. What we need is just one stroke of genius. The question we now need to ask is: what happens when two characters from the plain-texts are XORed together?

Using the ASCII encoding, we can build the following (symmetric) table:

The crucial part is the last line of the table. When XORing a space with any of the upper/lowercase letters, a number \(\geq 65\) is obtained. And notice, that is the only case when this happens!

Imagine to have the three following plaintexts:

Attack now
Withdraw tomorrow
Come today

and suppose we know they have been encrypted with the same one time pad. As seen above, we don't need to consider the key \(\mathcal{K}\), as that can be made to vanish if used multiple times. Let's look at the messages split in columns:

I will treat messages as arrays: the first char of the first message will be \(\mathcal{M}\_0[0]\), the second char of the second message will be \(\mathcal{M}\_1[1]\), and so on.

Let's look at the 7th column, where the first message has a space. What happens if we XOR \(\mathcal{M}\_0[6]\) with \(\mathcal{M}\_1[6]\) and \(\mathcal{M}\_2[6]\)? As expected, we get:

So it seems we can pretty confidently assert that \(\mathcal{M}\_0[6]\) is a space. But since \(\mathcal{M}\_0[6] \oplus \mathcal{M}\_1[6]\) is known, we can easily recover \(\mathcal{M}\_1[6]\) as well! And, of course, we can do the same with \(\mathcal{M}\_2[6]\). Boom!

But the best is yet to come! We know that \(\mathcal{C}\_0 = \mathcal{M}\_0 \oplus \mathcal{K}\). Thus, we can now recover one char of the key itself:

Now we are able to decode any 7th character of any message encoded with the same \(\mathcal{K}\)! If we intercept enough ciphertexts, all encoded with the same one time pad key, it's likely that there will be enough spaces spread throughout all columns to allow a fair amount of decryption with this method. Even if that would not be the case, enough spaces would probably be present to assure at least a partial decryption, that may then be completed by hand.

To sum up, the idea of the many time pad is that:

It is surprising how much one can do with seemingly useless information. It becomes clear now why cryptographic protocols should never leak any information whatsoever!

Python code for many time pad

The many time pad vulnerability is pretty powerful. It is not difficult to understand, and not so difficult to implement. Below is an almost-working Python code that you may draw inspiration from.

key = bytearray(b'?' * max_length)

    #Key decrypting routine
    for k in range(max(len(c) for c in ciphertexts)):
        cts = [c for c in ciphertexts if len(c) > k] #selects all cipher texts long at least k
        guess = ord('?') #holds guess for current key char

        for curs1 in range(len(cts)):
            for curs2 in range(len(cts)):
                if curs2 == curs1:
                    continue

                xor = ord(cts[curs1][k]) ^ ord(cts[curs2][k])

                if 0 < xor < 65:
                    guess = ord('?')
                    break
                guess = SPACE

            if guess == SPACE: #we can use the space to recover one key char and decrypt the whole column!
                key[k] = ord(cts[curs1][k]) ^ SPACE
                break

    #Decode messages
    for k in range(len(key)):
        for curs in range(len(cleartexts)):
            if len(cleartexts[curs]) > k:
                cleartexts[curs][k] = key[k] ^ ord(ciphertexts[curs][k])

    print("\n".join(c.decode('ascii') for c in cleartexts))