TL;DR

Challenge 12 in Cryptopals.

Things start moving:

This is the first challenge we’ve given you whose solution will break real crypto.

Yesss! We’re going to break real crypto!

We can perform another chosen-plaintext attack, much like the last time. This means that we have an oracle to which we can feed any plaintext we want, and get back some ciphertext.

In this case, our oracle will be an encrypting box that only encrypts using a fixed key and always appends some fixed stuff to the plaintext we provide. In the words of the challenge, it does this:

AES-128-ECB(your-string || unknown-string, random-key)

The unknown-string is given as a Base64 input, to obfuscate it to us. Our goal is to find it out… without just decoding and reading it:

Um9sbGluJyBpbiBteSA1LjAKV2l0aCBteSByYWctdG9wIGRvd24gc28gbXkg
aGFpciBjYW4gYmxvdwpUaGUgZ2lybGllcyBvbiBzdGFuZGJ5IHdhdmluZyBq
dXN0IHRvIHNheSBoaQpEaWQgeW91IHN0b3A/IE5vLCBJIGp1c3QgZHJvdmUg
YnkK

This is our oracle, in Perl:

sub encryption_oracle_ecb_always_same_key ($input) {
   state $key = random_key(); # random_octets(16)
   state $suffix = decode_base64(<<'END');
Um9sbGluJyBpbiBteSA1LjAKV2l0aCBteSByYWctdG9wIGRvd24gc28gbXkg
aGFpciBjYW4gYmxvdwpUaGUgZ2lybGllcyBvbiBzdGFuZGJ5IHdhdmluZyBq
dXN0IHRvIHNheSBoaQpEaWQgeW91IHN0b3A/IE5vLCBJIGp1c3QgZHJvdmUg
YnkK
END

   $input = $input . $suffix;
   return aes_ecb_encrypt($input, $key);
}

Function aes_ecb_encrypt() can be easily coded with the help of CryptX (or from our toy AES implementation, if we have time to waste):

sub aes_ecb_encrypt ($plaintext, $key) {
   if ($ENV{AES_BASIC}) {
      my $be = block_encrypter($key);
      my $padded = pkcs7_pad($plaintext, 16);
      my @chunks;
      while (length $padded) {
         push @chunks, $be->(substr $padded, 0, 16, '');
      }
      return join '', @chunks;
   }

   state $ecb = Crypt::Mode::ECB->new('AES');
   $ecb->encrypt($plaintext, $key);
}

As requested, the $key is the same for all invocations (within a process) and the $suffix is decoded inside the oracle but not explicitly shown.

Now, on with the requests in the challenge! Our main steps will be, as requested:

{
   my $o = \&encryption_oracle_ecb_always_same_key;
   my $bs = detect_block_size($o);
   say 'block size: ', $bs;
   say 'ECB mode: ', implements_ecb($o) ? 'YES' : 'NO';
   say decrypt_trailing_string($o);
}

Block size

In this case, we’re even suggested how to detect the block size. We feed increasingly longer string to the oracle, until we see a change in size of the output: this change will be our block size, because the oracle needed to add one more block.

my $bs = detect_block_size(\&encryption_oracle_ecb_always_same_key);

sub detect_block_size ($oracle) {
   my $input = '';
   my $past_length;
   while ('necessary') {
      $input .= 'X';
      my $length = length $oracle->($input);
      $past_length //= $length;
      return $length - $past_length if $length > $past_length;
   }
}

This technique would not in general work with a random prefix and/or suffix, like we have in other challenges. It might be refined to e.g. run it many times and find out the minimum common divisor across all these attempts, feeding variable length plaintexts.

ECB function detection

This is easy because we already have this black box analyzer from last post about Cryptopals, so we reuse it on the spot:

say 'ECB mode: ', implements_ecb($o) ? 'YES' : 'NO';

Decryption

The challenge gives us the instructions to code our cracking machine, here’s an implementation in Perl:

sub decrypt_trailing_string ($oracle) {
   my $bs = detect_block_size($oracle);
   my $tlen = length $oracle->('');
   my $plaintext = '';
   my $prestuff = join '', 0..9, 'a' .. 'f';
   CHAR:
   while ((my $plen = length $plaintext) < $tlen) {
      my $prefix = substr($prestuff, 0, ($bs - 1 - ($plen % $bs)));
      my $reference = $oracle->($prefix);

      my $n_block = int($plen / $bs);
      my $reference_block = substr $reference, $n_block * $bs, $bs;

      $prefix = substr $prefix . $plaintext, 1 - $bs, $bs - 1;
      for my $ic (0 .. 255) {
         my $candidate = chr($ic);
         my $tester = $prefix . $candidate;
         my $encrypted = $oracle->($tester);
         my $block = substr $encrypted, 0, $bs;
         if ($reference_block eq substr $encrypted, 0, $bs) {
            $plaintext .= $candidate;
            next CHAR;
         }
      }
      last;
   }
   substr $plaintext, -1, 1, '';
   return $plaintext;
}

