In this mini-series I describe the solutions of my favorite tasks from this year’s Flare-On competition. To those of you who are not familiar, Flare-On is a marathon of reverse engineering. This year it ran for 4 weeks, and consisted of 9 tasks of increasing difficulty. Collection of my sourcecodes created in the process of solving can be found in my Github repository flareon_2025.

Task 9 was the last one, and it came with a significant increase in the difficulty level compared to the earlier tasks.

SHA256 of the executable: 785a6e2bb7ce9685afe80589bbc7e28b1676e003b0041e1f74e4984044a4e551.

Overview

PE-bear

The file is a 64-bit Windows PE. Since the very first look we can see that it is quite big: 1.07 GB. When we run it from command-line, we get:

I started by opening it in PE-bear. We can spot that the .rsrc section takes the majority of space.

The natural next step in this situation would be to see the list of the resources. At first, PE-bear showed me only 50 entries in the resources directory (due to a hard-limit set in code, that is now removed; in reality there are 10000 of them). It is clear from the first look that the resources are compressed PE files. The pattern starting the header looked familiar to me from malware analysis: it is M8Z – which suggests compression with aPlib.

It can be decompressed with a Python script using malduck library (example here).

IDA

Before proceeding further I decided to take a look in IDA.

The PE files from the resources are indeed loaded, and manually mapped:

The function that loads the PEs (renamed to pass_Buffer1_and_load_libs) occurs in the function responsible for checking the license, and is called in the loop 10000 times.

This shed light on why the executable is named 10000.exe : it carries inside 10000 of different DLLs.

Extracting DLLs

After removing the hardcoded limit PE-bear was able to see all the DLLs, and dump them into a selected directory. Decompressed the full directory content with the help of the following script:

+ aplib_decompress.py

As a result I obtained 10000 DLLs, with the export tables similar to the following:

Each DLL has a long list of entries with mangled names. Two distinct types appear. There are multiple functions with a name like _Z21f00155255799705906783Ph ( format: _Z21f{number}Ph) – for simplicity, they will be referenced as “f” functions. In addition to it, each DLL has exactly only one “check” function (_Z5checkPh) .

The real names of the DLLs are stored in the Export Table, so, with the help of another script, using pefile I renamed them to the stored names.

+ rename_dlls.py

The DLLs are not just independent units. They may import each other:

As we can see, they use for it simplified version of their names – without the “.real.” part. So, in order to keep it consistent, I made a little cleanup script, that walks though all the DLLs and rename them accordingly:

+ remove_name_part.py

As a result we have all DLLs: from 0000.dll to 9999.dll stored in a directory. That is in total around 4 GB of data.

Understanding the flow

As the initial overview already revealed, the task is about checking some license file. At this point we have several questions to answer:

1. What is the expected format of the license file?
2. What is the condition that makes the license correct?
3. How does it connect to the DLLs that we just obtained?

The code of this challenge is not obfuscated, so it is relatively easy to follow. Most important actions happen in the function at VA = 0x140001e87 denoted as verify_license.

Analyzing the code of the following function, few things come to light.

• The license is supposed to be stored in the file license.bin, in the same directory as the task
• Its size is exactly 0x53020 bytes
• the content is read into a buffer, and SHA256 hash is calculated first. This hash will be used at the end.
• The license consists of 10000 chunks. Each of them is 34 bytes long. The first WORD of the chunk must be not greater than 9999. It is an index, used to decide what DLL should be used for the verification of that chunk. The appropriate DLL is fetched from the resources, and manually loaded. Then, the function “check” (mangled _Z5checkPh) is called, with the current chunk passed as an argument. If the chunk verification failed, the loop exits with an error.
• Each iteration causes an update of another, global buffer. This buffer is then compared with the hardcoded one using simple memcmp. If the comparison fails, the application exits with an error.
• If all the steps passed, the license is accepted. The previously calculated SHA256 of the license is used to decrypt the flag.

There are still some more details to figure out, but at this point we can answer the 3 basic questions:

1. What is the expected format of the license file?

• The license is expected to be exactly 0x53020 bytes long. It consists of 10000 chunks. Each chunk contains (1+16) WORDs, meaning it is 34 bytes long.

• The first WORD of the chunk denotes the ID (0–9999) of the DLL that will be used for its verification. The remaining 32 bytes are the content passed to the “check” function. The chunk is correct if the “check” function returned TRUE.

2. What is the condition that makes the license correct?

• The license must be filled with chunks that pass verification with each of the 10000 DLLs. However, the order in which the verification is performed also matters, and is unknown so far. The order of the DLLs depends on the first WORD of the chunk – so it is not just the index of the loop iteration.

3. How does it connect to the DLLs that we just obtained?

• Each DLL is used to verification of a single chunk of the license. The “check” function from the DLL is fetched and called on the buffer, and is supposed to return TRUE.

Loading a single DLL

I decided that it will be easier if I divide the problem on sub-problems, and make a loader that can run a selected “check” function from an individual DLL. At first, it looked straight-forward: just use the LoadLibrary function to load a particular module, then GetProcAddress to select the “check” function, and run it on a buffer with the data…

But something was clearly wrong – in some cases, the DLL was crashing instead of giving the output. Following execution under the debugger I found the reason. The “check” function calls multiple “f” functions – it may be from itself, or other DLLs. At the beginning of each “f” function, a global buffer is referenced, and the first DWORD of the input buffer is XORed with the DWORD pointed.

I realized that it points to DLL_base + [some offset]. The offset is different for each DLL, and sometimes goes beyond the size of one page (0x1000) – so it was clearly not intended to read from the module header. This looked weird at first, unless I checked how the original DLL is actually initialized.

In the original executable of the task, each DLL is loaded manually. So, the DllMain is also called in a custom way:

In case of a normal DLL load, the first argument passed is the DLL base – but here, the passed buffer was always the same (which I denoted as g_Buf1), located inside the main executable. That means it is a shared global buffer, used to exchange some information across different DLL runs.

This buffer is 10000 DWORDs long, and initially empty.

This fact disrupts loading the DLL by LoadLibrary – we have no influence on the parameters that are passed to DllMain along the line.

We could of course still load the DLL by a custom loader, for example using libraries such as libPEconv – but it doesn’t really give the same benefits during debugging. The DLL will be loaded in a private space, and not treated as a module, so we can’t i.e. set breakpoints at particular functions relative to the module base.

Then I came up with a much simpler idea, and decided to call the DllMain of all the relevant DLLs for the second time. First, I load the DLL of my interest by LoadLibraryA. This causes all the dependencies to load automatically – some of which are other DLLs belonging to the challenge. Once the loading completed, I walk through all the modules in memory (using Module32FirstW – Module32NextW ), and check if the module name matches the numerical pattern. If so, I fetch its DllMain (using Entry Point in the header), and call it manually, this time passing the pointer to my own buffer instead of DLL_base. Thanks to this, the internal pointers to the g_Buf1 in each DLL get updated, no longer pointing the DLL_base, but the buffer of my choice. And the DLL is ready to be used as a standalone unit.

Full code of the used loader is available in the relevant Github repository [here]

Plugging the custom g_Buf1 into the loader allowed me to run DLLs independently, and check how the input is transformed:

Of course it is not enough to pass the check, but it will be very helpful in testing the correctness of the further steps that we will implement, without always needing to run the bulky EXE.

The role of Global Buffer (g_Buf1)

By analyzing how the DLL is loaded we noticed that some information between each check is passed by a global buffer (renamed to g_Buf1). A value from this buffer, at offset relevant to the particular DLL name, is used in the chunk processing – so, it order to have the chunk check resolved properly, we need to know what exactly was passed.

The buffer is initially empty. But at the end of processing, if all chunks are verified properly, it is compared by memcmp with another, non-empty, hard-coded buffer (referenced as a Validation Buffer: g_ValidBuf). That means that we need to recreate the conditions, under which, during the processing of all chunks, the Global Buffer will be filled with the same content as Validation Buffer. That leads to another question: how and when is this buffer filled?

