Can you go with the flow?

no_mo_flo is a reverse engineering challenge from this year’s PlaidCTF. It’s a 64-bit executable that reads 32 characters from stdin, and tells you if this is the correct flag or not (classic).

Opening it in IDA reveals that it takes the input and breaks it into two 16 bytes buffers:

for ( i = 0; i <= 15; ++i )
{
  v5[i] = buf[2 * i];
  v6[i] = buf[2 * i + 1];
}

It will then register a SIGFPE handler and trigger divisions by 0. When triggerred, the handler will emulate jumps depending on $rflags, $r10, and $r11.

The SIGFPE handler looks like this

int __fastcall sigfpe_handler(__int64 a1, siginfo_t *a2, ucontext_t *ctx)
{
	greg_t reg_r11;
	greg_t reg_eflags;
	greg_t reg_r10;
	char *str;

	if ( custom_flow_enabled ) {
		reg_r10 = ctx->uc_mcontext.gregs[REG_R10];
		reg_eflags = ctx->uc_mcontext.gregs[REG_EFL];
		reg_r11 = ctx->uc_mcontext.gregs[REG_R11];
		switch ( reg_r11 ) {
			case CUSTOM_JMP:
				reg_r11 = custom_jmp(reg_r10);
				break;
			case CUSTOM_JNL:
				reg_r11 = custom_jnl(reg_r10, reg_eflags);
				break;
			case CUSTOM_JNG:
				reg_r11 = custom_jng(reg_r10, reg_eflags);
				break;
			case CUSTOM_JG:
				reg_r11 = custom_jg(reg_r10, reg_eflags);
				break;
			case CUSTOM_JL:
				reg_r11 = custom_jl(reg_r10, reg_eflags);
				break;
			case CUSTOM_JNE:
				reg_r11 = custom_jne(reg_r10, reg_eflags);
				break;
			case CUSTOM_JE:
				reg_r11 = custom_je(reg_r10, reg_eflags);
				break;
			default:
				break;
		}
		zero = 1LL;
		custom_flow_enabled = 0LL;
	} else {
		reg_r11 = sigaction(8, 0LL, 0LL);
		if ( (signed int)reg_r11 < 0 ) {
			str = strerror(errno);
			reg_r11 = printf("sigaction install fail %s\n", str);
		}
	}
	return reg_r11;
}

As we can see, $r11 is used as an opcode, and $r10 to store the jump value. If we look at the function called inside the switch, we have a reimplementation of the x86 opcodes, for example with jne:

__int64 custom_jne(__int64 reg_r10, __int64 reg_eflags)
{
	if (reg_eflags & X86_EFLAGS_ZF)
		custom_jmp_to = reg_r10;
	else
		custom_jmp_to = custom_jmp_from + 56;

	return custom_jmp_to;
}

The code that triggers the SIGFPE handler looks like this:

.text:0000000000400F18 check_odd_bytes:                        ; CODE XREF: main+AA
.text:0000000000400F18                 sub     rsp, 8
.text:0000000000400F1C                 mov     esi, 1
.text:0000000000400F21                 mov     eax, 0
.text:0000000000400F26                 mov     edx, eax
.text:0000000000400F28                 shl     edx, 2
.text:0000000000400F2B                 movsxd  rdx, edx
.text:0000000000400F2E                 mov     rax, rdi
.text:0000000000400F31                 add     rax, rdx
.text:0000000000400F34                 mov     rdx, rax
.text:0000000000400F37                 mov     eax, [rdx]
.text:0000000000400F39                 mov     edx, eax
.text:0000000000400F3B                 sub     edx, 3
.text:0000000000400F3E                 mov     eax, edx
.text:0000000000400F40                 cmp     eax, 40h
.text:0000000000400F43                 lea     r10, check_odd_byte_1
.text:0000000000400F4B                 mov     r11, CUSTOM_JNE
.text:0000000000400F52                 mov     dword ptr ds:custom_flow_enabled, 1
.text:0000000000400F5D                 mov     ds:custom_save_rax, rax
.text:0000000000400F65                 mov     rax, 0
.text:0000000000400F6C                 mov     ds:custom_save_rdx, rdx
.text:0000000000400F74                 lea     rdx, loc_400F7B
.text:0000000000400F7B
.text:0000000000400F7B loc_400F7B:                             ; DATA XREF: check_odd_bytes+5C
.text:0000000000400F7B                 mov     ds:custom_jmp_from, rdx
.text:0000000000400F83                 cdq
.text:0000000000400F84                 idiv    ds:zero
.text:0000000000400F8C                 mov     ds:zero, 0
.text:0000000000400F98                 mov     rax, ds:custom_save_rax
.text:0000000000400FA0                 mov     rdx, ds:custom_save_rdx
.text:0000000000400FA8                 mov     r11, ds:custom_jmp_to
.text:0000000000400FB0                 jmp     r11

