[Hard] FlecksOfGold

FlecksOfGold

27^th 02 24 / Document No. D24.102.14

Prepared By: clubby789

Challenge Author: clubby789

Difficulty: Hard

Classification: Official

Synopsis

FlecksOfGold is a Hard reversing challenge. Players will reverse engineer a program written using an open-source Entity Component System. They will then either patch the binary to enable discovering the flag, or uncover it manually through reversing.

Skills Required

- Open-source research skills
- Strong usage of a decompiler

Skills Learned

- ECS fundamentals
- Basic binary patching

Solution

If we execute the provided binary, it hangs for some time with no output, so we'll begin analysing it.

Analysis

The binary is large and optimized, making analysis somewhat hard as much of the logic is inlined into main. Luckily, it is unstripped. We can therefore see many references to ecs - Entity Component System. This is a design pattern of having several unique 'entitities', each with a number of attached 'components', which are acted upon by 'systems' (usually functions).

We can also see specific references to flecs - an open source C/C++ Entity Component System. This binary is written in C++ and uses some C++ features, but is mostly a wrapper around the C API of flecs.

By skimming main, we can spot some interesting code and symbol names.

flecs::_::cpp_type_impl<Position>::s_allow_tag = 1
flecs::_::cpp_type_impl<Position>::s_size = 0x10
flecs::_::cpp_type_impl<Position>::s_alignment = 8

We can assume that this is declaring some component Position of size 0x10. We can also see

flecs::_::cpp_type_impl<FlagPart>::s_allow_tag = 1
flecs::_::cpp_type_impl<FlagPart>::s_size = 2
flecs::_::cpp_type_impl<FlagPart>::s_alignment = 1

We have some component FlagPart made of 2 bytes.

Further down, we see

zmm0_3, zmm1_1 = rand_pos.constprop.1()
int64_t* world_1 = world
void* rax_44 = ecs_new_w_id(world_1, 0)

Where rand_pos calls rand_range(-495.0, 495.0) twice before some floating point arithmetic. We can assume here that rand_pos is generating a random position in the given range, then ddoing some normalization (float(int(ftrunc(...))) being in use implies some kind of rounding to integers).

After this, we call ecs_new_w_id on the world - we can either guess or read flecs source code to see that this creates a new entity in the world and returns its ID. We are then likely attaching our generated Position component to it. This is then repeated below with references to FlagPart - possibly various parts of the flag are being scattered at random positions.

This all occurs in a large loop - after this, there is another loop which loops over an array names - 20 strings of person names. For each of these, we create an entity and a random position from (-50.0, 50.0). Below this, we attach a Person component, with a size of 0. Often, ECS will attach a component with no data, simply to mark an entity as a specific type. This means that we are creating a 'Person' entity with the given name, and a random position.

Finally, there is a component CanMove attached - however, this happens inside of an if (false) branch, so it is not attached in practise.

Systems

Once we have declared our entities, we must define the systems to run on them.

flecs::system_builder<Person, Position>::system_builder(&var_b08, world, 0)
int64_t* rax_99 = flecs::filter_builder_...>, Person, Position>::term<CanMove>(&var_b08)
*(rax_99[2] + 0x68) = 1
rax_99[0x159].b = 1
int32_t (* rax_101)[0x4] = data_eb3b0(0x10)
if (rax_101 != 0) {
    *rax_101 = _mm_unpacklo_epi64(var_d80_1, &var_d30)
}
rax_99[0x152] = rax_101
bool cond:0 = rax_99[0x13e].b == 0
rax_99[0x150] = flecs::_::each_delegat... Position&, Person, Position>::run
void** rdi_68 = rax_99[0x158]
rax_99[0x154] = flecs::_::free_obj<fle...on, Position&, Person, Position> >
if (cond:0) {
    rax_99[0x13e].b = rax_99[0x159].b
}
ecs_system_init(rdi_68, &rax_99[7])

Luckily, C++ symbol names usually include function signatures (this is necessary for function overloading to work). We can see a reference to system_builder<Person, Position> - likely a system which acts upon all entities with both a Person and Position component. After this, there's a reference to filter_builder with a mention of CanMove. This is likely filtering out the above to only People with the CanMove marker attacked