The Global Buffer is referenced in 4 places:

First, reference, that we already saw earlier, is in the function that manually loads the DLL. At that point, the buffer is just passed to the manually called dll_main. Another known reference (the first from the bottom) is in the verify_license function – where the comparison with Validation Buffer is made. There are two middle references that we didn’t explore yet, inside the function that I denoted as add_stuff_to_Buffer1. This function is called in the loop that is responsible for checking a single chunk of the license. It has one argument, that is an index of the iteration (not to be confused with the index of the DLL).

This function iterates over a vector, and uses it to resolve at what position the current index will be added.

This vector is created at the DLL load, and contains all the manually loaded DLLs that are available at the current time. It contains elements of the structure that is used to keep track on the manually loaded buffers. Each element contains the DLL id (that is the same as the ID of the resource from which the DLL was loaded: resID). Fragment of this logic presented below:

Now, this resource ID is mapped to the DWORD in the g_Buf1. This means: the currently checked DLL and all its recursive dependencies are representing fields of the g_Buf1 where the index of the current iteration will be added.

This knowledge will be helpful in reconstructing the order of the DLL loads. Once we know the proper order, that allows to recreate Validation Buffer, we know how to fill the first DWORD of each chunk.

But before we dive into this part, let’s have a look how the rest of the chunk is validated.

The “check” function

The prototype of the “check” function is very simple. It takes the pointer to a 32-byte long chunk.

int check(BYTE* chunk);

The “check” function in each DLL is structured following the same template. Let’s start by getting a general overview of what is going on. Our goal is to use what we learned by analyzing this function to reconstruct the corresponding chunk in a way that it will pass the verification.

First, there are multiple calls to the “f” functions. The referenced functions can be from the current DLL, or from any of the imported ones. Each call to the “f” function transforms a chunk in some way.

The detailed analysis of this part will be described further in this blog.

After this preprocessing, there comes the part of the task that requires more advanced math knowledge.

Matrix exponentiation and its inverse

The second part of the check seems complicated. I decided to use AI to get the explanation of what exactly is going on. It turns out that this is a key verification, using modular matrix exponentiation.

The pseudo-code that I obtained from one of the analyzed DLLs:

/***************************************************************
 *  check(chunk : byte *)  →  bool
 *
 *  Validates ‟chunk” against a baked-in public key / signature. 
 *  The code is heavily obfuscated, but when cleaned up it becomes:
 *
 *      Step 0  – run a pipeline of reversible scramblers on chunk
 *      Step 1  – build a 16-element vector  V  from chunk
 *      Step 2  – ensure every element of V is < P 
 *                (P is a prime)
 *      Step 3  – compute a long chain of modular operations  
 *                (lots of   a·b  mod P)
 *      Step 4  – if the final scalar  s  is 0   ⇒  reject
 *      Step 5  – raise a 4×4 matrix  M  to a 64-bit exponent e
 *                (again mod P)
 *      Step 6  – compare the resulting 4×4 matrix with a baked
 *                constant reference; return true when equal.
 *
 *  That is exactly what RSA-PKCS-1 style “textbook signature
 *  verification” looks like once flattened by a compiler and
 *  obfuscated by a packer.
 ****************************************************************/

function check(chunk : pointer to uint8) returns bool
{
    /********************  STEP 0 – scramble the input  ********************/
    for  f in HUGE_PILE_OF_HELPERS                      // 200+ calls
        f(chunk)                                        // reversible mixers / S-boxes

    /********************  STEP 1 – build initial vector  ******************/
    V[0‥15]  ← read16BigEndianQwords(chunk)             // two qwords per limb

    /********************  STEP 2 – range-check against prime P  ***********/
    P  ← 0xDC37C0E3 04978087 594B7F91 F11228E5          // 127-bit prime
    for i in 0‥15
        V[i]  ← V[i]  xor  chunk_qword[(i mod 4)]       // small secret tweak
        if V[i] ≥ P                                     // any limb ≥ P  ⇒  reject
            return false

    /********************  STEP 3 – massive modular arithmetic  ************/
    /*
       From here to the next comment the code is nothing but
       sequences like

          tmp   = (A * B) mod P
          A     = (tmp * C) mod P
          …
       where P is always the same prime and  A,B,C are 128-bit
       intermediates.  The compiler emitted calls to the helper
       “unsigned_modulus()” we reverse-engineered earlier.

       The net effect is:
           s =  complicated_function(V, built-in constants)  mod P
     */
    s = complicatedScalarComputation(V, P)              // ≈400 lines in IDA listing

    /********************  STEP 4 – reject when s == 0  ********************/
    if s == 0
        return false                                    // invalid input

    /********************  STEP 5 – modular-matrix exponentiation  *********/
    /*
       A 4 × 4 matrix  M  (elements mod P) is assembled from the
       current scratch area.  Then a classic square-and-multiply
       is performed with exponent e = 0x594B7F91F11228E5.

       Only the bit positions set in e trigger a matrix multiply,
       hence the ‟if ((e >> k) & 1)” branch inside two nested 4×4
       loops you saw in the disassembly.
     */
    M      ← matrixFrom(V)          // 4×4, limbs are 128-bit ints mod P
    e      ← 0x594B7F91F11228E5
    Result ← IdentityMatrix(4)

    for bit = 0 .. 63
        if (e >> bit) & 1
            Result = (Result × M) mod P
        M = (M × M) mod P           // always square (Montgomery ladder)

    /********************  STEP 6 – compare with golden reference  ********/
    Golden[4][4] =
    [
      0x65DE31EF76B34C5E, 0xBF9224AA780960BA, 0x944C61FE664D8A46, 0x85FFAACD31F816D1,
      0x5FE739DE69B61B49, 0x4362AB9DFD8274E5, 0xC90B9E6AC29A84EC, 0x661807122A7615D7,
      0x2367A1BF2B936D7C, 0x289E160527983DEF, 0xB0E4B274464C4BFD, 0x5222046DFEF7B826,
      0x6158769ED8530622, 0x056EABD584B51A70, 0xA5B7C08151FFACE8, 0xC7B8D0A6D71A6E00
    ]

    /*
       The SIZE[] table you saw (1,0…0,1,0…0…) is just the list
       of ‟valid” bytes in Golden that must be compared; the rest
       is padding turned to zero by memset().
    */
    if memcmp_masked(Result, Golden, Size) == 0
        return true
    else
        return false
}

/****************************************************************
 * Helper  – compares only the bytes whose corresponding Size[i]
 *           entry is 1.  (Exactly what the memset/Size[] dance
 *           in the assembly achieves.)
 ****************************************************************/
function memcmp_masked(a, b, Size[]) returns int
{
    for idx = 0 .. (sizeof(Size)-1)
        if Size[idx] == 1 and a[idx] ≠ b[idx]
            return ‑1
    return 0
}

It may be confusing at first why AI mapped those arguments as 128-bit, but looking how they are mapped in memory reveals that the rest is just a padding:

To understand the whole implementation better I reconstructed this part in C/C++. Snippet here.

Because the exponent e and modulus P are known constants, and the operations are deterministic, this transformation can be inverted: meaning that given the final matrix, we can compute the required pre-image. So this is how we will further approach solving this part.

To implement the inverse, once again I used the power of AI, and this time Python (because the solution requires access to bigint library, and it works seamlessly in Python).

The snippet that I used for testing the complete reverse of a single chunk is available here.

The “f” functions

In order to revert the whole check, and obtain the initial buffer, we still need to understand the first part of the check function, which is a block of calls to different “f” function. Although their volume may be intimidating, in fact there are only 3 types of “f” functions. What differs between them are the hard-coded arguments.

I started by reimplementing each type, and making their arguments external rather than internal.

Example:

Reimplemented:

