BkPctf - Alewife

The name of the file should have given us a hint as to the nature of the problem.. but it took me a while as I just started working on it and didn't pay attention to the name (nor see the problem description text).. and of course my modus operandi is to reverse engineer things to find a vulnerablity, so I didn't connect but just dove into the reversed binary so I didn't pay attention to the ArrayOps string.

The problem was a pwnable, which meant that there was a vulnerability somewhere. My job was to find it. But first I had to understand what the program was doing as the only output strings were:

• "**:"
• "***:"
• "ii:"
• "iii:"
• "ss:"
• "sss:"
• "ArrayOps\n"
• "--:"

The input to the program is through three functions (as I named them), after printing a prompt they do their respective action.

• GetUint (0x400960) - gets up to 0x3f bytes into 0x40 sixed cleared stack buffer, then calls strtoul
• GetInt (0x40097f) - gets up to 0x3f bytes into 0x40 sized cleared stack buffer, then calls atoi, returns value
• Get_0x3f (0x400a04) - gets up to 0x3f bytes with a single read into a malloc'd buffer

Sadly, none of these were vulnerable to any overflow, so the bug had to be somewhere else.

After a while reversing we determined that the code allowed you to manage three types of arrays:

1. Mixed String/Integer arrays.
2. Integer arrays
3. String arrays

Each array was a fixed size of up to 256 elements, and you were limited to 32 of each type. The main function was a loop that allowed you to select the type of array, and then perform an action. After reversing we discovered the menu tree:

• 1 - Mixed Arrays
  • 1 - Allocate a new array
  • 2 - More operations
    • 1 - Add integer(s) to array
    • 2 - Add string(s) to array
    • 3 - Remove last element from array (decrement count)
    • 7 - Subtract two integer values
    • 8 - Add two interger values
    • 9 - Concatenate two string values
  • 3 - Clear an array
  • 4 - Print the array
  • 5 - Copy the array to a non-mixed type
• 2 - Integer Arrays
  • 2 - More Operations
    • 1 - Replace array elements
    • 3 - Sort array
    • 4 - Remove the last element (decrement count)
  • 3 - Clear Array
  • 4 - Print Array
• 3 - String Arrays
  • 2 - More Operations
    • 2 - Replace array elements
    • 3 - Sort arry
    • 4 - Remove last element
  • 3 - Clear Array
  • 4 - Print Array

All of the functions that would take an index verified the index was >= 0 and < 32. As you may have noticed, there is not a way to directly allocate a single-type array, you have to use the copy function, which requires all elements to be of the same type.

Each of the arrays used a structure:

//Structure for mixed array
//int is an 8 byte type
struct mixed_element {
	char type; // 2 = number, 3 = string
	char pad[7];
	struct {
		int value;
		FUNC_PTR to_str;
		FUNC_PTR add;
		FUNC_PTR subtract;
	} number;
	struct {
		char *ptr; //Pointer of the string from the user, allocated in heap as read by Get_0x1f
		FUNCPTR to_str;
		FUNCPTR strcat
	} str;
}

struct MixedArray {
	char allocated;
	char pad[7];
	mixed_element data[256];
	int numElements;
	FUNCPTR printFunction;
}

//Structure for Integer and String Arrays
struct array {
	char initialized;
	char pad[7];
	DATA_TYPE data[256]; //DATA_TYPE is int for integer arrary, char* for string arrays
	DATA_TYPE *pData; //Pointer to the start of data.
	int numElements;
	FUNCPTR printArray;
	FUNCPTR sort;
}

// Layout of BSS
MixedArray mixed_arrays[0x20]; // 0x602ec0
array int_arrays[0x20]; // 0x6831c0
array str_arrays[0x20]; // 0x6936c0

There's nothing there for type confusion as the values in the mixed array do not overlap, and the integer and string arrays are separate. But what does stand out is the pData member of the integer and string arrays, why is it needed if the array contents are statically allocated, if we could somehow get something into this pointer we could have a potential arbitrary write.

The print, to_str, sort, add, and subtract functions all looked ok. The strcat had a bug with it's use of realloc - if you passed in the same index to copy, it would free the data pointer (with realoc), but sadly, there wasn't a way to re-use the pointer as every read malloc'd a new buffer.

So I then started looking at other functions. When I found get_int_array

