Cryptopals 17 - The CBC padding oracle

TL;DR

Challenge 17 in Cryptopals.

As they say…

This is the best-known attack on modern block-cipher cryptography.

The “game” here is that we get an oracle that tells us whether the padding of a chosen ciphertext provided by us is valid or not. This might be not that obvious, but even a slight change in an error message (like “request invalid” and “request unauthorized”) would do the trick, so it’s easier to stumble than expected.

This is the setup part: the key is generated randomly but reused all along (as would do a web server) and we’re choosing one message randomly across the ones proposed. The oracle decrypts whatever it gets and returns whether the padding is fine or not.

#!/usr/bin/env perl
use v5.24;
use warnings;
use experimental 'signatures';
no warnings 'experimental::signatures';

use CryptoPals qw<
  xxd decode_base64
  aes_cbc_encrypt aes_cbc_decrypt
  random_octets validate_pkcs7_pad
>;

# Ask the server for something to crack
my $enc = something_obscure(shift // undef);

# Crack it
say cbc_padding_oracle_crack($enc, \&oracle_pad_is_right);

########################################################################
#
# This is the simulated server side, giving back an error when the
# the padding is wrong and no error otherwise. The encryption key is
# known to both the encryption and the decryption routines.
sub key { state $key = random_octets(16) }

sub something_obscure ($n = undef) {
   my @unknowns = split m{\n+}mxs, <<'END';
MDAwMDAwTm93IHRoYXQgdGhlIHBhcnR5IGlzIGp1bXBpbmc=
MDAwMDAxV2l0aCB0aGUgYmFzcyBraWNrZWQgaW4gYW5kIHRoZSBWZWdhJ3MgYXJlIHB1bXBpbic=
MDAwMDAyUXVpY2sgdG8gdGhlIHBvaW50LCB0byB0aGUgcG9pbnQsIG5vIGZha2luZw==
MDAwMDAzQ29va2luZyBNQydzIGxpa2UgYSBwb3VuZCBvZiBiYWNvbg==
MDAwMDA0QnVybmluZyAnZW0sIGlmIHlvdSBhaW4ndCBxdWljayBhbmQgbmltYmxl
MDAwMDA1SSBnbyBjcmF6eSB3aGVuIEkgaGVhciBhIGN5bWJhbA==
MDAwMDA2QW5kIGEgaGlnaCBoYXQgd2l0aCBhIHNvdXBlZCB1cCB0ZW1wbw==
MDAwMDA3SSdtIG9uIGEgcm9sbCwgaXQncyB0aW1lIHRvIGdvIHNvbG8=
MDAwMDA4b2xsaW4nIGluIG15IGZpdmUgcG9pbnQgb2g=
MDAwMDA5aXRoIG15IHJhZy10b3AgZG93biBzbyBteSBoYWlyIGNhbiBibG93
END
   my $plaintext  = decode_base64($unknowns[$n // rand @unknowns]);
   my $lplain     = length $plaintext;
   my $iv         = random_octets(16);
   my $ciphertext = aes_cbc_encrypt($plaintext, key(), $iv);
   return $iv . $ciphertext;
} ## end sub something_obscure ($n = undef)

sub oracle_pad_is_right ($ciphertext) {
   my $iv = substr $ciphertext, 0, 16, '';
   my $plaintext = aes_cbc_decrypt($ciphertext, key(), $iv);
   eval { validate_pkcs7_pad($plaintext, 16); 1 };
}

This is where we crack it. The attack itself is not completely straightforward, but the code to implement it comes out compact in my opinion.

sub cbc_padding_oracle_crack ($ciphertext, $oracle) {
   my $previous = substr $ciphertext, 0, 16, '';
   my @chunks;
   while (length $ciphertext) {
      my $target = substr $ciphertext, 0, 16, '';
      push @chunks, cbc_padding_oracle_block($previous, $target, $oracle);
      $previous = $target;
   }
   return validate_pkcs7_pad(join('', @chunks), 16);
} ## end sub cbc_padding_oracle_crack

sub cbc_padding_oracle_block ($previous, $target, $oracle) {
   my $s    = 0;             # where to start searching
   my $zero = 'YELLOW SUBMARINE'; # anything does here
   for my $k (reverse(0 .. 15)) {
      ($zero, $s) =
        cbc_padding_oracle_zeroing($zero, $target, $k, $s, $oracle);

      # For the last octet, we might have hit a false positive depending
      # on the contents of the penultimate char. Let's change it and check
      # whether the zeroing octet is still valid; if yes OK, otherwise we
      # have to continue the quest for the last zeroing octect.
      if ($k == length($target) - 1) {
         my $altered = $zero;
         my $penultimate = substr $altered, $k - 1, 1;
         substr $altered, $k - 1, 1, $penultimate ^ "\xff";
         ($zero) =
           cbc_padding_oracle_zeroing($zero, $target, $k, $s + 1, $oracle)
           unless $oracle->($altered . $target);
      } ## end if ($k == length($target...))

      $s = 0;    # reset for next iteration anyway
   } ## end for my $k (reverse(0 .....))
   return $zero ^ $previous;
} ## end sub cbc_padding_oracle_block

sub cbc_padding_oracle_zeroing ($previous, $target, $k, $start, $oracle) {
   my $prefix  = substr $previous, 0, $k;
   my $padchar = chr(16 - $k);
   my $trail   = $k < 15 ? substr($previous, $k + 1) : '';
   my $suffix  = $trail ^ ($padchar x (15 - $k));
   for my $i ($start .. 255) {
      my $padder          = chr($i);
      my $forged_previous = $prefix . $padder . $suffix;
      next unless $oracle->($forged_previous . $target);
      return ($prefix . ($padder ^ $padchar) . $trail, $i);
   } ## end for my $i ($start .. 255)
   return $previous;
   die "WTF?!?\n";
} ## end sub cbc_padding_oracle_zeroing

As indicated in the comments, when guessing the last octet in a block, there’s a slight chance of a false positive, which can be dismissed very quickly.

The core of the attack is in function cbc_padding_oracle_zeroing, where we try out all possible values over a specific octet $k. Variable $s indicates what is the starting value, because we might want to skip the false positive.

Attacking each block of encrypted data requires at most $257 + 15 * 256 = 4097$ calls to the oracle, which is definitely better than brute force attacking the key!

The last octet, as said, requires one more check to disambiguate the false positive.

Stay safe and secure!

ETOOBUSY 🚀 minimal blogging for the impatient