Cryptopals 24 - Create the MT19937 stream cipher and break it

TL;DR

Challenge 24 in Cryptopals.

This challenge is about half chores and half a summary of what we already saw.

There’s some stuff to implement, like a stream cipher where we extract bytes from the Mersenne twister to do the encryption. As we already discussed, this can be a very bad idea if the pseudo-random function is easily predicted.

In this case, the first part forcefully restricts the seed to a 16-bits integer, i.e. in the range $0 - 65535$, while the second deals with epochs again, which we are forcing into an even shorter time span (no more than 5 minutes back). Both parts basically boil down to the same approach, though: try the seed until one of them works.

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

use CryptoPals qw< mt19937_factory xxd random_octets encode_base16 decode_base16 >;

my $seed = shift // 0xC0BE;
$seed &= 0xFFFF;
my $plaintext = 'Whatevah, folks!!!';

my $ciphertext = mt19937_encrypt($seed, $plaintext);
say '' . xxd($ciphertext);

my $decrypted = mt19937_decrypt($seed, $ciphertext);
say "\nOriginal plaintext  <$plaintext>\nRoundtrip plaintext <$decrypted>";

my $reset_token = mt19937_reset_token();
say "first  reset token: <$reset_token>";

my $other_reset_token = other_random_reset_token();
say "second reset token: <$other_reset_token>";

my $random_prefix   = random_octets(30 + int rand 30);
my $known_plaintext = 'YELLOW SUBMARINE';
my $kpl             = length $known_plaintext;
my $reference_ciphertext =
  mt19937_encrypt($seed, $random_prefix . $known_plaintext);

my $found_seed;
for my $candidate (0 .. 0xFFFF) {
   my $candidate_plaintext =
     mt19937_decrypt($candidate, $reference_ciphertext);
   next if $known_plaintext ne substr $candidate_plaintext, -$kpl, $kpl;
   $found_seed = $candidate;
   last;
} ## end for my $candidate (0 .....)

if (defined $found_seed) {
   printf "seed: %d (%04X)\n", $found_seed, $found_seed;
}
else {
   warn "did not find the seed...\n";
}

sleep rand 5;
say 'first  ', is_from_recent_mt19937($reset_token) ? 'YES' : 'NO';
say 'second ', is_from_recent_mt19937($other_reset_token) ? 'YES' : 'NO';

sub mt19937_encrypt ($seed, $data) {
   my $mt     = mt19937_factory($seed);
   my $offset = 0;
   my $length = length $data;
   my $left   = $length;
   my @chunks;
   while ($left > 0) {
      my $chunk_key = pack 'N', $mt->();
      my $chunk_length = $left > 4 ? 4 : $left;
      $chunk_key = substr $chunk_key, 0, $chunk_length;
      push @chunks, substr($data, $offset, $chunk_length) ^ $chunk_key;
      $left -= $chunk_length;
      $offset += $chunk_length;
   } ## end while ($left > 0)
   return join '', @chunks;
} ## end sub mt19937_encrypt

sub mt19937_decrypt ($seed, $data) { goto \&mt19937_encrypt }

sub mt19937_reset_token ($seed = undef) {
   my $mt = mt19937_factory($seed // time());
   return encode_base16(join '', pack 'N*', map { $mt->() } 1 .. 6);
}

sub other_random_reset_token {
   return encode_base16(join '', pack 'N*', map { int rand 0xFFFFFFFF } 1 .. 6 );
}

sub is_from_recent_mt19937 ($token) {
   my $target = unpack 'N', decode_base16(substr $token, 0, 8);
   my $candidate = time();
   for (0 .. 600) { # up to 3 minutes before
      my $mt = mt19937_factory($candidate--);
      return 1 if $target eq $mt->();
   }
   return 0;
}

Just for completeness, an other_random_reset_token function is coded, using the stock rand() function for getting the token. As expected, the first one complies with the generation with the Mersenne twister, while the second one does not.

Stay safe and secure!

ETOOBUSY 🚀 minimal blogging for the impatient