F-hash -- Volga CTF 2020

F-hash Writeup – Volga CTF 2020

Points: 250

Solves: 43

The binary

We are given a C++ binary. Just running the binary gives you the flag, but it will “never” end. Our goal is to optimize it.

By looking at the backtrace in gdb we can see that function sub_13b0 is being called recursively.

After reversing it the minimal amount, I figured out that the function prototype is void sub_13b0(res_struct *a1, int a2, int64_t a3, int64_t a4), where res_struct is:

struct res_struct {
  int64_t a;
  int64_t b;
  int64_t c;
};

We can also see that if a2 == 1 or a2 == 2 the recursion stops (base cases).

Solution

My idea was to memoize the results of the recursive function and replace a1 with the cached result when a call with the same input (the combination of a2, a3 and a4) occurs.

I didn’t want to reverse the function completely and implement it in python and so I decided to use frida to dynamically hook the function and do the memoization.

My first idea was to replace the function body by doing the following:

• new input: call the original function and cache the result
• cached input: write the cached result in a1 and return immediately

Just as a POC this was the code I started with:

// frida --no-pause --runtime=v8 -l frida_trace.js ./f-hash

var f_hash_addr = 0x555555554000;
var recursive_func_ptr = ptr(f_hash_addr + 0x13b0);
var recursive_func = new NativeFunction(recursive_func_ptr, 'void', ['pointer', 'int64', 'int64', 'int64']);

Interceptor.replace(recursive_func_ptr, new NativeCallback(function (a1, a2, a3, a4) {
    console.log(" the_recursive_function(a1: " + a1 + ", a2: " + a2 + ", a3: " + a3 + ", a4: " + a4 + ")");

    // Call the original function
    recursive_func(a1, a2, a3, a4)

}, 'void', ['pointer', 'int64', 'int64', 'int64']));

The problem was that when I call the original function, its recursive calls won’t be hooked, and so it will just run forever as before. I didn’t come up with any way to do this by replacing the body.

---

My next idea was to use OnEnter, OnLeave and some hackery to get the job done:

• In the OnEnter hook:
  • new input: do nothing
  • cached input: make a2 = 1 so that we hit a recursion base case (avoiding further recursion)
• In the OnLeave hook:
  • new input: memoize the result
  • cached input: replace the a1 struct with the cached result (because we changed a2 in the onEnter hook and so the result is wrong)

It was a bit of hacky solution but it works. The script:

// frida --no-pause --runtime=v8 -l frida_trace.js ./f-hash

// ====================
// UTILS
// ====================
function deref64(i) {
    return Memory.readU64(ptr(i))
}

function p(s) {
  console.log(s);
}

// ====================
// Hooks
// ====================
// Intercepts the recursive function
var mem = new Object();

function hash_args(args) {
    return args[1] + "_" + args[2] + "_" + args[3];
};

var f_hash_addr = 0x555555554000;
var recursive_func_ptr = ptr(f_hash_addr + 0x13b0);

Interceptor.attach(recursive_func_ptr, {
  onEnter: function(args) {
    this.a1 = parseInt(args[0]);
    this.hash = hash_args(args);

    if (typeof mem[this.hash] !== 'undefined') {
        // Recursion stoppage case (we will replace the result in the OnLeave hook)
        args[1] = ptr(1);
    }
  },

  onLeave: function(retval) {
    if (typeof mem[this.hash] === 'undefined') {
        // We have never seen this.. Memoize!
        mem[this.hash] = [deref64(this.a1), deref64(this.a1+8), deref64(this.a1+16)];
    } else {
        // Just replace the fake result with the memoized one (because we made it run the recursion stoppage case)
        var prev_results = mem[this.hash]
        ptr(this.a1).writeU64(prev_results[0])
        ptr(this.a1+8).writeU64(prev_results[1])
        ptr(this.a1+16).writeU64(prev_results[2])
    }
  }
});