flag_shop picoCTF 2019 Solution

Description

1. Step 1Trigger signed int overflow on the purchase

   Observation

   The fake flag costs 900 coins and the shop takes a quantity field. So the server multiplies price by quantity to get a total, and a large enough quantity can overflow a signed 32-bit integer and flip that total negative.

   The shop sells fake flags for 900 coins each. The server computes total_cost = 900 * number_flags as a signed 32-bit integer. Enter a large quantity such as 2147483647 (INT_MAX). Because 900 * 2147483647 far exceeds INT_MAX, the result wraps around to a large negative number. The server then subtracts that negative cost from your balance, which actually increases your balance. Each such purchase adds roughly 900 coins (the wrapped result -900 means your balance goes from 1100 to 2000). Repeat a few times, or enter a carefully chosen quantity like 3,579,138 so the product overflows to a very large negative number, giving you a balance well above 100,000 in a single transaction.

   What didn't work first

   Tried: Trying to buy the real flag directly by entering a negative quantity to get coins subtracted in reverse.

   Most shop servers cast input to unsigned or reject negatives outright with an 'invalid quantity' error. The overflow has to happen inside the server's own multiplication, not by handing it a negative number. Supply a large positive quantity and let the server-side multiplication wrap.

   Tried: Buying fake flags one at a time repeatedly to slowly accumulate the 100,000 coins needed.

   A fake flag costs 900 coins and you start with 1100, so you can afford exactly one honest purchase before going broke. Grinding is deliberately impossible; the exploit is the only path to enough coins. The quantity field is what triggers the overflow, not repeating the transaction.

   Learn more

   A signed integer overflow occurs when an arithmetic operation produces a result outside the range representable by the integer type. A 32-bit signed integer can hold values from −2,147,483,648 to 2,147,483,647 (INT_MIN to INT_MAX). When the true mathematical result exceeds INT_MAX, two's complement wrapping produces a large negative number.

   Here, the server computes total_cost = 900 * number_flags. With number_flags = 2,147,483,647 (INT_MAX), the true product is about 1.93 trillion, which is far beyond INT_MAX. Two's complement wrapping leaves the stored value at -900. The server then computes balance -= total_cost, and subtracting -900 is the same as adding 900, so the balance rises from 1100 to 2000. Alternatively, choosing a quantity such as 3,579,138 makes the product wrap to a very large negative number, crediting millions of coins in a single purchase.

   This class of vulnerability is responsible for real-world security incidents. Notable examples include the Ariane 5 rocket explosion (1996), where a 64-bit float was converted to a 16-bit signed integer causing a crash; various game economy exploits; and CVE entries in financial software. In C/C++, always validate that the quantity is in a safe range before multiplying, use types like int64_t for quantities that could grow large, or use checked arithmetic functions that return an error on overflow.

2. Step 2Buy the real flag

   Observation

   After the overflow purchases the balance shows a large positive number. The exploit worked, so the balance check on the real flag will now pass with an ordinary purchase.

   With the inflated balance, purchase the 1337-flag from the shop. The server prints the real picoCTF flag.

   What didn't work first

   Tried: Trying to enter the same large overflow quantity when purchasing the real flag to get a further discount.

   The real flag has a fixed price and the server just checks whether your balance covers it, so an ordinary purchase is all that is needed. Another overflow quantity here may produce an error or odd behavior. Select the real flag and confirm with the default quantity of 1.

   Learn more

   Once you have a massive coin balance from the overflow exploit, the shop's normal price check passes trivially. The server simply verifies balance >= price, which is now satisfied since your balance is a large positive number (or the check itself wraps in your favor).

   This demonstrates the broader vulnerability class of improper input validation combined with integer handling errors. A secure implementation would validate that the requested quantity is positive and within a reasonable range before performing any arithmetic, or use checked arithmetic functions that return an error on overflow.

   In CTF binary exploitation challenges, integer overflows often serve as a stepping stone to more serious vulnerabilities - for example, overflowing an allocation size to cause a heap underallocation, then overflowing the allocated buffer to corrupt adjacent memory. Understanding how integers behave at their boundaries is a foundational skill for binary exploitation.

Flag

Signed integer overflow in C wraps around - 900 * a large quantity overflows to a negative cost, which adds to your balance instead of subtracting.