implementation of sha-256 in perl

Question

i'm trying very hard on implementing the sha-256 algorithm. I have got problems with the padding of the message. for sha-256 you have to append one bit at the end of the message, which I have reached so far with $message .= (chr 0x80); The next step should be to fill the emtpy space(512bit block) with 0's. I calculated it with this formula: l+1+k=448-l and append it then to the message. My problem comes now:Append in the last 64bit block the binary representation of the length of the message and fill the rest with 0's again. Since perl handles their data types by themself, there is no "byte" datatype. How can I figure out which value I should append?

please see also the official specification: http://csrc.nist.gov/publications/fips/fips180-3/fips180-3_final.pdf

Answer 1

If at all possible, pull something off the shelf. You do not want to roll your own SHA-256 implementation because to get official blessing, you would have to have it certified.

That said, the specification is

5.1.1 SHA-1, SHA-224 and SHA-256

Suppose that the length of the message, M, is l bits. Append the bit 1 to the end of the message, followed by k zero bits, where k is the smallest, non-negative solution to the equation

l + 1 + k ≡ 448 mod 512

Then append the 64-bit block that is equal to the number l expressed using a binary representation. For example, the (8-bit ASCII) message “abc” has length 8 × 3 = 24, so the message is padded with a one bit, then 448 - (24 + 1) = 423 zero bits, and then the message length, to become the 512-bit padded message

                                  423       64
                                 .-^-.  .---^---.
01100001  01100010  01100011  1  00…00  00…011000
   “a”       “b”       “c”                  '-v-'
                                             l=24

Then length of the padded message should now be a multiple of 512 bits.

You might be tempted to use vec because it allows you to address single bits, but you would have to work around funky addressing.

If bits is 4 or less, the string is broken into bytes, then the bits of each byte are broken into 8/BITS groups. Bits of a byte are numbered in a little-endian-ish way, as in 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80. For example, breaking the single input byte chr(0x36) into two groups gives a list (0x6, 0x3); breaking it into 4 groups gives (0x2, 0x1, 0x3, 0x0).

Instead, a pack template of B* specifies

A bit string (descending bit order inside each byte).

and N

An unsigned long (32-bit) in "network" (big-endian) order.

The latter is useful for assembling the message length. Although pack has a Q parameter for quad, the result is in the native order.

Start with a bit of prep work

our($UPPER32BITS,$LOWER32BITS);
BEGIN {
  use Config;
  die "$0: $^X not configured for 64-bit ints"
    unless $Config{use64bitint};

  # create non-portable 64-bit masks as constants
  no warnings "portable";
  *UPPER32BITS = \0xffff_ffff_0000_0000;
  *LOWER32BITS = \0x0000_0000_ffff_ffff;
}

Then you can defined pad_message as

sub pad_message {
  use bytes;

  my($msg) = @_;
  my $l = bytes::length($msg) * 8;
  my $extra = $l % 512;  # pad to 512-bit boundary
  my $k = 448 - ($extra + 1);

  # append 1 bit followed by $k zero bits
  $msg .= pack "B*", 1 . 0 x $k;

  # add big-endian length
  $msg .= pack "NN", (($l & $UPPER32BITS) >> 32), ($l & $LOWER32BITS);

  die "$0: bad length: ", bytes::length $msg
    if (bytes::length($msg) * 8) % 512;

  $msg;
}

Say the code prints the padded message with

my $padded = pad_message "abc";

# break into multiple lines for readability
for (unpack("H*", $padded) =~ /(.{64})/g) {
  print $_, "\n";
}

Then the output is

6162638000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000018

which matches the specification.