int get_int_array() {  //0x400cd3
	int result;
	array *c;
	int idx;
	
	for (idx = 0; idx < 0x20; idx++) {
		c = &int_arrays[idx];
		result = is_initialized(c);
		if (!result) {
			int_array_ctor(c);
			return idx;
		}
	}
	return result;
}

//for completeness
int is_initialized(array *a)  { //0x400c5a
	return a->initialized;
}

void int_array_ctor(array *a) { //0x4021db
	a->pData = &a->data;
	a->numElements = 0;
	a->initialized = 1;
	a->sort = SortIntArray;
	a->print = PrintIntArray;
	memset(a->pdata, 0, 0x256 * 8);
}

So it looks like that function always will return an empty freshly initialized array... but what happens if all the arrays are in use?
It returns the value of the last is_initialized() call, which happens to be 1. Which means that whatever function was calling this that thought it was getting an empty array isn't. I had found the bug. But now how to use it as all the read functions from the user verify that we're not sending more than 256 values.

It turns out this function was only called in the copy_to function.
The basic layout of the copy to function was:

int copy_to(mixed_idx, type) { //0x4016e2
	if 8mixed_idx > 0x1f) 
		return -1;
	if (type == 2) {
		to_idx = get_int_array();
		if (copy_to_int(&mixed_arrays[mixed_idx], &int_arrays[to_idx]) != 0) {
			memset(&int_arrays[to_idx], 0, sizeof(array));
			return -1;
		}
	}
	else if (type == 3) {
		to_idx = get_str_array();
		if (copy_to_str(&mixed_arrays[mixed_idx], &str_arrays[to_idx]) != 0) {
			memset(&str_arrays[to_idx], 0, sizeof(array));
			return -1;
		}
	}
	return to_idx;
}

Not much there.. but if we looked at the individual copy to function:

int copy_to_type(MixedArray *mixed, array *ar) { //copy_to_int @ 0x400b69
	i = 0;
	if (mixed && mixed->numElements <= 0x100) {
		type *pData = ar->pData;
		while (i < mixed->numElements) {
			mixed_element *c = &mixed->data[i];
			if (c->flag != TYPE) { //TYPE == 2 for int, 3 for string
				return -1;
			}
			pData[i] = mixed_element->type.value;
			ar->numElements++;
			++v5;
		}
	}

Did you notice something above in copy_to_type? Even though the copy starts at element 0, the number of elements is never reset.

So it looks like we could make numElements greater than 256, however we can't just write arbitrary values.. as copy_to is always starting at index 0, and the replace array functions validate that we aren't sending more than 256 elements. But it turns out we have a very useful function, sort! All we need to do is inrease numElements and then sort the value we want into pdata.

One issue is that in order to use sort, I either need to have my desired pData be greater than the current value (meaning it's just pointing at other data or heap), or the function pointers get sorted to a bad value as they are less than the original pData. If all I needed was an arbitrary write that would be ok, but I need an info leak in order to make the exploit easier. I chose to two a two stage approach by first setting pData to iself, then changing it to my final desired value and restoring the function pointers in the first arbitrary write. Then leaking my information and finally getting execution control.

So now for the exploit (high level, as the implementation is left as an exercise for the reader)

1. Create a new mixed array #0
2. Fill it with [0]*254 + [0xfffffff]*2
3. Copy the array 20 times to fill up all integer arrays
4. Create a new mixed array #1
5. Add some integers to the new mixed array. These values will be what we sort into pData
   • I added 4 copies of &int_arrays[1].pData
6. Copy mixed array #1 (it will go into int_array[1], and increase num_elements to 260)
7. Then sort the 2nd integer array (idx 1)
   • it's pData member now points to itself!
8. Create a new mixed array #2
9. Add the values [ &GOT, 0x40, &PrintIntArray, &SortIntArray ]
10. Copy the values from mixed #2; this will copy them to array idx 1 again, changing pData to point to the GOT, and restoring the function pointers (and making the size sane)
11. Call print int array with idx 1 to leak information about libc
12. Change the atoi entry in the GOT addresses we received to the address of system() based on the information we just leaked
13. Create a new mixed array #3
14. Put the updated GOT values into mixed #3
15. Copy mixed #3; which will overwrite the GOT
16. Now any value we send for a command is executed via system()
17. Run a shell!

The final flag was: Because_C++_is_t00_hard!!!