Angr hooking - de/recompiling - chainbreaker

The executable that I am going to analyze here is interesting in several ways. First, no attempt at code obfuscation is made and the decompilers from both Ghidra and IDA produce code that can be recompiled with little effort. Also, the program is very short, making it a good example from an academic standpoint. The input is passed via a command line argument and so angr or PinCTF are natural first approaches to find the flag. However, there is just enough complication to prevent this from working and that is what makes this such a nice example to show progressive improvements to the angr input file using hooks. Let's see what the program does:

$ ./chainbreaker

usage: ./chainbreaker SEED

$ ./chainbreaker a

Starting chainbreaker!

ERROR

Seed must be an integer!

$ ./chainbreaker 0

Starting chainbreaker!

Seed 0 requires 96 links

LINK 1          0       ->      ERROR

Invalid chain produced!

$ ./chainbreaker 2

Starting chainbreaker!

Seed 2 requires 96 links

LINK 1          2       ->      5        Sleeping for 5ms

LINK 2          5       ->      20       Sleeping for 20ms

LINK 3          20      ->      119      Sleeping for 119ms

LINK 4          119     ->      426      Sleeping for 426ms

LINK 5          426     ->      1529     Sleeping for 1529ms

LINK 6          1529    ->      8160     Sleeping for 8160ms

[ ...]

LINK 94         2049    ->      16472    Sleeping for 16472ms

LINK 95         16472   ->      -445     Sleeping for 0ms

LINK 96         -445    ->      -1570    Sleeping for 0ms

ERROR

Starting seed doesnt match final output

Ok. The program wants an integer seed, from which it produces a chain link number and then iterates through a series of computations to check if the seed is correct. The usage of the sleep timer precludes PinCTF. It is easy to patch the program to always sleep for 0 time, but different seeds use different link sizes and that alone causes any run time differential due to the final check to drown in the signal. Another natural thing to try is angr. Lets look at the decompiled code:

The 'parse' function looks like this:

It's fairly simple code. Many of the 'std::' calls are compiler generated from higher level string functions the original author used, as described here.

Note that the input gets parsed into a 32 bit integer value. If we can get the computation to run fast enough, this challenge could be solved brute force. Since it's simple to do, first I want to try to recompile the code with some changes to optimize run time. I used Visual Studio for this case:

On a LG Gram 17 laptop, this program can try the whole 32-bit keyspace in about 15 minutes. Modern computers are awesome!

Seed ffffd32a requires 72 links

You have broken the chain!

 -11478

But this article is supposed to be about angr hooks, so lets continue there. A first crack at this should avoid code sections that 'puts' error messages and look for code paths that lead to puts("You have broken the chain!").

import time

import claripy

import angr

# specify good and bad endpoints

bad1 = (0x40149D) # ERROR\nStarting seed doesnt match final

bad2 = (0x4014AB) # usage: ./chainbreaker SEED

bad3 = (0x401461) # ERROR\nMaximum allowed iterations reached

bad4 = (0x40122C) # ERROR\nInvalid chain produced!

good = (0x401487) # You have broken the chain!

project = angr.Project("./chainbreaker", auto_load_libs=True)

#create an initial state with a symbolic bit vector as argv1

sym_arg_size = 1 #Length in Bytes because we will multiply with 8 later

sym_arg = claripy.BVS('sym_arg', 8*sym_arg_size)

argv = [project.filename]

argv.append(sym_arg)

initial_state = project.factory.full_init_state(args=argv)

for byte in sym_arg.chop(8):

    initial_state.add_constraints(byte >= '\x30') # '0'

    initial_state.add_constraints(byte <= '\x39') # '9'

sm = project.factory.simulation_manager(initial_state)

t0 = time.time()

sm.explore(find=good,avoid=[bad1,bad2,bad3,bad4])

t1 = time.time()

print (t1-t0)

found = sm.found[0]

result = found.solver.eval(sym_arg, cast_to=bytes)

print(result)

This code limits the input seed to a single digit, and yet angr has not finished hours later. And we would only get an error message at that point any way because the correct input has 6 digits and starts with a '-'. Since we already have the key, we can investigate what goes wrong. With the input modified like this:

data =    '-1147'                            # this is the start of the correct password

stringAsList = list(data);                   # turn string into list

stringAsList.append(sym_arg)                 # declare how long the 

bytestring = claripy.Concat(*stringAsList)   # turn list into bytestring

argv.append(bytestring)

print(argv)

