TL;DR

Challenge 18 in Cryptopals.

So, counter mode. Citing the challenge itself:

This is the only block cipher mode that matters in good code.

Most modern cryptography relies on CTR mode to adapt block ciphers into stream ciphers, because most of what we want to encrypt is better described as a stream than as a sequence of blocks. Daniel Bernstein once quipped to Phil Rogaway that good cryptosystems don’t need the “decrypt” transforms. Constructions like CTR are what he was talking about.

The lazyness of implementing one single function that gives encryption and decryption is so perlish! Well, I don’t want to put a flag or anything, just that if you look for lazyness in programming, you’ll probably end up reading about Larry Wall.

Implementing counter mode can be done easily, with a natural interface being like this:

sub aes_ctr_encrypt ($key, $nonce, $data) { ... }

But we received a gift of only needing to implement half of the code, so why not use this for making things a little more spiced up?

First of all, CTR mode is a general concept that is not necessarily tied to a specific block encryption algorithm. Hence, the most generic interface I can think of is the following:

sub ctr_mode_encrypt ($block_encrypter, $nonce, $ctr, $data) { ... }

where:

• $block_encrypter is a sub reference that takes a block and encrypts it
• $nonce is the fixed nonce
• $ctr is a sub reference that gives out the counter part at each call
• $data is what we want to encrypt.

With this in hand, we have:

sub aes_ctr_encrypt ($key, $nonce, $data) {
   ctr_mode_encrypt(aes_block_encrypter($key), $nonce, counter_64bits(),
      $data);
}

sub aes_block_encrypter ($key) {
   return AesBasic::block_encrypter($key) if $ENV{AES_BASIC};
   my $c = Crypt::Cipher::AES->new($key);
   return sub ($block) { $c->encrypt($block) };
}

The counter_64bits() function is from previous post Cryptopals Diversion 1 - A counter, while the aes_block_encrypter gives us what we need based on the provided $key, using our toy AES implementation or the much more dependable implementation from CryptX.

Then, of course, we’re not finished yet! In my delirium I thought why not let data be passed in chunks of whatever length?!?, so…

sub ctr_mode_encrypt ($block_encrypter, $nonce, $ctr, $data) {
   ctr_mode_encrypter($block_encrypter, $nonce, $ctr)->($data);
}

sub ctr_mode_encrypter ($block_encrypter, $nonce, $ctr) { ... }

OK, OK, enough hollow generalizations, we’ve come to the bottom of it.

The much awaited implementation

Implementing the some-pieces-at-a-time interface requires us to keep track of the used bits (well, whole octets in our case) and save the unused ones for possible future calls. This makes things only slightly more complicated, but not much.

sub ctr_mode_encrypter ($block_encrypter, $nonce, $ctr) {
   my $leftover = '';
   my $lleftover = 0;
   return sub ($data) {
      my $offset = 0;
      my $lqueue = length $data;
      my @chunks;
      while ($lqueue > 0) {
         if ($lqueue > $lleftover) { # add MOAR bytes! MOAR! MOAR! MOAR!
            $leftover .= $block_encrypter->($nonce . $ctr->());
            $lleftover = length $leftover;
         }

         # how many do we really need, or can extract?
         my $lchunk = $lqueue < $lleftover ? $lqueue : $lleftover;

         # get those from $data and cut from $leftover
         push @chunks, substr($data, $offset, $lchunk)
            ^ substr($leftover, 0, $lchunk, '');

         # advance, rinse, repeat
         $offset += $lchunk;
         $lleftover -= $lchunk;
         $lqueue -= $lchunk;
      }

      # whatever we collected so far...
      return join '', @chunks;
   };
}

Variable $leftover saves the unused octets for XORing coming from past calls, and of course it’s initialized to be empty. Variable $lleftover is just a convenience variable to keep its length and save a few keystrokes down the line.

The sub returns a callback function that accepts $data to encrypt, assuming that repeated calls will be operated on consecutive chunks of the whole data (e.g. stuff that is received from the network and that we want to decrypt on the spot).

We will encrypt it a block at a time, so $offset helps keeping track where we are in $data while we do the encryption. It will be an offset in terms of number of octets.

Variable $lqueue keeps track of how many octets are still queued to be encrypted; at the beginning, it’s the whole length of $data. Variable @chunks will save the different parts of $data that have been encrypted.

We now need to iterate until we addressed all octets in $data, i.e. as long as $lqueue is greater tha 0.

Our first operation will be checking if we need to generate more octets from our factory, which can be done comparing $lqueue (the number of octets left for encryption) against $lleftover (the number of octets available for immediate XOR encryption). If we need MOAR, we add MOAR!

Then we proceed to figure out how big will this chunk be. We need the minimum between what we need (again, $lqueue) and what we have (again, $lleftover), which goes into $chunk.

The encryption itself is a straightforward XOR between the relevant section of $data (remember $offset?) and the octets in $leftover, which are chipped off to avoid reuse.

Then, it’s just bookkeeping: $offset is advanced to point to the first octet of $data that has to be encrypted, $lleftover is decreased by the amount of used octets from $leftover, and $lqueue is decreased by the same amount. I suspect that I might do with one less variable, but whatever.

Conclusions

I made it much more complicated than strictly requested, but I like the idea to try and think bigger, considering what might be real-world constraints - like, e.g., doing in-line decryption as data arrives, instead of waiting for all of it and doing everything in one big swoop.

Stay safe and secure!