The $tlen variable is used only as a safeguard against possible infinite looping, but actually the code is supposed to exit as long as we’re trying to get a char beyond the last one in our unknown-string.

Variable $plaintext is where we’re going to fit our unknown-string, char by char. At the very beginning we known nothing, so it’s empty.

The $prestuff is built as 0123456789abcdef and it’s useful when debugging. In the final function it can be any 16-chars long string. It will be used to take just the right amount of octets to feed into the oracle in order to put the right octet of the unknown-string in the right place (i.e. at the end of a block).

In each loop instance, we concentrate on a single octet of the unknown-string, starting from… the first one. If we feed a 15-octets long prefix, this first char will be placed as the 16th octet in the block, i.e. the last one. This is why $prefix is 15 octets long at the beginning, when $plen is 0.

As an example, if our unknown string were YELLOW SUBMARINE-YELLOW SUBMARINE, at the beginning we would have this:

               v
0123456789abcdeY   ELLOW SUBMARINE-   YELLOW SUBMARINE
               ^

As our decrypted $plaintext grows, we will shorten this $prefix to move the second octet of the unknown-string onto that position, then the third, and so on. So, at our fourth iteration we will be concentrating on the fourth character:

               v
0123456789abYELL   OW SUBMARINE-YEL   LOW SUBMARINE
               ^

After discovering the 16th character with an empty prefix, we will reset it back to 15 and start analyzing the second block from the oracle instead:

                                  v
0123456789abcdeY   ELLOW SUBMARINE-   YELLOW SUBMARINE
                                  ^

and so on. In this way, the prefix can be only 0 to 15 octets long (16 different possible lengths) and this accounts for the funny way it’s initialized and used:

my $prefix = substr($prestuff, 0, ($bs - 1 - ($plen % $bs)));
my $reference = $oracle->($prefix);

As we saw, depending on the octets we already know in $plaintext, we concentrate on a different block in the $reference provided by the $oracle:

my $n_block = int($plen / $bs);
my $reference_block = substr $reference, $n_block * $bs, $bs;

Now $reference_block contains the encryption of a block where we already know every character but the last one, so it’s time to leverage the deterministic nature of ECB and try to re-create this encrypted block trying every possible alternative for this last octet, until we find something that matches our $reference_block.

To do this, we first find out the first 15 octets in the target block:

$prefix = substr $prefix . $plaintext, 1 - $bs, $bs - 1;

This time we MUST use the $plaintext too, because we are crafting a first-block and we will disregard what comes next from the oracle. The 16th octet is searched by iterating over the integers from 0 to 255, and appending the candidate to this prefix:

my $candidate = chr($ic);
my $tester = $prefix . $candidate;
my $encrypted = $oracle->($tester);
my $block = substr $encrypted, 0, $bs;

As we can see, we’re always feeding exactly one block’s worth of data to the $oracle in this inner loop, and we’re only interested into the first block from it.

In our example, suppose that we’re testing octet S for the very first octet in the unknown-string, we would be feeding this to the oracle:

0123456789abcdeS

and the oracle would be giving us the encryption for this:

0123456789abcdeS   YELLOW SUBMARINE   -YELLOW SUBMARIN   E

This will not give us a match, but we will go on until we want to try Y instead, for which the oracle will be encrypting this:

0123456789abcdeY   YELLOW SUBMARINE   -YELLOW SUBMARIN   E

Do you recognize the first block it encrypts? Sure enough, it’s the same it encrypted in the first place when we only fed it with 0123456789abcde:

0123456789abcdeY   ELLOW SUBMARINE-   YELLOW SUBMARINE

In general, then, if the first block is the same as the $reference_block, we found the right $candidate, yay! We add it to the $plaintext and move on to look for the following CHAR.

If we don’t find anything… no panic, it just means that we hit the end of the unknown-string and we can exit the main loop. As a matter of fact, this happens one octet after, because we’re going to have a positive match even for the one-byte padding (octet corresponding to value 0x01)! This accounts for the character chopping at the end of the function, just before returning:

substr $plaintext, -1, 1, '';
return $plaintext;

I hope this was clear enough… stay safe and secure!