Contents ::

1. The One-Time Pad
2. The Perfect Cipher
3. When Perfection becomes not so Perfect
4. OTP in the Wild

 

The One-Time Pad

If you have read the article Bitwise Operation or have dabbled in cryptography before a bit, you should be familiar with the XOR operation. This simple operation is interesting because of its bijective property, i.e. it is invertible. This means I can XOR the bitstring of my message LearnCyber with some key, say duckieRULZ, to obtain my ciphertext.

01001100 01100101 01100001 01110010 01101110 01000011 01111001 01100010 01100101 01110010
01100100 01110101 01100011 01101011 01101001 01100101 01010010 01010101 01001100 01011010
-------------------------------------------------------------------------------------------- + mod 2 (XOR)
00101000 00010000 00000010 00011001 00000111 00100110 00101011 00110111 00101001 00101000

// or in bytes: (\x10\x02\x19\x07&+7)(

If done correctly, this one-time pad technique allows us to store secrets under perfect secrecy. As a brief recap, perfect secrecy implies that absolutely no information whatsoever can be learned about the plaintext from its corresponding ciphertext. This deep-dive article will seek out to accomplish three goals:

1. Show the one-time pad is indeed perfectly secret;
2. Show under what conditions perfect secrecy is achieved;
3. Show what goes wrong if not used correctly.

 

The Perfect Cipher

As we discussed in the article Perfectly Secret or Computationally Secure, perfect secrecy is achieved if the probability distribution of the message does not change upon revealing the ciphertext. In other words, the posterior probability is equal to the a prior distribution,

$$P(M=m|C=c)=P(M=m).$$

To show this holds for the one-time pad, assume we have a plaintext messsage $m$, of length $n$ bits, and a key of equivalent length randomly chosen from a uniform distribution over the full $n$-bit space. Starting with the Bayesian definition of the posterior probability,

$$P(M=m|C=c)=\frac{P(M=m)P(C=c|M=m)}{P(C=c)},$$

we say that the probability of the ciphertext being $c$ given the plaintext being $m$ is equal to the probability of the key being the exact key that links said ciphertext to said plaintext. As our keys are uniformly chosen we know that

$$P(C=c|M=m)=P(K=k)=2^{-n}.$$

Next, we can express the probability of the ciphertext being $c$ WITHOUT knowing its plaintext is equal to the sum of the products of probabilities of each plaintext being $m$ and the key being the exact key that connects the two,

$$P(C=c)=\sum _{m\in M}P(M=m)\cdot P(K=k)=2^{-n}\sum _{m\in M}P(M=m).$$

Furthermore, the message must be within the message space such that a sum of the message probability distribution over the entire message space will always equal to unity, and thus

$$\sum _{m\in M}P(M=m)=1.$$

Plugging everything we learned so far into the definition of the posterior probability we find exactly what we expect,

$$P(M=m|C=c)=\frac{P(M=m)\cdot 2^{-n}}{1\cdot 2^{-n}}=P(M=m)$$

It should be noted that we were only able to arrive at the desired result because of our assumption of the key being randomly chosen from a uniform distribution, such that

$$P(K=k)=2^{-n}.$$

In turn this allows us to pull the constant out from the sum in the denominator and cancel out with the numerator itself. If there is even the slightest deviation from a uniform distribution then the one-time pad does no longer satisfy perfect secrecy.

So what happens in this case, and when can we expect it to happen? Let's check out some common scenarios and what exactly goes wrong.

 

When Perfection becomes not so Perfect

Say I managed to extract a random key from a good entropy source for my message, but then I realised I forgot to add part of my message. Now that my extended message is larger than my key, how should I proceed?

~ thinking space ~

The correct answer is to get a new random key from the entropy source. Sadly, certain protocols will refer to other methods like repeating the key, or extending it using some simple algorithm. In either case the new key is no longer random, i.e. the added part is not independent from the pre-existing part. As we discussed above, this implies a one-time pad using the new key will not be perfectly secure and thus leak information about my underlying message. Let us take a look at some examples.

Example 1 :: Encrypted HTTP Response

Say we have managed to intercept an HTTP response encrypted by a repeating OTP key, for instance ::

b"j\xfe\xbf\xach\xeeX\x92\xfdjt\r\x1c_k*@\xb6@\xd1\xc6\xd5T\xfaL\x86\xcb\xces\xff2\xc6\xbexv\r\x0e#\x00\x124\xed\x01\x82\xc6\xc70\xafe\xe7\xbf\xf6\x14\xba\x04\xd5\xb8*~\x1d[gS*G\xb8Z\xc0\x99\x9bs\xa2v\xd3\x9b\x99}\xff\x02\xc6\xa5,kUH}L\x1b$\xb4\\\xd5\x8e\x86b\xfb\x1f\xff\xbf\xbaj\xe7|\xe0\xb260XRd\rla\xb9S\xc0\x94\xcf'\xba\x15\xa0\xe1\xa8/\xbaV\xd0\xb8;6XH0FLe\xb0\x14\xdd\x8f\xd5C\xfaA\xc1\x82\x99<\xb2B\xcd\xa4\x070\x0cQ#\x7fP0\xb3k\xdc\xc8\x86X\xe2\x16\xc4\x92\xa3v\xac\x05\xd6\xee+9\x13"