BYTE* f_type2(BYTE* arg1, size_t dll_id, const uint64_t kQargs[33])
{
    DWORD* arg1_d = (DWORD*)arg1;
    DWORD* verif = (DWORD*)g_Buffer1;
    arg1_d[0] ^= verif[dll_id];

    for (size_t i = 0; i <= 31; ++i)
    {
        arg1[i] = *((BYTE*)kQargs + arg1[i]);
    }
    return arg1;
}

The snippet illustrating all types is available in the relevant GitHub repository, here.

I passed my reconstructed code to GPT Chat, and prompted it to invert those functions. The result that I’ve got worked very well. It can be found here.

Summing up, we reached the conclusion that all operations done in the “check” can be fully inverted, and the buffer that is used at the end for the chunk verification, can be used for chunk reconstruction.

The biggest problem to solve now is, how to extract all the needed arguments from each function, to make chunk recovery at scale?

Parsing DLLs

This is one of the most tedious part of this task, but it can’t be avoided. We have to parse all the 10000 DLLs, one by one, extract their arguments, and store for further use.

Since this task requires parsing a massive amount of data, I decided that instead of doing it with a Python script, I would use a native compiled application.

I already have a utility that could easily become a base. It is a simple, multiplatform command-line disassembler based on bearparser and capstone. It can be found here. The utility loads a given PE file, and dumps disassembly of the function with a supplied name. It automatically applies information found in the PE structure. For example, it resolves imported functions. This is important in our case – we will not only operate on a raw assembly. We also have to make a list of all “f” functions needed for each “check” function, and their sequence.

I decided to divide the task of parsing into two stages.

Dumping arguments of the “f” functions

In the first stage, I refactored the disasm-cli, and made a version optimized for this task only. It is available here.

Instead of loading a single DLL at the time, and dumping a single function, it walks through a directory, and loads sequentially DLLs that match the pattern of the numeric names, in the defined range. Then, once it loaded the DLL, it walks through all the exports from the given DLL, and filters out all the entries that don’t match the pattern of the “f” function name. Now we can focus on extracting the needed arguments from the “f” function, as well as its type.

Since the functions of each type has distinct length, we can guess the type simply by looking how many lines of disassembly they produce. This is how I implemented the type recognition:

int get_func_type(size_t count)
{
    if (count == 172 || count == 173)
        return 1;
    if (count == 98 || count == 99)
        return 2;
    if (count == 56 || count == 57)
        return 3;
    return 0;
}

The arguments are always loaded by "movabs" and they are always put in a known order. Example:

; 0000.dll._Z21f38236877289593244403Ph
[...]
22415f6a9 : mov byte ptr [rax], dl
22415f6ab : movabs rax, 0x22f130e6fafe934b
22415f6b5 : movabs rdx, 0x777fd23eb0b83b25
22415f6bf : mov qword ptr [rbp - 0x60], rax
22415f6c3 : mov qword ptr [rbp - 0x58], rdx
22415f6c7 : movabs rax, 0xf605c9124bc28c77
22415f6d1 : movabs rdx, 0x59263089104bc46b
[...]

So once we have the “f” function’s start and end, we can simply parse all the movabs lines and store their values.

The cli program produces CSV files, logging arguments of all the found “f” functions from all the parsed DLLs.

Format:

dll_name,func_name,func_type,[ arg0 arg1 ...]

Example of the output:

0000.dll,_Z21f92961177136248183669Ph,1,[ 0x4424e37bb62cc35f 0xc1bc82578497fd19 0xd183214321ad80c1 0xfb1788c5e6d0b56e ]
0000.dll,_Z21f47243230667592677056Ph,2,[ 0xa0d8041e1fd3377a 0xc77ea7007b565897 0x149a47dfd54ef22d 0xc3fa2520f95a59f 0x95f77b9a8db2a26 0x6baebf39803325a3 0x538719f9d1f5af8a 0x2710983692826288 0x914184e8b76f05c2 0x6915cfc4f0c9900a 0xe075bdac8b3bb383 0xf186de7307ff1724 0x8cf47dc6a1b29c4f 0xd22b504d3d9dbb21 0x5cd7cafb302e641d 0xc8ad893c79205e48 0xb6ef599b40fa43dc 0x6ec0b4b44c37813 0x66816c605a18d649 0x168d8e961c8522e4 0x93354ad401e1fe9e 0x1a724cdde3f6b52c 0xcc236acdc1ab1b94 0x707faafdb0ed7165 0xbae93ae629f36367 0xe245a612618fea08 0x5d340338f776fc31 0x68a955d9dabcb4ce 0xebd054be0d99f8c0 0xb1ee4232b82fcb74 0x5b116e7ca40ee751 0x3ee56d465702c528 ]
[...]

Those results will be then loaded to the next parser, that will reconstruct all the input needed to reverse a single “check” per DLL.

Dumping arguments per DLL

The real goal to achieve in this part is to dump all the arguments that will let us solve a single chunk. That means. we will walk thought the set of DLLs, parse the “check” function of each DLL, and reconstruct the data needed to resolve it, including:

1. An ordered list of “f” functions, along with the arguments of each, and along with the ID of the DLL where the function comes from (the DLL ID is the same as the offset of the value in g_Buf1 with which the first DWORD of the chunk is XOR-ed at the beginning of the “f” function).
2. All the arguments used for the second part of the “check”. That means the definition of the matrix, e, and P, that will be used to its exponentiation, as well as the result that is expected. At this point we can also do the matrix inverse, and pre-calculate the content of the buffer that was expected at the beginning of this part (incorporating the script created earlier).

The previously generated CSV files with arguments mapped per particular “f” function will be used as lookup tables in the first part of the resolution.

For the convenience of parsing, I decided to first convert the CSV file into a pickle format. The used script is available here. This parsing transforms the simple list (where each line represents as single “f” function along with its list of arguments) into a mapping of objects.

rec = parse_line(line)
key = f"{rec.dll}.{rec.func}"
mapping[key] = rec

The generated pickle file is then use in a new script, that resolves the “check”.

The second script makes use of the original disasm-cli utility from the beardisasm repository. Since we are interested in disassembling one function at the time, the basic functionality will be sufficient, and we don’t have to extend it. The Python script will be a wrapper calling the original executable whenever the disassembly is needed.

def dump_check(dll_name, fmapping, out_dir):
    func_name = "_Z5checkPh"
    wrapper = DisasmCLIWrapper(DISASM_PATH)
    lines = wrapper.disasm(DLLS_PATH + dll_name, func_name)

    values = extract_values(lines)
    cfunc = CheckFuncWrapper(dll_name, values)
    cfunc.solve()
    
    raw_func_list = extract_dll_and_func(lines)
    for dll_func in raw_func_list:
        if not dll_func in fmapping.keys():
            print(f"Function not found: {dll_func})")
            dll, func = dll_func.split(".dll.", 1)
            # fail-safe: resolve if not found:
            dump_func(dll + ".dll", func, cfunc.funcs_list)
            continue
        rec = fmapping[dll_func]
        cfunc.funcs_list.append(rec)

    out_file = out_dir + "//" + dll_name + ".resolved.txt"
    pkl_file = out_dir + "//" + dll_name + ".pkl"
    save_cfunc_as_pickle(cfunc, pkl_file)
    
    with open(out_file, "w", encoding="utf-8") as f:
        m0_hex = [f"0x{v:x}" for v in cfunc.m0]
        f.write(f"Precalculated: {m0_hex}\n")

        for func in cfunc.funcs_list:
            f.write(f"{func}\n")
    print(f"{dll_name} -> {m0_hex}")

The implementation contains also a fail-safe option, to cover the possibility if some “f” function was not found in the previously loaded lookup. In such case, the script will call the basic disasm-cli tool to dump this function from the specific DLL, and parse to the same format as it was used by the original lookup:

def dump_func(dll_name, func_name, funcs_list): #0000.dll
    wrapper = DisasmCLIWrapper(DISASM_PATH)  # or just "disasm-cli" if on PATH
    lines = wrapper.disasm(DLLS_PATH + dll_name, func_name)
    ff = FFuncWrapper(dll_name, func_name, get_func_type(lines), extract_int_values(lines))
    funcs_list.append(ff)
    print(ff)
    if ff.type == None:
        print("WARNING: %s : %d" % (func_name, len(lines)))

