User:Pedro Oval/Base64 HMAC MD5
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.");
}
}