Defcon Quals writeup for byhd (reversing a Huffman Tree)

This is my writeup for byhd, a 2-point challenge from the Defcon Qualifier CTF. You can get the files, including my annotated assembly file, here. This is my second (and final) writeup for the Defcon Qualifiers, you can find the writeup for shitsco here.

This was a reverse engineering challenge where code would be constructed based on your input, then executed. You had to figure out the exact right input to generate a payload that would give you access to the server (so, in a way, there was some exploitation involved).

Up till now, cnot from PlaidCTF has probably been my favourite hardcore reversing level, but I think this level has taken over. It was super fun!

The setup

When you fire up byhd, it listens on port 9730 and waits for connections:

$ strace ./byhd
bind(3, {sa_family=AF_INET, sin_port=htons(9730), sin_addr=inet_addr("")}, 16) = 0
listen(3, 20)                           = 0

When you connect, it forks off a new process, and therefore we have to fix it as described in an old post I wrote to ensure everything stays in one process (otherwise, you're gonna have a Bad Time). You also have to add a user and group and such, and you may need to run it as root.

After I fix that, it reads from the socket properly! But when I send data to it, it just disconnects me:

$ nc 9730 | hexdump -C
00000000  ff ff ff ff                                       |....|

Because it's so, so common in protocols, I tried to prefix a 4-byte length to my string:

$ echo -ne '\x04\x00\x00\x00\x41\x41\x41\x41' | nc -vv 9730 inverse host lookup failed:
(UNKNOWN) [] 9730 (?) open
 sent 8, rcvd 0

No response this time? On the server side, we can see why:

# ./byhd-fixed
Segmentation fault

The crash is really weird, too:

# gdb -q ./byhd-fixed
(gdb) run

Program received signal SIGBUS, Bus error.
0x0000000000401cc1 in ?? ()
(gdb) x/i $rip
=> 0x401cc1:    call   0x4010b0 <munmap@plt>

SIGBUS at a call? Wat? Instead of AAAA, let's send it \0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0:

$ echo -ne '\x10\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00' | nc -vv 9730

Which results in:

(gdb) run

Program received signal SIGSEGV, Segmentation fault.
0x00007ffff7ff9000 in ?? ()
(gdb) x/8i $rip
=> 0x7ffff7ff9000:      push   rax
   0x7ffff7ff9001:      nop
   0x7ffff7ff9002:      push   rdi
   0x7ffff7ff9004:      (bad)
   0x7ffff7ff9005:      jg     0x7ffff7ff9007
   0x7ffff7ff9007:      add    dh,bl
   0x7ffff7ff9009:      fs
   0x7ffff7ff900a:      fcomip st,st(7)

(gdb) x/32xb $rip
0x7ffff7ff9000: 0x50    0x90    0xff    0xf7    0xff    0x7f    0x00    0x00
0x7ffff7ff9008: 0xde    0x64    0xdf    0xf7    0xff    0x7f    0x00    0x00
0x7ffff7ff9010: 0x00    0x00    0x00    0x00    0x00    0x00    0x00    0x00
0x7ffff7ff9018: 0xc0    0x53    0xdf    0xf7    0xff    0x7f    0x00    0x00

I don't know what's going on, but that sure doesn't look like code it's trying to run!

That's enough of messing around, we're gonna have to do a deep dive to figure out what's happening...

Reading itself

After it forks off a thread, and before it reads anything from the socket, the process opens itself and reads all the bytes:

# strace ./byhd-fixed
execve("./byhd-fixed", ["./byhd-fixed"], [/* 21 vars */]) = 0
brk(0)                                  = 0x1d66000
bind(3, {sa_family=AF_INET, sin_port=htons(9730), sin_addr=inet_addr("")}, 16) = 0
listen(3, 20)                           = 0
accept(3, {sa_family=AF_INET, sin_port=htons(39624), sin_addr=inet_addr("")}, [16]) = 4
chdir("/home/byhd")                     = 0
stat("./byhd-fixed", {st_mode=S_IFREG|0755, st_size=18896, ...}) = 0
open("./byhd-fixed", O_RDONLY)          = 3
read(3, "\177ELF\2\1\1\0\0\0\0\0\0\0\0\0\2\0>\0\1\0\0\0\220\21@\0\0\0\0\0"..., 18896) = 18896
close(3)                                = 0

That's interesting! First it accepts a connection, then it gets the size of itself, opens itself, and reads the whole thing. Then, finally, it tries to read from the socket it opened.

My first hunch was that it's some anti-tampering code, which isn't 100% wrong (nor was it 100% right). I threw together a quick wrapper in C to fix things:

#include <unistd.h>

int main(int argc, const char *argv[])
  execlp("/home/byhd/byhd-fixed", "/home/byhd/byhd", NULL);

  printf("Fail :(\n");
  return 0;

Note that I'm running "/home/byhd/fixed/byhd", but setting argv[0] to "/home/byhd/byhd". You can verify with strace that it indeed opens the 'real' executable and not the modified one:

# strace ./wrapper
execve("./wrapper", ["./wrapper"], [/* 21 vars */]) = 0
execve("/home/byhd/byhd-fixed", ["/home/byhd/byhd"], [/* 21 vars */]) = 0
brk(0)                                  = 0x2007000
chdir("/home/byhd")                     = 0
stat("/home/byhd/byhd", {st_mode=S_IFREG|0644, st_size=18896, ...}) = 0
open("/home/byhd/byhd", O_RDONLY)       = 3
read(3, "\177ELF\2\1\1\0\0\0\0\0\0\0\0\0\2\0>\0\1\0\0\0\220\21@\0\0\0\0\0"..., 18896) = 18896
close(3)                                = 0
read(4, "\20\0\0\0", 4)                 = 4
read(4, "\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0", 16) = 16
--- SIGSEGV (Segmentation fault) @ 0 (0) ---
+++ killed by SIGSEGV +++
Segmentation fault (core dumped)


For the next little while, I jumped around quite a bit because I wasn't sure exactly what I was trying to do. I eventually decided to start from the top; that is, the code that runs right after it reads the file.

Before I explain what's happening, let's take a look at some assembly! If you're interested in the actual code, have a look at this; otherwise, just skip past to the description. I re-implemented this in a few lines of Ruby.

Note that I've removed a bunch of in-between code, including register movement and error handling, to just show the useful parts:

; The function definition
.text:0040173B ; int __cdecl generate_histogram(char *itself, size_t length)

; Allocate 0x400 bytes
.text:0040175F                 mov     edi, 400h       ; size
.text:00401764                 call    _malloc         ; Allocate 0x400 bytes
.text:00401769                 mov     [rbp+allocated], rax

; In this loop, ebx is the loop counter
.text:0040178C top_loop:                               ; CODE XREF: generate_histogram+7Cj

; Point 'rax' to the current byte (the string plus the index)
.text:0040178C                 mov     edx, ebx        ; edx = current iteration
.text:0040178E                 mov     rax, [rbp+itself]
.text:00401792                 add     rax, rdx        ; Go to the current offset in the file

; Read the current byte
.text:00401795                 movzx   eax, byte ptr [rax] ; Read the current byte

; Multiply it by 4
.text:0040179B                 lea     rdx, [rax*4+0]  ; rdx = current_byte * 4

; Set rax to that index in the array
.text:004017A3                 mov     rax, [rbp+allocated] ; rax = allocated buffer
.text:004017A7                 add     rax, rdx        ; Go to that offset

; Increment the index
.text:004017AA                 mov     edx, [rax]
.text:004017AC                 add     edx, 1
.text:004017AF                 mov     [rax], edx      ; Increment that offset

; Increment the loop counter
.text:004017B1                 add     ebx, 1
.text:004017B4 bottom_loop:                            ; CODE XREF: generate_histogram+4Fj

; Loop till we're at the end, then return
.text:004017B4                 cmp     ebx, [rbp+itself_length]
.text:004017B7                 jb      short top_loop
.text:004017C9                 retn

It turns out, the code generates a histogram based on the executable file. In other words, it basically does this:

data =[0]).read

