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