flag_shop picoCTF 2019 Solution

Description

1. Step 1

   Trigger signed int overflow on the purchase

   Observation

   I noticed the fake flag price was 900 coins and the shop accepted a quantity field for purchases, which suggested that the server was computing total cost via multiplication and that entering a sufficiently large quantity could overflow a signed 32-bit integer and flip the cost 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 user input to an unsigned integer or reject negative values outright with an 'invalid quantity' error. The overflow needs to happen inside the server's own multiplication, not by feeding it a raw negative number. The correct approach is to supply a large positive quantity that causes the server-side multiplication to overflow.

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

   Each fake flag purchase at the honest price costs 900 coins and you start with 1100, so you can only afford one purchase before going broke. The challenge is designed so that grinding is not possible - the exploit is the only path to enough coins. The key insight is that the quantity field, not a repeated transaction, is what triggers the overflow.

   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 2

   Buy the real flag

   Observation

   I noticed that after the overflow purchases the balance showed a large positive number, which confirmed the exploit worked and that the server's balance-check for the real flag would now pass with a normal 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 checks whether your balance covers it - you only need to confirm the purchase normally. Attempting another overflow quantity at this step may cause unexpected behavior or an error. Simply select the real flag option and confirm the purchase 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.