Trouble implementing SHA256 in FPC

[popeax]

I'm trying to implement the SHA256 secure hash algorithm in FPC but am having some trouble. What I've written so far is below. Calling SHA256Hash returns an incorrect hash. I suspect this may be an endianness problem but I'm not sure how to fix it - any help would be really appreciated.

The spec: http://csrc.nist.gov/publications/fips/fips180-2/fips180-2.pdf

It is safe to assume that all constants are correct, I have thoroughly checked them.

Side note: I know there are existing libraries that could do this for me, but now that I've started doing it from scratch I really want to finish it.

Code: [Select]

function ROR32(Data: LongWord; N: LongWord): LongWord;
begin
   Result := ((Data shr N) or (Data shl (32 - N)));
end;

function AddWrap32(X: LongWord; Y: LongWord): LongWord;
begin
   Result := (X + Y) mod 4294967295; // Upper-bound of 32-bit unsigned int is the modulus
end;

function Ch32(X, Y, Z: LongWord): LongWord;
begin
   Result := (X and Y) xor (not X and Z);
end;

function Maj32(X, Y, Z: LongWord): LongWord;
begin
   Result := ((X and Y) xor (X and Z) xor (Y and Z));
end;

function Sigma0_256(X: LongWord): LongWord;
begin
   Result := ROR32(X, 2) xor ROR32(X, 13) xor ROR32(X, 22);
end;

function Sigma1_256(X: LongWord): LongWord;
begin
   Result := ROR32(X, 6) xor ROR32(X, 11) xor ROR32(X, 25);
end;

function Gamma0_256(X: LongWord): LongWord;
begin
   Result := ROR32(X, 7) xor ROR32(X, 18) xor (X shr 3);
end;

function Gamma1_256(X: LongWord): LongWord;
begin
   Result := ROR32(X, 17) xor ROR32(X, 19) xor (X shr 10);
end;

function SHA256Hash(Plaintext: String): String;
var
   BPlain: array of Byte;
   l: QWORD;
   i, j, Blocks: LongInt;
   Congruent: Boolean;
   h0: LongWord = $6a09e667; h1: LongWord = $bb67ae85; h2: LongWord = $3c6ef372; h3: LongWord = $a54ff53a;
   h4: LongWord = $510e527f; h5: LongWord = $9b05688c; h6: LongWord = $1f83d9ab; h7: LongWord = $5be0cd19;
   a, b, c, d, e, f, g, h, t1, t2, mask: LongWord;
   W: array [0..63] of LongWord;
   K: array[0..63] of LongWord = (
   ($428a2f98), ($71374491), ($b5c0fbcf), ($e9b5dba5), ($3956c25b), ($59f111f1), ($923f82a4), ($ab1c5ed5),
   ($d807aa98), ($12835b01), ($243185be), ($550c7dc3), ($72be5d74), ($80deb1fe), ($9bdc06a7), ($c19bf174),
   ($e49b69c1), ($efbe4786), ($0fc19dc6), ($240ca1cc), ($2de92c6f), ($4a7484aa), ($5cb0a9dc), ($76f988da),
   ($983e5152), ($a831c66d), ($b00327c8), ($bf597fc7), ($c6e00bf3), ($d5a79147), ($06ca6351), ($14292967),
   ($27b70a85), ($2e1b2138), ($4d2c6dfc), ($53380d13), ($650a7354), ($766a0abb), ($81c2c92e), ($92722c85),
   ($a2bfe8a1), ($a81a664b), ($c24b8b70), ($c76c51a3), ($d192e819), ($d6990624), ($f40e3585), ($106aa070),
   ($19a4c116), ($1e376c08), ($2748774c), ($34b0bcb5), ($391c0cb3), ($4ed8aa4a), ($5b9cca4f), ($682e6ff3),
   ($748f82ee), ($78a5636f), ($84c87814), ($8cc70208), ($90befffa), ($a4506ceb), ($bef9a3f7), ($c67178f2)
   );
begin

   FillByte(W, length(W), 0);
   l := NtoBE(QWORD(length(Plaintext) * 8)); // Unsigned big endian 64-bit int representing message length (in bits) for appending to the message
   SetLength(BPlain, length(Plaintext) + 1); // Internal message buffer

   for i := 0 to length(Plaintext) - 1 do begin
      BPlain[i] := NtoBE(Ord(Plaintext[i+1]));
   end;

   BPlain[high(BPlain[i])] := $80;

   // Pad and check for congruence
   Congruent := false;
   while (not Congruent) do begin
      if (((length(BPlain) * 8) mod 512) = 448) then begin
         Congruent := true;
         break;
      end
      else begin
         SetLength(BPlain, length(BPlain) + 1);
         BPlain[high(BPlain)] := 0;
      end;
   end;

   Move(l, BPlain[high(BPlain) - sizeof(l)], sizeof(l)); // Copy the message length into the message buffer

   i := 0;
   while (i < length(BPlain)) do begin

      a := h0;
      b := h1;
      c := h2;
      d := h3;
      e := h4;
      f := h5;
      g := h6;
      h := h7;

      for j := 0 to 63 do begin

         if (j < 16) then W[j] := BPlain[j + i]
         else W[j] := AddWrap32(AddWrap32(AddWrap32(Gamma1_256(W[j - 2]), W[j - 7]), Gamma0_256(W[j - 15])), W[j - 16]);

         t1 := AddWrap32(AddWrap32(AddWrap32(AddWrap32(h, Sigma1_256(e)), Ch32(e, f, g)), K[j]), W[j]);
         t2 := AddWrap32(Sigma0_256(a), Maj32(a, b, c));

         h := g;
         g := f;
         f := e;
         e := AddWrap32(d, t1);
         d := c;
         c := b;
         b := a;
         a := AddWrap32(t1, t2);

      end;

      h0 := AddWrap32(a, h0);
      h1 := AddWrap32(b, h1);
      h2 := AddWrap32(c, h2);
      h3 := AddWrap32(d, h3);
      h4 := AddWrap32(e, h4);
      h5 := AddWrap32(f, h5);
      h6 := AddWrap32(g, h6);
      h7 := AddWrap32(h, h7);

      Inc(i, 64);

   end;

   Result := lowercase(IntToHex(h0, 1) + IntToHex(h1, 1) + IntToHex(h2, 1) + IntToHex(h3, 1) + IntToHex(h4, 1) + IntToHex(h5, 1) + IntToHex(h6, 1) + IntToHex(h7, 1));

