Borrowed Memory

1. Initial triage

The challenge ships a single file, borrowed_memory.bdsec:

$ file borrowed_memory.bdsec
borrowed_memory.bdsec: ELF 64-bit LSB pie executable, x86-64, version 1 (SYSV),
dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, ..., stripped

A stripped, PIE x86-64 binary. Running it cold prints a banner:

        _________________________________________
       /                                         \
      /          B D S e c   C T F   2 0 2 6    \
     /_____________________________________________\
     |                                             |
     |              BORROWED MEMORY                |
     |                                             |
     |       0x???? -> 0x???? -> 0x????            |
     |_____________________________________________|

Return what was borrowed.
>

strings on the binary turns up nothing useful (no plaintext flag, no obvious "correct"/"wrong" markers), which tells you immediately this isn't a simple string-compare check — the validation is computed, not stored.

Being stripped, there are no symbol names, so everything has to be worked out from raw disassembly (objdump -d -M intel).

2. Understanding the input format

The banner's 0x???? -> 0x???? -> 0x???? hints at a chain of three(-ish) hex values, but reversing the input loop shows it's actually 12 hex tokens, each expected in the range 0x4000–0x47FF (a sub+cmp 0x7ff+ja reject bounds check). Interestingly, the loop that reads them prints a > prompt and calls fgets once per token — so the program actually wants 12 separate lines of input, not one line with 12 space-separated values (an easy trap if you assume the banner's arrow format is literal).

Each parsed token is stored into a small stack array of 12 words, which then feeds a completely separate verification loop.

3. The verification loop, at a glance

For each of the 12 slots, the program:

1. Computes a "current" 16-bit state value, si (starts from a fixed seed).
2. Checks that your supplied token equals si + 0x4000.
3. Runs a fairly elaborate mess of XORs, table lookups, byte-rotates, and a 64-bit multiply-based modulo trick, branching on one of 4 possible values of an intermediate byte (0xC0/0xC1/0xC2/0xC3).
4. Derives the next value of si from that computation — not from your input at all.
5. Also derives one byte of a "keystream" and one 32-bit "state" word per round, both of which get folded into decrypting the flag at the very end.
6. Runs an internal self-consistency check (cmp cx, ax) that must hold for the round to be considered valid.

The key realization: the next si is a pure function of the current si and a fixed lookup table — never of the token you type. This means the entire 12-round chain (and therefore the 12 "correct" tokens) is completely predetermined; you're not really solving anything by choice, you're just supplying the one sequence the state machine will walk through regardless. There's exactly one valid answer, and it's derivable, not brute-forceable.

A neat side effect of the design: a 16-bit counter (r11w) starts at 0xBEEF and drops by 0x111 every round. After exactly 12 rounds it lands on 0xB223 — the "success" checkpoint — which is what forces the puzzle to be exactly 12 tokens long.

4. The "random" table isn't random

The 2048-byte lookup table used throughout the verification loop is built by a custom PRNG (xorshift/avalanche-style mix, seeded with 0x91e10da5) at startup:

eax = 0x91e10da5;
for (edx = 0; edx < 0x800; edx++) {
    ecx = eax + edx + 0x045d9f3b;
    eax = ecx;
    eax = (eax << 13) ^ ecx;
    eax ^= (eax >> 17);
    eax ^= (eax << 5);
    table[edx] = (uint8_t)(eax >> 11);
}

That part was straightforward to reimplement in Python and replicate byte for byte.

However — the very next thing the setup code does is scatter dozens of individual mov byte/word/dword [addr], imm instructions across addresses that fall inside that same table region (0x4080–0x4880). At first glance these look like the usual CTF trick of building string literals one byte at a time to defeat strings. They aren't (or not only that) — many of them are silently patching specific bytes of the "random" table after it's generated, overwriting the PRNG output at ~50 scattered offsets with fixed values. This is what actually encodes the puzzle's solution into what looks like pure noise.

Missing this cost the most time in the challenge: a straight reimplementation of the PRNG alone produces a table that's almost right, so early rounds of a hand simulation pass by luck (shared low-order noise), and it silently diverges a couple of rounds in with checksum mismatches that are very hard to diagnose by re-reading assembly.

5. Pivoting to a dynamic oracle

Rather than keep hand-translating registers 1:1 (error-prone — 8/16/32/64-bit partial-register semantics, an unmasked out-of-bounds table read in one of the four branches, a 64-bit multiply-based division trick, etc.), the more reliable move was to let the real binary compute everything and just read its registers, using gdb's Python API:

1. Confirmed the (PIE, but GDB-non-randomized) load base is stable at 0x555555554000 across runs.
2. Fed 12 dummy in-range tokens (0x4000) on separate lines, since the input loop reads one line per token.
3. Set a breakpoint at the top of each verification round (the instruction that loads your supplied token, movzx r8d, word [rbp]).
4. At each hit:
   • Read $esi (the current internal state, si).
   • Compute the expected token for this round: esi + 0x4000.
   • Overwrite the in-memory input buffer ($rbp) with that correct value before letting execution continue — so the check always passes, without me needing to understand the round's internal arithmetic at all.
5. Let it run to completion.

class Iter(gdb.Breakpoint):
    def stop(self):
        esi = int(gdb.parse_and_eval("$esi")) & 0xFFFF
        token = (esi + 0x4000) & 0xFFFF
        rbp = int(gdb.parse_and_eval("$rbp"))
        gdb.selected_inferior().write_memory(rbp, token.to_bytes(2, 'little'))
        return False  # don't actually stop, just patch and continue

This sidesteps every subtlety of the obfuscated hashing/rotation logic entirely — the CPU does the "reversing" for us, we just skim the one register that matters at the one moment that matters.

6. Result

Running the harness end to end, the program itself walked all 12 rounds successfully and printed:

> > > > > > > > > > > > [+] BDSEC{p01nt3rs_l13_bUt_0ffs3ts_r3m3mb3r}

with the recovered token chain:

0x41a4 -> 0x42f0 -> 0x4143 -> 0x436c -> 0x421d -> 0x44a8 ->
0x40f6 -> 0x455b -> 0x4317 -> 0x468c -> 0x425a -> 0x473d

Flag: BDSEC{p01nt3rs_l13_bUt_0ffs3ts_r3m3mb3r}

7. Takeaways

• When a stripped binary's "random" table doesn't look quite random enough to trust a from-scratch PRNG reimplementation, check for post-generation patches hiding among what looks like ordinary string-obfuscation byte-stores; CTF authors love reusing that pattern to also smuggle in actual puzzle logic.
• If a per-round check's next state provably doesn't depend on your input (only on internal state + a fixed table), stop trying to search/brute-force it; it's a fixed sequence you need to derive, not guess.
• When manual translation of heavily obfuscated bit-twiddling starts producing subtle mismatches, switching to a dynamic oracle (breakpoint
  • live register read + memory patch, via gdb's Python API) is often far faster and far less error-prone than continuing to hand-trace 16/32/64-bit partial-register semantics, unmasked table indices, and multiply-based division tricks by eye.