Use a heap overflow to write arbitrary data

Question

I've been trying to learn the basics of a heap overflow attack. I'm mostly interested in using a corruption or modification of the chunk metadata for the basis of the attack, but I'm also open to other suggestions. I know that my goal of the exploit should be do overwrite the printf() function pointer with that of the challenge() function pointer, but I can't seem to figure out how to achieve that write. I have the following piece of code which I want to exploit, which is using malloc from glibc 2.11.2 :

void challenge()
{
        puts("you win\n");
}

int main(int argc, char **argv)
{
        char *inputA, *inputB, *inputC;

        inputA = malloc(32);
        inputB = malloc(32);
        inputC = malloc(32);

        strcpy(inputA, argv[1]);
        strcpy(inputB, argv[2]);
        strcpy(inputC, argv[3]);

        free(inputC);
        free(inputB);
        free(inputA);

        printf("execute challenge to win\n");
}

Obviously, achieving an actual overwrite of an allocated chunk's metadata is trivial. However, I have not been able to find a way to exploit this code using any of the standard techniques. I have read and attempted to implement the techniques from:

• The paper: w00w00 on Heap Overflows
  • Although the paper is very clear, the unlink technique has been obsolete for some time.
• Malloc Maleficarum.txt
  • This paper expands upon the exploit techniques from the w00w00 days, and accounts for the newer versions of glibc. However, I have not found that given the 5 techniques detailed in the paper, that the code above matches any of the prerequisites for those techniques.
• Understanding the Heap By Breaking it(pdf)
  • The pdf gives a pretty good review of how the heap works, but focuses on double free techniques.

I originally tried to exploit this code by manipulating the size value of the chunk for inputC, so that it pointed back to the head of the inputC chunk. When that didn't work, I tried pointing further back to the chunk of inputB. That is when I realized that the new glibc performs a sanity check on the size value.

How can a user craft an exploit to take advantage of a free, assuming he has the ability to edit the allocated chunk's metadata to arbitrary values, and user it to overwrite a value in the GOT or write to any other arbitrary address?

Note: When I write 'arbitrary address' I understand that memory pages may be read only or protected, I mean an address that I can assume I can write to.

Solution 1

Note: I will say before I answer that this is purely an academic answer, not intended to be used for malicious purposes. I am aware of the exercises OP is doing and they are open source and not intended to encourage any users to use these techniques in unapproved circumstances.

I will detail the technique below but for your reference I would take a look at the Vudo malloc tricks (It's referenced in one of your links above) because my overview is going to be a short one: http://www.phrack.com/issues.html?issue=57&id=8

It details how malloc handles creating blocks of memory, pulling memory from lists and other things. In particular the unlink attack is of interest for this attack (note: you're correct that glibc now performs a sanity check on sizes for this particular reason, but you should be on an older libc for this exercise... legacy bro).

From the paper, an allocated block and a free block use the same data structure, but the data is handled differently. See here:

chunk -> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
         | prev_size: size of the previous chunk, in bytes (used   |
         | by dlmalloc only if this previous chunk is free)        |
         +---------------------------------------------------------+
         | size: size of the chunk (the number of bytes between    |
         | "chunk" and "nextchunk") and 2 bits status information  |
  mem -> +---------------------------------------------------------+
         | fd: not used by dlmalloc because "chunk" is allocated   |
         | (user data therefore starts here)                       |
         + - - - - - - - - - - - - - - - - - - - - - - - - - - - - +
         | bk: not used by dlmalloc because "chunk" is allocated   |
         | (there may be user data here)                           |
         + - - - - - - - - - - - - - - - - - - - - - - - - - - - - +
         |                                                         |
         |                                                         |
         | user data (may be 0 bytes long)                         |
         |                                                         |
         |                                                         |
 next -> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
         | prev_size: not used by dlmalloc because "chunk" is      |
         | allocated (may hold user data, to decrease wastage)     |
         +---------------------------------------------------------+

Allocated blocks don't use the fd or bk pointers, but free ones will. This is going to be important later. You should know enough programming to understand that "blocks" in Doug Lea's malloc are organized into a doubly-linked list; there's one list for free blocks and another for allocated ones (technically there are several lists for free depending on sizes but it's irrelevant here since the code allocates blocks of the same size). So when you're freeing a particular block, you have to fix the pointers to keep the list in tact.

e.g. say you're freeing block y from the list below:

x <-> y <-> z

Notice that in the diagram above the spots for bk and fd contain the necessary pointers to iterate along the list. When malloc wants to take a block p off of the list it calls, among other things, a macro to fix the list:

#define unlink( y, BK, FD ) {            
    BK = P->bk;                          
    FD = P->fd;                          
    FD->bk = BK;                         
    BK->fd = FD;                         
}

