TL;DR

Challenge 11 in Cryptopals.

In this challenge, we’re introduced quite casually to a new concept, i.e. the oracle.

No, it’s not the database, but an oracle machine, i.e.:

a black box […] which is able to solve certain problems in a single operation.

In our case, the interesting part is that it’s a black box, i.e. something that we know how to feed data in and how to get data from, but we don’t know (at least exactly) its inner workings.

It can be interesting to read something about where this word comes from.

In our case, we have to code our own oracle machine, in terms of something that can be fed some plaintext of our choice and will give us back that plaintext encrypted with a random key, half of the times using ECB mode, the other half using CBC mode (with a random Initialization Vector). Which of the two is decided randomly by the function, ehr the oracle.

So, in this case we sort of know what’s inside the machine, but we don’t have access to the randomized parts so we don’t know which of the two were used, with what key and, in case of the CBC mode, with which IV.

It turns out that we can at least detect the coin flip between the two modes, after all. This should be no wonder at this point: ECB mode is deterministic, so we already saw that it is easy to spot. Whenever it’s not flagged as ECB… it will be CBC!

So OK, let’s get started, bottom-up style. Drawing random bytes:

sub random_octets ($n = 16) { pack 'C*', map { int rand 256 } 1 .. $n }

I suspect there might be a better way but whatever.

Now on with a predictable implementation of the challenge’s oracle. To mix waters a bit, there’s also adding some random stuff before or after, so we generate a $prefix and a $suffix. Based on input $use_ecb_mode we can control which mode will be used.

sub encryption_oracle_with ($input, $use_ecb_mode) {
   my ($prefix, $suffix) = map { random_octets(5 + int rand 6) } 1 .. 2;
   $input = $prefix . $input . $suffix;
   my $key = random_octets(16);

   return aes_ecb_encrypt($input, $key) if $use_ecb_mode;

   my $iv = random_octets(16);
   return aes_cbc_encrypt($input, $key, $iv);
}

We can use this for forcing one or the other:

sub encryption_oracle_cbc ($i) { encryption_oracle_with($i, 0) }
sub encryption_oracle_ecb ($i) { encryption_oracle_with($i, 1) }

At last, of course, we can also code our oracle by flipping a coin in the second parameter:

sub encryption_oracle ($i) { encryption_oracle_with($i, int rand 2) }

OK, enough for the oracle part, let’s move on to the detector. It will be passed an oracle as input, so it can be used on different black boxes (or even white boxes, as we will see later):

sub encryption_detector ($oracle) {
   return implements_ecb($oracle, 16) ? 'ECB' : 'CBC';
}

This is a bit anticlimax, but we’re going top-down actually! It’s much easier to spot ECB because it’s deterministic, so whatever is not ECB will be CBC in this challenge.

Now we have to take a decision. Assume that AES is the underlying block cipher, or not? Let’s make a looser assumption, i.e. that the underlying block cipher has a block size that is at most 1024.

Here’s the over-engineered solution:

sub implements_ecb ($oracle) {

   # some assumptions...
   my $MIN_BLOCK_SIZE = 1;
   my $MAX_BLOCK_SIZE = 1024; # just an assumption...
   my $MIN_EQUAL_BLOCKS = 2;

   # "ensure" there will be at least four blocks - a prefix and a suffix
   # can spoil at most two of them, leaving the other two untouched.
   my $plaintext_length = (2 + $MIN_EQUAL_BLOCKS) * $MAX_BLOCK_SIZE;
   my $plaintext = 'X' x $plaintext_length;

   my $ciphertext = $oracle->($plaintext);
   my $ciphertext_length = length $ciphertext;

   my $block_size = $MIN_BLOCK_SIZE;
   BLOCK_SIZE:
   while ($block_size <= $MAX_BLOCK_SIZE) {
      if ($ciphertext_length % $block_size == 0) {
         my $n_blocks = $ciphertext_length / $block_size;
         my $equal_blocks = int($plaintext_length / $block_size) - 2;
         my $previous = '';
         my $offset = 0;
         my $n_equal = 1;
         while ($n_equal + $n_blocks >= $equal_blocks) {
            my $current = substr $ciphertext, $offset, $block_size;
            if ($current eq $previous) {
               return 1 if ++$n_equal == $equal_blocks;
            }
            else {
               $n_equal = 1;  # reset
            }

            # prepare for next block equality check
            $offset += $block_size;
            --$n_blocks;
            $previous = $current;
         }
      }
      ++$block_size;
   }

   return 0;
}

What gives?

First, we make sure that there will be at least two consecutive blocks that will be equal, in case of ECB mode. So we craft a plaintext that has at least four blocks, assuming the biggest block size that we can predict (1024 in our case). Why four? Well, the prefix might spoil the first block, and the suffix might spoil the last, so we will be left with at least two “unspoiled” blocks that will be equal. I guess three would be the same, but whatever.

Now we invoke the $oracle and get a $ciphertext back. If it has enough replicas inside then it’s ECB, otherwise… not. So we try out different block sizes, making sure to settle only on those that can divide the ciphertext length; the number of expected replicas will depend on the block size, i.e. if the block size is smaller then we expect to get more replicas. In particular, we have to get $equal_blocks consecutive blocks to get ECB right.

Either we find the right amount of replicas, in which case we return 1 (a true value), or we try out the next block size until we run out of options (i.e. the candidate block size becomes too big).

Now let’s set some tests up:

use Test::More;

subtest 'ecb only' => sub {
   is encryption_detector(\&encryption_oracle_ecb), 'ECB', "ECB $_"
      for 1 .. 10;
};

subtest 'cbc only' => sub {
   is encryption_detector(\&encryption_oracle_cbc), 'CBC', "CBC $_"
      for 1 .. 10;
};

diag encryption_detector(\&encryption_oracle) for 1 .. 10;

done_testing();

The two subtests are to make sure that the detector works fine: we first feed ECB for 10 times, then CBC for 10 times. We assume that this will be enough! Then we run 10 times randomly, just for the sake of it.

Overall, our detector seems to work properly:

$ perl 11.pl
    # Subtest: ecb only
    ok 1 - ECB 1
    ok 2 - ECB 2
    ok 3 - ECB 3
    ok 4 - ECB 4
    ok 5 - ECB 5
    ok 6 - ECB 6
    ok 7 - ECB 7
    ok 8 - ECB 8
    ok 9 - ECB 9
    ok 10 - ECB 10
    1..10
ok 1 - ecb only
    # Subtest: cbc only
    ok 1 - CBC 1
    ok 2 - CBC 2
    ok 3 - CBC 3
    ok 4 - CBC 4
    ok 5 - CBC 5
    ok 6 - CBC 6
    ok 7 - CBC 7
    ok 8 - CBC 8
    ok 9 - CBC 9
    ok 10 - CBC 10
    1..10
ok 2 - cbc only
# CBC
# ECB
# ECB
# ECB
# CBC
# ECB
# ECB
# CBC
# ECB
# ECB
1..2

It seems we’re done with this challenge… stay safe and secure!