User:Pedro Oval/Base64 HMAC MD5

From Second Life Wiki
< User:Pedro Oval
Revision as of 19:45, 15 December 2010 by Pedro Oval (talk | contribs) (Fix bug in padding when key length > hash function input length; add test vectors from RFC 2202, which include those in RFC 2104)
Jump to navigation Jump to search

MD5 core and TrimRight written by Strife Onizuka. HMAC code and modifications to Base64_MD5 by Pedro Oval. Modifications to Base64_MD5 comprise: accept base64 strings, accept an initial input state and accept an extra bitlength to consider as already added; separated into round function and padding function, to avoid the costly Base64 bitshift that would be needed otherwise. Added function HexToBase64Unpadded, written by Pedro Oval.

Best speed seen (under Mono): 0.201600 seconds.

<lsl> string HexToBase64Unpadded(string a) { 

   integer i = 0;
   integer len = llStringLength(a += "0000") - 4;
   string res = "";
   while (i < len)
   {
       res += llGetSubString(llIntegerToBase64(4*(integer)("0x" + llGetSubString(a, i, i+5))), 1, 4);
       i += 6;
   }
   return llGetSubString(res, 0, len*2/3);

}

string TrimRight(string src, string chrs)//LSLEditor Unsafe, LSO Safe { 

   integer i = llStringLength(src);
   do ; while(~llSubStringIndex(chrs, llGetSubString(src, i = ~-i, i)) && i);
   return llDeleteSubString(src, -~(i), 0x7FFFFFF0);

}

string hexc="0123456789abcdef";

list MD5_r1 = [7, 12, 17, 22]; list MD5_r2 = [5, 9, 14, 20]; list MD5_r3 = [4, 11, 16, 23]; list MD5_r4 = [6, 10, 15, 21];

list MD5_k1 = [ 

   0xd76aa478, 0xe8c7b756, 0x242070db, 0xc1bdceee, 0xf57c0faf, 0x4787c62a, 0xa8304613, 0xfd469501,
   0x698098d8, 0x8b44f7af, 0xffff5bb1, 0x895cd7be, 0x6b901122, 0xfd987193, 0xa679438e, 0x49b40821];

list MD5_k2 = [ 

   0xf61e2562, 0xc040b340, 0x265e5a51, 0xe9b6c7aa, 0xd62f105d, 0x02441453, 0xd8a1e681, 0xe7d3fbc8,
   0x21e1cde6, 0xc33707d6, 0xf4d50d87, 0x455a14ed, 0xa9e3e905, 0xfcefa3f8, 0x676f02d9, 0x8d2a4c8a];

list MD5_k3 = [ 

   0xfffa3942, 0x8771f681, 0x6d9d6122, 0xfde5380c, 0xa4beea44, 0x4bdecfa9, 0xf6bb4b60, 0xbebfbc70,
   0x289b7ec6, 0xeaa127fa, 0xd4ef3085, 0x04881d05, 0xd9d4d039, 0xe6db99e5, 0x1fa27cf8, 0xc4ac5665];

list MD5_k4 = [ 

   0xf4292244, 0x432aff97, 0xab9423a7, 0xfc93a039, 0x655b59c3, 0x8f0ccc92, 0xffeff47d, 0x85845dd1,
   0x6fa87e4f, 0xfe2ce6e0, 0xa3014314, 0x4e0811a1, 0xf7537e82, 0xbd3af235, 0x2ad7d2bb, 0xeb86d391];


