Cryptopals 26 - CTR bitflipping


Challenge 26 in Cryptopals.

I can feel some sneering in this blunt statement from this challenge:

There are people in the world that believe that CTR resists bit flipping attacks of the kind to which CBC mode is susceptible.

Which, of course, they don’t believe:

Re-implement the CBC bitflipping exercise from earlier to use CTR mode instead of CBC mode. Inject an “admin=true” token.

So… a proof by contradiction, how elegant.

Apart, of course, from the fact that we have to implement it.

I guess that there are at least two lessons to be learned here:

  • if there’s a way for the attacker to control the ciphertext (or whatever), there probably are ways for the attacker to abuse this;
  • confidentiality alone will not help authenticating the plaintext.

Apart, of course, from the confirmation, time and again, of the zeroeth lesson of all:

  • there’s nothing really safe in security, so we should better refrain from believing too much our educated guesses.

I like it for its very scientific approach. I hate it because people can be in danger.

So, what can we abuse here? Looking closely, it’s not that different from before:

  • in CBC mode we can forge the previous block to get a favorable XOR in the right octet of the plaintext;
  • in CTR mode we can forge the current block to get a favorable XOR in the right octect of the plaintext.

We don’t even have to mentally shift anywhere!

It’s actually even worse in CTR mode. When we get the ciphertext back from the oracle, we know that it’s the XORing of the plaintext and the randomish sequence generated by CTR mode:


As we know both the ciphertext and the plaintext at this point, we can calculate the encrypting sequence back:


Now we can create whatever plaintext we want and calculate the corresponding ciphertext:


We don’t even get to sacrifice a block of data like in CBC mode!

OK, let’s look at the implementation. First of all we change our oracles to simulate the blue team switching to CTR for fun and wishful safety:

sub oracle_is_admin_ctr ($ciphertext) {
    my $dec = aes_ctr_crypt($ciphertext, the_key(), the_nonce());
    my $is_admin = $dec =~ m{;admin=true;}mxs;
    return $is_admin;

sub oracle_encrypt_ctr ($string) { # %-encode ;, % and =
   $string =~ s{([;=%])}{'%' . unpack 'H2', $1}egmxs;
   $string = 'comment1=cooking%20MCs;userdata=' . $string .
   return aes_ctr_crypt($string, the_key(), the_nonce());

sub the_key   { state $key = random_key() }
sub the_nonce { state $iv  = random_octets(8) }

The oracle_is_admin_ctr() is forced to use the same key and nonce as oracle_encrypt_ctr because otherwise it would not allow in even legitimate administrators. The underlying function is the same in the two cases (aes_ctr_crypt) thanks to how CTR works.

Now let’s go to the exploit. As requested, we’re just making the minimal adjustments to the previous solution, although we might be able to fit whatever we want in the plaintext, as observed:

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

my $blk_off = 16 * (3 - 1); # working on third block
my $sixth = substr $encrypted, $blk_off + 5, 1;
substr $encrypted, $blk_off + 5, 1, $sixth ^ "\x02";

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

ok oracle_is_admin_ctr($encrypted), 'requested string is present';

The $hack_input is inserted to fit exactly into the full third block of $encrypted data. For this reason, we pre-compute the $blk_off offset to work on that block, making sure to change the sixth and twelveths octet, just like before (although in CBC mode we were doing these modifications in the second block, so we had a different offset).

This is it, we just had to move from the second block to the third, the rest is unchanged.

So again, me from the future: don’t think that confidentiality alone can guarantee integrity/authentication. These have to be cared for explicitly.

Stay safe and secure!

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