Blackhat Demo Explained

It was a hot morning approx. 9 in Vegas waiting for the John’s McDonald and Chris’ Valasek lecture about Heap Exploitation, it was an advanced lecture, and dizzy I was, so I didn’t understand much. Those guys posted a demo explanation about the attack. You can also download their paper. BHUSA09-McDonald-WindowsHeap-PAPER

Posted by Chris Valasek on December 09, 2009 at 11:08 AM EST.

Introduction

As several of you may or may not remember, John McDonald and I did a presentation this year at BlackHat on Practical Windows Heap Exploitation. In this presentation we had a video that claimed to show reliable heap exploitation on Windows Server 2003 lacking a fully controlled environment. Now that our advisory is published we can finally prove to you that the video was not fake; explaining the vulnerability and some of our techniques.
Vulnerability

The code below represents a poor attempt at pseudo code for the vulnerability:

//some parsing and validation of the request done here
//
//
//

num_of_strs = ReadDWORD();//we assume that they are attempting to account for DWORD
//writing (you know what happens when you assume….)

buffer = malloc(num_of_strs * 4);

while(num_of_strs) {

string str = ReadWString();  //this does a bit of validation
if(!str)
break;

DWORD intval = (DWORD)IntFromStringHash[str]; //limited values
if(!intval)
break;

memcpy(buffer, intval, 4);

size–;
}

As you can see from the code above, the vulnerability is caused by an integer overflow when multiplying a user supplied integer. The wrapped integer is subsequently used in an allocation, resulting in an insufficiently sized buffer. From there the code loops ‘num_of_strs’ iterations through the user-controlled payload attempting to read strings, producing an integer value based on the string value. This integer is then written to the recently allocated buffer and the process is repeated. This leads to a condition where you can write more data to the buffer than was previously allocated. Unfortunately you do NOT entirely control the contents of that write.

Exploitation Prerequisites

We had to overcome quite a few hurdles to successfully exploit this vulnerability. The first being the ability to normalize the heap, ensuring a chunk of a known size ended up in the heap cache. The second was overwriting the size of an adjacent heap chunk with values that would be advantageous to exploitation. The third was ensuring that this highly multi-threaded application didn’t use our mangled heap chunks in a legitimate allocation, hence crashing before we could attempt to fully exploit the service.

Heap Normalization

Since eDirectoy is a multi-threaded program that performs many complex operations we couldn’t just make an allocation followed directly by an overflow/overwrite. Our research showed that the heap was rarely in a predictable state.

The diagram above shows that there could be various entries in the heap cache making it too difficult to reliably predict a chunk size to overwrite. To remedy this situation we decided to use a series of memory leaks putting the heap in a more normalized state.

We used a combination of soft leaks and hard leaks (Waisman 2007) to achieve heap normalization. The term soft leak will refer to a chunk of memory that is allocated by the attacker and freed at a time of the attacker’s choosing, while a hard leak will refer to a chunk of memory that is allocated, never to be freed again. While most developers are familiar with hard leaks (memory leaks), most people don’t realize soft leaks exist (think about memory allocated on a per-connection basis). While finding soft leaks using a heap profiler was done quite easily, it took some static analysis to find a sufficient hard leak (finding a bug, to exploit a bug :-)).

The first step was to allocate a chunk of memory for which we knew the size, could free at a later time, and would guarantee that, when freed, would not be coalesced. This was achieved by wrapping our soft leak allocation within two hard leaks (some details omitted):

The next step was to issue requests that caused hard leaks resulting in a heap cache that was empty for all buckets less than 8192 bytes (This isn’t actually the case. As long as you can ensure that the entries in the cache won’t interfere with your size-overwrite then it will work). This gives us the opportunity to use our soft leak to free a chunk of a known size into the heap cache.  Leaving the heap looking like this:

Size Overwrite

At this point we were actually ready to start the exploitation process. Since we knew about a chunk in the heap cache and its size, we could then proceed to issue a request that would be serviced by our recently freed chunk (on the heap cache). We also needed to overwrite the heap metadata for a chunk of a known size. The way we accomplished this was to issue an allocation for 0x900 bytes, resulting in a block split that would contain an adjacent chunk of 0x738 bytes:

This block splitting returned us the chunk of size 0x900 and left chunk of size 0x738 on the heap cache for overwriting. The difficult part here was getting an intval returned from the IntFromStringHash table that would work for exploitation. Remember, we needed to ensure that the value we used to overwrite the size of 0x738 was large enough to reside in the heap cache,  overwrite the flags so that the block would not be coalesced, and was a value not frequently used in allocations. The following diagram shows what the block looked like pre-overflow and post-overflow:

Now that we’ve overwritten the size of an entry in the heap cache, there exists a stale entry. This guarantees us that every time we make a request for the size we overwrote; we will receive the same address back. From there we used FreeList Insertion technique (Moore 2007) to overwrite a lookaside list with an address of a function pointer. We had to find a lookaside list that wasn’t used frequently, or at all, by the application to avoid premature termination due to heap corruption. After that it was trivial to turn off DEP and execute code.

Trials and Tribulations

After a subpar explanation of all these steps I’d like to discuss what made exploitation so challenging. A vast majority of our time was spent finding elegant (LOL!) solutions to heap normalization. This was very important because we did not have a stable heap due to the nature of the service, as known heap chunk sizes were not predictable without some massaging. Without heap normalization, we would have had wildly unreliable exploitation, if any at all.

The second most challenging portion was overwriting a chunk’s size with a value we could control. Since this wasn’t your typical heap-overflow we had to find a string-to-integer-value that, when split, would result in an entry of a known size residing on the heap cache. On top of having the entry, post-split, on the heap cache it was also very helpful to have the integer value mark the flags in the adjacent chunk header as NON-Free (busy or otherwise).

Conclusion

Although the time it took us to reach reliable exploitation neared several weeks it was worth the effort to prove a few things. Some people would have called this vulnerability ‘un-exploitable’, which is obviously not the case. While others would have claimed remote code execution without actually showing it was possible. X-Force always demands that a working exploit be written for a code execution bug. This way, we never have to use the term ‘potential code execution’. Finally we had to prove that the heap cache exploitation techniques were not just parlor tricks designed for a BlackHat talk, but a real-world technique that could leverage near impossible exploitation scenarios into internet victories.

Click here for our Blackhat demo video.

Please feel free to email any questions to:
cvalasek@us.ibm.com / jrmcdona@us.ibm.com

References

Waisman, Nicolas. 2007. Understanding and bypassing Windows Heap Protection. SyScan 2007, http://www.immunityinc.com/downloads/Heap_Singapore_Jun_2007.pdf

Moore, Brett. 2008. Heaps About Heaps. SyScan 2008, http://www.insomniasec.com/publications/Heaps_About_Heaps.ppt

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: