# Integer Overflow for the Perfectionist Beginner

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 [1]:

```
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");
}
}
}
```

[1] - 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
2. Buy Flags
3. Exit
Enter a menu selection
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 ...
YOUR FLAG IS: picoCTF{m0n3y_bag5_e062f0fd}
```

## Wrap-Up

We love doing bit arithmetics and we cannot lie.

Sometimes, capturing the flag will suffice, and sometime you’ll want to know more. This was a case of wanting to know more.

We hope this was an enjoyable read for you.

**Mor & Ophir**