Movement

The referenced function ending with run could be the body of the system itself. If we dig into it, it is mostly a wrapper around calling main::'lambda'(flecs::entity, Person, Position&)::operator().constprop.0. This function first generates two random numbers between -0.5 and 0.5, adds them to an argument, before clamping the value to 500.

double zmm0_1 = rand_range(-0.5, 0.5) + *arg4
double zmm3 = -500.0
if (zmm3 > zmm0_1) {
    zmm0_1 = zmm3
} else {
    zmm0_1 = _mm_min_sd(500.0, zmm0_1)
}
double zmm4 = arg4[1]
*arg4 = zmm0_1
double zmm0_2 = rand_range(-0.5, 0.5) + zmm4
double zmm5 = -500.0
if (zmm5 > zmm0_2) {
    zmm0_2 = zmm5
} else {
    zmm0_2 = _mm_min_sd(500.0, zmm0_2)
}

arg4 is likely a pointer to a Position (implied by the name). This is therefore likely an x and y double, and this system randomly moves our people around, but prevents them from going beyond (-500.0..500.0).

Queries

ECS often have a 'Query' system; a way to search for all entities with given components within a system. We see a reference to flecs::query<Position, FlagPart>::next_each_action - likely a query for every FlagPart entity and its Position. ecs_query_next_instanced is assigned to a variable, and later repeatedly called in a loop on the result of ecs_query_iter. We can presume this is creating an iterator and repeatedly getting the next entity in the query until we have read them all.

Helpfully, below, there is some printing which emits the message Explorer ?? has found a flag part (where ?? is the result of calling ecs_get_name on our Person entity).

zmm0_3 = float.d(int.d(ftrunc(fconvert.t(*arg4))))
double temp2_1 = *rax_7
zmm0_3 - temp2_1
if (not(is_unordered.q(zmm0_3, temp2_1)) && not(zmm0_3 != temp2_1)) {
    zmm0_3 = float.d(int.d(ftrunc(fconvert.t(arg4[1]))))
    double temp3_1 = rax_7[1]
    zmm0_3 - temp3_1
    if (not(is_unordered.q(zmm0_3, temp3_1)) && not(zmm0_3 != temp3_1)) {
        int64_t pos = sx.q(rbp_1_1->pos)
        if (pos.d s< data_eb7a0 && (*r14)[pos] != rbp_1_1->chr) {

This snippet truncates our position to an integer and compares it to some value, likely the position component of the flag part.

I have assumed here that rbp_1_1 is our 2-byte FlagPart structure, where the first byte is an index into some array and the second is a character or byte placed into it.

r14 likely contains our flag characters discovered so far; if the discovered flag part does not match the current content of r14[pos], we place it in the array. We then print it out below.

(If we return to main briefly, we can see a small malloc buffer being initialised to ? and null terminated. This likely is our buffer for the flag).

Solving

We can take a guess of the program functionality here.

• We create 20 'explorers' in random people (without attaching CanMove to them)
• We create a number of 'flag parts' and scatter them around the world
• Each tick of the ECS, we randomly move our people around the world (only if they have CanMove attached)
• If they are overlapping with a flag part, we 'discover' it and add it to our flag array

There are a few ways we can approach solving this. We could locate the creation of the FlagPart components and extract the indexes and values. Instead, I will demonstrate patching the binary so our explorers can move. This will demonstrate the intended functionality.

We will navigate to 0x48b6, where we create a single-byte variable on the stack with a value of 0. This value is then loaded and checked before branching.

mov     byte [rbp-0xd29 {var_d31_1}], 0x0
movzx   eax, byte [rbp-0xd29 {var_d31}]  {0x0}
test    al, al
jne     0x4b78  {0x0}

We can (using our decompiler of choice) patch the 0x0 of the mov to 0x1. Saving the patched version to a new file and running it, we will begin seeing explorers discover flag parts. If we wait a short time, the whole flag will be printed.