User:Pedro Oval/Base64 HMAC MD5

From Second Life Wiki
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.

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 vector added by the author
        test_vector_MD5("", "", "74e6f7298a9c2d168935f58c001bad88");

        // 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.");
    }
}