Last weekend, I played with Men in Black Hats in Boston Key Party 2015. This event was made a DEFCON 23 Finals qualifier, so we were hoping to make a strong showing. Unfortunately, we didn't have the whole team available. On top of that, some of us (read: myself) made some pretty stupid mistakes.

UPDATE (2016-09-05): The Rubinius source tree now looks absolutely nothing like it did when I originally wrote this post. I've updated the GitHub links to point to version 2.5.2, which was the version I was looking at when trying to solve this challenge.

UPDATE (2016-09-06): I moved the source code for my disassembler to a GitHub Gist (having 300+ lines of code in-line seemed a bit much in retrospect).

The challenge I spent the most time on was "Sullivan Square" - a 350-point reverse engineering challenge. The challenge (which can be found here) stated that it required Rubinius 2.5.2, which made me very excited. I love Ruby and I've wanted an excuse to mess with Rubinius for awhile. Here was my chance!

Trie Harder

The challenge archive contained the following files:

fuzyll@corellia:~/Downloads/bkp2015$ tar tzvf trieharder.tar.gz.584eb2259dfcabe769faffa96b151020
drwxrwxr-x  0 jeff   jeff        0 Feb 25  2015 distribute/
-rw-rw-r--  0 jeff   jeff     4021 Feb 22  2015 distribute/cipher.rbc
-rw-rw-r--  0 jeff   jeff     1412 Feb 22  2015 distribute/trie_harder.rbc
-rwxrwxr-x  0 jeff   jeff       65 Nov 16  2014 distribute/run.sh
-rw-rw-r--  0 jeff   jeff    11057 Feb 22  2015 distribute/trie.rbc
-rw-rw-r--  0 jeff   jeff     5816 Feb 22  2015 distribute/trie.dump

It appears there were three "compiled" Ruby scripts (cipher.rbc, trie.rbc, and trie_harder.rbc) and an output file trie.dump. The logical thing to do would be to begin black-boxing the software. To do this, we'd need to run it. Unfortunately, Rubinius was having none of that:

fuzyll@corellia:~/Downloads/bkp2015$ rbx --version
rubinius 2.5.2 (2.1.0 7a5b05b1 2015-01-30 3.4 JI) [x86_64-linux-gnu]
fuzyll@corellia:~/Downloads/bkp2015$ rbx trie_harder.rbc
/home/fuzyll/Downloads/bkp2015/distribute/trie_harder.rbc (Rubinius::InvalidRBC)

After a few minutes of trying to figure out what was wrong (and failing), I contacted the challenge author, Jeff Crowell. Other teams had apparently run into the same problem. He wasn't quite sure what the issue was, either, since it all worked for him. A few teams, however, had obviously managed to get past whatever the problem was - they had the flag. Challenge accepted! I was going to figure this out.

It's at this point that I should mention: In hindsight, I should have done exactly what Neg9 did next. Rubinius was throwing a Rubinius::InvalidRBC exception. In the Rubinus source code (in vm/builtin/system.cpp), it winds up throwing this exception when the bytecode has an invalid signature (line 141):

CompiledFile* cf = CompiledFile::load(stream);
 if(cf->magic != "!RBIX") {
   delete cf;
   return Primitives::failure();
 }

 uint64_t sig = signature->to_ulong_long();
 if((sig > 0 && cf->signature != sig)
     || cf->version != version->to_native()) {
   delete cf;
   return Primitives::failure();
 }

The correct solution here (that Neg9 implemented) is to modify Rubinius and patch out the signature check.

In the general case: If you're presented with a challenge that fundamentally doesn't work, contact the challenge author. If they say it's intended or able to be worked around, do that. Don't immediately jump to what you'd do in the worst-case scenario at work. This is a CTF - the challenges are designed to be quickly solvable, unlike the real world.

Anyway, I foolishly assumed that tracking down the specific Rubinius error and attempting to fix it would be harder than it actually was. As a result, I never attempted it. Instead, I decided the only remaining valid approach was to literally reverse engineer the application. And so, I did.