The macro itself isn't hard to understand, but the important thing to note in older versions of libc is that it doesn't perform sanity checks on the size or the pointers being written to. What it means in your case is that without any sort of address randomization you can predictably and reliably determine the status of the heap and redirect an arbitrary pointer to an address of your choosing by overflowing the heap (via the strncopy here) in a specific way.

There's a few things required to get the attack to work:

• the fd pointer for your block is pointing to the address you want to overwrite minus 12 bytes. The offset has to do with malloc cleaning up the alignment when it modifies the list
• The bk pointer of your block is pointing to your shellcode
• The size needs to be -4. This accomplishes a few things, namely it sets the status bits in the block

So you'll have to play around with the offsets in your specific example, but the general malicious format that you're trying to pass with the strcpy here is of the format:

| junk to fill up the legitimate buffer | -4 | -4 | addr you want to overwrite -12 (0x0C) | addr you want to call instead

Note the negative number sets the prev_size field to -4, which makes the free routing believe that the prev_size chunk actually starts in the current chunk that you control/are corrupting.

And yes, a proper explanation wouldn't be complete without mentioning that this attack doesn't work on current versions of glibc; the size has a sanity check done and the unlink method just won't work. That in combination with mitigations like address randomization make this attack not viable on anything but legacy systems. But the method described here is how I did that challenge ;)

Solution 2

Note that most of the techniques explained in Malloc Malleficarum are now protected. The glibc has improved a lot all that double free scenarios.

If you want to improve your knowledge about the Malloc Malleficarum techniques read the Malloc Des-Malleficarum and the House of Lore: Reloaded written by blackngel. You can find these texts in phrack.

Malloc Des-Malleficarum

I'm also working on it, and I can say to you that, for example, House of Mind is no longer exploitable, at least, as is explained in the texts. Although it might be possible to bypass the new restrictions added to the code. Add that the easiest way to execute your code is to overwrite the .dtors address therefore your code will always be executed once the program finish.

If you download the glibc code and study the critic zones of malloc., etc you will find code checks that are not documented in the documents previously mentioned. These check were included to stop the double free party.

On the other hand, the presentation of Justin N. Ferguson (Understanding the Heap by breaking it) that you could find in youtube (BlackHat 2007) is perfect in order to understand all the heap mechanics, but I must admit that the techniques shown are far from being reliable, but at least, he opens a new field to heap exploitation.

Understanding the heap by breaking it

Anyways, I'm also working on it, so if you want to contact me, we can share our advances. You can reach me in the overflowedminds.net domain as newlog (build the mail address yourself ^^ ).

Comments

[ose]

Could you clarify which meta-data you are referring to?

[Hot Licks]

Getting predictable results (vs simply crashing the app) out of a heap overflow attack is virtually impossible. Basically you need to know the order of stuff in the heap, and that's only predictable in a few limited circumstances. At best you could use some sort of "peek" scheme to find that you're looking for, but then it would need to have a reliable "signature" to search for. In your case you could search for the text "Execute challenge to win", but even finding that text wouldn't help much, since it's likely in protected storage.

