Cryptopals 16 - CBC bitflipping attacks

TL;DR

Challenge 16 in Cryptopals.

After doing some cut-and-paste with ECB mode, we find out that we can have some fun in messing with the ciphertext of CBC mode too. In particular, by changing one or more bits in the ciphertext of a block, we can directly influence the octets in the plaintext of the following block.

Why is that? Well, it’s easy to see by looking at how decryption works:

CBC-mode decryption

Thanks to the venerable XOR, whatever bit flip we do to a block of the ciphertext will perform a bit flip in the same position to the plaintext of the following block.

This challenge asks us to do exactly this, in order to obtain the sub-string ;admin=true; in the decrypted output. It’s sort of brittle, because we will be introducing some garbage into the decrypted string, but it might actually work!

Let’s start with the oracles:

sub oracle_encrypt ($string) { # %-encode ;, % and =
   $string =~ s{([;&=%])}{'%' . unpack 'H2', $1}egmxs;
   $string = 'comment1=cooking%20MCs;userdata=' . $string .
      ';comment2=%20like%20a%20pound%20of%20bacon';
   return aes_cbc_encrypt($string, the_key(), the_iv());
}

sub oracle_is_admin ($ciphertext) {
    my $dec = aes_cbc_decrypt($ciphertext, the_key(), the_iv());
    my $is_admin = $dec =~ m{;admin=true;}mxs;
    return $is_admin;
}

sub the_key { state $key = random_key() }
sub the_iv  { state $iv  = random_key() }

This is what we want to encrypt:

0123456789ABCDEF

comment1=cooking
%20MCs;userdata=

CLOUD9admin9true

;comment2=%20lik
e%20a%20pound%20
of%20bacon

The central part indicates that we want to introduce a fake block that contains string 9admin9true, which is then followed by a block with ; and other stuff.

The interesting thing about 9 is that it’s perfectly innocuous to the oracle, but it’s very, very close to both ; and =, as the following translation of the associated ASCII codes shows us:

9 00111001
; 00111011
= 00111101

Our two special characters are just one bit flip away!

So here’s how we do it. First, we get the encrypted stuff from the relevant oracle:

my $hack_input = 'CLOUD9admin9true';
my $encrypted = oracle_encrypt($hack_input);

At this point, we operate on the sixth and the twelveth octets of the ciphertext in the second block, by flipping respectively bit of weight 2 and 4. This will influence the corresponding octets in the plaintext of the third block, i.e. our two 9 characters:

my $sixth = substr $encrypted, 16 + 5, 1;
substr $encrypted, 16 + 5, 1, $sixth ^ "\x02";

my $twelveth = substr $encrypted, 16 + 11, 1;
substr $encrypted, 16 + 11, 1, $twelveth ^ "\x04";

Now our carefully crafted ciphertext $encrypted is ready to be checked by the granting oracle, where the XOR operator will do the magic:

say oracle_is_admin($encrypted) ? 'admin is true' : 'no admin...';

This, of course, tells us… admin is true, yay!

Stay safe and secure!


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