histogram = {}
histogram.default = 0

data.each_byte() do |b|
  histogram[b.chr] = histogram[b.chr] + 1

Which might look like:

$ ruby histogram.rb /etc/passwd
{"r"=>73, "o"=>119, "t"=>54, ":"=>204, "x"=>38, "0"=>39, "/"=>141, "b"=>78, "i"=>80, "n"=>107, "a"=>105, "s"=>78, "h"=>22, "\n"=>34, "1"=>41, "f"=>27, "l"=>71, "e"=>85, "d"=>81, "m"=>35, "2"=>18, "3"=>16, "4"=>13, "v"=>21, "p"=>58, "7"=>3, "y"=>31, "c"=>13, "5"=>12, "u"=>33, "w"=>9, "6"=>10, "9"=>3, "g"=>39, " "=>68, "8"=>6, "+"=>2, "q"=>2, "k"=>7, "z"=>4, "-"=>1}

Running that code on the actual binary, it works great; but it's a lot longer and much uglier output, so I didn't want to include it here. Feel free to try :)

I was still working off the assumption this was all anti-tampering code. As I said earlier, that was only partly right...

Building a tree

This is where it started to get weird and interesting. I could understand the histogram being generated, but then it stated adding and removing stuff from the array! What was happening!?

Once again, here's the actual annotated code, with the error handling and stuff removed. Feel free to read or skip it!