The Disassembler

The first thing I needed to understand was how the Rubinius bytecode files were put together. I started by doing xxd cipher.rbc | head:

00000000: 2152 4249 580a 3130 3138 3434 3635 3336  !RBIX.1018446536
00000010: 3537 3833 3035 3536 3436 0a32 350a 4d0a  5783055646.25.M.
00000020: 310a 6e0a 6e0a 780a 450a 380a 5553 2d41  1.n.n.x.E.8.US-A
00000030: 5343 4949 0a31 300a 5f5f 7363 7269 7074  SCII.10.__script
00000040: 5f5f 0a69 0a31 390a 3130 360a 370a 300a  __.i.19.106.7.0.
00000050: 310a 3732 0a35 360a 310a 330a 3633 0a32  1.72.56.1.3.63.2
00000060: 0a31 380a 3732 0a32 0a35 360a 330a 330a  .18.72.2.56.3.3.
00000070: 3231 0a32 0a31 370a 490a 340a 490a 300a  21.2.17.I.4.I.0.
00000080: 490a 300a 490a 300a 490a 300a 6e0a 6e0a  I.0.I.0.I.0.n.n.
00000090: 490a 300a 700a 340a 780a 450a 380a 5553  I.0.p.4.x.E.8.US

From this, we can see the file starts with the magic !RBIX and that newlines (0x0A) appear to be a delimiter. Searching the source code for !RBIX with grep -r "\!RBIX" * gave me the following matches:

kernel/loader.rb:        if IO.read(@script, 6) == "!RBIX\n"
vm/drivers/jit-test.cpp:  if(cf->magic != "!RBIX") {
vm/drivers/compile.cpp:  if(cf->magic != "!RBIX") throw std::runtime_error("Invalid file");
vm/test/test_compiled_file.hpp:    stream.str("!RBIX\n1\n42\nt");
vm/test/test_compiled_file.hpp:    TS_ASSERT_EQUALS(cf->magic, std::string("!RBIX"));
vm/test/test_compiled_file.hpp:    stream.str("!RBIX\n1\n42\nt");
vm/test/test_compiled_file.hpp:    TS_ASSERT_EQUALS(cf->magic, "!RBIX");
vm/test/fixture.rbc_:!RBIX
vm/builtin/system.cpp:    if(cf->magic != "!RBIX") {
vm/environment.cpp:    if(cf->magic != "!RBIX") {

I decided that vm/builtin/system.cpp would be a pretty great place to start looking. Yes, if you've been paying attention, that's the exact same file Neg9 looked at to patch out the signature check. In fact, it's one line after the start of the code I showed above. Have I mentioned that I screwed up solving this challenge pretty badly?

When I looked at the line above it (see above), I saw that CompiledFile::load was where Rubinius did the parsing of the file. In my rush to try and solve the challenge, I never looked at the code below it - I simply went to go find the implementation of CompiledFile::load. Oops...

It's in vm/compiled_file.cpp on line 21:

CompiledFile* CompiledFile::load(std::istream& stream) {
  std::string magic;
  uint64_t signature;
  int version;

  stream >> magic;
  stream >> signature;
  stream >> version;
  stream.get(); // eat the \n

  return new CompiledFile(magic, signature, version, &stream);
}

This tells us that the first 3 things in the file, separated by newlines, are the magic, signature, and version. The rest of the parsing isn't done here, so it has to be done elsewhere. Rather than head back to the implementation of the caller, I saw the next function listed below CompiledFile::load (line 34):

Object* CompiledFile::body(STATE) {
  UnMarshaller mar(state, *stream);
  return mar.unmarshal();
}

Yes! This looks like the code I want - the opposite of Marshal! So, off I went to vm/marshal.cpp. Facepalm.

In vm/marshal.cpp on line 300, I found the parser for the types that come right after the version in the bytecode file:

Object* UnMarshaller::unmarshal() {
  char code;

  stream >> code;

  switch(code) {
  case 'n':
    return cNil;
  case 't':
    return cTrue;
  case 'f':
    return cFalse;
  case 'I':
    return get_int();
  case 'R':
    return get_rational();
  case 'C':
    return get_complex();
  case 's':
    return get_string();
  case 'x':
    return get_symbol();
  case 'p':
    return get_tuple();
  case 'd':
    return get_float();
  case 'i':
    return get_iseq();
  case 'M':
    return get_compiled_code();
  case 'c':
    return get_constant();
  case 'E':
    return get_encoding();
  default:
    std::string str = "unknown marshal code: ";
    str.append( 1, code );
    Exception::type_error(state, str.c_str());
    return cNil;    // make compiler happy
  }
}

When Rubinius encounters one of these types, it calls the appropriate handler for that type. I won't reproduce them all here, but you can find them in the same source file.

This is where I began re-implementing. Once I was done with this, I also re-implemented each of the handlers. One of them, get_compiled_code, lead me to the file vm/instructions.def, which defines all of the available instructions in the Rubinius VM. I implemented those as a Hash I could look things up in.

When I was done, I wound up with this script. If you run it, it will disassemble all the blocks it finds in the bytecode files you gave it.

The Source

Now that we have a disassembler, it's time to reverse the bytecode into pure Ruby! Here's an example snippet from running the disassembler on cipher.rbc:

# stack size: 4
# locals: 1
# arguments: 1 / 0 / 1
# lines: [-1, 0, 0]
# literals: [:@map, :encrypt, :[]]
# locals: [:char]
def encrypt
   0:   push_ivar {:literal=>:@map}
   2:   push_literal {:literal=>:encrypt}
   4:   send_stack {:literal=>:[], :count=>1}
   7:   push_local {:local=>:char}
   9:   send_stack {:literal=>:[], :count=>1}
   12:  ret

# stack size: 5
# locals: 1
# arguments: 1 / 0 / 1
# lines: [-1, 0, 0, 0, 20]
# literals: [nil, :Regexp, "", :new, :split, nil, :map, :join]
# locals: [:str]
def encrypt
   0:   push_local {:local=>:str}
   2:   push_literal {:literal=>nil}
   4:   dup_top
   5:   is_nil
   6:   goto_if_false {:location=>20}
   8:   pop
   9:   push_cpath_top
   10:  find_const_fast {:literal=>:Regexp}
   12:  push_literal {:literal=>""}
   14:  meta_push_0
   15:  send_stack {:literal=>:new, :count=>2}
   18:  set_literal {:literal=>nil}
   20:  send_stack {:literal=>:split, :count=>1}
   23:  create_block {:literal=>nil}
   25:  send_stack_with_block {:literal=>:map, :count=>0}
   28:  send_stack {:literal=>:join, :count=>0}
   31:  ret

These two blocks implement the encrypt method of the Cipher object. The bottom block calls the top block at 23.

The top block translates, more or less, to @map[:encrypt][char]. We can see it:

• push an ivar (instance variable), @map, onto the stack at 0
• push the literal :encrypt (a Symbol) onto the stack at 2
• send_stack at 4

send_stack, as documented in vm/instructions.def (line 1086), will take a literal ([], in this case) and count (1) arguments (:encrypt) and apply them to the next value on the stack (@map). The result will be placed on the stack. This is the @map[:encrypt] part. Then:

• At 7, the local char is pushed onto the stack
• send_stack is called again at 9 to complete the @map[:encrypt][char] statement
• The block is then finished, so we return at 12.

I'll spare you the full rundown of how the bottom block operates. Here's what I "decompiled" cipher.rbc into (look at encrypt specifically to see what these two blocks above became):

class Cipher
    def initialize(shuffled)
        normal = ("a".."z").to_a + ("A".."Z").to_a + ("0".."9").to_a + [" "]
        @map = normal.zip(shuffled).inject({ :encrypt => {}, :decrypt => {} }){ |hash, elem|
            if not elem.instance_of? Array
                raise "no idea what this code is doing"  # FIXME
            end
            a = elem[0]
            b = elem[1]
            hash[:encrypt][a] = b
            hash[:decrypt][b] = a
            hash
        }
    end

    def encrypt(str)
        return str.split(//).map{ |char| @map[:encrypt][char] }.join
    end

    def decrypt(str)
        return str.split(//).map{ |char| @map[:decrypt][char] }.join
    end
end

After the competition was over, I had Crowell give me the original code for this class. Turns out I was pretty damn close! If you're interested, go back through that bottom block by hand and see if you can come to the same conclusion I did. (I think the code I couldn't quite figure out was Rubinius sticking in some default error handling, but I'm not sure).

Once cipher.rbc was done, I moved on to the other two files. These had some trickier logic to figure out, but it wasn't too hard to step through it all quickly by hand with vm/instructions.def up on another monitor.

Here's my by-hand decompilation of trie.rbc:

require "./cipher"

class Trie
    class Node
        attr_accessor :left, :mid, :right, :char, :value, :end

        def initialize(char, value)
            @char = char
            @value = value
            @right = nil
            @mid = nil
            @left = nil
            @end = false
            return
        end

        def last?
            return @end == true
        end
    end

    def push_recursive(node, string, index, value)
        char = string[index]
        node = Node.new(char, value) if node.nil?
        if node.char < char
            node.left = push_recursive(node.left, string, index, value)
        elsif node.char > char
            node.right = push_recursive(node.right, string, index, value)
        elsif index < string.length - 1
            node.mid = push_recursive(node.mid, string, index + 1, value)
        else
            node.end = true
        end
        return node
    end

    def get_recursive(node, string, index)
        return nil if node.nil?
        char = string[index]
        if node.char < char
            return get_recursive(node.left, string, index)
        elsif node.char > char
            return get_recursive(node.right, string, index)
        elsif index < string.length - 1
            return get_recursive(node.mid, string, index + 1)
        elsif node.last?
            return [node.char, node.value]
        else
            return nil
        end
    end

    def initialize
        @root = nil
    end

    def push(key, value)
        cipher = Cipher.new(["K", "D", "w", "X", "H", "3", "e", "1", "S", "B", "g", "a", "y", "v", "I", "6",
                             "u", "W", "C", "0", "9", "b", "z", "T", "A", "q", "U", "4", "O", "o", "E", "N",
                             "r", "n", "m", "d", "k", "x", "P", "t", "R", "s", "J", "L", "f", "h", "Z", "j",
                             "Y", "5", "7", "l", "p", "c", "2", "8", "M", "V", "G", "i", " ", "Q", "F"])
        key = cipher.encrypt(key.to_s)
        return nil if key.empty?
        @root = push_recursive(@root, key, 0, value)
        return @root
    end

    def has_key?(key)
        key = key.to_s
        return false if key.empty?
        nope = get_recursive(@root, 0, key)
        return !nope
    end

    def get(key)
        cipher = Cipher.new(["K", "D", "w", "X", "H", "3", "e", "1", "S", "B", "g", "a", "y", "v", "I", "6",
                             "u", "W", "C", "0", "9", "b", "z", "T", "A", "q", "U", "4", "O", "o", "E", "N",
                             "r", "n", "m", "d", "k", "x", "P", "t", "R", "s", "J", "L", "f", "h", "Z", "j",
                             "Y", "5", "7", "l", "p", "c", "2", "8", "M", "V", "G", "i", " ", "Q", "F"])
        key = cipher.encrypt(key.to_s)
        return nil if key.empty?
        node = get_recursive(@root, key, 0)
        return node.last? if node != nil
        return nil
    end
    alias_method :[], :get
end

...and trie_harder.rbc:

require "./trie"
require "./cipher"

puts "            [*] Greetings to all of the eiltes here [*]"
puts "--- I heard you guys all hate ruby, so I have decided to be nice---"
puts "            --- enjoy this great bytecode instead! ---"
puts ""
print "So, you can tell me now... what's the flag? "
flag = gets.chomp
dumped = File.read("trie.dump")
t = Marshal.load(dumped)
res = t.get(flag)
if not res.nil?
    puts res
else
    puts "nop"
end

The best part? I can run the damn thing in Ruby proper - no more Rubinius!

The Challenge

Now that we have source code, we need to actually solve the challenge! trie_harder.rb above will load trie.dump and Marshal its contents into Ruby as objects. It will then get flag from the loaded object and puts res if res is not nil. Otherwise, it will puts the string "nop".

The object that it loads is a Trie (see trie.rb above), which implements - you guessed it - a trie. Trie specifically implements a ternary tree with child nodes ordered by character. Every character of our input will "look up" the corresponding character in the ternary tree.

The data that is Marshaled in looks like this (pretty-printed):

#<Trie:0x00000001133ef8
 @root=
  #<Trie::Node:0x00000001133de0
   @char="W",
   @end=false,
   @left=
    #<Trie::Node:0x00000001133d90
     @char="D",
     # ...snip...
   @mid=
    #<Trie::Node:0x0000000112beb0
     @char="D",
     # ...snip...
   @right=
    #<Trie::Node:0x000000011322d8
     @char="y",
     # ...snip...
   @value="this isnt the flag">>

If the first character of your input is "less than" a "W", you'll head down the left path (towards a check against a "D"). If the first character of your input is a "W", you'll head down the middle path (towards a different check against a "D"). If the first character of your input is "more than" a "W", you'll head down the right path (towards a check against a "y"). Each of these paths will determine which value is chosen at the end. You can see this in code by looking at push_recursive and get_recursive in my decompiled trie.rb above.

In the data, there are a number of possible values we can have:

not the flag but a true statement ;)
wow not this either
1 c4n r34d th15 ju57 l1k3 x86 0r 3n6L15h!
this isnt the flag
nope lots of fake flags
good boy this is the flag
stop being such a n00b and get the flag
lole n1c3 try
neither is this

When we decrypted the input that would lead us specifically to the value "good boy this is the flag" (which, upon inspection, was "XcXFAp9F0Wc8FDHcveFypMWF288i"), we got our flag. Here's the code I added to do it:

# XXX: add these lines to the bottom of trie_harder.rb to print the flag out
cipher = Cipher.new(["K", "D", "w", "X", "H", "3", "e", "1", "S", "B", "g", "a", "y", "v", "I", "6",
                     "u", "W", "C", "0", "9", "b", "z", "T", "A", "q", "U", "4", "O", "o", "E", "N",
                     "r", "n", "m", "d", "k", "x", "P", "t", "R", "s", "J", "L", "f", "h", "Z", "j",
                     "Y", "5", "7", "l", "p", "c", "2", "8", "M", "V", "G", "i", " ", "Q", "F"])
puts cipher.decrypt("XcXFAp9F0Wc8FDHcveFypMWF288i")

When run, this prints the flag: d1d y0u tr13 be1ng m04r 2337.

Lessons Learned

Read the source code. Now, read it again.

If I had simply looked a few lines farther down in the same function I was already reading, I would have been able to completely skip a lot of effort. It's also worth noting that, even if that simple patch wasn't possible, I could have implemented the disassembler far more quickly if I'd looked at the Ruby files in the Rubinius repository. I wasn't the only player that wrote a disassembler, but theirs was far more concise than mine.

This is a pretty classic example of over-thinking the problem (and over-engineering the solution). Many other teams solved this challenge faster than I did. I should have understood that trying to get Rubinius to work was the more efficient path.

When you're an engineer tasked with solving hard problems on a daily basis, it can be easy to get caught up in the problem and miss the quicker, better solution right in front of you. That's what makes CTFs so great: You get to have experiences like this to learn from without spending all of your customer's money (and/or all of your development time). CTFs make you a better problem solver by forcing you to be more efficient. You can't win if you're too busy re-inventing the wheel.

Don't be me!