Breaking CTR with fixed nonce

September 05, 2021

In this post we will investigate the “break fixed-nonce CTR” exercise from Cryptopals. It’s helpful to read the problem statement before reading this blog post and I highly recommend attempting the previous exercises yourself as they do a great job ramping up your knowledge on the subject. We also have a previous post explaining how CTR works.

In this exercise we are presented with 40 CTR-encrypted ciphertexts and we know that each of them were encrypted under the same nonce.

In CTR a nonce is just a random value that will be concatenated with a counter, both are usually 8 bytes each. Once these two values are concatenated they will be encrypted under AES-128-ECB and then XORed with 16 bytes from our plaintext. As a reminder, here’s the full process:

CTR Encryption by Gwenda

Thought process

We have 40 CTR-encrypted ciphertexts under the same nonce, so what’s wrong with that? At first I had no idea, so I decided to look closely at the encryption process and try to derive some commonality between this exercise and problems that I have previously solved.

For the sake of simplicity let’s imagine that we only have two plaintexts being encrypted under a fixed nonce and the same key and try to encrypt it ourselves:

Nonce: [33, 112, 111, 116, 97, 116, 111, 33]

Key: [76, 80, 122, 102, 50, 110, 51, 198, 232, 120, 106, 233, 189, 55, 5, 47] (16 bytes)

Plaintext 1: [115, 117, 112, 101, 114, 115, 101, 99, 114, 101, 116, 109, 101, 115, 115, 97, 103, 101, 100, 111, 110, 116, 112, 101, 101, 107, 112, 108, 101, 97, 115, 101]

Plaintext 2: [105, 95, 97, 109, 95, 104, 97, 114, 109, 108, 101, 115, 115, 95, 112, 108, 101, 97, 115, 101, 95, 100, 111, 110, 111, 116, 95, 112, 101, 101, 107, 33]

Let’s see how plaintext 1 would be encrypted:

The first block will be encrypted with:

First we generate the Nonce + Counter:
- [33, 112, 111, 116, 97, 116, 111, 33, 0, 0, 0, 0, 0, 0, 0, 0]
Now we encrypt this value under AES-128-ECB using our key.
We XOR this value with our first block from plaintext 1 to get the ciphertext.

The second block will be encrypted with:

First we generate the Nonce + Counter:
- [33, 112, 111, 116, 97, 116, 111, 33, 0, 0, 0, 0, 0, 0, 0, 1]
Now we encrypt this value under AES-128-ECB using our key.
We XOR this value with our second block from plaintext 1 to get the ciphertext.

Now let’s see how plaintext 2 would be encrypted:

The first block will be encrypted with:

First we generate the Nonce + Counter:
- [33, 112, 111, 116, 97, 116, 111, 33, 0, 0, 0, 0, 0, 0, 0, 0]
Now we encrypt this value under AES-128-ECB using our key.
We XOR this value with our first block from plaintext 2 to get the ciphertext.

The second block will be encrypted with:

First we generate the Nonce + Counter:
- [33, 112, 111, 116, 97, 116, 111, 33, 0, 0, 0, 0, 0, 0, 0, 1]
Now we encrypt this value under AES-128-ECB using our key.
We XOR this value with our second block from plaintext 2 to get the ciphertext.

Wait, did you notice anything similar between these encryptions?

It’s totally fine if not, here they are:

The first block of plaintext 1 gets XORed with the exact same value as the first block from plaintext 2.
The second block of plaintext 1 gets XORed with the exact same value as the second block from plaintext 2.

If you remember our Repeating Key XOR and Repeating Key XOR II posts you will notice that we have the exact same problem in our hands!

Every first block of each CTR-encrypted ciphertext can be cracked using repeating key XOR, and we will do the same for each subsequent block.

Attack

We will approach this problem by doing the following:

Concatenate the first 16 bytes of every message, and apply repeating key XOR
Concated the next 16 bytes of every message, and apply repeating key XOR
Repeat until we exhaust the entire message.

But not every message has the same length!

That’s ok, we can use the message with the smallest length and apply our attack. We might miss something, but at least we will decrypted the majority of our messages.

Let’s see this in code:

require 'base64'
require 'openssl'

def aes_ecb_encrypt(plaintext, key)
  if !(plaintext.size % 16).zero?
    raise 'Buffer must be composed of 16-byte chunks' 
  end

  cipher = OpenSSL::Cipher.new('AES-128-ECB')
  cipher.encrypt
  cipher.key = key.pack('C*')
  cipher.padding = 0
  result = cipher.update(plaintext.pack('C*')) + cipher.final
  result.unpack('C*')
end

def aes_ctr_encrypt(plaintext, key, nonce)
  blocks = plaintext.each_slice(16)

  blocks.each_with_index.flat_map do |block, counter|
    # Make sure our counter is 8 bytes
    counter = [counter].pack('q<').bytes

    intermediate = aes_ecb_encrypt(nonce + counter, key)
    intermediate = intermediate.take(block.size)

    block.zip(intermediate).map { |a, b| a ^ b }
  end
end

BLOCK_SIZE = 16
NONCE = 0
KEY = 16.times.map { rand(0..255) }

CIPHERTEXTS = [
  # See encoded plaintexts in:
  # https://cryptopals.com/sets/3/challenges/19 
].map do |c|
  aes_ctr_encrypt(
    Base64.decode64(c).bytes,
    KEY,
    NONCE
  ).flatten
end

MIN_LENGTH = CIPHERTEXTS.min_by(&:size).size
ALIGNED_CIPHERTEXTS = CIPHERTEXTS.map do |cipher|
  cipher
    .slice(0, MIN_LENGTH)
    .each_slice(BLOCK_SIZE)
    .to_a
end

# Making every first block of every ciphertext be part of
# the same Array, the second block of every ciphertext part
# of the same Array and so on and so forth.
transposed_blocks = ALIGNED_CIPHERTEXTS.transpose.to_a

keystream = transposed_blocks.flat_map do |blocks|
  blocks.transpose.map do |block|
    max_score = 0
    chosen = ''

    (0..255).each do |candidate|
      result = block.map { |b| b ^ candidate }

      # See https://bernardoamc.com/repeating-key-xor/
      # for the implementation of english_score.
      score = english_score(result.pack('C*'))

      if score > max_score
        max_score = score
        chosen = candidate
      end
    end

    chosen
  end
end.pack('C*')

CIPHERTEXTS.each do |c|
  key = keystream.bytes.slice(0, c.size)
  key_size = key.size

  plain = c.map.with_index(0) do |byte, index|
    byte ^ key[index % key_size]
  end

  puts plain.pack('C*')
end

And this is all we need to do in order to attack multiple CTR-encrypted ciphertexts under the same nonce! We could refine our english_score method to yield even better results and work to decrypt more of the message, but the fact that we can already infer parts of the plaintext with this approach validates the attack.

In future posts we will start exploring the concept of message authentication and potential pitfalls of common implementations. As always please reach out to me via email or Twitter if you have suggestions, questions or just want to chat about the topic.