.text:00402127 enter_second_loop:                      ; CODE XREF: generate_block_tree+2AFj

; Remove and store the smallest entry
.text:00402127                 mov     rax, [rbp+entry_list] ; An array of 256 8-byte values, each of which points to 20 bytes of allocated memory
.text:0040212B                 mov     rdi, rax        ; allocated_block
.text:0040212E                 call    get_smallest_entry ; Removes the smallest histogram entry from the list and returns it
.text:00402133                 mov     [rbp+smallest_entry], rax

; Remove and store the next smallest entry
.text:00402137                 mov     rax, [rbp+entry_list] ; An array of 256 8-byte values, each of which points to 20 bytes of allocated memory
.text:0040213B                 mov     rdi, rax        ; allocated_block
.text:0040213E                 call    get_smallest_entry ; Removes the smallest histogram entry from the list and returns it
.text:00402143                 mov     [rbp+next_smallest_entry], rax

; Allocate memory for a new entry
.text:00402165                 mov     edi, 20h        ; size
.text:0040216A                 call    _malloc         ; Allocate space for a new entry
.text:0040216F                 mov     [rbp+new_entry], rax

; Store the smallest entry in the 'left' branch
.text:004021B2                 mov     rax, [rbp+new_entry]
.text:004021B6                 mov     rdx, [rbp+smallest_entry]
.text:004021BA                 mov     [rax+entry_struct.left_histogram], rdx

; Store the next-smallest entry in the 'right' branch
.text:004021BD                 mov     rax, [rbp+new_entry]
.text:004021C1                 mov     rdx, [rbp+next_smallest_entry]
.text:004021C5                 mov     [rax+entry_struct.right_histogram], rdx

