User:Pedro Oval/Base64 HMAC MD5

From Second Life Wiki
< User:Pedro Oval
Revision as of 11:20, 6 March 2011 by Pedro Oval (talk | contribs) (Small optimization)
Jump to navigation Jump to search

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

  • Accept base64 strings instead of plain text 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.

All test cases pass with both LSO and Mono.

<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 RemovePadding(string b64) // specialized - it won't work if the string consists of all "=" { 

   integer i;
   do ; while(llGetSubString(b64, i = ~-i, i) == "=");
   return llGetSubString(b64, 0, i);

}

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)); 

   return [H1+A, H2+B, H3+C, H4+D];

}


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(RemovePadding(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));
   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(RemovePadding(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-MD5 test failed.\nComputed: " + hmac + "\nExpected : " + HexHash);
   }
   else
   {
       llOwnerSay("HMAC-MD5 test 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"

       // Test vectors added by the author to check for corner cases with the padding.
       // Buffer exactly 54 bytes; needs 1+1 padding bytes, this should not be a problem.
       test_vector_MD5("blah",
                       "012345670123456701234567012345670123456701234567012345670123",
                       "ed5accadc5138ea952d2cb519406f928");
       // Buffer exactly 55 bytes; needs 1+0 padding bytes, this might be a problem if adding 0 bytes is a problem.
       test_vector_MD5("blah",
                       "0123456701234567012345670123456701234567012345670123456701234A==",
                       "123d6892faec7f8d30844711b32be334");
       // Buffer exactly 56 bytes; needs 1+7+56 padding bytes. Problematic only in case the detection of the corner case is flawed.
       test_vector_MD5("blah",
                       "01234567012345670123456701234567012345670123456701234567012345A=",
                       "1651d80e8892463daa9aca2d0a9a2f76");
       // Buffer exactly 63 bytes; needs 1+56 padding bytes. The first byte must be appended to the end of the buffer; the rest in the next buffer.
       test_vector_MD5("blah",
                       "012345670123456701234567012345670123456701234567012345670123456701234567012345670123",
                       "3eb5654edd27e2441e7a521827ff6a77");
       // Buffer exactly 64 bytes; needs 1+55 padding bytes added to the next buffer. Should not be a problem.
       test_vector_MD5("blah",
                       "0123456701234567012345670123456701234567012345670123456701234567012345670123456701234A==",
                       "25fd54c13d95468e2f525163d7b6d63d");
       llOwnerSay("End of tests.");
   }

} </lsl>

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