TL;DR

Challenge 10 in Cryptopals.

Surely it’s nice to be given a box and be told to break it, but it can be rewarding to build the box ourselves in the first place. Just to get that feeling that Hey! This is a really sturdy box!

Until, of course, it isn’t any more.

So in this challenge we’re requested to just do some programming to implement (AES-based) CBC mode, which stands for Cipher Block Chaining.

This is an operation mode, i.e. something that leverages an encryption mechanism that works fine on a single block to provide something that works hopefully fine on any-length inputs. Although we’re using AES here, nothing prevents us from doing it the generic way and accept the block-level encryption/decryption primitives as inputs as well.

Let’s not overengineer it, though. Now.

Back to CBC, it aims at solving the curse of ECB mode, namely its deterministic and pure function behaviour that can be abused in many ways (like replaying over and over something that we know that works, even if we don’t know what’s inside).

To address this, first of all the chaining concept is introduced. Each plaintext block isn’t just encrypted in isolation with the single-block encryption mechanism of choice, which would give us ECB; it’s first XORed with the ciphertext coming from the previous block, then encrypted. Hence, the same plaintext block appearing in different positions would normally yield different outcomes.

There are, of course, a couple of issues left:

• the very first block of plaintext does not have a previous block’s ciphertext to XOR with, and
• the same multi-block message would be encrypted to the same ciphertext anyway, deterministically.

The Initialization Vector comes to help us, getting two birds with one stone. It’s a block of random gibberish that acts as a fake ciphertext put before the first block to be encrypted; this both gives us something to XOR the first block of plaintext with (addressing the former issue), as well as randomness in the process (addressing the latter).

Thanks to Wikpedia, we have this image of how encryption works:

The reverse operation is straightforward and shows that the IV should somehow be sent to the receiver (again, thanks to Wikipedia):

As it’s like a block of ciphertext, it might be pre-pended to the whole ciphertext, with the rule that it will be tossed away on the receiving side. Failing to send it makes it impossible to decrypt the first block of ciphertext only, so we might just skip it if it’s only salutations 🙄

So OK, on with the implementation now:

sub aes_cbc_encrypt ($plaintext, $key, $iv = undef) {
   my $c = Crypt::Cipher::AES->new($key);
   my $encrypter = sub ($block) { $c->encrypt($block) };
   $encrypter = block_encrypter($key) if $ENV{AES_BASIC};
   $iv //= "\x00" x 16;
   my $padded = pkcs7_pad($plaintext, length $iv);
   my @chunks;
   while (length $padded) {
      push @chunks, $iv = $encrypter->($iv ^ substr($padded, 0, 16, ''));
   }
   return join '', @chunks;
}

sub aes_cbc_decrypt ($ciphertext, $key, $iv = undef) {
   my $c = Crypt::Cipher::AES->new($key);
   my $decrypter = sub ($block) { $c->decrypt($block) };
   $decrypter = block_decrypter($key) if $ENV{AES_BASIC};
   $iv //= "\x00" x 16;
   my @chunks;
   while (length $ciphertext) {
      my $chunk = substr $ciphertext, 0, 16, '';
      push @chunks, $iv ^ $decrypter->($chunk);
      $iv = $chunk;
   }
   return join '', @chunks;
}

Encryption is not strictly requested in the challenge but whatever. We can be strict and use A toy AES implementation by setting environment variable AES_BASIC to a true value, or just rely upon CryptX for speed.

The IV is passed as an explicit input in both functions, mainly for keeping them symmetric. As we already told, we might avoid it in decryption by just tossing away the very first block. It is anyway an optional parameter, which is initialized (deterministically!) to all zeros. This is useful when studying stuff, even more so when you’re asked to use exactly that IV for solving the challenge, that is applying the decryption function to the provided input.

The astute reader will have spotted that these two functions aren’t really one the inverse of the other. The encryption function performs automatic padding on its input, while the decryption function gives back everything, including the padding. This is done on purpose, because it will be handy later. Maybe I should change the name of the second function to reflect this, but we’re studying here so I guess this note should suffice.

So here’s the solution to the challenge (not really cut-and-paste but whatever):

use CryptoPals qw< slurp_base64 xxd >;
my $ciphertext = slurp_base64(shift // '10.txt');
my $key = 'YELLOW SUBMARINE';
my $iv = "\x00" x 16;
my $plaintext = aes_cbc_decrypt($ciphertext, $key, $iv);
say ''. xxd($plaintext);

I will just slightly spoiler here by showing that the padding is left in the reconstructed $plaintext, as it can be seen in the last line that is printed by the code above:

#                                      vvvv vvvv              vvvv
0000b30: **** **** **** **** **** **** 0404 0404  ************....
#                                      ^^^^ ^^^^              ^^^^

Stay safe and secure!