Spot the Vuln: Bored Games
justin April 15th, 2007
Sorry about the recent lull in posts. John and I have had some major changes with our day jobs, and Mark is busy closing out his month long "Dowd Live 2007 World Tour." We expect regular posting to begin again in the next week or two, though, so don’t give up on us yet. Just to show we still care, here’s a C++ vulnerability puzzle that should hold your attention for a minute or two.
The following two files implement a board class for a network game. Assume that you control the parameters for board creation and can arbitrarily get and set squares on the board after it’s been created. Where’s the vulnerability and how would you exploit it?
Board.h
class Board {
public:
static const int ERROR_SQUARE = -1; // invalid square id
Board(unsigned int, unsigned int);
~Board(void);
// returns square at a given coordinate
int getSquare(unsigned int x, unsigned int y);
// sets square at a given x-ycoordinate
bool setSquare(unsigned int x, unsigned int y, int square);
// return x dimension (width)
int getXdim(void) {return m_x;}
// return y dimension (height)
int getYdim(void) {return m_y;}
private:
unsigned int m_x;
unsigned int m_y;
int *m_squares;
};
Board.cpp
Board::Board(unsigned int x_dim, unsigned int y_dim) {
int len = x_dim * y_dim;
m_x = 0;
m_y = 0;
m_squares = NULL;
if (x_dim > 0 && (x_dim <= (unsigned int)-1/y_dim)
&& len <= (size_t)-1/sizeof(m_squares[0])) {
m_x = x_dim;
m_y = y_dim;
m_squares = (int*)calloc(len, sizeof(m_squares[0]));
}
}
Board::~Board(void)
{
if (m_squares) free(m_squares);
}
// returns square at a given coordinate
int Board::getSquare(unsigned int x, unsigned int y) {
if (x >= m_x || y >= m_y) return Board::ERROR_SQUARE;
return m_squares[y * m_x + x];
}
// sets square at a given x-ycoordinate
bool Board::setSquare(unsigned int x, unsigned int y, int square) {
if (x >= m_x || y >= m_y) return false;
m_squares[y * m_x + x] = square;
return true;
}
“int len = x_dim * y_dim;”
This line suffers from an integer arithmetic boundary condition as you describe on pg 210 onwards.
x_dim and y_dim are unsigned ints, with the ability to be in the range 0 to 4,294,967,295 each. However, the destination integer is going to likely be a signed int on most C++ implementations, thereby permitting valid values in the range -2,147,483,648 to 2,147,483,647.
The problem exists when the x_dim and y_dim dimensional attributes multiply together to produce a result larger than the signed int can handle, which will lead to an integer overflow with len set to a negative value.
This causes the expression “len <= (size_t)-1/sizeof(m_squares[0])" to always evaluate true, permitting an odd calloc.
From there we could use setSquare or getSquare to write or read from arbitrary memory locations outside the m_squares[] array.
Hoping this is the answer you’re looking for.
The constructor parameter y_dim is not checked for non-zero.
Passing x_dim > 0 and y_dim == 0 will result in a calloc() with len == 0. Thus the getSquare() and setSquare() methods will allow you to read/write arbitrary heap values.
Exploiting is a simple matter of finding, for example, the vptr table of the current object and overwriting a function pointer.
/olle
Well, (assuming a 32-b arch), if you passed in 536870911 and 2 to the constructor, x_dim would be <= (unsigned int)-1/2, len would be 1073741822 which is less than (size_t)-1/sizeof(m_squares[0]), then with calloc(), 1073741822*sizeof(m_squares[0]) = 0 (assuming 32-b int’s), which would yield either a pointer to 0 bytes or NULL depending on libc (although I guess newer ms environments throw an exception), with a usable area of zero you’ve got a range of m_squares to m_squares[1*536870911+536870910] to write to, or given a null you have a range of 0×00 to 0×1FFFFFFF to write to via Board::setSquare().
There’s probably something better, but without sitting down and figuring out all the possible combinations and what can cause problems with len/len*4 and still passing the checks, thats the first thing that comes to mind.
erm, when i test that, I actually end up with 0×3FFFFFFD as a result of y*m_x+x, but then its multiplied with 4 yielding 0xfffffff4, which says the write range when calloc() returns NULL is potentially much larger than expected.
There are two issues. The third condition in the constructor assumes that the entire address space can be allocated, which is false — for example, the application already has some of it. But what makes this mistake exploitable is that the return value of calloc() is not checked.
This allows us to do the following on a 32-bit system: initialize a Board with “x_dim=(size_t)-1/sizeof(m_squares[0])” and “y_dim=1″, thus passing all the tests and ending with a calloc(0xffffffff) which will give us a Board with “m_squares” to 0, “m_x=0
Then we can read and write to arbitrary places in the application memory using getSquare() and setSquare(). Just remember to adjust to the “x” and “y” values to account for the pointer arithmetic going on!
@Rhys - We were intentionally messing with people a bit here. The signed int will be promoted to an unsigned int with the same bit pattern, so the comparison is valid. However, this is assuming a 32-bit architecture, which is a constraint we should have made clear.
@olleB - Good catch, but passing zero for y_dim would throw a divide-by-zero exception in the first comparison in the constructor: (unsigned int)-1/y_dim. You can crash it, but you can’t exploit it that way.
@jf - I’ll leave the intricacies of libc to Mark and John, though we’ll assume for this exercise that libc will check for an integer overflow when appending its own headers. However, it looks like you caught the real issue on your second post.
@Adam - That’s exactly right. All the integer overflow checks were just a distraction. The real problem is a simple failure to check the return value of calloc when you ask for an excessively large size. So, this ends up being an exploitable NULL dereference because you can offset NULL by an arbitrary value.
That closes out this game. I figured it would be a reasonably quick catch but I hope it was at least entertaining. And congratulations to Adam, who has now won the respect and admiration of his peers… and that’s all you really need, right?
———-
Update: I made a mistake in my response to Rhys. I commented (incorrectly) that the conversion could be an issue on 64-bit systems because I was thinking x_min and y_min are size_t. However, they’re both unsigned ints, so there shouldn’t be an issue regardless of the architecture.
@justin-
Well that was my point, to some degree, it depends on how it catches an int overflow in calloc(), under glibc and presumably bsd the return value on int overflow is NULL (size > UINT_MAX/nmemb), under older versions of windows the allocation is allowed (allocating 0 bytes of usable memory), and newer versions throw an exception (I believe because of safeint stuff). So for the sake of moving my reply along, we’ll say under glibc it returns a NULL because (536870911*2)*4 would result in an overflow, allowing us to provide an offset large enough in setSquare() that can reach most of the address space allowing for a write.
Doing it this way allows us to reliably cause calloc() to fail instead of hoping the machine can’t allocate an incredibly large amount of space, which may or may not be possible depending on circumstances, thus I’m actually depending on it catching the int overflow in calloc().
Finally, I used 2 for y_dim to avoid a multiply with zero in setSquare(), but after looking at it again with some sleep it seems like maybe setting m_y to 1 would make calculation of addresses in the write less complicated.
erm, nevermind, i was wrong ;] I made a silly mistake in my arithmetic and (wrongly) assumed 1073741822*2 = 2^32
I thought one of the big issues was that the board functions do not check for negative indexes allowing you to access memory outside the board even for valid boards.
@Roy
No, the indexes will all be treated as unsigned types for the comparison. Nice shot though.