two-sum picoCTF 2023 Solution

Description

1. Step 1Read flag.c to understand the overflow check

   Observation

   The challenge ships flag.c along with a condition, n1 > n1 + n2, that is impossible for positive integers. So the overflow is built into the C code, and reading it shows exactly how the check fires.

   Open flag.c and find addIntOvf(). The function returns -1 when two positive inputs produce a negative sum (if(a > 0 && b > 0 && result < 0) return -1). That sign-flip is the hallmark of 32-bit signed integer overflow: any pair of positives whose sum exceeds INT_MAX (2,147,483,647) wraps into negative territory, and addIntOvf catches it by checking the sign bits of all three values.

   bash

   cat flag.c

   Copied!

   Expected output

   picoCTF{Tw0_Sum_Integer_Bu773R_0v3rfl0w_...}

   What didn't work first

   Tried: Skip reading flag.c and just guess that any large numbers will work

   Skip the source and you miss that the check is a sign flip, not a bounds comparison. Overflow detection is written many ways: a direct INT_MAX comparison, __builtin_add_overflow, an unsigned reinterpretation. Reading the code tells you which one you are up against.

   Tried: Assume the function returns 0 on overflow and 1 on success, submitting values just below INT_MAX

   addIntOvf returns -1 on overflow and 0 otherwise, the reverse of the usual convention. Submit values below INT_MAX, say a billion plus a billion, and the sum still fits in 32 bits: no overflow, no trigger, no flag.

   Learn more

   Integer overflow occurs when an arithmetic operation produces a result outside the range representable by the integer type. A 32-bit signed integer holds values from -2,147,483,648 to 2,147,483,647 (INT_MIN to INT_MAX). When you add 2,147,483,647 + 2,147,483,647, the mathematical result (4,294,967,294) exceeds INT_MAX, so it wraps around to -2 in two's complement arithmetic.

   Two's complement is the near-universal representation of signed integers in hardware. In two's complement, addition and subtraction work identically for signed and unsigned numbers at the bit level; the CPU does not distinguish. Overflow just means the carry bit is discarded, and the result is interpreted as a signed value. For 32 bits: 0x7FFFFFFF + 0x7FFFFFFF = 0xFFFFFFFE = -2 when read as signed.

   The condition n1 > n1 + n2 is logically impossible for positive integers in math. But in C with 32-bit signed ints, if the sum wraps to a negative number, a positive n1 is indeed greater than the negative sum. The addIntOvf check in the source catches this purely from sign bits: a positive a, a positive b, and a negative result together are the fingerprint of overflow - no comparison against a hardcoded constant needed.

2. Step 2Submit the overflow pair

   Observation

   addIntOvf() flags overflow when a and b are both positive and the result is negative. Two copies of INT_MAX guarantee the sum wraps negative and satisfies that impossible inequality.

   Pipe two INT_MAX values into the service. The sum wraps to a negative number, the bogus inequality holds, and the flag prints.

   bash

   printf '2147483647\n2147483647\n' | nc saturn.picoctf.net <PORT_FROM_INSTANCE>

   Copied!

   What didn't work first

   Tried: Submit 2147483648 (INT_MAX + 1) as one of the values

   2147483648 does not fit in a 32-bit signed integer; scanned into an int it arrives as -2147483648. addIntOvf requires both inputs to be positive, so a negative one fails the guard and the overflow branch never runs.

   Tried: Use Python to send the values interactively instead of printf piping

   Sending interactively works in principle, but it is easy to send the first number and then wait for a prompt before the second. If the server reads both in one scanf loop with no prompt in between, you wait forever. Piping both values at once removes the timing dependency.

   Learn more

   INT_MAX (2,147,483,647 = 2^31 - 1) is the maximum value for a 32-bit signed integer. Any pair of positive integers whose sum exceeds INT_MAX will overflow and produce a negative (or unexpectedly small) result. Using INT_MAX twice is the cleanest choice because it maximally overflows, but values like 1,200,000,000 + 1,000,000,000 would also work.

   Real-world impact of integer overflow is serious and well-documented:

   • CVE-2019-14287 (sudo): the user ID -1 and its unsigned twin 4294967295 are the same 32-bit value, and it slipped past the check that forbids uid 0 while setresuid() reads -1 as "leave the id unchanged", so sudo stayed root and a rule written to exclude root handed out a root shell.
   • CVE-2022-37454 (XKCP/SHA-3): integer overflow in the official Keccak/SHA-3 implementation triggered a buffer overflow exploitable in any consumer of the library.
   • The Ariane 5 rocket crash (1996): a 64-bit float was cast to a 16-bit integer, overflowing and shutting down the guidance system. Old, but still the canonical example of why width conversions matter.
   • Game economy exploits: item counts and gold values stored as 32-bit ints that wrap around when maximized.

   In C, signed integer overflow is formally undefined behavior; the compiler is allowed to assume it never happens and optimize accordingly, which can introduce security vulnerabilities even when the developer expects wrap-around behavior. Unsigned integers, by contrast, are defined to wrap. Languages like Rust and Swift trap on overflow by default in debug builds. For more on the disassembly workflow used here, see Buffer Overflow Binary Exploitation in CTF.

Flag

Any pair causing signed overflow works; using INT_MAX keeps the math simple.