.text:0000000000400FB3                 mov     esi, 0
.text:0000000000400FB8                 lea     r10, check_odd_byte_1
.text:0000000000400FC0                 mov     r11, CUSTOM_JMP
.text:0000000000400FC7                 mov     dword ptr ds:custom_flow_enabled, 1
.text:0000000000400FD2                 mov     ds:custom_save_rax, rax
.text:0000000000400FDA                 mov     rax, 0
.text:0000000000400FE1                 mov     ds:custom_save_rdx, rdx
.text:0000000000400FE9                 lea     rdx, loc_400FF0
.text:0000000000400FF0
.text:0000000000400FF0 loc_400FF0:                             ; DATA XREF: .text:0000000000400FE9
.text:0000000000400FF0                 mov     ds:custom_jmp_from, rdx
.text:0000000000400FF8                 cdq
.text:0000000000400FF9                 idiv    ds:zero
.text:0000000000401001                 mov     ds:zero, 0
.text:000000000040100D                 mov     rax, ds:custom_save_rax
.text:0000000000401015                 mov     rdx, ds:custom_save_rdx
.text:000000000040101D                 mov     r11, ds:custom_jmp_to
.text:0000000000401025                 jmp     r11

If we look a little inside it, this roughly translates into:

check_odd_bytes:                        ; CODE XREF: main+AA
                sub     rsp, 8
                mov     esi, 1
                mov     eax, 0
                mov     edx, eax
                shl     edx, 2
                movsxd  rdx, edx
                mov     rax, rdi
                add     rax, rdx
                mov     rdx, rax
                mov     eax, [rdx]
                mov     edx, eax
                sub     edx, 3
                mov     eax, edx
                cmp     eax, 40h
                jne     check_odd_byte_1 ; Here is the change

                mov     esi, 0
                jmp     check_odd_byte_1 ; and the second one


Two main functions will then be called, sub_4006c6 and sub_400f18, that will respectively verify the first buffer and the second one. Two nice solving techniques are broken by this scheme: symbolic analysis (like angr) is very hard with stuff like signal handlers and instruction counting is impossible since characters are not checked sequentially (here, they are checked two by two, the even ones, then the odd ones).

While gaby was reversing and simplifying the jumps handling to NOP out the divisions by 0 (see above), he figured out that the first function was not using the handler at all. So I tried to launch angr on the first function only, and managed to get the first half of the flag like this:

#!/usr/bin/env python2

import angr
from simuvex.procedures.stubs.UserHook import UserHook

p = angr.Project('no_flo_f51e2f24345e094cd2080b7b690f69fb')


# You win
find = 0x4027ce
# You lose
main = 0x40272e
# Basic blocks that get eax to be reset in the first function
# (see get_basic_blocks.py)
avoid = (0x4027f8, 0x40071d, 0x40077a, 0x4007d7, 0x400834, 0x400894, 0x4008f4,
         0x400950, 0x4009a8, 0x400a09, 0x400a6f, 0x400ac7, 0x400b24, 0x400b81,
         0x400bd9, 0x400c31, 0x400c8e, 0x400ce6, 0x400d3e, 0x400d96, 0x400df2,
         0x400e4a, 0x400ea0, 0x400eeb)
 flag_addr = 0