Most, if not all, HTTP responses will start with the string HTTP/1.1 followed by a response code. If the request was valid it is highly likely the follow-up is 200 OK\n. Under this assumption we can already recover 16 bytes of the used one-time pad key.

b"HTTP/1.1 200 OK\n"  -->  b'"\xaa\xeb\xfcG\xdfv\xa3\xddXD=<\x10  '

For a correctly generated OTP key this would not be of any consequence as the rest of the key is independent from the recovered bytes. However, in this situation we know a short OTP key was repeated. Therefore, now that we have a partial key we can start looking for the used key length by simply appending our partial key with zero bytes, decrypting the ciphertext, and look for recognisable pieces of plaintext. Starting from a key length of 16, we will eventually try a key length of 23. The result however, is just garbage.

b'HTTP/1.1 200 OK\n@\xb6@\xd1\xc6\xd5T\xd8\xe6m7\x89\xac\x89\x91\x1b\xe6<K1\x1e\x03 \x124\xed\x01\x82\xc6\xc7\x12\x05\x8e\x1b\xf8)b\x19\xd9\x8d\xfc\x17B\r{GS*G\xb8Z\xc0\x99\xb9\xd9I\x8a\x94D\xef\xde"Z\x82\x98\x10{uh}L\x1b$\xb4\\\xd5\xac,\x89\x07X \xc9\x19\xb7\xbf8\xdd\x8e&\x10xRd\rla\xb9S\xe2>$\xdb\xfd\xca\xd6Buw\xfek\xec\xa8\x1b\x16XH0FLe\xb06wd)\x04%7b_\xc1x\x8f~\xdd\x84\'0\x0cQ#\x7fP0\x91\xc174\xc1\x87\x94\xb5\x19\xca\xe7K\x90\x15\xf6\xce+9\x13'

But if we then try a length of 24 we suddenly see some recognisable pieces of text at regular intervals ~ !

b"HTTP/1.1 200 OK\n@\xb6@\xd1\xc6\xd5T\xfan, 24 Dec 2023 24\xed\x01\x82\xc6\xc70\xafGMT\nServer: gws\nG\xb8Z\xc0\x99\x9bs\xa2Type: text/html;$\xb4\\\xd5\x8e\x86b\xfb=UTF-8\nContent-La\xb9S\xc0\x94\xcf'\xba7\n\nThe secret fle\xb0\x14\xdd\x8f\xd5C\xfackie{m4ny_t1m3_p0\xb3k\xdc\xc8\x86X\xe24ny_1ssu3s}."

With the extra revealed pieces of plaintext we might be able to predict unrevealed pieces to reveal the rest of the key. For example:

# X are unknowns
b"Content-La\xb9S\xc0\x94\xcf'\xba7"  -->  b"Content-Length: XX"
b"@\xb6@\xd1\xc6\xd5T\xfan, 24 Dec 2023 24\xed\x01\x82\xc6\xc70\xafGMT"  ->  b"Date: XXn, 24 Dec 2023 2X:XX:XX GMT"
b"G\xb8Z\xc0\x99\x9bs\xa2Type: text/html;$\xb4\\\xd5\x8e\x86b\xfb=UTF-8"  -->  b"Content-Type: text/html; charset=UTF-8"

With some knowledge of HTTP responses we can recover the full 24-byte key.

b'"\xaa\xeb\xfcG\xdfv\xa3\xddXD=<\x10  \x04\xd74\xb4\xfc\xf5\x07\x8f'

Revealing the decrypted HTTP response to contain a secret flag ~ !

HTTP/1.1 200 OK
Date: Sun, 24 Dec 2023 20:56:27 GMT
Server: gws
Content-Type: text/html; charset=UTF-8
Content-Length: 57

The secret flag is Duckie{m4ny_t1m3_p4d_h4s_m4ny_1ssu3s}.

Ta-da ~ !

If we do not know enough about the underlying plaintext we might not be able to use such pattern analysis techniques. However, a case of one-time pad key re-use is identical to the repeated Vigenere key case. Therefore, we should be able to apply the same frequency analysis techniques as we have before.

Another significant potential vulnerability of the one-time pad is its reliance on a good entropy source. If the key is sampled from anything but a uniform distribution of the entire plaintext/ciphertext space, it will leak information. How much information it leaks will depend on how much the used distribution differes from the full uniform distribution. Care for an example?

Example 2 :: Readable OTP Key

In this example we will take a look at a sloppy cryptographer that likes to write their important keys down in their diary, lest they forget them. Bytes are not nicely written however, so he choses to represent his generated keys and ciphertexts in base64. To do so, he wrote two python functions. One to generate a random OTP key in base64 and another to encrypt some plaintext bytes into a base64 ciphertext.