; Get the sum of the two entry values (the character counts, if they're leaf nodes)
.text:004021E2                 mov     rax, [rbp+smallest_entry] ; ** This section puts the two smallest histograms into a new field, then puts their sum into the 'value' entry
.text:004021E6                 mov     edx, [rax+entry_struct.histogram_entry]
.text:004021E9                 mov     rax, [rbp+next_smallest_entry]
.text:004021ED                 mov     eax, [rax+entry_struct.histogram_entry]
.text:004021F0                 add     edx, eax

; Store the sum of the two child nodes in the new node's entry
.text:004021F2                 mov     rax, [rbp+new_entry]
.text:004021F6                 mov     [rax+entry_struct.histogram_entry], edx

; Store the new node at the end of the list
.text:00402201                 mov     rsi, rdx        ; new_entry
.text:00402204                 mov     rdi, rax        ; entry_list
.text:00402207                 call    add_entry_to_end_maybe

What I could see in the code is that it removed the two smallest entries, created a new entry that points to them, and put it at the end of the list. Then it would loop until there was only one entry. Typing it like that makes it sound really obvious to me, but digging through the code was remarkably difficult. In fact, it took me a long, long time to realize that it was removing the smallest entries and adding a new entry. I totally misunderstood the code...

Anyway, let's look at an example: you have the string 'eebddaafbcdfdbaee'. The histogram looks like:

{"a"=>3, "b"=>3, "c"=>1, "d"=>4, "e"=>4, "f"=>2}

We'll re-write it, for simplicity, like this:

a[3]  b[3]  c[1]  d[4]  e[4]  f[2]

First, it removes the smallest two entries from the list, c[1] and f[2]:

a[3]  b[3]  d[4]  e[4]

And replaces them with another node that contains their combined value, with the two removed values underneath:

a[3]  b[3]  d[4]  e[4]  [3]
                        / \
                     c[1] f[2]

Then the next two smallest values are removed and combined under a single parent:

d[4]  e[4]  [3]       [6]
            / \       / \
         c[1] f[2] a[3] b[3]

Then remove the smallest two again. This step is interesting because one of the smallest nodes is a non-leaf:

e[4]   [6]
       / \
    a[3] b[3]

Add them back under a common node at the end:

e[4]   [6]       [7]
       / \       / \
    a[3] b[3]  [3] d[4]
               / \
             c[1] f[2]

Then the [4] and [6] are similarly combined:

     [10]         [7]
     /  \         / \
  e[4]  [6]     [3] d[4]
        / \       / \
     a[3] b[3]  c[1] f[2]

And finally, we only have a single parent node:

          /     \
     [10]         [7]
     /  \         / \
  e[4]  [6]     [3] d[4]
        / \      /    \
     a[3] b[3] c[1]   f[2]

And there you have it! A tree!

It's really funny: when I was working on this, I had the feeling at the back of my mind that this was a real tree algorithm, but I read a bunch on Wikipedia and couldn't find one that matched, so I gave up and just continued. Today, my co-worker mentioned "oh, like Huffman encoding!" and I said "nah, there's no compression involved".

But, as soon as I built that tree by hand, I realized that this absolutely IS a Huffman Tree! And checking Wikipedia, I can confirm that it is. That would have made the last part a whole lot easier...

Using the incoming data

Now, what's going on with the data I send in? I already confirmed that it's a 4-byte length value followed by some code, and the program crashes in different and creative ways depending on what code I send it. Now what?

If I'd recognized the Huffman Tree, I could have made a pretty good guess: that we're sending huffman-compressed data. And it would have been right, too! Unfortunately, I missed the obvious hints...

Anyway, I don't really want to dwell too much on this part, since it's conceptually really simple. There was a loop that would go through the data string you sent it, and touch each byte you sent 8 times. Hmm. Then there was some bitwise arithmetic that would do some shifting and ANDing of each byte. You'd think I would have figured out by that that it's breaking the string into bits, but I didn't. What made the light bulb go on was this:

.text:00401315                 and     eax, 1
.text:00401318                 test    eax, eax
.text:0040131A                 jz      short use_left
.text:0040131C                 mov     rax, [rbp+current_node] ; starts at the root
.text:00401320                 mov     rax, [rax+entry_struct.right_histogram]
.text:00401324                 mov     [rbp+current_node], rax ; starts at the root
.text:00401328                 jmp     short restart_loop
.text:0040132A ; ---------------------------------------------------------------------------
.text:0040132A use_left:                               ; CODE XREF: walk_tree_to_get_value+9Ej
.text:0040132A                 mov     rax, [rbp+current_node] ; starts at the root
.text:0040132E                 mov     rax, [rax+entry_struct.left_histogram]
.text:00401331                 mov     [rbp+current_node], rax ; starts at the root
.text:00401335 restart_loop:                           ; CODE XREF: walk_tree_to_get_value+ACj
.text:00401335                 add     [rbp+current_index_maybe], 1

Basically, based on the right-most bit in eax, it makes a decision to either jump to the left node or the right node. Then, when it gets to the leaf...

.text:00401363                 mov     rax, [rbp+current_node] ; starts at the root
.text:00401367                 movzx   eax, [rax+entry_struct.byte_value] ; Return the byte value at this leaf
.text:00401374                 pop     rbx
.text:00401375                 pop     rbp
.text:00401376                 retn returns the byte value in that leaf. If you read up on Huffman Trees, you'll see that that's exactly how they work.

The calling function adds that byte value to the end of an executable memory segment. When we're done reading the tree, the list of leaf-node bytes we've found are executed.

To summarize:

  • Build a histogram from itself
  • Convert that histogram into a Huffman Tree
  • Read data from the socket
  • Convert that data to bits, and use those bits to navigate the tree

We're almost done but... how do we get that tree!?

Putting it all together

All right, we understand the code, now we have to write an exploit. What do we do!?

The "right" way to do this is to build the same tree the same way, and to walk it from the node to the root to get he values. But this is a CTF and I want it to work on the first try, damnit! None of that "reconstructing the exact algorithm" nonsense! So I decided to steal their memory. :)

