The Counter Mode - manually!

The counter mode of operation (CTR) is defined in the NIST Special Publication 800-38A, pp. 15-16. I'd summarize it like this: The CTR mode transforms any block cipher into a stream cipher. Encryption and decryption are the same function. They encrypt a sequence of counter blocks and XOR the result with the plaintext (for encryption) or the ciphertext (for decryption).

My goal here is encrypting a plaintext with AES-256-CTR. And I want to do the CTR part manually, i.e. in my shell only with the usual tools like hexdump, basenc and dd. To encrypt the counter blocks, I'll need OpenSSL - but not in CTR mode!

The shell is probably not the best tool for something like this. Especially XORing data is a little awkward. Or maybe I just think so because I'm certainly not particularly good at shell programming. However, for now I'll stay with the shell and won't switch to a language like Ruby or Go. This way, you can follow without having to install an interpreter or compiler for my preferred language.

Preparation

Let's say, we want to encrypt the plaintext Lorem ipsum dolor sit amet with AES-256-CTR. The plaintext in ASCII encoding consist of two 128-bit blocks:

$ P="Lorem ipsum dolor sit amet"
$ echo -n $P | hexdump -C
00000000  4c 6f 72 65 6d 20 69 70  73 75 6d 20 64 6f 6c 6f  |Lorem ipsum dolo|
00000010  72 20 73 69 74 20 61 6d  65 74                    |r sit amet|
0000001a

To encrypt them in CTR, we start with two counter blocks, which we save in shell variables:

$ T1=00000000000000000000000000000000
$ T2=00000000000000000000000000000001

The next step is to encrypt them with AES-256. Since both T1 and T2 are exactly one block, we can apply the AES cipher function directly. To do this with OpenSSL, we choose the ECB mode, which simply applies AES block by block. Let's save a 256-bit key in a shell variable and then encrypt the counter blocks:

$ key=000102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f
$ O1=$(echo -n $T1 | basenc --base16 -d | openssl enc -aes-256-ecb -K $key -nopad)
$ O2=$(echo -n $T2 | basenc --base16 -d | openssl enc -aes-256-ecb -K $key -nopad)

We need the -nopad flag here, because otherwise OpenSSL will add a complete padding block to T1 and T2, respectively.

Now, we split the plaintext in blocks:

$ P1=$(echo -n $P | dd bs=16 skip=0 count=1 status=none)
$ P2=$(echo -n $P | dd bs=16 skip=1 count=1 status=none)

Ok, so the ciphertext will be P1 XOR O1 and P2 XOR O2. To be precise, the second ciphertext block is actually not P2 XOR O2, because P2 has only 10 bytes and O2 has 16 bytes. The CTR specification states that the last ciphertext block (which may not be a complete block) Cn is calculated like this:

Cn = Pn XOR MSB_u(On)

Here, u is the length of Pn and MSB_u(On) are the u most significant bytes of On, i.e. the u left-most bytes. In our case, u is 10, so we only need the first 10 bytes of O2:

$ O2_MSB=$(echo -n $O2 | dd bs=10 count=1 status=none)

Okay. Now, we need to calculate P1 XOR O1 and P2 XOR O2_MSB. How do we do that? We could look at the hexdumps, calculate the binary representations and do the XORing by hand. But of course it'd be nice to do it programmatically. As indicated, to do that in the shell is a little awkward.

XOR as shell function

We can XOR to integers (base 10) like this:

$ echo $((6 ^ 5))
3
# That's right:
#     0110 (6)
#     0101 (5)
# --------
# XOR 0011 (3)

To use this syntax, we first convert our data to a hexadecimal representation and then interpret this representation as one number and transform it to base 10:

