3
$\begingroup$

EDIT: I'm actually Thinking the issue is in the initialization phase, where we pad the message with 1's, 0's, and the message length.

EDIT EDIT See the bottom of the post, I've run out of ideas.. ):

I'm creating a user implemented SHA-1 function, and I can't seem to figure out why it's outputting the incorrect hash for whitespace, which I'm using as a test case (00100000).Any suggestions on where I've gone wrong would be much appreciated.

 ef[t_, b_, c_, d_] := 
  Which[0 <= t <= 19, (BitOr[BitAnd[b, c], BitAnd[BitNot[b], d]]), 
   20 <= t <= 39, BitXor[b, c, d], 
   40 <= t <= 59, (BitOr[BitAnd[b, c], BitAnd[b, d], BitAnd[c, d]]), 
   60 <= t <= 79, BitXor[b, c, d]];

k[t_] := Which[0 <= t <= 19, FromDigits["5a827999", 16], 
   20 <= t <= 39, FromDigits["6ed9eba1", 16], 40 <= t <= 59, 
   FromDigits["8f1bbcdc", 16], 60 <= t <= 79, 
   FromDigits["ca62c1d6", 16]];

h[t_] := Which[t == 1, FromDigits["67452301", 16], t == 2, 
   FromDigits["efcdab89", 16], t == 3, FromDigits["98badcfe", 16], 
   t == 4, FromDigits["10325476", 16], t == 5, 
   FromDigits["c3d2e1f0", 16]];

CirclePlus[x__] := Mod[Plus[x], 2^32];

sha1[msg_] := 
 Module[{pp, eta, g, ff, temp, al, v, fs, i, test, jj, list, output, 
   r, l, L, w, x, a, b, c, d, e, h1, h2, h3, h4, h5},
  r = msg;
  l = Length[r];
  L = Floor[l/512] + 1;
  AppendTo[r, Join[{1}, Table[0, {512 - (l + 65)}]]];
  AppendTo[r, IntegerDigits[l, 2, 64]];
  r = Flatten[r];
  w = Table[r[[512 i + 1 ;; 512 (i + 1)]], {i, 0, L - 1}];
  {h1, h2, h3, h4, h5} = {h[1], h[2], h[3], h[4], h[5]};
  x = Table[
    FromDigits[w[[i]][[32*j + 1 ;; 32*(j + 1)]], 2], {i, 1, L}, {j, 0,
      15}];
  Echo[x];
  For[i = 1, i <= L, i++,
   For[fs = 17, fs <= 80, fs++,
    temp = 
     RotateLeft[
      IntegerDigits[
       BitXor[x[[i, fs - 3]], x[[i, fs - 8]], x[[i, fs - 14]], 
        x[[i, fs - 16]]], 2, 32], 1];
    temp = FromDigits[temp, 2];
    AppendTo[x[[i]], temp];
    ];
   Echo[x];
   {a, b, c, d, e} = {h1, h2, h3, h4, h5};
   For[jj = 1, jj <= 80, jj++,
    Echo[a];
    a = RotateLeft[IntegerDigits[a, 2, 32], 5];
    a = FromDigits[a, 2];
    Echo[a];
    pp = ef[jj - 1, b, c, d];
    test = CirclePlus[a, pp, e, x[[i, jj]], k[jj - 1]];
    e = d;
    d = c;
    c = RotateLeft[IntegerDigits[b, 2, 32], 30];
    c = FromDigits[c, 2];
    b = a;
    a = test;
    ];

   {h1, h2, h3, h4, h5} = {h1\[CirclePlus]a, h2\[CirclePlus]b, 
     h3\[CirclePlus]c, h4\[CirclePlus]d, h5\[CirclePlus]e};
   ];
  list = {h1, h2, h3, h4, h5};
  output = 
   BitOr[2^128*list[[1]], 2^96*list[[2]], 2^64*list[[3]], 
    2^32*list[[4]], list[[5]]];
  {output, BaseForm[output, 16]}
  ]

sha1[{0,0,1,0,0,0,0,0}]

fcc7c975ba0df390bc9e7e8541498738e71be6cf

However, the actual value is

b858cb282617fb0956d960215c8e84d1ccf909c6

Any suggestions? After about 10 hours of playing with random things to see if they were the issue, I'm kind of out of ideas. Could the error be contained within ef? I tried replacing ef with the following:

ef[t_, b1_, c1_, d1_] := 
  Module[{apb, b, c, d}, {b, c, d} = 
    IntegerDigits[{b1, c1, d1}, 2, 32]; 
   apb = Which[
     0 <= t <= 19, (BitOr[BitAnd[b, c], BitAnd[BitNot[b], d]]), 
     20 <= t <= 39, BitXor[b, c, d], 
     40 <= t <= 59, (BitOr[BitAnd[b, c], BitAnd[b, d], BitAnd[c, d]]),
      60 <= t <= 79, BitXor[b, c, d]];
   FromDigits[apb, 2]];

