Talk:SHA-1

From Second Life Wiki
Jump to: navigation, search

Xaviar Czervik's Code?

I - Xaviar Czervik - wrote code for this function and it is no longer here. The function was originally written by me but everything has been replaced. It is even now Copyright Strife Onizuka. I'm not against this - as I'm sure Strife is a better coder than I am - I'd just like to know what happened to my code... Xaviar Czervik 10:18, 22 October 2007 (PDT)

I wracked my brains about your code for a long while before doing it.did it for several reasons:
  • It's slow and uses a lot of memory, converting the entire string into a list isn't a good idea.
  • The original version could only handle ASCII-7 text.
  • A version using UTF8ToUnicodeInteger fail on any Unicode character greater then 0x7FFF (since you didn't do a complete implementation of UTF-16).
  • LSL doesn't use UTF-16, it uses UTF-8; its logical to have a UTF-8 implementation.
  • The license link (FDL) didn't match the license granted (GPL).
  • A GPLed hashing library isn't useful. Anything that depends upon it becomes infected by the GPL. You couldn't use it with products you gave away.
  • The GPL is not compatible with the wiki license and LL has said they will only honor the wiki license.
  • The LGPL is compatible with the wiki CC-BY license.
I wanted to keep your name on the code but that presented a license issue. You wrote it almost verbatim from the pseudo-code from Wikipedia, except for the integer-list code. By the time I had rewritten it, it had none of your hallmarks, and only shared bits in common with the Wikipedia articles pseudo-code. Speaking of which I should put that in the header. -- Strife Onizuka 19:13, 24 October 2007 (PDT)
Okay - that's fine with me, I noticed that yours was very different (not to mention much better). Although, I didn't look at the Wikipedia pseudo-code, I was looking at a Java version of the code and trying to get it to work in LSL ;P. Xaviar Czervik 15:27, 25 October 2007 (PDT)

Bug in UTF8_SHA1

UTF8_SHA1 won't process correctly strings containing non-ASCII characters. The problem is in this code: <lsl>

   integer j = llStringLength(plain) << 3;

</lsl> That sets j to the number of characters in the string, not to the number of UTF-8 bytes, causing the SHA-1 to be computed over a reduced string, not the complete one, when it contains non-ASCII chars. Not that important now that we have llSHA1String, though, but it would be nice to either fix it or remove UTF8_SHA1 completely. -- Pedro Oval 16:01, 7 December 2010 (UTC)

You are correct about there being a problem. Thanks for pointing it out. Upon review, all of my hashing functions are effected by this bug. You should be able to substitute the following code into all of them. I haven't tested it but it looks correct. Please let me know if it works or doesn't work.

<lsl>

   //OR on the extra bit.
   integer T = llBase64ToInteger(llGetSubString((TrimRight(llGetSubString(plain = llStringToBase64(plain), -4, -1),"=")) + "AAAAAAAA", 0, 7));
   string buf = "AAA";
   integer i = -5;
   do buf += buf; while((i = -~i));
   if(T)
   {
       if(T & 0xFF0000)
           i = 8;
       else if(T & 0xFF000000)
           i = 16;
       T = T | (0x80 << i);
   }
   else//nothing to append to
       T = 0x80000000;
   integer j = (llStringLength(plain) << 6) - i;// only accurate to the byte.
   integer b = (~-(((j + 552) & -512) >> 5));//I'm assuming this still works.

// llOwnerSay(llList2CSV([i,j]));

   plain = llGetSubString( llDeleteSubString(plain, -4, -1) + 
                           llGetSubString(llIntegerToBase64(T), 0, 5) + 

</lsl> -- Strife (talk|contribs) 19:33, 7 December 2010 (UTC)

That one didn't work for me. This patch does:

<diff>--- 1.txt 2010-12-10 20:57:18.000000000 +0100 +++ 2.txt 2010-12-10 21:08:26.000000000 +0100 @@ -59,9 +59,15 @@

    integer H5 = 0xc3d2e1f0;
    //OR on the extra bit.

- integer j = llStringLength(plain) << 3; + plain = (plain = "") + llStringToBase64(plain); + integer j = llStringLength(plain); + if (j) + { + do ; while (llGetSubString(plain, --j, j) == "="); + j = (integer)((-~j) * 0.75) << 3; + }

    integer b = (~-(((j + 552) & -512) >> 5));

- integer T = llBase64ToInteger(llGetSubString((TrimRight(llGetSubString(plain = llStringToBase64(plain), -4, -1),"=")) + "AAAAAAAA", 0, 7)); + integer T = llBase64ToInteger(llGetSubString((TrimRight(llGetSubString(plain, -4, -1),"=")) + "AAAAAAAA", 0, 7));

    string buf = "AAA";
    integer i = -5;
    do buf += buf; while((i = -~i));

</diff>

My tests were done with:

<lsl> string s = "Étude¿º";

 string s1 = UTF8_SHA1(s);
 string s2 = llToUpper(llSHA1String(s));
 llOwnerSay("\n" + s1 + "\n" + s2 + "\n" + (string)(s1 == s2));</lsl>
-- Pedro Oval 20:24, 10 December 2010 (UTC)
(Edited to make a minor change to the patch and fix formatting problems) -- Pedro Oval 00:45, 11 December 2010 (UTC)
I was under the impression that there were some edge cases that would cause it to fail in this situation. If that is indeed all that is required then the following should work:

<lsl>

   integer j = llStringLength(plain = llStringToBase64(plain));
   string buf = TrimRight(llGetSubString(plain, -4, -1),"=");
   integer T = llBase64ToInteger(llGetSubString(buf + "AAAAAAAA", 0, 7));
   integer b = ((((j + llStringLength(buf)) * 3) + 8) >> 4) | 15;
   buf = "AAA";

</lsl>

The thing is, you should be able to use the code that positions the trailing 0x80 to figure out the real length. You shouldn't have to read the number of trailing "=" but maybe the TrimRight should be inlined and the 0x80 positioning code abandoned. hmmm.
--Strife (talk|contribs) 05:26, 11 December 2010 (UTC)
(Edited to simplify code, your use of float math is interesting, I will have to think about using it in the future.) -- Strife (talk|contribs) 05:56, 11 December 2010 (UTC)
(Edited to simplify code more, I'm truly appalled at how well it simplified.) -- Strife (talk|contribs) 06:13, 11 December 2010 (UTC)
I'm not sure if this is the patch you propose. If it is, then it still doesn't work.

<diff>--- 1.txt 2010-12-10 20:57:18.000000000 +0100 +++ 2.txt 2010-12-11 19:35:50.000000000 +0100 @@ -59,10 +59,11 @@

    integer H5 = 0xc3d2e1f0;
    //OR on the extra bit.

- integer j = llStringLength(plain) << 3; - integer b = (~-(((j + 552) & -512) >> 5)); - integer T = llBase64ToInteger(llGetSubString((TrimRight(llGetSubString(plain = llStringToBase64(plain), -4, -1),"=")) + "AAAAAAAA", 0, 7)); - string buf = "AAA"; + integer j = llStringLength(plain = llStringToBase64(plain)); + string buf = TrimRight(llGetSubString(plain, -4, -1),"="); + integer T = llBase64ToInteger(llGetSubString(buf + "AAAAAAAA", 0, 7)); + integer b = ((((j + llStringLength(buf)) * 3) + 8) >> 4) | 15; + buf = "AAA";

    integer i = -5;
    do buf += buf; while((i = -~i));
    if(j)</diff>
I'd vote for removing UTF8_SHA1. It makes no sense to duplicate the functionality of an existing LSL function, and it kind of distracts attention from the presence of the useful Base64_SHA1. Of course the problem should still be fixed in UTF8_SHA_256 etc. -- Pedro Oval 18:57, 11 December 2010 (UTC)
Well. We could always hope that the user function can be made to not truncate the sections of character values that the LL version does (for use in HMAC-SHA1), but I have no clue if that's even possible. -- Faust(T|C) 19:31, 11 December 2010 (UTC)
It isn't. LSL strings simply can't have zeros. That's precisely why the Base64 form is useful. And, by the way, an HMAC-SHA1 function based on Base64_SHA1 would be a nice addition to this page. -- Pedro Oval 00:25, 12 December 2010 (UTC)
~_~ I made the bad assumption that I wasn't needing the value of j later. -- Strife (talk|contribs) 06:28, 12 December 2010 (UTC)

I've released a new version that works, I've tested it (finally got around to setting up my build environment on this computer). The new code works in everything but MD4(too tired to work that one out). -- Strife (talk|contribs) 09:27, 12 December 2010 (UTC)

Thanks! The other hashing functions need fixing as well. I'll try to work on an HMAC for each, but I can't promise that will happen soon. There's the handicap of SVC-6548 disturbing. -- Pedro Oval 12:25, 12 December 2010 (UTC)
It does work with MD4 but I needed to tweak the build config for MD4 to get it to work. -- Strife (talk|contribs) 06:18, 13 December 2010 (UTC)
Finally got to implement the first HMAC function (Base64 HMAC-MD5) and it turned out to be a real pain. Suggestions welcome. This is probably not the best place to announce an HMAC for a different hash function, sorry for that, but I prefer to postpone the creation of the HMAC page until it can be considered stable. -- Pedro Oval 01:11, 16 December 2010 (UTC)
I've posted a few thoughts on it's talk page. Looks good. -- Strife (talk|contribs) 22:11, 16 December 2010 (UTC)