Cryptopals 37 - Break SRP with a zero key

TL;DR

Challenge 37 in Cryptopals.

You know when I wrote that cryptographic stuff MUST be used exactly as written on the can? Well, sometimes there is stuff that has not been written there yet!

The challenge commentary is worth citing here:

Trevor Perrin and Nate Lawson taught us this attack 7 years ago. It is excellent. Attacks on DH are tricky to “operationalize”. But this attack uses the same concepts, and results in auth bypass. Almost every implementation of SRP we’ve ever seen has this flaw; if you see a new one, go look for this bug.

This is indeed excellent, much like the Egg of Colombo. One of those things that, in hindsight, make you realize I could have thought of that. But you didn’t.

As attackers, our goal is to get in, which might mean figuring out the right HMAC for the provided salt, which might mean figuring out the key $K$, which might mean figuring out the value for shared secret $S$.

So let’s look at the math as used by the server:

\[S = (A \cdot v^u) ^ b \pmod N \\ S = (A ^ b \cdot v^{u\cdot b}) \pmod N \\ S = (A ^ b \pmod N) \cdot (v^{u \cdot b}) \pmod N\]

The client is providing $A$, so what happens if it’s a multiple of $N$? Simple: any of is non-zero powers is a multiple of $N$ as well, which means (remember that $b \ne 0$):

\[A = i \cdot N \\ \Rightarrow (A^b \pmod N) = 0 \\ \Rightarrow S = 0\]

This means: we can force our own known value of $S$ onto the server, even withouth knowing the password.

On the code side, this is relatively easy to accomplish, starting from our previous code. It suffices to code a rogue client (as a subclass of the previous normal client) that forces the public key to be a multiple of $N$ (according to our own provided value of $i$, represented by parameter fake_key_factor) and then uses $S = 0$ to compute the authenticator:

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

sub init ($self) {
   $self->{public_key} = $self->{fake_key_factor} * $self->{p};
}

sub login_phase2 ($self, $salt, $server_public_key) {
   my $K = $self->sha256(0);
   return $self->hmac_sha256($K, $salt);
}

The rest is the same as before, with a slight change on which client implementation we decide to use, depending on the password provided on the command line:

my %args = (I => $email, P => $password);
my $client;
if (($password // '/0') =~ m{\A / (\d+)}mxs) {
   $client = SRPRogueClientSession->new(%args, fake_key_factor => $1);
}
else {
   $client = SRPClientSession->new(%args);
}

All password matching regular expression /(\d+) result in using a rogue client, aaaaand:

# this is with the right password
$ perl 37-cnt.pl foo@bar.baz xxx
we're in!

# this is with the wrong password
$ perl 37-cnt.pl foo@bar.baz YYYYY
no luck...

# A = 0
$ perl 37-cnt.pl foo@bar.baz /0
we're in!

# A = N
$ perl 37-cnt.pl foo@bar.baz /1
we're in!

# A = 7N
$ perl 37-cnt.pl foo@bar.baz /7
we're in!

# you get the idea...

Stay safe and secure!

ETOOBUSY 🚀 minimal blogging for the impatient