Cryptopals 38 - Offline dictionary attack on simplified SRP

TL;DR

Challenge 38 in Cryptopals.

Sometimes I wish these challenges elaborated a bit more on the goals and the morale of what’s requested. You know, just to make sure that I’m not missing the full range of lessons.

In this case, the title says it pretty straight: we have to implement a dictionary attack. Then the text asks us to crack the password. So the immediate lessons I get even before starting are:

SRP is prone to be attacked with a dictionary attack
time and again, we’re proven that a weak password defies any effort.

The first deduction comes from the fact that we’re asked to implement the dictionary attack, so it should be feasible right?

In this case, it relies on the fact that all involved operations –which eventually boil down to exponentiations modulo a prime and SHA-256 calculations– can be easily implemented in a very fast way. Maybe this is nudging us towards something which requires much more to calculated, e.g. ARGON2.

Anyway.

I took it literally and maybe cheated a bit, but for a good cause. To make a dictionary attack successful, we need to have a dictionary. So I took the first one I found around, i.e. /usr/share/dict/words to both choose a single word as a password and to try them all for cracking.

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


use File::Basename 'dirname';
use lib dirname(__FILE__);
use CryptoPals qw< slurp sha256 hmac_sha256 >;
use DiffieHellman;
use Math::BigInt;
use Math::Prime::Util qw< powmod mulmod >;

use Digest;

$|++;
my $g = DiffieHellman::NIST_g;
my $n = DiffieHellman::NIST_p;

my $words_file = shift // '/usr/share/dict/words';
my @words = split m{\n+}mxs, slurp($words_file);

# MITM server... Settle for simple params
my $srv_b = 1;
my $srv_B = Math::BigInt->new($g); # $g ** $srv_b = $g
my $srv_u = Math::BigInt->new(1);  # don't bother
my $srv_salt = '';


# client, let's do this "correctly".
my ($clt_A, $clt_mac);
my $is_password_correct;
{
   my $client_password = $words[rand @words];
   say "pssst! client chose password '$client_password', KEEP IT SAFE!";
   $is_password_correct = sub ($p) { $p eq $client_password };

   my $dh = DiffieHellman->new(p => $n, g => $g);
   my ($clt_a_o, $clt_A_o) = $dh->generate_key_pair;
   my $clt_a = Math::BigInt->from_hex(unpack 'H*', $clt_a_o);
   $clt_A = Math::BigInt->from_hex(unpack 'H*', $clt_A_o);

   my $x_hex = unpack 'H*', sha256($srv_salt . $client_password);
   my $x = Math::BigInt->from_hex($x_hex);
   my $S = modexp($srv_B, $clt_a + $srv_u * $x, $n);
   $clt_mac = hmac_sha256(sha256($S), $srv_salt);
}

# MITM side after receiving $clt_A and $clt_mac
for my $word (@words) {
   print {*STDOUT} "\r" . (' ' x 60) . "\rTrying '$word'";
   my $x = Math::BigInt->from_hex(unpack 'H*', sha256($word));
   my $S = ($clt_A * modexp($g, $x, $n)) % $n;
   my $crk_mac = hmac_sha256(sha256($S), $srv_salt);
   if ($crk_mac eq $clt_mac) {
      say "\nfound word '$word' and it is ",
         $is_password_correct->($word) ? 'correct' : 'WRONG!!!';
      last;
   }
}

sub modexp ($b, $e, $n) { Math::BigInt->new(Math::Prime::Util::powmod($b, $e, $n)) };

On the server side, we have this:

\[x = H(\text{salt|password}) \\ S = A^b g^{xub} = A^b(g^{ub})^x \\ M = \text{HMAC-SHA256}(\text{SHA256}(S), \text{salt})\]

The choice of salt, $b$ and $u$ is in the sake of simplyfing calculations server-side, I hope I did not miss other more evident values to this regard:

\[\text{salt} = \text{''} \Rightarrow x = H(\text{password}) \\ b = 1, u = 1 \Rightarrow B = g^b = g, S = Ag^x \\ M = \text{HMAC-SHA256}(\text{SHA256}(S), \text{''})\]

Hence we’re sending an empty salt and $B = g$ back to the client, hoping they have no specific check to smell rotten fish! This eventually requires us to calculate one exponetiation and one multiplication only.

I can’t see space for calculating rainbow tables here, because the use of HMAC would basically require that we calculate it for every possible key $K$ (taken from a SHA-256), which is definitely too much. I might be missing something here too.

Stay safe and secure!

ETOOBUSY 🚀 minimal blogging for the impatient