$ a=a
# $a now contains the string 'a', i.e. 0x61
$ a_hex=$(echo -n $a | basenc --base16)
$ echo $a_hex
61
# Great. 0x61 in base 10 is 6*16 + 1 = 97.
$ echo $((16#$a_hex))
97
# Woohoo!

This way, we can transform our data into base 10 integers and XOR them. Afterwards, we must transform the integer back to raw data. We can transform a base 10 integer into its hexadecimal representation with printf and then decode it with basenc:

$ input=97
$ input_hex=$(printf "%02x" $input)
$ echo $input_hex
61
$ input_raw=$(echo -n $input_hex | basenc --base16 -d)
$ echo $input_raw
a

A side note: We can convert an integer to its hexadecimal representation with printf "%x" $input. However, this does not necessarily output complete bytes. For example:

$ printf "%x" 3
3

But basenc expects complete bytes with two characters each, so we must pad the output with zeros:

$ printf "%02x" 3
03

Okay, with these ingredients, we can implement an XOR function:

function xor() {
  op1_hex=$(echo -n $1 | basenc --base16)
  op1_dec=$(echo $((16#$op1_hex)))

  op2_hex=$(echo -n $2 | basenc --base16)
  op2_dec=$(echo $((16#$op2_hex)))

  xor_dec=$(echo $(($op1_dec ^ $op2_dec)))

  xor_hex=$(printf "%02x" $xor_dec)
  xor_raw=$(echo -n $xor_hex | basenc --base16 -d)

  echo -n $xor_raw
}

When we test this function, we may not see an output because it has no printable characters. So we must pipe it to hexdump or basenc:

$ xor e f | basenc --base16
03

The e character is encoded as 0x65, the f character is encoded as 0x66. 6 XOR 6 is 0, 5 XOR 6 is 3. It works!

Unfortunately, there is still a problem:

$ xor $P1 $O1
xor:2: number truncated after 17 digits: 4C6F72656D20697073756D20646F6C6F
xor:5: number truncated after 16 digits: F29000B62A499FD0A9F39A6ADD2E7780

Apparently, $((16#...)) cannot handle numbers of the size we need here. A simple solution that works for us is to split the arguments into bytes and XOR them separately:

function xor() {
  op_length=$(echo -n $1 | wc -c)

  for i in $(seq 1 $op_length)
  do
    op1_byte=$(echo -n $1 | dd bs=1 count=1 skip=$((i-1)) status=none)
    op2_byte=$(echo -n $2 | dd bs=1 count=1 skip=$((i-1)) status=none)

    op1_hex=$(echo -n $op1_byte | basenc --base16)
    op1_dec=$(echo -n $((16#$op1_hex)))

    op2_hex=$(echo -n $op2_byte | basenc --base16)
    op2_dec=$(echo -n $((16#$op2_hex)))

    xor_dec=$(echo -n $(($op1_dec ^ $op2_dec)))

    xor_hex=$(printf "%02x" $xor_dec)
    xor_raw=$(echo -n $xor_hex | basenc --base16 -d)

    if [ $i = 1 ]; then
      result=$xor_raw
    else
      result="$result$xor_raw"
    fi
  done

  echo -n $result
}

Not an elegant solution, but good enough for the CTR demonstration I'm doing here.

Back to CTR

Now we can calculate the ciphertext:

$ C1=$(xor $P1 $O1)
$ C2=$(xor $P2 $O2_MSB)
$ C="$C1$C2"
$ echo -n $C | hexdump -C
00000000  be ff 72 d3 47 69 f6 a0  da 86 f7 4a b9 41 1b ef  |..r.Gi.....J.A..|
00000010  82 7d 05 c7 3e 99 fe 88  c3 82                    |.}..>.....|
0000001a

Okay good, looks like gibberish. But how do we know if $C is actually the correct AES-256-CTR ciphertext?

Well, we can calculate it with OpenSSL and compare:

$ echo -n $P | openssl enc \
    -aes-256-ctr \
    -K $key \
    -iv 00000000000000000000000000000000 \
    | hexdump -C
00000000  be ff 72 d3 47 69 f6 a0  da 86 f7 4a b9 41 1b ef  |..r.Gi.....J.A..|
00000010  82 7d 05 c7 3e 99 fe 88  c3 82                    |.}..>.....|
0000001a

Yep, we did good. :)

I said above that encryption and decryption are the same function. We can decrypt the ciphertext by XORing the encrypted counter blocks again:

$ echo $(xor $C1 $O1)$(xor $C2 $O2_MSB)
Lorem ipsum dolor sit amet

Beautiful!

But what's up with the initialization vector? Why just 16 zero bytes? And what does "initialization vector" even mean in the context of CTR? The NIST spec doesn't speak of IVs. Let's have a look at OpenSSL's implementation of CTR!

OpenSSL's implementation of CTR

The relevant function is CRYPTO_ctr128_encrypt. When we ignore the lines that are contingent on the OPENSSL_SMALL_FOOTPRINT and STRICT_ALIGNMENT flags, the function becomes pretty simple:

void CRYPTO_ctr128_encrypt(const unsigned char *in, unsigned char *out,
                           size_t len, const void *key,
                           unsigned char ivec[16],
                           unsigned char ecount_buf[16], unsigned int *num,
                           block128_f block)
{
  unsigned int n;
  size_t l = 0;

  n = *num;

  while (l < len) {
    if (n == 0) {
      (*block) (ivec, ecount_buf, key);
      ctr128_inc(ivec);
    }
    out[l] = in[l] ^ ecount_buf[n];
    ++l;
    n = (n + 1) % 16;
  }

  *num = n;
}

The comment above the function states that *num and ecount_buf must be initialized with zeros. So n starts at 0. The while loop iterates over the input bytes that belong either to the plaintext (if we are encrypting) or to the ciphertext (if we are decrypting). The first thing that happens in the loop is that the IV ivec is encrypted with the given block cipher and the result is written to ecount_buf. The IV is then incremented. A look at ctr128_inc in the same file shows that this basically means that 1 is added to the IV. Then the first byte of the input is XORed with the first byte of the encrypted IV. In the next 15 iterations, the next input bytes are XORed with the next bytes of the encrypted IV. In the 17th iteration, n is 0 again. So now the incremented IV is encrypted, and the 17th input byte is then XORed with the first input byte of the result. And so on.

So when we give OpenSSL an "initialization vector" for CTR, this is the first counter block. Given any counter block, the subsequent counter block is generated by adding 1. This is why we could reproduce our encryption result with the counter blocks T1 and T2 by passing the zero IV to OpenSSL.

How to choose counter blocks

As you might suspect, it is not a very good idea to start the counter blocks with 0 by default. Or, in other words, to set the IV to 0 by default. The NIST spec states in Appendix B (p. 18): "The specification of the CTR mode requires a unique counter block for each plaintext block that is ever encrypted under a given key, across all messages." The authors then give some hints on how this can be achieved. I won't go into these details here. For now, I just wanted to understand the CTR algorithm itself and how it can be implemented in the shell.