How to break stream ciphers with repeating keystreams

Stream ciphers usually generate a keystream from a secret key and other input. The encryption function XORs the plaintext with the keystream. The decryption function XORs the ciphertext with the keystream. Examples of stream ciphers that work like this are AES-CTR and ChaCha20. If the keystream ever repeats itself, the respective ciphertexts can be decrypted without knowledge of the secret key quite easily. To do this is especially easy if the attacker manages to encrypt a message of their choosing with the repeating part of the keystream. In this post, I will show how the decryption works in such a case.

Theory

The scenario is this: The attacker wants to decrypt a given ciphertext cipher_secret and knows a plaintext-ciphertext combination (say, plain_known and cipher_known), where cipher_known has been encrypted with the same keystream as cipher_secret.

So we have:

cipher_secret = plain_secret XOR keystream
cipher_known = plain_known XOR keystream

cipher_secret can now be decrypted with just two XOR operations. First, we calculate the keystream:

keystream = 0 XOR keystream
          = (plain_known XOR plain_known) XOR keystream
          = plain_known XOR (plain_known XOR keystream)
          = plain_known XOR cipher_known

Now, we decrypt cipher_secret as usual:

plain_secret = cipher_secret XOR keystream

Example

Let's try this method in a *nix shell! The vulnerable application may encrypt plaintexts with AES-CTR using hard-coded counter blocks. This can be simulated with OpenSSL by using a fixed IV:

$ function enc() {
  echo -n $1 | openssl enc -aes-256-ctr \
    -K 000102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f \
    -iv 00000000000000000000000000000000
}

We use this function to generate the ciphertext known by the attacker:

$ cipher_secret=$(enc "I am secret")
$ echo -n $cipher_secret | hexdump -C
00000000  bb b0 61 db 0a 3a fa b3  db 96 ee                 |..a..:.....|
0000000b

Now, the attacker lets the application encrypt a plaintext with the same length (11 bytes):

$ plain_known="01234567890"
$ cipher_known=$(enc $plain_known)

I'll use the xor shell function from my last post to do the XORing:

$ keystream=$(xor $plain_known $cipher_known)
$ xor $cipher_secret $keystream
I am secret

That worked :)

The procedure is not dependent on the cipher algorithm, as long as it works by XORing the plaintext/ciphertext with a keystream. For example, you'll get the same result (with different ciphertexts) if you use ChaCha20 instead of AES-CTR:

function enc() {
  echo -n $1 | openssl enc -chacha20 \
    -K 000102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f \
    -iv 00000000000000000000000000000000
}

The case without known plaintext

What if the attacker doesn't know the plaintext corresponding to one of the ciphertexts, i.e. plain_known isn't actually known? In this situation, we have:

cipher_1 = plain_1 XOR keystream
cipher_2 = plain_2 XOR keystream

And therefore:

cipher_1 XOR cipher_2 = plain_1 XOR plain_2

So the attacker can't immediately calculate the plaintexts but the result of XORing two plaintexts, which is also quite bad: If one has some knowledge about the structure of the plaintexts—such as common words or most likely bytes—it becomes surprisingly simple to brute-force one plaintext and thereby reveal the other. I have demonstrated this technique here.