# ETOOBUSY đźš€ minimal blogging for the impatient

# Cryptopals 11 - An ECB/CBC detection oracle

**TL;DR**

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*!

*Comments? Octodon, Twitter, GitHub, Reddit, or drop me a line!*