def read(state):
    state.regs.rax = 32
    global flag_addr
    flag_addr = state.regs.rsi

    for i in range(31):
        if i % 2 == 0:
            # We are interested by the bytes that go into the first function
            state.mem[state.regs.rsi + i].char = state.se.BVS('c', 8)
        else:
            if i > 4 and i < 31:
                # Other are put to '`' to be computed later with
                # v0lt (see solve2.py)
                state.mem[state.regs.rsi + i].char = '`'
            elif i == 1:
                state.add_constraints(state.memory.load(flag_addr, 5) == int("PCTF{".encode("hex"), 16))
                state.mem[state.regs.rsi + 31].char = '}'

def clear_rax(state):
    state.regs.rax = 0

def do_nothing(state):
    # There might be an angr builtin
    # no time to read the docs!
    pass

# sighandler does nothing
p.hook(0x4027ba, angr.Hook(UserHook, user_func=do_nothing, length=5))
# read
p.hook(0x40274a, angr.Hook(UserHook, user_func=read, length=5))
# second function is completely bypassed for now
p.hook(0x4027d1, angr.Hook(UserHook, user_func=clear_rax, length=(0x4027e0 - 0x4027d1)))

init = p.factory.blank_state(addr=main)
pgp = p.factory.path_group(init)
ex = pgp.explore(find=find, avoid=avoid)

# Print half the flag to pipe it into v0lt
print(ex.found[0].state.se.any_str(ex.found[0].state.memory.load(flag_addr, 32)))

Basic blocks’ addresses from the previous script were dumped from IDA with this:

from idautils import *
from bisect import *

START = 0x4006c6
END = 0x400f13

# From https://reverseengineering.stackexchange.com/a/1648/11827
class BBWrapper(object):
    def __init__(self, ea, bb):
        self.ea_ = ea
        self.bb_ = bb

        def get_bb(self):
            return self.bb_

        def __lt__(self, other):
            return self.ea_ < other.ea_

class BBCache(object):
    def __init__(self, f):
        self.bb_cache_ = []
        for bb in idaapi.FlowChart(f):
            self.bb_cache_.append(BBWrapper(bb.startEA, bb))
        self.bb_cache_ = sorted(self.bb_cache_)

def find_block(self, ea):
    i = bisect_right(self.bb_cache_, BBWrapper(ea, None))
    if i:
        return self.bb_cache_[i-1].get_bb()
    else:
        return None



bb_cache = BBCache(idaapi.get_func(START))
for func in Functions(START, END):
    addr = func
    while addr < END:
        disasm = GetDisasm(addr)
        if "mov" in disasm and "r8d, 0" in disasm:
            print("{0}".format(hex(bb_cache.find_block(addr).startEA)))
        decoded = DecodeInstruction(addr)
        addr += decoded.size if decoded else 1

angr runs for less than 10 seconds and gives us half the flag:

