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


Challenge 19 in Cryptopals - part 2 starting the “attack”.

The challenge explicitly suggests:

Don’t overthink it.

Well, sure I like to overthink stuff, but this time the only thing that came to mind was that we already saw that XORing many things with the same key is bad. With code and everything.

This time it’s even simpler because we don’t have to guess the length of this XORing key. It’s way longer than all the plaintexts, which means that every character position is a story by itsef.

So I went for not overthinking, and attack the common part, i.e. the initial part of all cyphertexts that all strings have. To do this, the minimum length across all of them comes handy.

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

use List::Util 'min';

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

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

The minimum length is 20.

To be very lazy, at this point I went for a big, long string with that part from all input strings, one after the other.

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

As a matter of fact, I’m re-creating the conditions for Cryptopals 6 - Break repeated-key XOR, so that we can also reuse attack_repeated_xor_bylen using that minimum length as the length.

use CryptoPals qw< decode_base64 slurp attack_repeated_xor_bylen xxd >;
my $guessed = attack_repeated_xor_bylen($assembled, $lmin);
say substr $guessed, 0, 20, '' while length $guessed;

And presto!, the first 20 characters of each string come out unencrypted, yay!

It’s marginally interesting that the very first character comes out wrong. I can tell because one of the strings starts with the pronoun I, which is always uppercase in English, and yet it comes out lowercase. Why is that? Because it’s the very first character, and all characters are uppercase, so both uppercase and lowercase would work, and my quest evidently finds the lowercase first and calls it a day. Nothing bad for the understanding!

Stay safe and secure!

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