list Base64MD5Round(string b64, integer H1, integer H2, integer H3, integer H4, integer i) { 

   integer A = H1;
   integer B = H2;
   integer C = H3;
   integer D = H4;
   integer round = 0;
   list x = [];
   string buf;
   integer S = 0;
   integer T;
   do
   {
       T = llBase64ToInteger(buf = llGetSubString(b64, T = ((i + round) << 4) / 3, T+6)) << (S = (((i + round) % 3) << 1));
       if(S)
           T = T | (llBase64ToInteger("A" + (llDeleteSubString(buf, 0, 1))) >> (6 - S));
       x += (T = ((T << 24) | ((T & 0xFF00) << 8) | ((T >> 8) & 0xFF00) | ((T >> 24) & 0xFF)));

       S = A + llList2Integer(MD5_k1, round) + T + (D ^ (B & (C ^ D)));
       T = llList2Integer(MD5_r1, round & 3);
       A = D;
       D = C;
       C = B;
       B += (S << T) | ((S >> (32 - T)) & ~(0xFFFFFFFF << T));
   }
   while(16 > (round = -~round));
   do
   {
       S = A + llList2Integer(MD5_k2, round & 15) + (C ^ (D & (B ^ C))) + llList2Integer(x, (-~(5 * round)) & 15);
       T = llList2Integer(MD5_r2, round & 3);
       A = D;
       D = C;
       C = B;
       B += (S << T) | ((S >> (32 - T)) & ~(0xFFFFFFFF << T));
   }
   while(32 > (round = -~round));
   do
   {
       S = A + llList2Integer(MD5_k3, round & 15) + (B ^ C ^ D) + llList2Integer(x, (3 * round + 5) & 15);
       T = llList2Integer(MD5_r3, round & 3);
       A = D;
       D = C;
       C = B;
       B += (S << T) | ((S >> (32 - T)) & ~(0xFFFFFFFF << T));
   }
   while(48 > (round = -~round));
   do
   {
       S = A + llList2Integer(MD5_k4, round & 15) + (C ^ (B | (~D))) + llList2Integer(x, (7 * round) & 15);
       T = llList2Integer(MD5_r4, round & 3);
       A = D;
       D = C;
       C = B;
       B += (S << T) | ((S >> (32 - T)) & ~(0xFFFFFFFF << T));
   }
   while(64 > (round = -~round));

// llOwnerSay(llList2CSV(x)); 

   H1 += A;
   H2 += B;
   H3 += C;
   H4 += D;

   return [H1, H2, H3, H4];

}


string Base64MD5forHMAC(string b64, integer bit_length, integer extra_bit_length, integer H1, integer H2, integer H3, integer H4) { 

   //OR on the extra bit.
   integer b = (~-(((bit_length + 552) & -512) >> 5));
   integer T = llBase64ToInteger(TrimRight(llGetSubString(b64, -4, -1),"=") + "AAAA");
   string buf = "AAA";
   integer i = -5;
   do buf += buf; while((i = -~i));
   if(bit_length)
   {
       i = 0x800000;
       if(T & 0xFF00)
           i = 0x80;
       else if(T & 0xFF0000)
           i = 0x8000;
   }
   else
       T = 0x80000000;//T is corrupt because of https://jira.secondlife.com/browse/SVC-104

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

   bit_length += extra_bit_length;
   b64 = llGetSubString( llDeleteSubString(b64, -4, -1) + 
                         llGetSubString(llIntegerToBase64(T | i), 0, 5) + 
                         buf, 0, ((b << 4) / 3) - 7) + 
         llGetSubString(llIntegerToBase64((((bit_length & 0xFF) << 20) | ((bit_length & 0xFF00) << 4) | ((bit_length >> 12) & 0xFF0) | ((bit_length >> 28) & 0xF)) >> ((b % 3) << 1)), 0, 5) + 
           "AAAAAAAA";
   i = 0;
   list x;
   do
   {
       x = Base64MD5Round(b64, H1, H2, H3, H4, i);
       H1 = llList2Integer(x, 0);
       H2 = llList2Integer(x, 1);
       H3 = llList2Integer(x, 2);
       H4 = llList2Integer(x, 3);
   }while(b > (i += 16));
   x = [H4, H3, H2, H1];
   i = -4;
   buf = "";
   do
   {
       T = llList2Integer(x,i);
       bit_length = 32;
       do
           buf = llGetSubString(hexc, b = ((T >> (bit_length - 4)) & 0xF), b) + llGetSubString(hexc, b = ((T >> (bit_length - 8)) & 0xF), b) + buf;
       while ((bit_length -= 8));
   }while ((i = -~i));
   return buf;

}