If we ignore the fact that the answer is a negative number, we can see that the original angr input file does, in fact, find the right solution eventually - it's just very slow.

(angr) $ python angrfile 

[...]

<BV48 0x2d31313437 .. sym_arg_47_8>

['./chainbreaker', <BV48 0x2d31313437 .. sym_arg_47_8>]

[...]

813.7370481491089

b'8'

About 800 seconds for a single symbol; about 1600 for two, but after many hours 3 had not yet finished.

Next, lets patch out the delay so that angr does not symbolize it. From Ghidra, we get the addresses to hook (after rebasing the position-independent executable to 0x400000)

00401441 e8  e8  02       CALL       std::chrono::duration<long,std--ratio<1l,1000l   undefined duration<int,void>(dur

         00  00

00401446 48  8d  45       LEA        RAX => local_38 ,[RBP  + -0x30 ]

         d0

0040144a 48  89  c7       MOV        param_1 ,RAX

0040144d e8  cb  04       CALL       std::this_thread::sleep_for<long,std--ratio<1l   void sleep_for<long,std--ratio<1

         00  00

00401452 83  45  e4       ADD        dword ptr [RBP  + local_24 ],0x1

         01

And it's pretty easy to hook these calls:

def durationhook(state):

        print("0x401441 hooked")

project.hook(0x401441, durationhook, length=5) # hook this address, execute durationhook() and then skip 5 bytes, skipping the 'call' at this address

def sleep_forhook(state):

        print("0x40144d hooked")

project.hook(0x40144d, sleep_forhook, length=5) # hook this address, execute sleep_forhook() and then skip 5 bytes, skipping the 'call' at this address

An interesting fact in this case is that while the angr documentation states:

"The CFG analysis does not distinguish between code from different binary objects. This means that by default, it will try to analyze control flow through loaded shared libraries. This is almost never intended behavior, since this will extend the analysis time to several days, probably. To load a binary without shared libraries, add the following keyword argument to the Project constructor: load_options={'auto_load_libs': False} "

https://docs.angr.io/built-in-analyses/cfg#shared-libraries

the reality is that auto_load_libs has the opposite effect here.

The two hooks yield a computation time (for 1-symbolic-digit integers) of about 30 minutes. Can anything else be done for the current case? There are some messages during the angr execution that point to some potential targets:

so angr does not know that the sym_arg_size = 1 constrains these values. I have seen these warnings many times for programs that use string functions, so it's valuable to see how much of a problem this really is.

printf and puts seem obvious candidates to hook, as we don't need their output in this analysis:

Which results in a 25% run time reduction, but the messages don't all go away.

And it looks like the puts function was already hooked by the library simulation code. Re-hooking removes the call to stroq. The other calls are due to stoi and its' support calls:

std::allocator<char>::allocator(&v6);

std::__cxx11::basic_string<char,std::char_traits<char>,std::allocator<char>>::basic_string(&v5, argv[1], &v6);

inputasint = std::__cxx11::stoi((__int64)&v5, 0LL, 0xAu);

std::__cxx11::basic_string<char,std::char_traits<char>,std::allocator<char>>::~basic_string(&v5);

std::allocator<char>::~allocator(&v6);

The hooking of stoi requires quite a bit of changes, so here the complete script:

And the warnings about the unconstrained bytes disappeared:

Now an interesting thing happens, for both

initial_state.add_constraints(aux_arg <= -11470) # constrain variable to range we know the answer to be in

initial_state.add_constraints(aux_arg >= -11480) # constrain variable to range we know the answer to be in

and

initial_state.add_constraints(aux_arg <= -11400) # constrain variable to range we know the answer to be in

initial_state.add_constraints(aux_arg >= -11500) # constrain variable to range we know the answer to be in

the execution time is about 900 seconds, but for

initial_state.add_constraints(aux_arg <= -11000) # constrain variable to range we know the answer to be in

initial_state.add_constraints(aux_arg >= -12000) # constrain variable to range we know the answer to be in

After setting all these hooks, all that is left of the program is symbolic execution of the user space, but in this case angr is incapable of solving it. The hooking however does show its value. Instead of not being able to solve for even the last digit, angr can now solve 2. We also learned that the common warnings about the printf symbolization do not necessarily have to be too much of a concern.

References:

• https://bannsecurity.com/index.php/home/10-ctf-writeups/51-utctf-2019-crackme
• https://crackmes.one/crackme/5d2be1e733c5d410dc4d0d35