Cryptopals 13 - ECB cut-and-paste

TL;DR

Challenge 13 in Cryptopals.

In this challenge we’re again taking advantage of the deterministic nature of ECB to craft our way into becoming the admin in a fictional system.

The basic scenario is that a website encrypts our authorization profile into a bunch of encrypted data and gives it back to us, to use for following interactions. So we’re not receiving a session identifier, we’re receiving the session data.

This means that we are able to do two things:

  • log in and get something encrypted back, most probably using the same key every time, AND
  • try to craft our own encrypted stuff and make it so it seems both legit and very advantageous for us.

The fun thing in this challenge is that it’s… challenging. No hints, except the title: cut-and-paste. Let’s take a look.

We have basically two oracles here:

  • one that receives our payload (arguably formatted as an email address) and gives us our authorization profile encoded in a URL query-like format and encrypted with AES-128-ECB;
  • one that receives encrypted stuff like the above and tells us whether we have the admin role or not.

Let’s start with the first one, or better with a way to set a single encryption/decryption key for the whole process:

sub the_key { state $key = random_key() }

I love state variables. They were not strictly needed, but make things much more readable than:

{
    my $key;
    sub the_key { $key //= random_key() }
}

Anyway, I’m digressing. Our encryption oracle will be:

sub oracle_profile_for ($email) {

   # sanitize inputs with %-encoding
   $email =~ s{([;&=%])}{'%' . unpack 'H2', $1}egmxs;

   # assemble the payload according to the rules
   my $payload = "email=$email&uid=10&role=user";

   # return the encrypted payload
   aes_ecb_encrypt($payload, the_key());
}

We give an emailish thing as input, it gives AES-128-ECB-encrypted data back.

Now the other oracle, where we provide a viciously crafted payload and it will give us the keys to heaven:

sub oracle_role ($ciphertext) {
    my $plaintext = aes_ecb_decrypt($ciphertext, the_key());
    my %config =
        map { s{%(..)}{chr(hex($1))}ergmxs } # %-decode
        map { my ($k, $v) = split m{=}mxs }  # key=value split
        split m{\&}mxs, $plaintext;          # & split
    return $config{role};
}

OK, let’s try it with some innocent inputs:

my $first  = oracle_profile_for('eve@crack.admin');
say oracle_role($first);

This prints user, as expected.

Now there comes the fun part. By providing different-length email addresses to the encrypting oracle, we can move around parts of the plaintext and obtain the corresponding encrypted parts.

With our $first part above, we got back the encrypted form for this:

0123456789ABCDEF 0123456789ABCDEF 0123456789ABCDEF

email=eve@crack. admin&uid=10&rol e=user
^^^^^^^^^^^^^^^^ ^^^^^^^^^^^^^^^^
        A              B

The A and B parts that are highlighted will come handy later; the third block is not useful and its encrypted counterpart can be ignored.

I guess we can suspect where we’re heading to with the second block, because it contains a beautiful admin in a place that belongs to a value in our key=value encoding scheme (i.e. just before the & separator).

Now let’s consider an input that is two characters shorter, which will move the rest of the plaintext two characters to the left, giving us the encrypted counterpart for a very interesting second block:

0123456789ABCDEF 0123456789ABCDEF 0123456789ABCDEF

email=xxx@xxxxx. you&uid=10&role= user
                 ^^^^^^^^^^^^^^^^
                       C

The second block is highlighted and assigned the letter C for later reference. It looks very useful, as it ends with role= and allows setting the role to whatever comes first in the following block.

So far, we can craft a new ciphertext by taking part A, then part C, then part B from the highlights above:

0123456789ABCDEF 0123456789ABCDEF 0123456789ABCDEF

email=eve@crack. you&uid=10&role= admin&uid=10&rol
^^^^^^^^^^^^^^^^ ^^^^^^^^^^^^^^^^ ^^^^^^^^^^^^^^^^
        A              C                B

We’re nearly there and, depending on the server, we might already be there. But let’s make things clean and also give a value to that final rol key, by asking our encrypting oracle to consider another email address:

0123456789ABCDEF 0123456789ABCDEF 0123456789ABCDEF

email=xxx@xxxxx. xxxx&uid=10&role =user
                                  ^^^^^^^^^^^^^^^^
                                        D

So we can end up with the following:

0123456789ABCDEF 0123456789ABCDEF 0123456789ABCDEF 01234...

email=eve@crack. you&uid=10&role= admin&uid=10&rol =user
^^^^^^^^^^^^^^^^ ^^^^^^^^^^^^^^^^ ^^^^^^^^^^^^^^^^ ^^^^^...
        A              C                  B          D

Note that we’re assigning admin to role and user to rol (with a missing e)!

Let’s translate this into code:

my $first  = oracle_profile_for('eve@crack.admin');
my $second = oracle_profile_for('xxx@xxxxx.you');
my $third  = oracle_profile_for('xxx@xxxxx.xxxx');

my $crafted = ''
   . take_block($first,  0)   # A
   . take_block($second, 1)   # C
   . take_block($first,  1)   # B
   . take_block($third,  2)   # D
   . '';
say oracle_role($crafted);

sub take_block ($string, $n) { substr $string, $n * 16, 16 }

Aaaaand… we’re admin, yay!

So I guess that we should now be very convinced: deterministic behaviour can be abused in such many ways that we shouldn’t even bother talking about it. Except, of course, for studying and learning!!!

Stay safe and secure!


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