As a result, we get a completed report, one per DLL, that has all the data required to resolve the relevant chunk. Preview (0000.dll_listing.txt):

Precalculated: ['0x5a4e7d2f5af00585', '0x73e25c25e161d3e6', '0x57c73d52ba18cb4', '0x47ae048873095840']
CheckFuncWrapper(dll=0000.dll, p=0xdc37c0e304978087, e=0x594b7f91f11228e5, xor=['0x264f1c2a310e43aa', '0x6f62577ddb8f7c8', '0x2f5eef5c62186c64', '0x3b278b1ea0e08e88', '0x30b6b0678e48aee', '0x5857a70651b71bd1', '0x11328681bbf8806a', '0x46a52df6f08b2685', '0x5b5746a4910ca7fd', '0x4fce2f265662e21', '0x32a013dc0e0f538a', '0xfffec7ae2c6f8f79', '0x3b0ad6e24be21f00', '0xd285721394b26b6f', '0x49ff24112a0c1a2e', '0xf3a55fbbc4837e78'], m0=['0x5a4e7d2f5af00585', '0x73e25c25e161d3e6', '0x57c73d52ba18cb4', '0x47ae048873095840'], m1=['0x7c0161056bfe462f', '0x751479523cd9242e', '0x2a229c8949b9e0d0', '0x7c898f96d3e9d6c8', '0x5945162922148f6b', '0x2bb5fb23b0d6c837', '0x144ef55490590cde', '0x10b297e83827ec5', '0x1193b8bcbfca278', '0x771ebed78407fdc7', '0x37dc600925aedf3e', '0xb850c3265f66d739', '0x6144abcd11121a85', '0xa1672e3675d3b889', '0x4c8357c401ad969a', '0xb40b5b33b78a2638'], m2=['0x65de31ef76b34c5e', '0xbf9224aa780960ba', '0x944c61fe664d8a46', '0x85ffaacd31f816d1', '0x5fe739de69b61b49', '0x4362ab9dfd8274e5', '0xc90b9e6ac29a84ec', '0x661807122a7615d7', '0x2367a1bf2b936d7c', '0x289e160527983def', '0xb0e4b274464c4bfd', '0x5222046dfef7b826', '0x6158769ed8530622', '0x56eabd584b51a70', '0xa5b7c08151fface8', '0xc7b8d0a6d71a6e00'])
[...]

Link to the full report here.

This report will be loaded in another tool, that will finally help us regenerate the full license. But still one thing is missing to reconstruct the chunk. As mentioned earlier, at the beginning of each “f” function, there is an additional XOR with a DWORD. That DWORD comes from the global buffer (DWORD xor_key = g_Buf1[DLL_id]). The problem is, the value of g_Buf1 changes on each iteration of the loop that verifies chunks. And the way in which it changes depends on the DLL order. This leads us to another problem of this task: figuring out the proper order.

Reconstructing DLLs order

In the part “The role of Global Buffer (g_Buf1)” I described how on each iteration of the chunk verification loop, the shared global buffer is updated. The list of all the manually loaded DLLs that are present at current point, is iterated over (that means: the DLL immediately assigned to check the sample, plus its direct and indirect dependencies). Indexes of those DLLs point a specific DWORD in the g_Buf1 where the index of the current iteration will be added.

That’s why, to really map all the positions that changed when the particular DLL was used, we first need to have a complete list of dependencies for each DLL.

Mapping dependencies

To map those recursive dependencies, I used a simple tool based on libPEConv (the full code is here). One of the basic features of libPEConv is its ability to define a custom DLL resolver. For the current task, I created the following one:

class my_func_resolver : peconv::t_function_resolver{
public:
    my_func_resolver(dll_deps& _my_deps)
    : my_deps(_my_deps)
    {
    }

    FARPROC resolve_func(LPCSTR lib_name, LPCSTR func_name)
    {
        WORD num = (-1);
        if (!getDllId(lib_name, num)) {
            return nullptr;
        }
        if (!isNumericDLL(lib_name)) return nullptr;
        my_deps.deps.insert(num);
    }
    dll_deps& my_deps;
};

This resolver is plugged into the custom PE loading function implemented in libPEConv. Loading one DLL will cause a mapping of its immediate imports.

Once we have such mapping for each of the 10000 DLLs, we can recursively populate it. So, for example if the DLL 1 imports 2,7,9 as immediate imports, we will include to its final list of imports also the imports of 2,7,9, and so on (of course not allowing duplicates) – till we collect the complete list.

Reconstructing the DLL order

Even having the full DLL dependency mapping, reconstructing the order is still not so straight-forward. We know which positions have the index added when the DLL is loaded – but how can it help?

The key to solve it lies in the observation, that there are some DLLs in the set that have been loaded exactly once during the whole execution. That means, at their corresponding position in the g_Buf1 there is the actual index of the iteration where this DLL was used (and not a sum of multiple indexes).

The following listing shows the DLLs that are not dependencies of any:

DLL: 675 : 0
DLL: 788 : 0
DLL: 933 : 0
DLL: 1657 : 0
DLL: 1678 : 0
DLL: 2016 : 0
DLL: 2356 : 0
DLL: 2704 : 0
DLL: 2735 : 0
DLL: 2861 : 0
DLL: 2921 : 0
DLL: 3214 : 0
DLL: 3927 : 0
DLL: 5046 : 0
DLL: 6115 : 0
DLL: 6547 : 0
DLL: 6976 : 0
DLL: 7041 : 0
DLL: 7326 : 0
DLL: 7982 : 0
DLL: 8373 : 0
DLL: 8470 : 0
DLL: 9888 : 0
Counter: 23

The final stage of the g_Buf1 is saved in the hard-coded buffer, that I denoted as Validation Buffer. That means, we can retrieve those indexes from there.

The above listing with the DLL position appended:

DLL: 675 : 0 pos: 738
DLL: 788 : 0 pos: 498
DLL: 933 : 0 pos: 3302
DLL: 1657 : 0 pos: 2222
DLL: 1678 : 0 pos: 1539
DLL: 2016 : 0 pos: 5736
DLL: 2356 : 0 pos: 4567
DLL: 2704 : 0 pos: 3882
DLL: 2735 : 0 pos: 8186
DLL: 2861 : 0 pos: 3606
DLL: 2921 : 0 pos: 6060
DLL: 3214 : 0 pos: 9696
DLL: 3927 : 0 pos: 608
DLL: 5046 : 0 pos: 2383
DLL: 6115 : 0 pos: 5903
DLL: 6547 : 0 pos: 3890
DLL: 6976 : 0 pos: 1842
DLL: 7041 : 0 pos: 1817
DLL: 7326 : 0 pos: 1007
DLL: 7982 : 0 pos: 1301
DLL: 8373 : 0 pos: 4892
DLL: 8470 : 0 pos: 5365
DLL: 9888 : 0 pos: 4732
Counter: 23

Those DLLs are not dependencies of any other – so they have been loaded only once. However, during their load, their dependencies has been loaded. That means, at the index in g_Buf1, that represents each of their dependencies, there is a value representing: previous_sum + current_index .

If we subtract the current_index from the appropriate records in the Validation Buffer, what remains is the previous_sum. And in some cases, the previous_sum is just one value (if the DLL represented by it was not a dependency of any BUT the last processed DLL). So, we can repeat the whole subtraction method recursively, in each round obtaining more load indexes.

The program reconstructing the complete order is available here.

The listing showing the recovered order is available here.

Reconstructing the license

At this point, we have all the ingredients to prepare the correct license.

1. Arguments to reverse the “check”:
   • full sequence of the “f” functions, their arguments, and the output they produced (that we obtained by calculating the inverse of the matrix from the final comparison).
   • the order of the DLLs that allow us to reconstruct the content of the g_Buf1 at the point where the DLL was loaded, and therefore, the correct XOR value.