p1kachu@GreenLabOfGazon:no_mo_flow$ ./solve1.py
PCTF{`0`f`0`_`0`l`k`_`h`h`l`_`0}
p1kachu@GreenLabOfGazon:no_mo_flow$

and now, that we have this, we can “bruteforce” the other half using instruction counting since we will always pass the first check (the even characters)!

Using v0lt, we are able to get the second half of the flag:

#!/usr/bin/env python3

from v0lt import *

# Get half the flag from angr
first_half = input()

# Create an instruction counting instance that reads from stdin a password
# of 32 chars, and try to recover the other half of it
ic = InstructionCounter("/home/p1kachu/Desktop/tools/pin/",
                        "/home/p1kachu/no_flo_f51e2f24345e094cd2080b7b690f69fb",
                        binary_args=" &> /dev/null",
                        length=32,
                        input_form=InputForm.STDIN,
                        fixed_chars=first_half)

# ¯\_(ツ)_/¯
flag = ic.Accurate();

And, a little while later, the Russian Anthem was played ;)

p1kachu@GreenLabOfGazon:Downloads$ ./solve1.py | ./solve2.py
[+]SUCCESS  char known:   P -> P
[+]SUCCESS  char known:   C -> PC
[+]SUCCESS  char known:   T -> PCT
[+]SUCCESS  char known:   F -> PCTF
[+]SUCCESS  char known:   { -> PCTF{
[+]SUCCESS  char guessed: n -> PCTF{n
[+]SUCCESS  char known:   0 -> PCTF{n0
[+]SUCCESS  char guessed: _ -> PCTF{n0_
[+]SUCCESS  char known:   f -> PCTF{n0_f
[+]SUCCESS  char guessed: l -> PCTF{n0_fl
[+]SUCCESS  char known:   0 -> PCTF{n0_fl0
[+]SUCCESS  char guessed: ? -> PCTF{n0_fl0?
[+]SUCCESS  char known:   _ -> PCTF{n0_fl0?_
[+]SUCCESS  char guessed: m -> PCTF{n0_fl0?_m
[+]SUCCESS  char known:   0 -> PCTF{n0_fl0?_m0
[+]SUCCESS  char guessed: _ -> PCTF{n0_fl0?_m0_
[+]SUCCESS  char known:   l -> PCTF{n0_fl0?_m0_l
[+]SUCCESS  char guessed: i -> PCTF{n0_fl0?_m0_li
[+]SUCCESS  char known:   k -> PCTF{n0_fl0?_m0_lik
[+]SUCCESS  char guessed: e -> PCTF{n0_fl0?_m0_like
[+]SUCCESS  char known:   _ -> PCTF{n0_fl0?_m0_like_
[+]SUCCESS  char guessed: a -> PCTF{n0_fl0?_m0_like_a
[+]SUCCESS  char known:   h -> PCTF{n0_fl0?_m0_like_ah
[+]SUCCESS  char guessed: _ -> PCTF{n0_fl0?_m0_like_ah_
[+]SUCCESS  char known:   h -> PCTF{n0_fl0?_m0_like_ah_h
[+]SUCCESS  char guessed: 3 -> PCTF{n0_fl0?_m0_like_ah_h3
[+]SUCCESS  char known:   l -> PCTF{n0_fl0?_m0_like_ah_h3l
[+]SUCCESS  char guessed: l -> PCTF{n0_fl0?_m0_like_ah_h3ll
[+]SUCCESS  char known:   _ -> PCTF{n0_fl0?_m0_like_ah_h3ll_
[+]SUCCESS  char guessed: n -> PCTF{n0_fl0?_m0_like_ah_h3ll_n
[+]SUCCESS  char known:   0 -> PCTF{n0_fl0?_m0_like_ah_h3ll_n0
[+]SUCCESS  char known:   } -> PCTF{n0_fl0?_m0_like_ah_h3ll_n0}
[+]SUCCESS  pass found: PCTF{n0_fl0?_m0_like_ah_h3ll_n0}
p1kachu@GreenLabOfGazon:no_mo_flow$ ./no_flo_f51e2f24345e094cd2080b7b690f69fb
PCTF{n0_fl0?_m0_like_ah_h3ll_n0}
Good flow!!
p1kachu@GreenLabOfGazon:no_mo_flow$

flag: PCTF{n0_fl0?_m0_like_ah_h3ll_n0}

This was nice, because we could clearly see that the binary had been made such that these kind of techniques would not work! Almost no reversing was necessary for this (even if we did a lot before figuring out this). A little bit of hacking never hurts ;) Thanks PPP!

You can find the binary and sripts here