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 just by 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
}