The word ‘overflow’ itself is quite descriptive of the vulnerability we’re going to discuss in this post. Consider a glass into which water is being poured. If the total volume of water poured in is less than or equal to the volume of the glass, everything is rosy. When the volume of water exceeds the glass’ volume, it ‘overflows’ and you’ll have a wet floor to mop.
Variable Type Specifiers and Modifiers
In C (and many other languages), values are stored in variables which have a certain type. (Of course, there are languages like Python where the programmer does not have to specify variable types.) There are four basic variable types:
charintfloatdouble
In addition to the above types (also called type specifiers), there are four type modifiers:
signedunsignedshortlong
The variable type along with the (optional) modifier decides the maximum and minimum values that the variable can store. For example, on 32-bit machines a signed int variable type can store values from -2,147,483,648 to 2,147,483,647, or in other words a signed int is 4 bytes in size. For more information on data type sizes, refer to C Data Types
Note
The system that I’m using for all examples:
nikhilh@ubuntu:~$ uname -a
Linux ubuntu 4.15.0-36-generic #39~16.04.1-Ubuntu SMP Tue Sep 25 09:00:45 UTC 2018 i686 i686 i686 GNU/Linux
Ariane 5 Rocket Crash
If we have a signed int variable named, say x and we try to put in a value that is more than the maximum or minimum allowed value for a signed int, it’ll overflow. In loosely typed languages like C, overflow situations are usually not marked as an error at compile-time. gcc is likely to give a warning in such cases but they can be ignored (which is a problem). Consider the below program:
int main(void) {
int x = 0x180000000;
printf ("%d\n", x);
return 0;
}In C, the default type modifier for int is signed. We have a signed int variable type into which we are placing a value (for whatever reason) of 0x180000000 which is hex for 6,442,450,944 which is obviously more than the maximum allowed value of 2,147,483,647. Let’s see what happens when we compile using gcc and run:
nikhilh@ubuntu:~$ gcc -o overflow overflow.c
overflow.c: In function ‘main’:
overflow.c:5:13: warning: overflow in implicit constant conversion [-Woverflow]
int x = 0x180000000;
^
nikhilh@ubuntu:~$ ./overflow
-2147483648
C just looked at 32 bits, discarded the value at the 33rd bit and above. This is a case of truncation which was caused due to overflow. Imagine a situation where the value of x was required at a later stage in the program and it was expected that x would contain 0x180000000. In the worst case situation, it would cause a disaster. Consider the case of the Ariane 5 rocket which crashed because of a “a small computer program trying to stuff a 64-bit number into a 16-bit space.”
Integer Overflow – Examples
In general, not all vulnerabilities are exploitable by attackers. However, overflow vulnerabilities are especially dangerous because they may lead to program instability even under normal operation and in many cases, are exploitable as well. Before we look at more examples, here’s something to keep in mind:
Circle of Integers
When I was learning about integer overflows, I found the Circle of Integers (completely made up name) helpful in developing an intuitive feel for this subject.
For signed int, the Most Significant Bit (MSB) also marks the sign for the value – the sign bit. For ex: 0x7fffffff is equal to 2147483647 but 0x80000000 is equal to -2147483648 which is the same as 2^31 but with a negative sign because the MSB is set to 1. For unsigned int, no such sign bit exists. Therefore, 0x80000000 is equal to 2147483648.
Overflow occurs when two numbers with:
- same sign are added and the result is negative,
- different sign are subtracted and the result is positive.
Addition can be viewed as a clockwise movement on the Circle of Integers, while subtraction can be viewed as an anti-clockwise movement. Now that we know something about overflow conditions, let’s look at two examples.
Integer Overflow – Addition
Consider the below program:
int main(void) {
int num1 = 0x7fffffff;
int num2 = 0x1;
int addition_result = num1 + num2;
printf ("%d\n", addition_result);
unsigned int num3 = 0xffffffff;
unsigned int num4 = 0x1;
unsigned int uaddition_result = num3 + num4;
printf ("%u\n", uaddition_result);
return 0;
}For the untrained eye, the value in addition_result is expected to be 0x80000000 (or 2,147,483,648) and uaddition_result is expected to be 0x100000000 (or 4,294,967,296). Let’s see the actual values:
nikhilh@ubuntu:~$ gcc -o overflow overflow.c
nikhilh@ubuntu:~$ ./overflow
-2147483648
0
What the …? Here’s what happened:
- When
0x1was added to0x7fffffff, the result became0x80000000. So, why did this cause an overflow? The answer could still be represented in 32 bits. Actually, no. Forsigned inttype, the number of bits available for the value is 31 bits because the 32nd bit is the sign bit. In this case, the 32nd bit was also required to represent the sum and that caused an overflow. - In
unsigned intaddition, the 33rd bit was required to represent the sum and thus caused an overflow.
Again, imagine if the values in these variables were required in later stages of the program. What a disaster it would be when an operation expecting 0x100000000 gets 0x0 instead.
Integer Overflow – Multiplication
I have a perfect example for this. The following code is a snippet from one of the challenges in picoctf 2018:
...
if(number_flags > 0) {
int total_cost = 0;
total_cost = 1000*number_flags;
printf("\nYour total cost is: %d\n", total_cost);
if(total_cost <= account_balance) {
account_balance = account_balance - total_cost;
printf("\nYour new balance: %d\n\n", account_balance);
}
else {
printf("Not enough funds\n");
}
...Here’s how this code can be exploited:
nikel@pico-2018-shell-1:~$ nc 2018shell1.picoctf.com 5795 Welcome to the Store App V1.0 World's Most Secure Purchasing App [1] Check Account Balance [2] Buy Stuff [3] Exit Enter a menu selection 1 Balance: 1100 Welcome to the Store App V1.0 World's Most Secure Purchasing App [1] Check Account Balance [2] Buy Stuff [3] Exit Enter a menu selection 2 Current Auctions [1] I Can't Believe its not a Flag! [2] Real Flag 1 Imitation Flags cost 1000 each, how many would you like? 1000000000 Your total cost is: -727379968 Your new balance: 727381068
And that is integer overflow due to multiplication! Notice this statement in the source code:
total_cost = 1000*number_flagsWhat if the product value exceeded the range of positive values possible for signed int variable, total_cost? It would become negative, and that’s what happened! Imagine if a real production software had code like this!
Done!
That’s all! In this post, we specifically looked at integer overflows but overflow can occur in a variable of any data type. In the coming weeks, I’ll also write about buffer overflows which has been one of the most deadliest vulnerabilities in software.
Overflow vulnerabilities easily sneak into the code and it is quite difficult to detect them. The easiest way to mitigate them is to not introduce them in the first place. However, fuzzing is a good technique to detect overflows. Code reviews can also help but it needs a trained eye. Overflow vulnerabilities are dangerous as you’ve already seen in the case of Ariane 5 and the picoctf example.
Thanks for reading and if you have any questions, please let me know in the comments section below and I’ll get back to you as soon as I can.