Cryptopals 36 - Implement Secure Remote Password (SRP)

TL;DR

Challenge 36 in Cryptopals.

For how much I skipped implementing stuff in the previous post, I think I more than covered in this installment.

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

use File::Basename 'dirname';
use lib dirname(__FILE__);

package SRPSession;
use v5.24;
use warnings;
use experimental 'signatures';
no warnings 'experimental::signatures';
use DiffieHellman;
use Math::Prime::Util 'powmod';
use Math::BigInt;
use Digest;

sub new ($package, %args) {
   die 'no email' unless defined $args{I};
   die 'no password' unless defined $args{P};
   $args{p} //= DiffieHellman->NIST_p;
   $args{g} //= DiffieHellman->NIST_g;
   $args{k} //= 3;
   my $self = bless { %args }, $package;
   $self->{$_} = Math::BigInt->new($self->{$_}) for qw< p g >;
   $self->{n_hex} = length $self->{p}->to_hex;
   $self->{secret_key} = $self->generate_secret_key;
   $self->init;
   return $self;
}

sub modexp ($self, $b, $e, $p) { Math::BigInt->new(powmod($b, $e, $p)) }

sub sha256_hex ($self, @data) {
   Digest->new('SHA-256')->add(@data)->hexdigest;
}

sub sha256 ($self, @data) {
   Digest->new('SHA-256')->add(@data)->digest;
}

sub hmac_sha256 ($self, $key, $data) {
   my $ikey = $key ^ ("\x36" x length($key));
   my $okey = $key ^ ("\x5c" x length($key));
   return $self->sha256($okey, $self->sha256($ikey, $data));
}

sub hex2bigint ($self, $hex) { return Math::BigInt->from_hex($hex) }

sub generate_secret_key ($self) {
   while ('necessary') {
      my $candidate_hex = join '',
         map { sprintf '%0x', int rand 16 } 1 .. $self->{n_hex};
      my $candidate = Math::BigInt->from_hex($candidate_hex);
      return $candidate if $candidate < $self->{p};
   }
}

package SRPServerSession;
use v5.24;
use warnings;
use experimental 'signatures';
no warnings 'experimental::signatures';
use CryptoPals qw< random_octets >;
use parent -norequire => 'SRPSession';

sub init ($self) {
   my $salt = $self->{salt} = random_octets(16);
   my $x_hex = $self->sha256_hex($salt, $self->{P});
   my $x = $self->hex2bigint($x_hex);
   my $v = $self->{v} = $self->modexp($self->{g}, $x, $self->{p});
   my $gb = $self->modexp($self->@{qw< g secret_key p>});
   $self->{public_key} = ($v * $self->{k} + $gb) % $self->{p};
   return $self;
}

sub fail_login { die "invalid login\n" }

sub login_phase1 ($self, $email, $client_public_key) {
   fail_login() unless $email eq $self->{I};
   $self->{client_pk} = $client_public_key;

   my $u_hex = $self->sha256_hex($client_public_key, $self->{public_key});
   my $u = $self->hex2bigint($u_hex);

   my $v_u = $self->modexp($self->{v}, $u, $self->{p});
   my $S = $self->{S} = $self->modexp($client_public_key * $v_u,
      $self->{secret_key}, $self->{p});
   $self->{K} = $self->sha256($S);

   return $self->@{qw< salt public_key >};
}

sub login_phase2 ($self, $authenticator) {
   my $expected = $self->hmac_sha256($self->@{qw< K salt >});
   return $expected eq $authenticator;
}

package SRPClientSession;
use v5.24;
use warnings;
use experimental 'signatures';
no warnings 'experimental::signatures';
use parent -norequire => 'SRPSession';

sub init ($self) {
   $self->{public_key} = $self->modexp($self->@{qw< g secret_key p>});
   return $self;
}

sub public_key ($self) { return $self->{public_key} }

sub email ($self) { return $self->{I} }

sub login_phase1 ($self) { return $self->@{qw< I public_key >} }

sub login_phase2 ($self, $salt, $server_public_key) {
   my $u_hex = $self->sha256_hex($self->{public_key}, $server_public_key);
   my $u = $self->hex2bigint($u_hex);
   my $x_hex = $self->sha256_hex($salt, $self->{P});
   my $x = $self->hex2bigint($x_hex);
   my $base = $self->{k} * $self->modexp($self->{g}, $x, $self->{p});
   $base = ($server_public_key - $base) % $self->{p};
   my $S = $self->{S} = $self->modexp($base,
      $self->{secret_key} + $u * $x, $self->{p});
   my $K = $self->{K} = $self->sha256($S);
   return $self->hmac_sha256($K, $salt);
}

package main;
use v5.24;
use warnings;
use CryptoPals ':all';
use Data::Dumper;

use Test::More;

my %args = (
   I => 'foo@example.com',
   P => 'foo-bar-baz',
   # g, p, k set according to defaults
);

my $server = SRPServerSession->new(%args);
my $client = SRPClientSession->new(%args);

my @c2s = $client->login_phase1;
my @s2c = $server->login_phase1(@c2s);
my $authenticator = $client->login_phase2(@s2c);
ok $server->login_phase2($authenticator), 'client authenticator OK';

done_testing();

There are two session sides: the server and the client. The two share a common base class where most of the lower-level heavy lifting is performed, like calculations and hashing.

It’s been interesting to code the HMAC function according to the relevant Wikipedia page:

sub hmac_sha256 ($self, $key, $data) {
   my $ikey = $key ^ ("\x36" x length($key));
   my $okey = $key ^ ("\x5c" x length($key));
   return $self->sha256($okey, $self->sha256($ikey, $data));
}

This arrangement should address the issues related to puttin the key either before or after the message for taking the HMAC.

The technique, as stated in the challenge text:

is basically Diffie Hellman with a tweak of mixing the password into the public keys.

It indeed works… and I suspect we’re going to be asked and break it soon!

Stay safe and secure!

ETOOBUSY 🚀 minimal blogging for the impatient