import os, base64

def OneTimeKey(length: int) -> bytes:
    key = os.urandom(length)
    return base64.urlsafe_b64encode(key)

def OneTimePad(plaintext: bytes) -> bytes:
    key = OneTimeKey(len(plaintext))
    ciphertext = bytes([i ^ j for i,j in zip(key, plaintext)])
    return key, base64.urlsafe_b64encode(ciphertext)

OneTimePad(flag)

(b'I42LSIUjYNjx7AUfogZv4knpLHppxaFZcAJllu5tPJGC7NM=',
 b'DUFRJzosLhhqeg5MVS1mOQ0SLikABx1AEyoCQ0wKcjgPcjc=')

So what might be going wrong here? Surely it does not matter what data encoding you use for your plaintext, key, and ciphertext? What is important however, is WHEN you apply the encoding steps relative to the encryption step. More specifically, the encryption step should be done using the same encoding for both the plaintext and key. See where this is going wrong in the sloppy cryptographer's code?

In the code, the key is encoded in base64 and then XORed with the plaintext, which is still encoded in bytes. Therefore during the encryption step, each plaintext byte is XORed with the corresponding character of the base64 encoded key. So 256 possible plaintext values, but only 64 possible key values. Now, remember the criteria for perfect secrecy? A perfectly uniform key distribution over a key space of equal or larger size than the ciphertext space. In this case, we have a significantly smaller key space, of 64, compared to the ciphertext space, of 256. In other words, goodbye perfect secrecy ~ o/.

But how exactly would repeated encryptions of the same secret leak it? For every ciphertext value, we can reverse the encryption by just trying all 64 key values to see a total of 64 possible plaintext values that could have created this ciphertext. Of course we do not know which one is the true one yet, but we have surely narrowed it down from 256 to just 64 already. If we do the same once more, but for a different ciphertext (of the same secret), we will most likely get a different set of 64 possible plaintext values. The true value, however, must be present in both sets of possible values. More specifically, it has to be present in ALL sets of possible plaintext values for any number of ciphertexts we can collect. So let's collect some ciphertexts first.

ciphertexts = []
for _ in range(1024):
    ciphertexts += [base64.urlsafe_b64decode(OneTimePad(flag)[1])]

Now we can start our straightforward, although somewhat inefficient, approach to find the first secret plaintext value ~ !

base64Alphabet = b"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-_"
possibleValues = [ciphertexts[0][0] ^ i for i in base64Alphabet]

i = 1
while len(possibleValues) > 1:

    newPossibleValues = [ciphertexts[i][0] ^ j for j in base64Alphabet]

    possibleValues = [j for j in newPossibleValues if j in possibleValues]

    i += 1

print(i, possibleValues, bytes(possibleValues))

5 [68] b'D'

Looks like we were able to find the first plaintext value, a 'D', by cross-referencing just five ciphertexts. The number of ciphertexts you will need varies purely based on chance, so make sure to always gather more ciphertexts than you think you will need. Finally, creating an outer loop that iterates over the entire secret length will recover the full secret in no time ~ !

recoveredSecret = []

for k in range(len(ciphertexts[0])):

    possibleValues = [ciphertexts[0][0] ^ i for i in base64Alphabet]

    i = 1
    while len(possibleValues) > 1:

        newPossibleValues = [ciphertexts[i][0] ^ j for j in base64Alphabet]

        possibleValues = [j for j in newPossibleValues if j in possibleValues]

        i += 1

    recoveredSecret += possibleValues

print(bytes(recoveredSecret))

b'Duckie{r34d4bl3_but_4ls0_br34k4bl3}'

Ta-da ~ !

 

OTP in the Wild

Knowing that one-time pads can provide perfect secrecy, why do we not see them used more often as the to-go encryption standard? The reason is fairly straightforward, the requirement of the key being at least of equal length as the plaintext is not efficient enough for modern day internet traffic volumes.

HOWEVER

There is a small trick to still make it work. Instead of generating a plaintext-sized key, we only generate a small key, say 16 or 32 bytes. We then use that as a seed for a cryptographically secure pseudo-random number generator to generate a new larger key, the so-called key stream. Of course, as should be obvious after reading this article, this will not be perfectly secret. Instead, we must assure it is now computationally secure, as its security is now dependent on the security of the underlying PRNG properties. If the PRNG is secure enough, then so is the one-time pad scheme. Encryption schemes that use a small master key together with a cryptographically-secure PRNG to produce such key streams are called stream ciphers. These stream ciphers are usually fast and memory cheap, but not without their own pitfalls. Some of the most notably ones are stream re-use, stream malleability, and PRNG weaknesses. We will go more in-depth when we start discussing stream ciphers.

When is seemingly random data extracted from a smaller master key considered random enough to be secure? What does it even mean for data to be random and how can we assess it? All that and more will be discussed in the next article. But first, make sure to test your understanding of the one-time pad using the quiz below ~ !