cube

Platform: rev_kids20 | Category: Reversing | Type: Challenge | Difficulty: Medium | OS: NA | Author: XESXOR | Date: 2026-06-15 | Status: Solved Techniques: heap_struct_reconstruction, magic_number_division_recovery, static_decode, xor_modulo_key

Summary

Task: 32-bit x86 ELF builds the flag inside a nested heap structure (linked 16-byte cells) and only prints hints, never the flag; each diagonal cell stores table[idx] XOR (idx%255). Solution: statically reconstruct the cell indices and decode; key insight is that the compiler magic-number division (0x80808081 + sar 7 + shl8/sub) computes idx%255, NOT idx%257 — the wrong modulus only corrupts the row-3 tail, masking the bug behind a correct 'flag_is_' prefix.

cube — rev_kids20

Description

Бинарь аллоцирует флаг внутри какой-то структуры. Разберись, что это за структура, и достань флаг. (When run, it only prints: "Flag is allocated", "Hint: you can just use debugger", "Buf if you love create structs in IDA then enjoy", "P.S. I'm too lazy to free all this memory".)

English summary: A 32-bit x86 ELF (cube.elf, Intel 80386, dynamically linked, NOT stripped) constructs the flag inside a nested heap data structure of dynamically-allocated cells, but never prints it. The goal is to understand the structure and recover the flag. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Analysis

Functions of interest: main, row_allocator/allocate_rows, colmn_allocator/allocate_cols, cell_allocator/allocate_cells, check.

The heap structure (a "cube" of cells)

Each cell is a 16-byte heap block:

Nesting (3 levels):

• main loops a row index 0..3 → allocate_cols(node, row)
• allocate_cols loops a col/cell-group index 0..3 → allocate_cells(node, row, k)
• allocate_cells loops an inner counter k 0..3 ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

The global at .data 0x804a020 holds pointer 0x08048850, the base of a byte table in .rodata.

The byte-write logic (allocate_cells @ 0x08048530)

For each cell it computes:

idx = 100*row + 10*colidx + k     ; imul ecx,eax,0x64 (*100); (x<<2)+x +x (*10); + k

On the diagonal row == colidx, so idx = 110*row + k.

It loads b = table[idx], computes a key, and stores table[idx] XOR key into the cell's +4 byte — but only when check(row, colidx, k) returns 1.

check (@ 0x080484f1)

‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Returns 1 iff row == colidx AND (k==0 OR k==3 OR row==0 OR row==3):

• Diagonal nodes only.
• Corner diagonal nodes (row 0, row 3): all four cells k = 0..3 written.
• Middle diagonal nodes (row 1, row 2): only cells k = 0 and k = 3 written.

That gives exactly 12 written cells: idx 0,1,2,3 / 110,113 / 220,223 / 330,331,332,333.

The critical XOR-key gotcha (the whole lesson)

The XOR key is computed by the classic compiler magic-number division sequence using constant 0x80808081 and sar 7. 0x80808081 is widely cited as "the magic number for division by 257", so it is tempting to read the key as idx % 257. It is not — it is idx % 255. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Emulating the exact assembly:

edx:eax = idx * (signed)0x80808081      ; imul, take high dword edx
q = (edx + idx) >> 7   (arithmetic)     ; lea + sar 7  -> q = idx / 255
prod = (q << 8) - q = q*256 - q = q*255 ; shl edx,8 ; sub edx,eax
key  = idx - prod = idx % 255

The follow-up shl edx,8; sub edx,eax computes q*256 - q = q*255, which proves the divisor is 255, not 257.

Why this hides a real bug: for idx < 255, idx % 255 == idx % 257 == idx, so the entire flag_is_ prefix (idx ≤ 223) decodes identically under either modulus. Only the row-3 cells (idx 330..333) cross the divisor boundary: ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

So %257 gives the garbage tail djge → flag_is_djge (rejected by the server ~40 times), while the correct %255 gives flag → REDACTED (accepted).

Solution

No debugger needed. Running the binary prints only hints, and ptrace/gdb does not work under qemu-user in Docker anyway, so pure static decode is authoritative. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

cell = table[idx] XOR (idx % 255), table base 0x8048850, read row-major / cell-order over the 12 written diagonal cells.

 python read-only • copy allowed Copy
#!/usr/bin/env python3
import subprocess, re

# Read .rodata bytes from the ELF
out = subprocess.check_output(["objdump", "-s", "-j", ".rodata", "cube.elf"]).decode()
data = {}
for line in out.splitlines():
    m = re.match(r"\s*([0-9a-f]{6,8})\s+((?:[0-9a-f]{2,8}\s?){1,4})", line)
    if not m:
        continue
    base = int(m.group(1), 16)
    hexs = m.group(2).replace(" ", "")
    b = bytes.fromhex(hexs[:len(hexs)//2*2])
    for i, by in enumerate(b):
        data[base + i] = by
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

TBL = 0x8048850
def dec(idx):
    b = data.get(TBL + idx)
    return None if b is None else b ^ (idx % 255)   # NOT % 257

chars = []
for row in range(4):
    for k in range(4):
        if k in (0, 3) or row in (0, 3):   # check(): diagonal cells written
            idx = 110 * row + k            # row == colidx on diagonal
            c = dec(idx)
            chars.append(chr(c))
            print(f"row={row} k={k} idx={idx:3d} -> '{chr(c)}'")

print("FLAG:", "".join(chars))

Decoded cells (key = idx % 255): ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

• row0 (idx 0,1,2,3): f l a g
• row1 (idx 110,113): _ i
• row2 (idx 220,223): s _
• row3 (idx 330,331,332,333): f l a g

Row-major concatenation: flag + _ + i + s + _ + flag = REDACTED. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