recurse (RE3_recurse)

Platform: CUSTOM | Category: Reversing | Type: Challenge | Difficulty: Easy | OS: N/A | **Author: XESXOR Techniques: byte_predicate_inversion, function_pointer_dispatch_analysis, per_byte_brute_force_inversion, signed_byte_idiom_recognition

Summary

Walkthrough of the CUSTOM Reversing recurse (RE3_recurse). Task: 64-bit PIE ELF keygen that reads a 29-byte key and validates it with a recursive checker dispatching one of four byte-predicate functions per position against a .rodata constant. Solution: rever

Description

Reverse / Shtrikh17. Given a 64-bit ELF recurse. Prompts "Give me the key:", validates the input.

English summary: A non-stripped 64-bit PIE ELF prompts Give me the key:, reads a line, requires the input (after stripping the newline) to be exactly 0x1d (29) bytes, then validates it with a recursive checker. On success it prints Correct. The validated 29-byte key is itself the flag.

Analysis

main:

• fgets(buf, 0xff, stdin), strips the trailing \n.
• if (strlen(buf) != 0x1d) { puts("Incorrect length"); exit(...); } — the length gate confirms a 29-char answer.
• Builds a stack array of 29 function pointers, each one of {foo1, foo2, foo3, foo4} in a fixed order, plus a pointer to a constant 29-byte string at .rodata 0x2027.
• Calls checker(input, fptr_array, const_str, 29). ‍​‌‌​​​​‌​‌‌​​‌‌​​‌‌​​‌‌​​‌‌​​‌​​​​‌‌​​​​​‌‌​​‌‌​​‌‌​​‌​‌​‌‌​​‌​‌‍

checker(rdi=in, rsi=fptrs, rdx=const, ecx=count) is recursive:

• if count == 0 return 1.
• else result = fptrs[0](input[0], const[0]) & 1 (dispatched via call rcx where rcx = fptrs[i]),
• then result &= checker(input+1, fptrs+1, const+1, count-1).

All per-position results are AND-chained, so the key is valid iff every byte passes its own predicate. Each byte is independent — a perfect keygen target.

The four predicates (edi = input byte as dl, esi = const byte as al, return 1 if the relation holds): ‍​‌‌​​​​‌​‌‌​​‌‌​​‌‌​​‌‌​​‌‌​​‌​​​​‌‌​​​​​‌‌​​‌‌​​‌‌​​‌​‌​‌‌​​‌​‌‍

foo3/foo4 use the classic signed-byte normalization idiom (lea edx,[rax-0x11]; sar eax,31; shr eax,24; add; movzx; sub) to emulate signed 8-bit arithmetic. Rather than reason about it precisely, the simplest robust approach is to brute-force each predicate over 0..255 to find the unique input byte that satisfies it. ‍​‌‌​​​​‌​‌‌​​‌‌​​‌‌​​‌‌​​‌‌​​‌​​​​‌‌​​​​​‌‌​​‌‌​​‌‌​​‌​‌​‌‌​​‌​‌‍

The 29-byte constant (.rodata @ 0x2027):

73 8f 51 7a 63 99 6a 7f cf 77 76 64 20 9b 5f 90 30 8a 4e 83 20 94 22 76 8b 68 4b 74 6c

The function-pointer order (29 entries, extracted from main):

foo1 foo2 foo3 foo4 foo3 foo2 foo3 foo4 foo2 foo1 foo4 foo1 foo3 foo2 foo1
foo4 foo1 foo2 foo3 foo4 foo3 foo2 foo3 foo4 foo2 foo1 foo4 foo1 foo3

Solution

For each position i, take its predicate foo[order[i]] and its constant byte const[i], and find the unique input byte (brute 0..255) that makes the predicate return 1. That byte is the i-th key character. ‍​‌‌​​​​‌​‌‌​​‌‌​​‌‌​​‌‌​​‌‌​​‌​​​​‌‌​​​​​‌‌​​‌‌​​‌‌​​‌​‌​‌‌​​‌​‌‍

 python read-only • copy allowed Copy
#!/usr/bin/env python3
const = [0x73,0x8f,0x51,0x7a,0x63,0x99,0x6a,0x7f,0xcf,0x77,0x76,0x64,0x20,0x9b,
         0x5f,0x90,0x30,0x8a,0x4e,0x83,0x20,0x94,0x22,0x76,0x8b,0x68,0x4b,0x74,0x6c]
order = [1,2,3,4,3,2,3,4,2,1,4,1,3,2,1,4,1,2,3,4,3,2,3,4,2,1,4,1,3]

def foo3(inp):  # value compared to const
    edx = inp - 0x11
    eax = 0xff if edx < 0 else 0
    return (((edx + eax) & 0xff) - eax) & 0xffffffff

def foo4(inp):
    edx = inp + 0x17
    eax = 0xff if edx < 0 else 0
    return (((edx + eax) & 0xff) - eax) & 0xffffffff
‍​‌‌​​​​‌​‌‌​​‌‌​​‌‌​​‌‌​​‌‌​​‌​​​​‌‌​​​​​‌‌​​‌‌​​‌‌​​‌​‌​‌‌​​‌​‌‍

def inv(f, c):
    for x in range(256):
        if (f == 1 and x == c) \
           or (f == 2 and (x ^ c) == 0xff) \
           or (f == 3 and foo3(x) == c) \
           or (f == 4 and foo4(x) == c):
            return x

print("".join(chr(inv(order[i], const[i])) for i in range(29)))
# -> spbctf{REDACTED}

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

Key Takeaways / Lessons

• Mastering byte_predicate_inversion, function_pointer_dispatch_analysis, per_byte_brute_force_inversion, signed_byte_idiom_recognition was key to this challenge.
• Always check for common misconfigurations and verify assumptions.

---

Crafted by XESXOR Research • 2026-06-15 • CUSTOM • recurse (RE3_recurse) • Difficulty: Easy