2. The inverted version of each “f” function

The full program recreating the license based on the supplied data is available here.

The beginning of the valid license demonstrated here:

The full file can be found in the repository.

Decrypting the flag

I decided the simplest way to decrypt the flag would be by using the original executable. However, we will skip the part that does the license verification, since it takes too much time.

I loaded the original executable in X64dbg, and simply patched it to jump over the part of code responsible for checking each chunk in the loop.

I earlier checked some chunks individually using my custom loader, so at this point I am quite confident that the obtained file is valid.

I allowed the original program to calculate the SHA256 of the file, and then to use it as an AES key, to decrypt the buffer. This is how I’ve got the final flag!

"Its_l1ke_10000_spooO0o0O0oOo0o0O0O0OoOoOOO00o0o0Ooons@flare-on.com"

Flare-On is an annual CTF run by Mandiant Flare Team. In this series of writeups I present solutions to some of my favorite tasks from this year. All the sourcecodes are available on my Github, in dedicated repository: flareon2024.

The 9th task was undoubtedly the most difficult one this year. It is called “serpentine” – but despite the name, it is not a crypto challenge involving Serpent cipher. This is what the description says:

We are provided with a PE loading an obfuscated, self-modifying shellcode, and using exception-based flow obfuscation. Those elements remind of some hard tasks from the previous editions, such as “evil“, and “break” that I previously described. But the way they are served is yet different.

Overview

I started by opening the given executable in IDA. First thing we can notice is that it requires a password given as a commandline argument. It has to be 32-character long. If we supplied it, the program proceeds to run a shellcode. All the logic related to the password verification happens there.

The shellcode is hardcoded within the PE, and copied to a dynamically loaded memory in a TLS callback, before the main function was executed:

Analyzing the shellcode is a real challenge. It deobfuscates itself as it goes, and then obfuscates back. The flow is also interrupted by HLT instructions, that are causing an exception handler to trigger. It does not only makes our code to jump into an unexpected line, but also changes the execution context on return, making the whole logic very confusing and hard to follow.

Oftentimes, such cases can be helped to a big extent by a Pin tracer. I first tried to trace it with Tiny Tracer, but unfortunately, due to the specifics of this self-modifying code, the tracing followed only the initial part of the binary:

[...]
15770;kernelbase.InitializeCriticalSectionEx
14ab9;CPUID:1
20cb;kernel32.SetUnhandledExceptionFilter
14de;ntdll.RtlInstallFunctionTableCallback
15c4;kernel32.SetUnhandledExceptionFilter
1649;called: ?? [196f0000+0]
> 196f0000+0;ntdll.KiUserExceptionDispatcher
a736;ntdll.RtlAllocateHeap
116d;ntdll.[TpReleaseIoCompletion+1cc]*
> 196f0000+98;called: ?? [199d4000+d27]

Soon after the shellcode started, PIN exits with an error:

E: During exception handling, an inconsistent instrumentation had been found.

EDIT: it turns out that it is possible to trace the self-modifying part with PIN as well, we just need to add an option -smc_strict 1 – which means “Check for self-modifications inside basic block” (suggested by: aziz). Still, cleaning the code before the tracing, and removing the parts related to obfuscation, help a lot to keep the tracelog focused on the functionality, and reduces the need of its post-processing.

Exception handlers

As mentioned before, the HLT instructions, and the exception handlers (SEH) that they trigger, play a very important role in how this executable is obfuscated. After the exception, the code resumes its execution at a very different and unexpected address. If we don’t follow it, we lose the track.

At first, I tried to dump all the handlers addresses with the help of x64dbg. Each new exception handler is called via ntdll.RtlpExecuteHandlerForException . The redirection happens by call rax. By setting a breakpoint at this instruction, and editing the details, we can log the handler’s address. All the visited handlers will be saved in the listing at the log tab.

Soon I realized that there are too many blocks to resolve, and this is not the best way to dump them all. To really tackle this part, I have to parse the exception information.

In a typical case, the (SEH) exceptions thrown by a Windows binary are handled using the information stored in the Exception Table, that is a part of the PE format. However, this way of registering exceptions only work if they are thrown from within the corresponding PE image. In the current case, the exceptions are thrown from a shellcode, that is in a dynamically allocated, private memory. So the corresponding handlers have to be installed manually. In 64-bit Windows binaries it can be done with the help of the function RtlInstallFunctionTableCallback. However, this function is nowhere to be found in the Import Table of our executable, and by looking in IDA, it is difficult to spot where it is called. Fortunately, in this particular part, the trace done by Tiny Tracer comes in handy. We can see the following calls in the TAG file:

20cb;kernel32.SetUnhandledExceptionFilter
14de;ntdll.RtlInstallFunctionTableCallback
15c4;kernel32.SetUnhandledExceptionFilter

When we apply the tags in IDA, it clarifies a lot.

As the MSDN says, one of the arguments of RtlInstallFunctionTableCallback is a callback function to be installed. This callback is then executed each time an exception in the defined range gets hit. It is responsible for associating the exception with the relevant UNWIND_INFO: a structure containing all information needed for handling it. It includes the address of the handler to be called, and unwinding codes that define how the stack should be modified before the handler gets executed.

The installed callback is implemented as follows:

Analyzing the code of the callback function we can find where exactly the UNWIND_INFO is retrieved from. It turns out all is stored along with the shellcode. The offset to the structure is right after the HLT instruction (Rip + 1). Parsing this information will be crucial for deobfuscation.

Deobfuscation

The approach that I have taken is to first deobfuscate the binary as much as I can in order to clarify what is really happening, and then to trace it by a dedicated PIN tracer.

To do the deobfuscation, I have chosen Capstone Engine (for disassembling) and Keystone engine (to assemble back the cleaned code). Both of them are open source libraries with Python bindings, created by the same author.

There are two main problems to tackle:

1. Deobfuscating code blocks: cleaning all what happens between one ‘halt’ and the other. Removing all the redundant instructions, and stopping code from obfuscating itself back
2. Deobfuscation of the flow: figuring out what will be the next block after the HLT. Understanding and preserving all the changes done to the context at each exception.

The full code of the deobfuscator is available in the dedicated github repository: https://github.com/hasherezade/flareon2024/tree/main/task9/deobfuscator

Deobfuscating code blocks

Let assume a single block is a series of instructions that are executed between two halts. The vital code is revealed as the execution proceeds, and it is hidden in between the lines which only role is obfuscation. Retrieving of the vital lines is done following a predictable pattern. Example is given below.

First, call-to-pop is used to store the address of the beginning of the block at a particular offset:

The return address is popped into a further line of the block:

The next code modification is done by retrieving a byte from the code at the given offset, doing calculation on it, and storing the result back into the code, to one of the next lines of the block:

After the deobfuscated line is executed, it is overwritten by a constant.

The return address that was previously popped is used in the calculations for the new return.

The return address is calculated relative to the first address of the block, from where the call was made.

Then we may have a few vital lines, till another call is used to repeat the above pattern. We finally reach the HLT instruction, that terminates the block.

Using Capstone Engine via Python, I decompiled the dumped shellcode, implemented the steps done in order to deobfuscate the further lines, and skipped those that obfuscate the code back. After that, I filtered out the lines that were related to obfuscation, leaving only the vital code.

Examples of reconstructed blocks for the initial handlers:

######
### Handler RVA 0x98:
0x8 -> 0x2e4d49: movabs r11, 0x10add7f49
0x1 -> 0xa2: push r11
0x2 -> 0xa4: push 0x73775436
0x3 -> 0xa9: push 0x68a04c43
0x4 -> 0xae: push 0x12917ff9
0x8 -> 0x2e4db8: add qword ptr [rsp + 0x18], 0x35ac399f
*****
######
### Handler RVA 0x1a7:
0x1 -> 0x1a7: mov rbp, qword ptr [r9 + 0x28]
0x8 -> 0x2e4e8c: mov rdi, qword ptr [rbp + 0xe0]
0x1 -> 0x1b2: movzx rdi, dil
*****
######
[...]