[amccormack]

@ose I've edited the question to make it a little more clear. I'm interested in modifying the metadata of an allocated (or free, if that is possible) chunk. Things like the size, A|M|P flags, or the forward and back pointers for when that chunk is merged.

[R.. GitHub STOP HELPING ICE]

Considering that the GOT is normally below the heap rather than above it, I don't see a direct way to overflow into it. The intent might be to overwrite the malloc chunk headers/footers with specific values in their size fields in order to have free overwrite the GOT entries for you...

[amccormack]

@HotLicks I can analyze the binary to find the address of printf() in the Global Offset Table, and then overwrite it (using the heap exploit) with the address of challenge(). And for now, I am ok with the unrealistic circumstances surrounding how easy it is to manipulate the chunk metadata, but I would still like to understand how the attack could work.

[Jeff Burdges]

A priori, your best bet might be overflowing into heap data containing function pointers, such as a C++ class with virtual member functions.

[ose]

The other problem with this type of attack vector is that modern operating systems and compilers go a long way to mitigating this - eg. Memory protection, data execution prevention (DEP). You would need to consider the target architecture as well.

[Hot Licks]

I guess it depends on how the target architecture implements printf. But in general it would be just a load address of the literal and a call. The literal address (and literal) and the call target may be in binder tables, but those tables would be write-protected on most modern architectures.

[amccormack]

@HotLicks The target that I am looking at will allow for such an overwrite. However, I am more curious about arbitrary data writes in general. If the GOT is protected, then maybe I can use the data write to attack another area of the code (though maybe not in the above example). My real focus of the question is how to use the ability to manipulate the heap data structure to write to an arbitrary address.

[Hot Licks]

In C, once you have an address anywhere in heap, you have an address to everywhere in heap (and in the segment where heap resides). That's not the problem, and no real tricks are needed.

[R.. GitHub STOP HELPING ICE]

@HotLicks: You mean on common C implementations. Whereas in C, the address of one object can never be used as a base to address another object unless they exist as part of the same array (possibly the representation array of a potentially-aggregate type).

[R.. GitHub STOP HELPING ICE]

@amccormack: The GOT is not protected; it's part of the data segment. In principle it could be protected, but due to the popularity of the (IMO misguided) lazy binding feature of dynamic linking, protecting it without disabling lazy binding would be prohibitively slow (each binding would require 2 syscalls to unprotect and reprotect the GOT).

[Hot Licks]

@R.. -- But I know of no (non-academic) C implementation that uses the descriptors that would be necessary to restrict array accesses. (And, in fact, the C standards make descriptor-based implementations difficult if not impossible.)

[R.. GitHub STOP HELPING ICE]

Regarding the standard making it difficult, it's not that bad. One trivial implementation doubles the size of each pointer, and makes the upper half a physical pointer to the maximal containing object, and the lower half an offset in that object. Arithmetic only takes place on the offset component. Immediately prior to the base (physical) address of the object is stored the size, for bounds checking offset arithmetic (note that this has potentially no overhead for traditional malloc implementations that already store the size there; only non-malloc objects are enlarged).

[newlog]

GOT can be perfectly protected with RELRO.

[amccormack]

This program is written for GNU/Linux, and is using glibc 2.11.2. While my interests are in writing an exploit are purely academic, the reason I have reached out to the StackOverflow community for help on this problem is because despite hours of searching, I have found inadequate explanations on this issue. While I appreciate your input on defensive security experts, I am interested in understanding how this attack works and not the topic of professional practices and expectations.

[newlog]

As you said this approach is obsolete given many things. Such as sanity checks and the introduction of multiple arenas (so the -4 size won't work). If you know spanish you can read a paper I developed explaining all these things and how you might bypass them with modern glibc versions: overflowedminds.net/Papers/Newlog/… You can read some slides in english here: prezi.com/wcnbbokuousb/linux-heap-exploiting-revisited-en/…