Two Sums

The challenge (figure 1) wants 2 integers that satisfy the expression of:

n1 > n1 + n2  OR  n2 > n1 + n2

The condition being that they must both be positive. The 2 hints also offer very important details, namely that integer overflow is involved and that this is not a mathematical problem (figure 2).

This would make sense in that neither n1 or n2 would be positive mathematically.

n1 + n2 < n1
n2 < n1 - n1
n2 <0

n1 + n2 < n2
n1 < n2 - n2
n1 < 0

The challenge also reveals that flag.c, a C script runs when a user logs into the remote server. The script takes 2 numbers from the user as input. The addIntOvf function is first declared such that if both the input numbers are positive but their sums are negative or vice versa, it returns the value of -1. Later on in the main function if calling addIntOvf returns -1, the flag is printed out (figure 3).

Integer Overflow

In the C language, integers can be unsigned or signed. Unsigned integers are always positive, but for signed integers the most significant bit to the left is assigned to denote it as a positive or negative number. If that bit is 1, the integer is positive, if that bit is 0, the integer is negative.

X86, the most popular computing architecture on most server devices can either be 32 bits or 64 bits. In the case of 32 bits OS, up to 32 bits can be used to represent a C integer. If it’s signed, 1 out of 31 bit is used to denote it as positive or negative. As computers use binary number system of either 1 or 0, this means that the maximum combination this signed integer could represent would be:

2 ^ 31 = 2147483647

As the signed integer can be negative or positive, the range of denary numbers represented by this integer is therefore -2,147,483,647 to +2,147,483,647.

The same logic apply to 64 bits OS where 64 bits represent an integer. 1 out of 64 bit is used to denote it as positive or negative, whilst 63 bits represents the value. Hence the maximum combination is

2 ^ 63 = 9223372036854775808 

Thus a signed integer on 64 bit OS can cover the denary range of -9,223,372,036,854,775,808 to +9,223,372,036,854,775,808.

When the range is exceeded, integer overflow occurs because the designated storage has run out, this changes the value of the most significant bit and as a result the value becomes negative. For example, on a 32-bit system, 1 added to 2,147,483,647 would not give 2,147,483,648 but rather -2,147,483,648.

This means if n1 and n2 are integers large enough to exceed the storage limit when added together, the expressions can be satisfied.

Procedure

The server is likely of an x86 computing architecture. It’s unknown if it’s 32-bits or 64-bits. Thus, it’s worth trying to exceed the maximum positive denary number that can be represented on a 32-bit system first. If that does not work, the maximum for 64-bits can be tried.

For this purpose, I choose the following:

• let n1 = 2147483647 (the maximum positive signed integer that 32 bits can represent)
• let n2 = 2 (a randomly picked positive number that will push the sum over the limit)

The flag is then revealed because the values for n1 and n2 caused integer overflow.