Tower of Hanoi

HITCON 2016 - ROP

by on under HITCON
8 minute read ·

Who doesn’t like ROP? Let’s try some new features introduced in 2.3.

ROP is a simple Ruby VM crackme. We are given a file rop.iseq, without any other detail.

$ file rop.iseq
rop.iseq: data

Opening it with an hex editor, we see that it starts with YARB, and from its contents we can guess that it is a sort of bytecode format. With Google’s help, we come across Ruby’s RubyVM::InstructionSequence class, and in particular the load_from_binary method, introduced in Ruby 2.3. Its purpose is “to load an iseq object from binary format String object created by #to_binary“… and from Ruby’s source code (compile.c), we see that the binary file it loads must start with the bytes YARB… so it really seems that we are dealing with serialized Ruby bytecode!

We can simply load and execute this file with RubyVM::InstructionSequence. I had to download the Ruby interpreter from rvm, as the one coming with Ubuntu 16.04 had a value of the constant RUBY_PLATFORM slightly different than the one of the iseq file, causing a unmatched platform error when loading the iseq.

iseq = nil
File.open("rop.iseq", "rb") do |file|
  iseq = RubyVM::InstructionSequence.load_from_binary(file.read)
end
iseq.eval

The challenge waits for some input; trying to enter a string, it outputs Invalid Key @_@: we need to figure out a valid input. We can also dump the disassembly:

iseq.disasm

We could not find (quickly) much documentation about the Ruby virtual machine, or tools working with the iseq format, so we resorted to guess the behavior of the various opcodes (it is a simple stack-based VM) to understand what the program is doing.

Fortunately, the bytecode contains various trace instructions; we made use of set_trace_func to print those events during the program execution. This way, we could understand at which line of code the program was jumping to the function gg - and, thus, what components of our input string were correct!

From the disassembly, we see that the input is split into 5 substrings separated by '-'. Each of them has to match the regexp /^[0-9A-F]{4}$/, and is checked by a separate block of code. As soon as a substring does not satisfy a condition, the program calls the function gg, which outputs "Invalid Key @_@" and exits. Thus, we have to pass five checks, one for each substring.

Just to give an idea of how the disasm looked like, here is the first check:

0109 trace            1                                               (  42)
0111 getlocal_OP__WC__0 2
0113 putobject_OP_INT2FIX_O_0_C_
0114 opt_aref         <callinfo!mid:[], argc:1, ARGS_SIMPLE>, <callcache>
0117 putobject        16
0119 opt_send_without_block <callinfo!mid:to_i, argc:1, ARGS_SIMPLE>, <callcache>
0122 putobject        31337
0124 opt_eq           <callinfo!mid:==, argc:1, ARGS_SIMPLE>, <callcache>
0127 branchif         134
0129 putself
0130 opt_send_without_block <callinfo!mid:gg, argc:0, FCALL|VCALL|ARGS_SIMPLE>, <callcache>
0133 pop

(getlocal_OP__WC__0 2 is the variable xs, an array containing the user input split at '-')

Once understood the disassembled Ruby VM code, passing the two checks was trivial. Below a rough Ruby version of the five checks:

# 31337.to_s(16).upcase = 7A69
gg unless xs[0].to_i(16) == 31337
# "FACE".reverse = ECAF
gg unless xs[1].reverse == "FACE"
# bruteforce -> 1BD2
gg unless f(217, xs[2].to_i(16), 314159).to_s(28).upcase == "48D5"
# 53 * 97 = 5141
gg unless xs[3].to_i(10).prime_division.map(&:first).sort == [53, 97]
# (0x7A69 ^ 0xECAF ^ 0x1BD2 ^ 0x5141 ^ 5671).to_s(16).upcase = CA72
gg unless xs.map { |x|
  x.to_i(16)
}.inject(:^).to_s.sha1 == "947d46f8060d9d7025cc5807ab9bf1b3b9143304"

For the third check, instead of thinking about whether it was possible to invert f, we considered that the input space is very small (four digit hex numbers), and we resorted to bruteforce:

def f(a, b, m):
    s = 1
    r = a
    while b != 0:
        if b & 0x01 == 1:
            s = (s * r) % m
        b = (b >> 1)
        r = (r * r) % m
    return s

for x in range(0x0000, 0xFFFF):
    if(f(217, x, 314159) == int("48D5", 28)):
        print "Found ", hex(x)

This Python script took 0.263s on my laptop to find the correct string. Finally, for the last check, we noticed that 947d46f8060d9d7025cc5807ab9bf1b3b9143304 is the SHA-1 of 5671, so we get the last component of the input string by just XOR-ing the first four ones with

  1. The complete input string is
7A69-ECAF-1BD2-5141-CA72

which gives us the output

Congratz! flag is hitcon{ROP = Ruby Obsecured Programming ^_<}

For completeness, here is the complete Ruby source code of the crackme - as we were able to manually reverse:

require "digest"
require "prime"

def f(a, b, m)
   s = 1
   r = a
   while b != 0
      if b[0] == 1
         s = (s * r) % m
      end
      b = (b >> 1)
      r = (r * r) % m
   end
   return s
end

def gg
  print "Invalid Key @_@"
  exit
end

class String
  def sha1
    Digest::SHA1.hexdigest(self)
  end

  def enhex
    self.unpack("H*")[0]
  end

  def dehex
    [self].pack("H*")
  end

  def ^(other)
    self.bytes.map.with_index { |x, i|
        x ^ other[i % other.size].ord
    }.pack("C*")
  end
end

k = gets.chomp
xs = k.split("-")
gg unless xs.size == 5
gg unless xs.all? { |x|
  x =~ /^[0-9A-F]{4}$/
}

gg unless xs[0].to_i(16) == 31337
gg unless xs[1].reverse == "FACE"
gg unless f(217, xs[2].to_i(16), 314159).to_s(28).upcase == "48D5"
gg unless xs[3].to_i(10).prime_division.map(&:first).sort == [53, 97]
gg unless xs.map { |x|
  x.to_i(16)
}.inject(:^).to_s.sha1 == "947d46f8060d9d7025cc5807ab9bf1b3b9143304"

s = "bce410e85433ba94f0d832d99556f9764b220eeda7e807fe4938a5e6effa7d83c765e1795b6c26af8ad258f6"
puts "Congratz! flag is " + (s.dehex ^ k.sha1.dehex).to_s
HITCON, Reversing, 2016
comments powered by Disqus