https://gist.github.com/hasherezade/0ad2bd3612b43bbde500525443405fe3

This makes the code blocks much more readable. To clean it further, we can also resolve the calculated values, such as:

mov rbx, 0xffffffffd5d48854
add rbx, 0x2a743cac

Which can be resolved to:

mov rbx, 0x48C500

It not only lets us see some of the constants clearer, but also reveals the referenced offsets. For example, we can see where the address of the function showing the “Wrong key” message is loaded.

Deobfuscating the flow

The flow is still obfuscated using exception handlers, so we don’t know what will be the next block executed after the halt instruction. (Except for the few initial handlers, dumped earlier using x64dbg.)

Following the implementation of the callback function that was registered to resolve the exceptions, we can find the unwind information in the shellcode, at offset relative to the offset of the HLT instruction. It is calculated by the following formula:

begin = halt_offset
end = begin + 1
unwind = end + g_code_buffer[halt_offset + 1] + 1
unwind += unwind & 1

The format of the unwind information is documented on MSDN. Following the specification, I wrote a parser in Python: handlers_parser.py. Initially, the parser simply walked through the dumped shellcode, searching for the byte representing HLT (0xF4). Having found that, it tried to calculate the offset of the unwind information, relative to it. Of course this method was not fully accurate, because not every 0xF4 byte really represented HLT, so additional filtering was required – but it allowed to produce an initial listing. After refining the parsing of the unwind info, I integrated it into the main deobfuscator, and was able to produce a complete listing. It showed the full flow of execution – the halt instructions, associated unwind codes, and the handler that got executed.

Rebuilding the binary

Now we have everything that we need in order to rebuild the deobfuscated binary. Well – almost. Although we know what handlers will be executed in which order, it is not enough to simply replace the HLT instructions with the jumps to appropriate addresses. Flow redirection is only a part of the functionality that they implement. The other part is the change in the context.

We know that some adjustments are made basing on the unwind codes. For example:

######
### RVA 0x98:
0x8 -> 0x2e4d49: movabs r11, 0x10add7f49
0x1 -> 0xa2: push r11
0x2 -> 0xa4: push 0x73775436
0x3 -> 0xa9: push 0x68a04c43
0x4 -> 0xae: push 0x12917ff9
0x8 -> 0x2e4db8: add qword ptr [rsp + 0x18], 0x35ac399f
*****
> Index: 1
	Version: 1 ; Flags: 1 ; SizeOfProlog: 0 ; FrameReg: 0
# HLT at 0x107 ->	Handler: 0x1a7
	op_code: 10 ; op_info: 0 ->	UWOP_PUSH_MACHFRAME ; Nodes: 1
	op_code: 1 ; op_info: 1 ->	UWOP_ALLOC_LARGE ; Nodes: 3
		Arg0: 0x4
	op_code: 0 ; op_info: 13 ->	UWOP_PUSH_NONVOL ; Nodes: 1
		R13
######

One way to deal with it is to rebuild manually all what those instructions do, and implement the equivalent functionality. Eventually, I decided to go a different way, that appeared to me less error-prone. Rather than reimplementing the change in the context on my own, I left the HLT instructions in place to do their job, and rebuilt just the code around them. To leave the whole logic intact, we must ensure that the HLT instructions, and the exception information that belongs to them, is left at the expected offsets, and is not corrupt in any ways by other changes in code.

So, in order to have both, the cleaned code, and the original exceptions, I decided to add to the original binary two sections. The first section (that will be referred to as “original”) will contain the original shellcode, with the HLTs at their initial places, and with all the unwind info intact. The second section (that will be referred to as “cleaned” or “debfuscated”) will contain the rebuilt code. The execution will be transitioning between them. Whenever the exception is about to be called, the deobfuscated code will jump to the original code at the offset where the corresponding HLT is. This will trigger the exception that will be resolved by its corresponding info, with particular unwind codes. The exception handler will start to execute in the original section, at the address defined by the unwind info. But now, this address will contain jump back to the deobfuscated section, so that it can continue with the changed context.

Reconstruction of the code is done by the following script: capstone_deobf.py. The script is also aware of at what address the HLT should be called, and produces the jump to the original section at the particular offset. It also create an additional listing of offsets and jumps that will be used for the return from the original section back to the deobfuscated one, at the beginning of the new handler. This listing will be used for patching of the original section, and applied by another script: keystone_patcher.py.

Before we add the new sections, the challenge executable also needs some adjustments. Originally the shellcode is loaded into dynamically allocated memory – now we want it to load from the static address: a new section attached to the PE. This requires patching of the function that did the loading. Another issue is, since the shellcode is now the part of the PE image, its exceptions will be managed by the Exception Table from the PE headers. In order to register the custom exception handlers, we need to first remove the existing Exception Table from Data Directory, The patched binary may look in the following way: serpentine_shc_static_base.exe

After those adjustments we are ready to add the new sections.

Section 1 – the “original” shellcode:

Section 2 – the deobfuscated shellcode:

The jumps are the replacements for each HLT instruction, and they cause execution of HLT within the first section. The rest of the code executes in a linear way, and is easy to observe under the debugger.

The logic of password verification

At this point we can notice that the password verification is done in 32 roughly similar blocks. Each block ends with the comparison:

movabs r15, 0x1400011f0 ; R15 -> wrong_password
test r14, r14; is result 0?
lea r12, [rip  + 0x7]
cmovne r12, r15; if not, move the offset to wrong_password to r12
jmp r12; jump to R12

During the execution of the block, some chunks of the input are being fetched and processed. The result of executed calculations must be equal to 0, otherwise the program jumps to the function displaying “Wrong password” message.

The goal of the task becomes clearer: we need to reconstruct those 32 equations, and resolve them. But since it is so much code, it is impossible to do it manually. Some sort of automated tracing is needed. For this purpose I decided to use Intel Pin.

By definition, we can trace only the code that was executed: so we have to make the execution proceed till the end regardless of the given input. I did it by simply NOP-ing out the lines containing CMOVNE. The modified binary can be found in the repository: serpentine4_p1.exe.

Dumping equations with a PIN tracer

Full implementation of the tracer is available here: https://github.com/hasherezade/flareon2024/tree/main/task9/equations_builder

Intro

Pin Tracers are modules that are injected into a compiled application when it runs under the control of Intel Pin. They allow to intercept the execution of the target, and run our instrumentation function at every monitored event – before or after its execution. Pin allows to set callbacks at different granularity levels. We can watch not only every new module being loaded, every API function being called, but also every single instruction being executed. One example of a general-purpose Pin Tracer is TinyTracer, available on my Github. While it has rich capabilities, sometimes we can benefit more from writing tracers tailored for the specific task – and this is what I am gonna demonstrate in this part.

At this point, the goal was to understand what operations are being applied on the input, and reconstruct the equations as close as possible in the way they can be used with the Z3 Solver.

Since we have the whole password checking logic isolated in the newly added, cleaned section, I will watch the instructions executed within this boundary, and how do they change the context.

Initial tracer

First, we add the instrumentation function that will work at instruction granularity level:

// Register function to be called before every instruction
INS_AddInstrumentFunction(InstrumentInstruction, NULL);

The InstrumentInstruction is responsible for registering the callback function LogInstruction. It will get called prior to the every instruction execution (IPOINT_BEFORE) and get two arguments: the current context (IARG_CONTEXT), and the instruction disassembly.

VOID InstrumentInstruction(INS ins, VOID* v)
{
    const IMG pImg = IMG_FindByAddress(INS_Address(ins));
    BOOL inWatchedModule = FALSE;
    if (!IMG_Valid(pImg) || IMG_IsMainExecutable(pImg))
    {
        inWatchedModule = TRUE;
    }
    // only the main module
    if (inWatchedModule && g_disasmStart) {

        INS_InsertCall(
            ins,
            IPOINT_BEFORE, (AFUNPTR)LogInstruction,
            IARG_CONTEXT,
            IARG_PTR, new std::string(INS_Disassemble(ins)),
            IARG_END
        );
    }
}

