Sometimes you succeed in solving a problem but you don’t truly understand why it worked. This is what happened to Mor and me when we solved PicoCTF-2019 challenge called flag_shop.

In this challenge, you are a visitor in a flag shop. You can purchase the flag for a certain number of coins, then print it and win. The problem is, the winning flag costs 100,000 coins, and we only have 1,100. However, there’s a much cheaper flag in the shop which costs only 900 coins.

The code for buying cheap flags is as follows :

``````int account_balance = 1100;
int number_flags = 0;
int total_cost = 0;
while (1) {
scanf("%d", &number_flags);
if(number_flags > 0) {
total_cost = 900 * number_flags;
if (total_cost <= account_balance) {
account_balance = account_balance - total_cost;
}
else {
printf("Not enough balance\n");
}
}
}
``````

 - This is a slight simplification of the challenge, but the main concept remains.

Quite quickly we understood that our goal was to increase `account_balance` to a value higher than 100,000 - the price of our desired flag. If only `total_cost` could be negative (line 9), we could increase our balance. The good news is, `total_cost` can be negative if we trigger an integer overflow. Namely, if `total_cost` is high enough such that its most-significant bit is set - it’ll be considered negative (if you’re not familiar with integer overflows at all, read and then come back, we’ll be waiting).

### First Attempt

Our first thought was “Ok, let’s have `number_flags = -1`”. This will cause the total cost to be -900, leading to our balance growing by 900, right? -1 is represented by 32 set bits, which can be obtained from the number `2**32-1`. But this didn’t work, and nothing happened to our balance.

In a quick brute-force attempt we passed `2**31-1` as an input and boom, our balance increased to 2000. So we managed to trigger the integer overflow, because `total_cost` was negative, but why with the second input and not the first? The next section will answer this question.

### Breakdown

It took us some time to rediscover the first `if` statement (line 6). When our input was `2**32-1 = -1`, we never reached the code which calculates our new balance. So `2**32-1` was prone to failure. But why, why did `2**31-1` do the job in getting us +900 coins?

Let’s go back to some theory.

• Unsigned integers of 32 bits can represent any value between `0` and `2**32-1`.
• Signed integers of the same size can represent any value between `-2**31` and `2**31-1`.

By providing `2**31-1` as input, we practically gave the highest positive number possible with a signed integer. This is why we successfully passed the `if` check - the number of requested flags was positive. But how come `2**31-1`, which is the highest positive number, resulted in the same value we expected to get with `2**32-1`?

Let’s do the math associated with line 7. Trust me, this is going to be pretty basic arithmetic :)

``````total_cost = 900 * number_flags
= 900 * (2**31 - 1)
= 450 * 2 * (2**31 - 1)
= 450 * 2 * 2**31 - (450 * 2 * 1)
= 450 * 2**32 - (900)
= 450 * 0 - 900  // 2**32 is one followed by 32 zeros, thus a zero
= -900
``````

This is how we got -900. What would have happened with `2**32-1`?

``````total_cost = 900 * number_flags
= 900 * (2**32 - 1)
= 450 * 2 * (2**32 - 1)
= 450 * 2 * 2**32 - (450 * 2 * 1)
= 450 * 2**33 - (900)
= 450 * 0 - 900  // 2**33 reuslts in a zero for the same reason as before
= -900
``````

Practially, the same thing happens. Both inputs are large enough to result in a zero, leaving only the `-900` as a remainder. The only difference with regards to the challenge is that the first input passes the positivity check (line 6 in the challenge code), whereas the second doesn’t.

### Bonus: The One-Iteration Solution

What if we had to reach a balance higher than 100,000 with only a single iteration? What if we wanted the quickest win possible? Recall that with an input of `2**31-1`, we got an increase of `900*1`. What happens with `2**31-2`?

``````total_cost = 900 * (2**32 - 2)
= 450 * 2 * (2**32 - 2)
= 450 * 2 * 2**32 - (450 * 2 * 2)
= 450 * 2**33 - (1800)
= 450 * 0 - 1800
= -1800
``````

To generalize, for input `2**31-i` we get an increase of `900*i`.

If so, we need to choose an `i` for which `1100 + 900*i > 100000`. Such an `i` can be, for example, `128 = 2**7`. This gives us:

``````1100 + 900 * 128 = 116300 > 100000
``````

Our input needs to be `2**31-2**8 = ‭2147483520‬`. Here’s what we get back (notice the balance after the transaction):

``````vm@ophir-Virtual-Machine:~\$ nc 2019shell1.picoctf.com 14937
Welcome to the flag exchange
We sell flags

1. Check Account Balance

3. Exit

2

Currently for sale
1. Defintely not the flag Flag
2. 1337 Flag
1

These knockoff Flags cost 900 each, enter desired quantity
2147483520

The final cost is: -115200

Your current balance after transaction: 116300

... Commands to purchase the winning flag
now that we have enough money ...