Cryptopals 28 - Implement a SHA-1 keyed MAC

TL;DR

Challenge 28 in Cryptopals.

This challenge starts with requesting a SHA-1 implementation that we can use to later fiddle with. This is in preparation of the following challenge.

SHA-1 implementation

Here’s my implementation:

package My::SHA1;
use v5.24;
use warnings;
use experimental 'signatures';
no warnings 'experimental::signatures';
use List::Util 'reduce';

sub new ($package, %args) {
   my $self = bless {
      h0 => 0x67452301,
      h1 => 0xEFCDAB89,
      h2 => 0x98BADCFE,
      h3 => 0x10325476,
      h4 => 0xC3D2E1F0,
      ml => 0,           # message length, in bits
      left => '',        # leftover not reaching 512 bytes
      %args, # this can override anything
   }, ref($package) || $package;
   if (defined(my $starter = delete $self->{starter})) {
      $self->@{qw< h0 h1 h2 h3 h4 >} = unpack 'N5', pack 'H*', $starter;
   }
   return $self;
}

sub clone ($self) { return $self->new($self->%*) }

sub hex_digest ($self) {
   my $copy = $self->clone->_append_padding;
   die "residuals\n" if length($copy->{left});
   unpack 'H*', pack 'N5', $copy->@{qw< h0 h1 h2 h3 h4 >};
}

sub _append_padding ($self) {
   my $length = $self->{ml};
   my $l512 = (1 + $length) % 512;
   my $n_zeros = 448 - $l512 + ($l512 <= 448 ? 0 : 512);
   $self->add("\x80", "\x00" x ($n_zeros / 8),
      pack 'N2', $length >> 32, $length & 0xFFFFFFFF);
   return $self;
}

sub add ($self, @data) {
   my $b32m = 0xFFFFFFFF;

   my $data = join '', @data;
   $self->{left} .= $data;
   $self->{ml} += 8 * length($data);

   my @h = $self->@{qw< h0 h1 h2 h3 h4 >};

   while (length($self->{left}) >= 512 / 8) { # take 512-bits chunks

      # get chunk, 16 words of 32 bits each
      my @w = map {
         my $word = substr $self->{left}, 0, 32 / 8, '';
         unpack 'N', $word;
      } 0 .. 15;

      # expand to 80 words
      for my $i (16 .. 79) {
         my $n = reduce { $a ^ $b } @w[map { $i - $_ } (3, 8, 14, 16)];
         push @w, left($n, 1);
      }

      my ($A, $B, $C, $D, $E) = @h;
      for my $i (0 .. 79) {
         my ($F, $K) =
              $i < 20 ? (($B & $C) | (($b32m ^ $B) & $D),   0x5A827999)
            : $i < 40 ? ($B ^ $C ^ $D,                      0x6ED9EBA1)
            : $i < 60 ? (($B & $C) | ($B & $D) | ($C & $D), 0x8F1BBCDC)
            :           ($B ^ $C ^ $D,                      0xCA62C1D6);
         ($A, $B, $C, $D, $E) = (
            (( left($A, 5) + $F + $E + $K + $w[$i]) & $b32m),
            $A,
            left($B, 30),
            $C,
            $D
         );
      }

      $h[0] = ($h[0] + $A) & $b32m;
      $h[1] = ($h[1] + $B) & $b32m;
      $h[2] = ($h[2] + $C) & $b32m;
      $h[3] = ($h[3] + $D) & $b32m;
      $h[4] = ($h[4] + $E) & $b32m;
   }

   $self->@{qw< h0 h1 h2 h3 h4 >} = @h;

   return $self;
}

sub left ($n, $amount) {
   (($n << $amount) | ($n >> (32 - $amount))) & 0xFFFFFFFF;
}

1;

Of course it was not correct from the beginning, because of multiple bugs. Anyway, thanks also to the test vectors available at Examples with Intermediate Values, it was easy to find all bugs and fix them.

Usage is exemplified in the tests for it:

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

use Digest::SHA;
use Data::Dumper;

use Test::More;

# https://csrc.nist.gov/projects/cryptographic-standards-and-guidelines/example-values

my $full_msg = 'YELLOW SUBMARINE' x 10;

for my $len (0 .. length $full_msg) {
   my $tester = substr $full_msg, 0, $len;

   my $expected = Digest::SHA->new(1)->add($tester)->hexdigest;
   my $got = My::SHA1->new->add($tester)->hex_digest;
   is $got, $expected, "length: $len";
}

{
   my $ms = My::SHA1->new(starter => '67452301EFCDAB8998BADCFE10325476C3D2E1F0');
   my $exp = Digest::SHA->new(1)->add('abc')->hexdigest;
   my $got = $ms->add('abc')->hex_digest;
   is $got, $exp, 'use initializer, correct';
}

{
   my $ms = My::SHA1->new(starter => '0123456789ABCDEF01234567890ABCDEF0123456');
   my $exp = Digest::SHA->new(1)->add('abc')->hexdigest;
   my $got = $ms->add('abc')->hex_digest;
   ok $got ne $exp, 'use initializer, different';
}

done_testing();

Secret prefix MAC

Next in line is to code a function to produce a Message Authentication Code (MAC), implemented as SHA1(key || message):

sub SHA1_MAC_secret_prefix ($key, $message) {
    My::SHA1->new->add($key, $message)->hex_digest;
}

sub SHA1_MAC_secret_prefix_authenticate ($message, $mac) {
    my $expected = SHA1_MAC_secret_prefix(the_key(), $message);
    return $expected eq $mac;
}

# A random, but consistent key for the process run
sub the_key { state $key = random_key() }

Last part is interesting:

Verify that you cannot tamper with the message without breaking the MAC you’ve produced, and that you can’t produce a new MAC without knowing the secret key.

Considering what will be in the following challenge… I’m not sure how I’m supposed to verify this!

Stay safe and secure!


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