end;

[Marc]

I had a quick look at some functions and have some remarks.

Code: Pascal  [Select][+][-]

1. function ROR32(Data: LongWord; N: LongWord): LongWord;
2. begin
3.    Result := ((Data shr N) or (Data shl (32 - N)));
4. end;
5.  

Why using N:Longword and not N: Byte ?

Code: Pascal  [Select][+][-]

1. function AddWrap32(X: LongWord; Y: LongWord): LongWord;
2. begin
3.    Result := (X + Y) mod 4294967295; // Upper-bound of 32-bit unsigned int is the modulus
4. end;
5.  

This makes no sense to me. X+Y will never exceed High(LongWord) anyway. what you wrote here is something like:

Code: Pascal  [Select][+][-]

1. begin
2.   Result := X + Y;
3.   if Result = High(LongWord) then Result := 0;
4. end;

Reading para 3.2, they talk about 2^w and that is $100000000 and not $0FFFFFFFF
So the mod is not needed.

Code: Pascal  [Select][+][-]

1. function Ch32(X, Y, Z: LongWord): LongWord;
2. begin
3.    Result := (X and Y) xor (not X and Z);
4. end;
5.  

It's not clear from the document is the not should operate on X or on (X and Z), but I guess you're right.

Code: Pascal  [Select][+][-]

1.    K: array[0..63] of LongWord = (
2.    ($428a2f98), ($71374491), ($b5c0fbcf), ($e9b5dba5), ($3956c25b), ($59f111f1), ($923f82a4), ($ab1c5ed5),
3.   ....
4.  

you don't need to put () around the constants, but it doesn't hurt.

Code: Pascal  [Select][+][-]

1. var
2.    l: QWORD;
3.  

My advice, avoid using lowercase L as variable, it is very easy to misinterpret as 1 (one)

Code: Pascal  [Select][+][-]

1. var
2.   W: array [0..63] of LongWord;
3. begin
4.   FillByte(W, length(W), 0);
5.   ....  
6.  

Lenght(W) returns the length of the array, 64 in this case. What you want here is either

Code: Pascal  [Select][+][-]

1.   FillByte(W, SizeOf(W), 0);

or

Code: Pascal  [Select][+][-]

1.   FillLongWord(W, Length(W), 0);

Code: Pascal  [Select][+][-]

1.    for i := 0 to length(Plaintext) - 1 do begin
2.       BPlain[ i ] := NtoBE(Ord(Plaintext[i+1]));
3.    end;
4.  

BPlain[ i ] is a Byte, Plaintext[i+1] is a Char, Ord(Char) is a Byte. There is no need to convert a Byte to little of bigendean. There doesn't exist a NtoBE(Byte) version, so I fear the compiler converts it to a NtoBE(Word) call, resulting in the value 0 in your case.

Code: Pascal  [Select][+][-]

1.    BPlain[high(BPlain[ i ])] := $80;
2.  

No clue what you are trying to do here. BPlain[ i ] is a Byte, High(Byte) equals to 255, so you effectively wrote

Code: Pascal  [Select][+][-]

1.    BPlain[255] := $80;
2.  

Besides that you refer to the for loop variable i, which is undefined outside the for loop.

Code: Pascal  [Select][+][-]

1.    Congruent := false;
2.    while (not Congruent) do begin
3.       if (((length(BPlain) * 8 ) mod 512) = 448 ) then begin
4.          Congruent := true;
5.          break;
6.       end
7.       else begin
8.          SetLength(BPlain, length(BPlain) + 1);
9.          BPlain[high(BPlain)] := 0;
10.       end;
11.    end;
12.  

this can way easier...
The combo congruent := true and break is double. By breaking you are already outside the loop, so no need to set it to true.
I'm to lazy to verify, but I guess that the extra length needed is
  (64 - ((length(BPlain)+8 ) mod 64) )mod 64

Code: Pascal  [Select][+][-]

1.    Move(l, BPlain[high(BPlain) - sizeof(l)], sizeof(l)); // Copy the message length into the message buffer
2.  

Here you copy the lenght in bigendean order to the end of the buffer ?

(here I stopped)

[popeax]

Thank you very much for the comments! Some of those mistakes were glaringly obvious - sorry about that, I guess I had been staring at it for too long  . I'll reply again once I've taken another look!