All the important stuff related to the tracing happens withing this defined callback. At first, I simply logged all what is happening.

VOID LogInstruction(const CONTEXT* ctxt, std::string* disasmStr)
{
    if (!disasmStr) return;

    const char* disasm = disasmStr->c_str();
    if (!disasm) return;

    PinLocker locker;

    const ADDRINT Address = (ADDRINT)PIN_GetContextReg(ctxt, REG_INST_PTR);
    const ADDRINT base = get_mod_base(Address);
    if (base == UNKNOWN_ADDR) {
        return;
    }
    const ADDRINT rva = Address - base;
    // ensure that we are within boundaries of interest:
    if (rva < g_disasmStart || rva > g_disasmStop) {
        return;
    }
    // log the context as it was before executing the instruction:
    traceLog.logLine("\t\t\t\t" + dumpContext(disasm, ctxt));
    // log the disassembly:
    traceLog.logInstruction(base, rva, disasm);
}

The function dumpContext was designed to print changes in the registers at each step. As it goes, it produces a TAG file, similar by the one created by TinyTracer.

After we built the tracer, we run the patched serpentine.exe under its control, passing it a test input:

C:\pin\pin.exe -t C:\pin\source\tools\pin_tracer\x64\Release\Task9Tracer.dll -- serpentine4_p1.exe 0123456789ABCDEF1112211122111221

Example of the produced tracelog (fragment):

				{ [rsp] -> 7ff9aa2728bf; rsi = 67ffc70 rbp = 67ff5b0 rsp = 67ff038 rdx = 67ffea8 rcx = 67ffc70 rax = 1408aa098 r8 = 67ff780 r9 = 67ff600 r10 = 67ff0e0 r11 = 67ff060 r12 = 1408aa098 r14 = 67ff0b0 r15 = 67ff780  }
10aa005;mov r11, 0x10add7f49
				{ r11 = 10add7f49  }
10aa00f;push r11
				{ [rsp] -> 10add7f49; rsp = 67ff030  }
10aa011;push 0x73775436
				{ [rsp] -> 73775436; rsp = 67ff028  }
10aa016;push 0x68a04c43
				{ [rsp] -> 68a04c43; rsp = 67ff020  }
10aa01b;push 0x12917ff9
				{ [rsp] -> 12917ff9; rsp = 67ff018  }
10aa020;add qword ptr [rsp+0x18], 0x35ac399f
				
10aa029;jmp 0x1408aa107
				{ [rsp] -> 7ff9aa2728bf; rsi = 67fedf0 rbp = 67fe730 rsp = 67fe1b8 rdx = 67ff018 rcx = 67fedf0 rax = 1408aa1a7 r8 = 67fe900 r9 = 67fe780 r10 = 1408aa107 r11 = 67fe1e0 r12 = 1408aa1a7 r14 = 67fe230 r15 = 67fe900  }
10aa02e;mov rbp, qword ptr [r9+0x28]
				{ rbp = 67fe230  }
10aa032;mov rdi, qword ptr [rbp+0xe0]
				{ rdi = 4241393837363534  }
10aa039;movzx rdi, dil
				{ rdi = 34  }
[...]

The jumps (i.e. jmp 0x1408aa107) redirect to the original section, that calls the HLT instruction, triggering the context change. So on return, we have the complete context printed. Further on, only the registers that has changed are printed, to keep the tracing more focused.

In the above fragment, we can already see some part of the supplied input (“0123456789ABCDEF1112211122111221”) being loaded into the registers:

				{ rdi = 4241393837363534  } -> "BA987654"
10aa039;movzx rdi, dil
				{ rdi = 34  } -> '4'

Since I wanted to automatically recognize at what index the particular byte of the input is, I added additional option to the tracer (enabled with -c). It requires a hardcoded string to be passed as the input: 0123456789ABCDEFabcdefghijklmopq and does the automatic lookup, finding the position of the character.

int getValIndx(ADDRINT rax)
{
    char str[] = "0123456789ABCDEFabcdefghijklmopq";
    const size_t len = strlen(str);
    for (int i = 0; i < len; i++) {
        if (rax == ADDRINT(str[i])) return i;
    }
    return (-1);
}

Now, when run with this flag, the tracer displays automatically that we are dealing with i.e. x_4 – the 4th character of the input.

After some experiments I started to notice the patterns, and pinpointed the lines where the important operations are happening.

Each of the 32-bit equations operates on 8 different characters of the input. The first operation done to each character is multiplication with a constant. There are no other multiplications in the code, so we can be sure that whenever this instruction occurs, it is used to process a byte of the input.

I logged those lines with a tracer, and stored the output of the multiplication, to check how it is used later.

				{ rdi = 4241393837363534  }
10aa039;movzx rdi, dil
				{ rdi = 34  }
10aa03d;jmp 0x1408aa20a
				{ rdi = 0 rsi = 67fdf70 rbp = 67fd8b0 rsp = 67fd338 rdx = 67fe1b8 rcx = 67fdf70 rax = 1408aa2a2 r8 = 67fda80 r9 = 67fd900 r10 = 67fd3e0 r11 = 67fd360 r12 = 1408aa2a2 r14 = 67fd3b0 r15 = 67fda80  }
10aa042;mov r8, qword ptr [r9+0x28]
				{ r8 = 67fd3b0  }
10aa046;mov rax, qword ptr [r8+0xb0]
				{ rax = 34  }
10aa04d;mov r10, 0xef7a8c
				{ r10 = ef7a8c  }