// The Real Thing string Base64_HMAC_MD5(string B64Key, string B64Data) { 

   integer bit_length = llSubStringIndex(B64Key, "=");
   if (!~bit_length)
   {
       bit_length = llStringLength(B64Key);
   }
   if (bit_length > 86)
   {
       B64Key = HexToBase64Unpadded(Base64MD5forHMAC(B64Key, (bit_length*6)&-8, 0, 1732584193, -271733879, -1732584194, 271733878));
       bit_length = 22;
   }
   B64Key = llGetSubString(B64Key, 0, bit_length-1);
   string buf = "AAA";
   integer i = -5;
   do buf += buf; while((i = -~i));
   B64Key = llXorBase64StringsCorrect(llGetSubString(B64Key + buf, 0, 85) + "==", "NjY2NjY2NjY2NjY2NjY2NjY2NjY2NjY2NjY2NjY2NjY2NjY2NjY2NjY2NjY2NjY2NjY2NjY2NjY2NjY2NjY2Ng==");

   list x = Base64MD5Round(B64Key, 1732584193, -271733879, -1732584194, 271733878, 0);
   bit_length = (6 * !(B64Data=="") * (llStringLength(B64Data)-4+llStringLength(TrimRight(llGetSubString(B64Data,-4,-1), "=")))) & -8;
   B64Data = HexToBase64Unpadded(Base64MD5forHMAC(B64Data, bit_length, 512, llList2Integer(x, 0), llList2Integer(x, 1), llList2Integer(x, 2), llList2Integer(x, 3))) + "==";

   // Xor with Base64(chr(0x36 xor 0x5C) * 64)
   B64Key = llXorBase64StringsCorrect(B64Key, "ampqampqampqampqampqampqampqampqampqampqampqampqampqampqampqampqampqampqampqampqampqag==");
   x = Base64MD5Round(B64Key, 1732584193, -271733879, -1732584194, 271733878, 0);
   bit_length = 128;
   return Base64MD5forHMAC(B64Data, bit_length, 512, llList2Integer(x, 0), llList2Integer(x, 1), llList2Integer(x, 2), llList2Integer(x, 3));

}


test_vector_MD5(string B64Key, string B64Data, string HexHash) { 

   llResetTime();
   string hmac = Base64_HMAC_MD5(B64Key, B64Data);
   if (hmac != HexHash)
   {
       llOwnerSay("HMAC failed.\nComputed: " + hmac + "\nExpected : " + HexHash);
   }
   else
   {
       llOwnerSay("HMAC passed in " + (string)llGetTime() + " seconds.");
   }

}

default { 

   state_entry()
   {
       // RFC 2202 test vectors:
       test_vector_MD5(HexToBase64Unpadded("0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b") + "==",
                       llStringToBase64("Hi There"),
                       "9294727a3638bb1c13f48ef8158bfc9d");
       test_vector_MD5(llStringToBase64("Jefe"),
                       llStringToBase64("what do ya want for nothing?"),
                       "750c783e6ab0b503eaa86e310a5db738");
       test_vector_MD5("qqqqqqqqqqqqqqqqqqqqqg==",
                       "3d3d3d3d3d3d3d3d3d3d3d3d3d3d3d3d3d3d3d3d3d3d3d3d3d3d3d3d3d3d3d3d3d0=",
                       "56be34521d144c88dbb8c733f0e8b3f6");
       test_vector_MD5(HexToBase64Unpadded("0102030405060708090a0b0c0d0e0f10111213141516171819")+"==",
                       HexToBase64Unpadded("cdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcd")+"=",
                       "697eaf0aca3a3aea3a75164746ffaa79");
       test_vector_MD5(HexToBase64Unpadded("0c0c0c0c0c0c0c0c0c0c0c0c0c0c0c0c") + "==",
                       llStringToBase64("Test With Truncation"),
                       "56461ef2342edc00f9bab995690efd4c");

       string buf = "aaaaa";
       buf += buf;
       buf += buf;
       buf += buf;
       buf += buf;
       buf += buf;
       test_vector_MD5(HexToBase64Unpadded(buf) + "=",
                       llStringToBase64("Test Using Larger Than Block-Size Key - Hash Key First"),
                       "6b1ab7fe4bd7bf8f0b62e6ce61b9d0cd");
       test_vector_MD5(HexToBase64Unpadded(buf) + "=",
                       llStringToBase64("Test Using Larger Than Block-Size Key and Larger Than One Block-Size Data"),
                       "6f630fad67cda0ee1fb1f562db3aa53e");
   }

} </lsl>

Retrieved from "https://wiki.secondlife.com/w/index.php?title=User:Pedro_Oval/Base64_HMAC_MD5&oldid=1128562"