Cryptopals 19 - Break fixed-nonce CTR mode using substitutions (part 3)

TL;DR

Challenge 19 in Cryptopals - part 3 (last!). I know that this should be The Weekly Challenge day, but just to keep things close together…

We left part 2 with some working decryption code for the first 20 characters, but strings go up to 38 characters. What to do?

To be honest, I surrendered and avoided coding. Or, better, I avoided coding some artificial dumbness and went the opposite side, i.e. a terminal user interface!

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

use List::Util 'min';
use CryptoPals qw< decode_base64 slurp attack_repeated_xor_bylen xxd >;

my @encrypted = map { decode_base64($_) } split m{\n}mxs,
  slurp(shift // '19.enc');

my $lmin = min(map { length $_ } @encrypted);
say "min<$lmin>";

my $assembled = join '', map { substr $_, 0, $lmin } @encrypted;
my $guessed = attack_repeated_xor_bylen($assembled, $lmin);

my @plaintexts;
for my $i (0 .. $#encrypted) {
   push @plaintexts, substr $guessed, 0, $lmin, '';
   my $additional = length($encrypted[$i]) - $lmin;
   $plaintexts[-1] .= "\x00" x $additional;
}

$|++;
while ('necessary') {
   my $cursor = print_plaintexts(\@plaintexts);
   print {*STDOUT} "\ncursor at $cursor\ncommand> ";
   my $command = <STDIN>;
   if ($command =~ m{\A q}imxs) { last }

   elsif ($command =~ m{\A
            (?:s|set) \s+ (\d+) \s+ (?:(\d+) \s+)? (\S+)}imxs) {
      my ($row, $col, $char) = ($1, $2, $3);
      $col = $cursor unless length($col // '');
      set_according_to(\@plaintexts, \@encrypted, $row, $col, $char);
   }
   elsif ($command =~ m{\A
            (?:s|set) \s+ (\d+) \s+ (\d+) \s+ (\S+)}imxs) {
      set_according_to(\@plaintexts, \@encrypted, $1, $2, $3);
   }
}

say 'bye';

sub set_according_to ($ps, $es, $row, $column, $guess) {
   $guess = chr(hex($row)) if $guess =~ m{\A %(..)}mxs;
   my $key_char = substr($es->[$row], $column, 1) ^ $guess;
   for my $i (0 .. $ps->$#*) {
      next if length($ps->[$i]) <= $column;
      substr $ps->[$i], $column, 1,
         substr($es->[$i], $column, 1) ^ $key_char;
   }
}

sub reset_column ($ps, $column, $min_column) {
   for my $i (0 .. $ps->$#*) {
      next if length($ps->[$i]) < $column;
      substr $ps->[$i], $column, 1, "\x00";
   }
}

sub print_plaintexts ($ps) {
   my $lmax = 0;
   for my $i (0 .. $ps->$#*) {
      my $plain = $ps->[$i];
      my $len = length $plain;
      $len -= $plain =~ s{\x00}{_}gmxs;
      $lmax = $len if $len > $lmax;
      printf {*STDOUT} "%2d %s\n", $i, $plain;
   }
   return $lmax;
}

The first part is the same as before, with the exception that printing has been moved into its own function print_plaintexts, which also shows how many unknown characters are left to discover in each string and prepends strings with an integer identifier.

The interface is very crude, with only two commands (plus q to quit):

set to guess a specific character in a row and column. Basically we say I expect that characters in this row and this column should be an e, make it so and from this derive the rest of the column;
reset to reset what’s in a column, e.g. because the guess was wrong.

The set part works exactly because of what’s written in the challenge text itself:

CIPHERTEXT-BYTE XOR PLAINTEXT-BYTE = KEYSTREAM-BYTE
CIPHERTEXT-BYTE XOR KEYSTREAM-BYTE = PLAINTEXT-BYTE

With our guess we’re saying that one specific ciphertext character corresponds to a specific plaintext character - this allows us figure out the keystream octet. We then use this to get the plaintext for all other rows.

Using this interface is very clunky, but whatever I’m not using it for life! It has its own luxuries, though:

you can avoid providing a column, in which case the cursor will be used (its value is printed at each iteration and points to the first character that is still unset)
it’s possible to set percent-encoded replacements, so that passing a space character can be done by using %20.

Stay safe and secure!

ETOOBUSY 🚀 minimal blogging for the impatient