10aa054;push r10
				{ [rsp] -> ef7a8c; rsp = 67fd330  !!! TRACKED_MULTIPLYING: #[ res = x_4  * 0xef7a8c ] // [CNTR: 0]  }
10aa056;mul qword ptr [rsp]
				{ rdx = 0 rax = 30a4e470  !!! MUL_RES: 30a4e470 }

Reconstructing the equations

Since the context is rewritten on each HLT, and the tracer treats all the changes made by the unwind codes as black boxes, we can’t really follow the operations in a way typical to taint analysis. But we can still notice how the results change.

Each equation consists of 8 multiplication operations. They are done each time a new character of the input is loaded. The result of each multiplication is processed by some operations. Then it is merged with another multiplication result, by either being added, substracted, or XORed. While some of the operations are easy to spot in the code, other are hard to track, but we can deduce them from the observed results.

I modified the tracer to follow the consecutive results, and constructed additional file (.listing.txt) with log focused only on the performed operations. The detailed log (.tag) will be used as a reference.

The first equation logged by the listing looks in the following way (full listing here):

res = x_4  * 0xef7a8c
m = x_24  * 0x45b53c
#[ res += 0x9d865d8d ; res -= 0x6279a273 ;  res ^= 0xfe8fa58d ]
res -= m
m = x_0  * 0xe4cf8b
#[ res += 0x18baee57 ; res -= 0xe74511a9 ;  res ^= 0x7bdd36d9 ] 
res -= m
m = x_8  * 0xf5c990
#[ res += 0x6ec04422 ; res -= 0x913fbbde ;  res ^= 0x914fc462 ] 
res -= m
m = x_20  * 0x733178
#[ res += 0x6bfaa656 ; res -= 0x940559aa ;  res ^= 0x9c3adeea ] 
res ^= m
m = x_16  * 0x9a17b8
#[ res += 0x9fa354cb ; res -= 0x605cab35 ;  res ^= 0x61e3db3b ] 
res ^= m
m = x_12  * 0x773850
#[ res += 0x35d7fb4f ; res -= 0xca2804b1 ;  res ^= 0x5a283bb1 ] 
res ^= m
m = x_28  * 0xe21d3d
#[ res += 0xb622a84a ; res -= 0x49dd57b6 ;  res ^= 0x5a6f68be ] 
res ^= m
#[ res += 0x420a6868 ; res -= 0xbdf59798 ;  res ^= 0xc2359898 ] 

###

The lines starting with ‘#’ denote the operations that are deduced by the changes in the output. We are not really sure which of the operations was used, that’s why multiple options are shown in the log. In most cases, this gets clarified when we create logs with different inputs, and compare them.

Example – log of the same equation generated with a different input (full listing here):

res = 23 * 0xef7a8c
m = 23 * 0x45b53c
#[ res += 0x9d865d8d ; res -= 0x6279a273 ;  res ^= 0x9ef9df95 ]
res -= m
m = 23 * 0xe4cf8b
#[ res += 0x18baee57 ; res -= 0xe74511a9 ;  res ^= 0x79cb12a9 ] 
res -= m
m = 23 * 0xf5c990
#[ res += 0x6ec04422 ; res -= 0x913fbbde ;  res ^= 0xb2c1cc26 ] 
res -= m
m = 23 * 0x733178
#[ res += 0x6bfaa656 ; res -= 0x940559aa ;  res ^= 0x9c1bdade ] 
res ^= m
m = 23 * 0x9a17b8
#[ res += 0xa022d6d5 ; res -= 0x5fdd292b ;  res ^= 0x61e3db3b ] 
res ^= m
m = 23 * 0x773850
#[ res += 0x35d7fb4f ; res -= 0xca2804b1 ;  res ^= 0x4dd804cf ] 
res ^= m
m = 23 * 0xe21d3d
#[ res += 0xda62e782 ; res -= 0x259d187e ;  res ^= 0x5a6f68be ] 
res ^= m
#[ res += 0xd30c9a66 ; res -= 0x2cf3659a ;  res ^= 0xdd0ca6aa ] 

###

Some constants in the parts in question repeat in both, so we can guess they give away the valid operations. I created another script in Python to merge the listings: cleanup.py.

This is how the first generated equation looks like:

res_0 = x_4  * 0xef7a8c
m = x_24  * 0x45b53c
res_0 += 0x9d865d8d
res_0 -= m
m = x_0  * 0xe4cf8b
res_0 += 0x18baee57
res_0 -= m
m = x_8  * 0xf5c990
res_0 += 0x6ec04422
res_0 -= m
m = x_20  * 0x733178
res_0 += 0x6bfaa656
res_0 ^= m
m = x_16  * 0x9a17b8
res_0 ^= 0x61e3db3b
res_0 ^= m
m = x_12  * 0x773850
res_0 += 0x35d7fb4f
res_0 ^= m
m = x_28  * 0xe21d3d
res_0 ^= 0x5a6f68be
res_0 ^= m
WARNING: no common part

Full listing: t1_vs_t2.txt .

While it gave multiple valid equations, there are still some unresolved cases, where no common part was found. The reason of such situation can be understood by following the main trace (.tag) in more details.

Filling the missing parts

The deduced operations are just an attempt to summarize the changes done to the result between two points of observation. We know what was the value before, and what was the value after, but we weren’t able to trace all what happened in between – so we only print some options of what was possibly added, substracted or XORed to get that result:

#[ res += 0x420a6868 ; res -= 0xbdf59798 ;  res ^= 0xc2359898 ] 

Then, comparing traces done with different input, we pick one of the options that repeat in both. It can give a sufficient approximation in most of the cases, but will fail on some.

In reality, there were multiple operations done to our result in between those two different points of observation. If those operations are of the same type, we can summarize them as one. For example, if the value is changed by ADD const_1 and then by SUB const_2:

res += const_1
res -= const_2

They can be summarized as one operation:

res += const_3 ; where const_3 = const_1 - const_2

The same happens when there are multiple XOR operations applied:

res ^= const_1
res ^= const_2
res ^= const_3

Can be summarized as:

res ^= const_4 ; where const_4 = const_1 ^ const_2 ^ const_3

So having just two points of observation of the res value – before and after the set of operations – is sufficient to deduce a valid constant.

But there are rare cases when this won’t give a valid result. For example, if the value is changed first by XOR with const1 and then by SUB with const2. They are not transitive, and they cannot be replaced by one operation on const3. Comparing traces with different input, we can see that the attempt to aggregate those operations as one doesn’t give a consistent result. Script will print “no common part”. It means, we need more points of observation. Instead of trying to compress the changes to one value, and one operation, we will split it on as many sub-operations as it is required, to again get consistent results between traces with different input.

Automating this part of tracing was more problematic. Fortunately, the number of such missing cases is small enough, so I decided to do this search manually, and only enrich the tracelog to help me out a bit.

The cases with “no common part” always happen at the end of the equation: between the last multiplication, and the comparison of the result to 0 (TEST operation). So, for those parts of code, I enabled more detailed logging:

    bool arithm = false;
    if (disasm.find("sub ") == 0 ||
        disasm.find("add ") == 0 ||
        disasm.find("xor ") == 0 ||
        disasm.find("or ") == 0 ||
        disasm.find("and ") == 0
        )
    {
        arithm = true;
    }
    bool isArithmTrackingEnabled = (mulCntr == 7) ? true : false;
    if (isArithmTrackingEnabled && arithm) {
        ss << " TRACKED_ARITHM: " << disasm;
    }
    if (isArithmTrackingEnabled && isPrevArithm && anyChanged) {
        ss << " TRACKED_ARITHM_RES ";
    }

The logged lines are marked with the keyword “TRACKED_ARITHM” that will make them easier to find in the whole .tag file.

This is the fragment that I’ve got tracking all the above operations done at the end of the first equation.

https://github.com/hasherezade/flareon2024/blob/aef1969f228c7fe44359d86a37ad328a3e2a0f04/task9/equations_builder/listings/track.txt#L20

The first point of observation is just after the last MUL:

{ rbp = ffffffff2dd98f84  !!! TRACKED_MULTIPLYING: #[ m = 6d * 0xe21d3d ]  UNK: #[ res -= 0x49dd57b6 ;  res ^= 0x5a6f68be ] // [CNTR: 7]  }
{ r12 = ffffffff2dd98f84  TRACKED_CHANGED BY: xor r12, qword ptr [rdi+0xd8] #[ res ^= m ]  TRACKED_ARITHM: xor r12, qword ptr [rdi+0xd8] }
{ r12 = ffffffff4d9ffd7d  TRACKED_CHANGED  -> VAL: ffffffff4d9ffd7d TRACKED_ARITHM_RES  }

Next point of observation is somewhere in between, and we have to find it by looking at the log from different operations.

{ r14 = ffffffff110ee05e  TRACKED_ARITHM_RES  }

{ [rsp]  -> f4732f0; rsp = 66f5790  TRACKED_ARITHM: add qword ptr [rsp+0x20], 0xe565b33 }

The final point of observation is just before the value gets tested:

{ r12 = ffffffff8faa65e5  TRACKED_ARITHM_RES  }
{ r15 = 1400011f0  TRACKED_TEST r14 = ffffffff8faa65e5 UNK: #[ res += 0x420a6868 ;  res ^= 0xc2359898 ]  }

Now instead of two points of observations, I have 3:

res_0 = 0xffffffff4d9ffd7d
res_0 = 0xffffffff110ee05e
res_0 = 0xffffffff8faa65e5

I created another code snippet where I manually pasted values from different equations and different traces:

https://github.com/hasherezade/flareon2024/blob/aef1969f228c7fe44359d86a37ad328a3e2a0f04/task9/equations_builder/test.cpp

This allowed me to find a set of two operations with the help of which I can summarize how the result has changed:

res_0 ^= 0x5C911D23
res_0 += 0x7E9B8587

I repeated those steps with several different equations that had the missing part at the end.

Finally, my solver got complete enough: task9_z3s.py – and it was able to print the flag:

$$_4lway5_k3ep_mov1ng_and_m0ving