TL;DR

Challenge 14 in Cryptopals.

It seems that the people behind challenge 12 suspect they’re being violated and decided to do something about this. They have come up with an update where the put a prefix before the previous encryption plaintext, whose nature we don’t know (in particular, content and more importantly length). So we end up with this:

AES-128-ECB(rnd-prefix || attacker-controlled || target-bytes, rnd-key)

Again this prefix and the key are random to us, but will be the same across each process (simulating some stuff that has been saved in the server).

The challenge text hints us that we don’t need anything fancy, just use the tools that we already have at our disposal.

Let’s start from the oracle, which we don’t control:

sub encryption_oracle ($input) {
   state $key = random_octets(16);
   state $prefix = random_octets(10 + int rand 30);
   state $suffix = decode_base64(<<'END');
Um9sbGluJyBpbiBteSA1LjAKV2l0aCBteSByYWctdG9wIGRvd24gc28gbXkg
aGFpciBjYW4gYmxvdwpUaGUgZ2lybGllcyBvbiBzdGFuZGJ5IHdhdmluZyBq
dXN0IHRvIHNheSBoaQpEaWQgeW91IHN0b3A/IE5vLCBJIGp1c3QgZHJvdmUg
YnkK
END
   return aes_ecb_encrypt($prefix . $input . $suffix, $key);
}

We are setting the $prefix randomly as requested, but persisting it inside the process so that we always use it over and over in repeated calls to the oracle.

The really interesting part, though, is the decryption routine:

sub decrypt_trailing_string ($oracle) {
   my $bs = detect_block_size($oracle);
   my ($pad_length, $working_block) = find_prefix_pad($oracle, $bs);
   my $base_pad = 'x' x $pad_length;
   my $n_trash = $working_block * $bs;

   # find length of payload
   my $payload_len = length($oracle->($base_pad)) - $n_trash;
   say "max_payload_length<$payload_len>";
   my $n = 0;
   while ('necessary') {
      ++$n;
      my $len = length($oracle->($base_pad . ('x' x $n))) - $n_trash;
      if ($len > $payload_len) {
         $payload_len -= $n;
         last;
      }
   }

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

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

      $prefix = substr $prefix . $plaintext, 1 - $bs, $bs - 1;
      for my $ic (32 .. 255, 0 .. 31) {
         my $candidate = chr($ic);
         my $tester = $prefix . $candidate;
         my $encrypted = $oracle->($base_pad . $tester);
         my $block = substr $encrypted, $n_trash, $bs;
         if ($reference_block eq $block) {
            $plaintext .= $candidate;
            if ($ENV{BASIC}) {
               $|++;
               printf {*STDOUT} "\r%d/%d ", $plen + 1, $payload_len;
            }
            last;
         }
      }
   }

   return $plaintext;
}

To some extent, it’s the same as before. There is a variation in how the actual target-bytes length is evaluated, which tells us exactly how many octets we are after to fill in our $plaintext, which means (among other small changes) that we don’t have to remove the last char at the end. For anything else, though, the actual decryption mechanism is the same.

The addition of the random bytes at the beginning is dealt with at the beginning, together with the evaluation of the target-string length.

We call a find_prefix function to evaluate how much we should pad the random prefix to re-align it to a block. This allows us to always apply this padding and work exactly as before, but concentrating on a later block instead of the first. This is why we get two values back from find_prefix_pad: the pad lenght, and what is the index of the block we have to concentrate on for our crackAHEMdecryption.

The length of the payload is then found like this:

• first we evaluate its gross size by encrypting an “empty” string (i.e. a string that has padding only) and removing the number of octets that belong to the blocks we skip (i.e. the blocks for the rnd-prefix and the padding we are adding);
• then we increase the size of the input string to the oracle, up until we get one more block. That will mark how many less octets the payload is long.

The rest, as mentioned, is like before, with the only differences that:

• we always add the padding at the beginning, AND
• we start taking our test block not from the very beginning, but taking into account the rnd-prefix and its padding (i.e. we skip $n_trash octets).

Now let’s see how we can find the right padding for the rnd-prefix, so that we can ignore it.

sub find_prefix_pad ($oracle, $blen = undef) {
   $blen //= detect_block_size($oracle);

   # get index of first block to focus on for finding duplicates
   my @baseline = divide_in_blocks($oracle->(''), $blen);
   my @onebyte  = divide_in_blocks($oracle->('!'), $blen);
   my $skip = 0;
   while (@baseline && $baseline[0] eq $onebyte[0]) {
      ++$skip;
      shift @baseline;
      shift @onebyte;
   }

   my $pfx = random_octets(16) x 3;
   my $plen = 0;
   while ('necessary') {
      my @blocks = divide_in_blocks($oracle->(substr $pfx, 0, $plen + 32));
      last if $blocks[$skip]     eq $blocks[$skip + 1]
         ||   $blocks[$skip + 1] eq $blocks[$skip + 2];
      ++$plen;
   }
   my $working_block = $skip + int((15 + $plen) / 16);

   return ($plen, $working_block);
}

We start by calling the oracle with no payload, then with a one-byte payload, and then comparing the corresponding blocks. Any initial blocks that are the same will fully belong to the rnd-prefix, due to the nature of ECB mode. This is saved in $skip.

The first block to change might have a variable number of octets from the last part of rnd-prefix. So we inject an increasing number of bytes from three repeating input blocks, starting from two blocks’ worth of bytes. As soon as we find a repetition, we know that there are two blocks under our control that made it to occupy their own encrypted blocks, so we can stop. This gives us $plen.

The working block is finally saved in $working_block, by taking into account the $skip blocks and, possibly, $plen. In particular, there might be the case where $plen is 0 in which case $skip is exactly the number we have to return; otherwise, if there’s even one single byte of padding, there’s another block to be removed.

I hope everything’s clear, otherwise… feel free to provide additional explanations!

Stay safe and secure!