Which changed nothing. ):

$\endgroup$
  • 1
    $\begingroup$ It would be nice if it was generalized to include SHA-2, SHA-3 and the Shaker functions. $\endgroup$ – Moo Apr 8 at 12:19
  • $\begingroup$ I'm new to writing cryptographic hash functions, give me some slack and some time, I'll get there :) $\endgroup$ – Shinaolord Apr 10 at 1:06
2
$\begingroup$

NOTE: As I discovered later, this code only functions for strings that are represented as a number of bits between 512K > s > 512K-64, for number of bits needed to represent the string s ( it may be 512K-65, I was trying adding one byte at a time during testing. For example, it works upto 440 bits, stopped at 448, began working again at 512, and this pattern repeated for each multiple of 512), for K an integer [1,2,3...]. At the end of this post I will include a link to the correct implementation for all string lengths.

Here is a correctly inmplemented code (except for note above), I was rewriting a with RotateLeft[a,5] which threw everything out of whack.

ef[t_, b_, c_, d_] := 
  Which[0 <= t <= 19, (BitOr[BitAnd[b, c], BitAnd[BitNot[b], d]]), 
   20 <= t <= 39, BitXor[b, c, d], 
   40 <= t <= 59, (BitOr[BitAnd[b, c], BitAnd[b, d], BitAnd[c, d]]), 
   60 <= t <= 79, BitXor[b, c, d]];

k[t_] := Which[0 <= t <= 19, FromDigits["5a827999", 16], 
   20 <= t <= 39, FromDigits["6ed9eba1", 16], 40 <= t <= 59, 
   FromDigits["8f1bbcdc", 16], 60 <= t <= 79, 
   FromDigits["ca62c1d6", 16]];

h[t_] := Which[t == 1, FromDigits["67452301", 16], t == 2, 
   FromDigits["efcdab89", 16], t == 3, FromDigits["98badcfe", 16], 
   t == 4, FromDigits["10325476", 16], t == 5, 
   FromDigits["c3d2e1f0", 16]];
CirclePlus[x__] := Mod[Plus[x], 2^32];

sha1[msg_] := 
 Module[{pp, eta, g, ff, temp, al, v, fs, i, test, jj, list, output, 
   r, l, L, w, x, a, b, c, d, e, h1, h2, h3, h4, h5},
  r = msg;
  l = Length[r];
  L = Floor[l/512] + 1;
  AppendTo[r, Join[{1}, Table[0, {512 - (l + 65)}]]];
  AppendTo[r, IntegerDigits[l, 2, 64]];
  r = Flatten[r];
  w = Table[r[[512 i + 1 ;; 512 (i + 1)]], {i, 0, L - 1}];
  {h1, h2, h3, h4, h5} = {h[1], h[2], h[3], h[4], h[5]};
  For[i = 1, i <= L, i++,
   Clear[x];
   x = Table[
     FromDigits[w[[i]][[32*j + 1 ;; 32*(j + 1)]], 2], {j, 0, 15}];
   For[fs = 17, fs <= 80, fs++,
    temp = 
     RotateLeft[
      IntegerDigits[
       BitXor[x[[fs - 3]], x[[fs - 8]], x[[fs - 14]], x[[fs - 16]]], 
       2, 32], 1];
    temp = FromDigits[temp, 2];
    AppendTo[x, temp];
    ];
   {a, b, c, d, e} = {h1, h2, h3, h4, h5};
   For[jj = 1, jj <= 80, jj++,
    al = RotateLeft[IntegerDigits[a, 2, 32], 5];
    al = FromDigits[al, 2];
    pp = ef[jj - 1, b, c, d];
    test = 
     al\[CirclePlus]pp\[CirclePlus]e\[CirclePlus]x[[jj]]\[CirclePlus]\
k[jj - 1];
    e = d;
    d = c;
    c = RotateLeft[IntegerDigits[b, 2, 32], 30];
    c = FromDigits[c, 2];
    b = a;
    a = test;
    ];

   {h1, h2, h3, h4, h5} = {h1\[CirclePlus]a, h2\[CirclePlus]b, 
     h3\[CirclePlus]c, h4\[CirclePlus]d, h5\[CirclePlus]e};
   ];
  list = {h1, h2, h3, h4, h5};
  output = 
   BitOr[2^128*list[[1]], 2^96*list[[2]], 2^64*list[[3]], 
    2^32*list[[4]], list[[5]]];
  output2 = IntegerDigits[Flatten[list], 2, 32];
  output2 = FromDigits[Flatten[output2], 2];
  outputa = BaseForm[output2, 16];
  {output, output2, outputa, BaseForm[output, 16]}
  ]

One that works for a string of any length is included in my answer to my own question( again), here.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.