User:Pedro Oval/Base64 HMAC MD5

From Second Life Wiki
< User:Pedro Oval
Revision as of 04:40, 16 December 2010 by Pedro Oval (talk | contribs) (Reorganize the summary of changes. Add the bugfix note. Add empty string test vector. Add more timings.)
Jump to navigation Jump to search

MD5 core and TrimRight written by Strife Onizuka. HMAC calculation function, test vectors function and testcases, and modifications to Base64_MD5 made by Pedro Oval. Also, added function HexToBase64Unpadded, written by Pedro Oval. Modifications to Base64_MD5 comprise:

  • Accept base64 strings.
  • Accept an initial input state.
  • Accept an extra bitlength to consider as already added.
  • Separated into compression function and padding function, to avoid the costly Base64 bitshift that would be needed otherwise.
  • Renamed globals to minimize the risk of a collision with usercode.
  • Fixed bug with data ending in zeros.

Best speed seen under Mono: 0.201365 seconds for test case 15; worst: 0.495030 for test case 5. Best speed seen under LSO : 5.698544 seconds for test case 19; worst: 13.351786 seconds for test case 7.

<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 Base64MD5Compress(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(!(bit_length % 24))
           i = 0x80;
       else if((bit_length % 24) == 16)
           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 = Base64MD5Compress(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 = Base64MD5Compress(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 = Base64MD5Compress(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");

       // Test vectors added by the author for zero-terminated data strings at different padding positions
       // (generated with an independent program written in PHP):
       test_vector_MD5("blah", "", "c10685c0953708077f6f4c7c5511ae53"); // ""
       test_vector_MD5("blah", "AA==", "a761432a72606fd467aee08dd354d055"); // "\0"
       test_vector_MD5("blah", "AAA=", "7ec1859fa4f3dc93557de5b6e0e6b579"); // "\0\0"
       test_vector_MD5("blah", "AAAA", "daa25eabf94b653324a7d014bacf93ce"); // "\0\0\0"
       test_vector_MD5("blah", "MQA=", "ed3a85846a50c499d0eee5789eb32f4d"); // "1\0"
       test_vector_MD5("blah", "MQAA", "df9ebb2a9194f1ccc005016cd7b8d2c2"); // "1\0\0"
       test_vector_MD5("blah", "MQAAAA==", "84106dafe40539b5b7d680cc05ee5836"); // "1\0\0\0"
       test_vector_MD5("blah", "MTIA",     "a2aaec505f58dc3267f39b7c1ad130ba"); // "12\0"
       test_vector_MD5("blah", "MTIAAA==", "24b9ea69f29389136386c06632a0e4c2"); // "12\0\0"
       test_vector_MD5("blah", "MTIAAAA=", "dbf936625759ada5eacc7f88f66ff20e"); // "12\0\0\0"
       test_vector_MD5("blah", "MTIzAA==", "8f2b761ddcf87a60593bde245691b409"); // "123\0"
       test_vector_MD5("blah", "MTIzAAA=", "9c196ba2c2dc1fa610800fd026e3f405"); // "123\0\0"
       test_vector_MD5("blah", "MTIzAAAA", "a0331f1846fa6937347e62ec7414ee43"); // "123\0\0\0"
       llOwnerSay("End of tests.");
   }

} </lsl>

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