So, the first thing I did was put a breakpoint immediately after the tree was built to find the address of the root. On my box, the address of the root node, after the tree was built, happened to be 0x60e050. Then I wanted to dump the heap:

(gdb) x/1000000xb 0x603000
0x603000:       0x1b    0x0c    0x07    0x08    0x90    0x01    0x07    0x10
0x603008:       0x14    0x00    0x00    0x00    0x1c    0x00    0x00    0x00
0x603010:       0x80    0xe1    0xff    0xff    0x2a    0x00    0x00    0x00
0x603018:       0x00    0x00    0x00    0x00    0x00    0x00    0x00    0x00
0x603020:       0x14    0x00    0x00    0x00    0x00    0x00    0x00    0x00

I determined the starting address by trial and error - I wanted it to be as small as possible, but I needed the memory between it and the root node to be contiguous. 0x602000 wasn't allocated, but 0x603000 worked fine.

I dumped that to a file from gdb, then processed the file with Ruby:

# Split the file into lines
file.split(/\n/).each do |line|
  if(line =~ /Cannot/)

  # Break off the address and data
  addr, data = line.split(/:\s/, 2)
  addr = addr.to_i(16)

  # Remove the crud
  data.gsub!(/0x/, '')
  data.gsub!(/[^a-fA-F0-9]/, '')

  # Get both the qword (64-bit value) and pair of dwords (32-bit values) on that line
  qword = [data].pack("H*").unpack("Q").pop
  dword1 = qword & 0x0FFFFFFFF
  dword2 = (qword >> 32) & 0x0FFFFFFFF

  # Store them, indexed by the address
  @@qwords[addr] = qword
  @@dwords[addr] = dword1
  @@dwords[addr+4] = dword2

Now I have a nice address->value mapping for the entire dumped memory. So I can now define a function to read a node:

def get_node(addr)
  node = {}
  node[:addr]  = addr
  node[:left]  = @@qwords[addr + 0x00]
  node[:right] = @@qwords[addr + 0x08]
  node[:value] = @@dwords[addr + 0x10]
  node[:count] = @@dwords[addr + 0x1c]

  return node

And, starting at the root, re-build the whole tree recursively:

@@seqs = {}
def walk_nodes(addr, seq = "")
  node = get_node(addr)

  if(node[:left] != 0)
    walk_nodes(node[:left], seq + "0")

  if(node[:right] != 0)
    walk_nodes(node[:right], seq + "1")

  if(node[:left] == 0)
    @@seqs[node[:value]] = seq

node = get_node(ROOT)

In the end, @@seqs looks like this:

0 => 0
255 => 1000
215 => 100100000000
177 => 100100000001
30 => 10010000001
56 => 1001000001
220 => 100100001
114 => 10010001
7 => 1001001
133 => 10010100
97 => 10010101

Now that I have a mapping, I can do a bunch of lookups for the shellcode of my choice:

tree_code = ""

SHELLCODE.split(//).each do |c|
  tree_code += @@seqs[c.ord]

while((tree_code.length % 8) != 0) do
  tree_code += '0'
tree_code = [tree_code].pack("B*")
tree_code = [tree_code.length].pack("I") + tree_code
tree_code.split(//).each do |b|
  print('\x%02x' % b.ord)

And I'm done! I have a compressed version of my shellcode that I can feed directly into the program:


Conclusion: my 118 bytes of shellcode compresses down to a clean 142 bytes. :)


So, once you figure it out, this level is actually pretty straight forward!

Basically, read its own binary, build a Huffman Tree, then use the user's input to walk that Huffman Tree to build the executable code to run. Or, in other words, decompress and run the shellcode that we send!

2 thoughts on “Defcon Quals writeup for byhd (reversing a Huffman Tree)

  1. Reply


    Excellent writeup, I am glad you enjoyed my challenge.

  2. Reply


    Why is that runing byhd-fixed from gdb is different then runing it from c using execlp ?
    When i run byhd-fixed from gdb i get different output from __xstat function as compared to runing it from c using execlp .

Leave a Reply

Your email address will not be published.