User:Pedro Oval/Base64 HMAC MD5

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