two-sum picoCTF 2023 Solution

Description

1. Step 1

   Read flag.c to understand the overflow check

   Observation

   I noticed the challenge provided a downloadable flag.c source file alongside a condition (n1 > n1 + n2) that is mathematically impossible for positive integers, which suggested the overflow mechanism was implemented in the C code and reading it would reveal exactly how the check triggers.

   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

   Without reading the source you miss that the check is specifically addIntOvf detecting a sign flip, not a simple bounds comparison. Different challenges implement overflow detection differently - some check against INT_MAX directly, some use __builtin_add_overflow, and some compare unsigned reinterpretations. Reading the source confirms the exact mechanism so you pick the right input strategy.

   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 on no overflow - the opposite of a typical success/failure convention. If you submit values below INT_MAX (for example 1,000,000,000 + 1,000,000,000 = 2,000,000,000 which fits in 32 bits), no overflow occurs, the condition never triggers, and the server rejects the input without printing the 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 2

   Submit the overflow pair

   Observation

   I noticed that flag.c's addIntOvf() function detects overflow by checking for a positive a, positive b, and negative result, which confirmed that sending two INT_MAX values (2,147,483,647) would guarantee the sum wraps to a negative and satisfy the bogus 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 60781

   Copied!

   What didn't work first

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

   2147483648 cannot be represented as a 32-bit signed integer at all - it is INT_MIN in two's complement and the C server will read it as -2147483648 when scanned with scanf into an int. The addIntOvf check requires both inputs to be positive (a > 0 && b > 0), so a negative input fails that guard and the overflow branch is never reached.

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

   Interactive Python sending is fine in principle, but a common mistake is sending '2147483647' followed by a newline and then waiting for a prompt before sending the second value. If the server reads both numbers in a single scanf loop without printing an intermediate prompt, the interactive approach stalls waiting for output that never comes. The printf pipe sends both values at once with no timing dependency, which is the reliable approach.

   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-2018-10933 (libssh): integer-handling bug let attackers bypass authentication entirely.
   • 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.