Protostar Exploit Challenges Format 1 Solution

Format 1 Solution

I’ve seen a lot of different solutions to this problem and they’re all good, but I couldn’t find one that actually explained the oddity I observed while completing the challenge. My initial approach was to use the command:

./format1 `perl -e ‘print “AAAA” . “%08x.”x200

If you aren’t already familiar with the format string exploit you need to use read up here.

What Stack Space Looks Like

I’ll start by explaining what is going on here. Because our input is being interpreted directly by printf we can inject our own format strings. Now usually when you use a format string with printf you pass arguments via the stack just like anything else. Take this for example:

printf(“My favorite number is %d and it is at location %08x.”, favorite_number, &favorite_number)

When we call print f the stack will be aligned in the following manner:

Top of the Stack
Address of the format string
favorite_number
*favorite_number
Bottom of the Stack

Now in our case printf isn’t expecting any format characters which we can see by disassembling the vuln function in GDB.

figure1

Before the call there are two lines of interest:

mov eax, DWORD PTR [ebp+0x8]
mov DWORD PTR [esp], eax

ebp+0x8 contains a pointer to our format string. The second line places that pointer into the address pointed to by the stack pointer. Now if you were to just let the program finish running here is what you would see:

figure2

What’s happening is that you are reading values off the top of the stack as if they were arguments to printf starting with $esp+4. In fact we can see that in GDB. I took this right before the call to printf. During the actual  running printf, the program will reference arguments by comparing to $ebp. The reason for the +4 is that directly beneath $ebp is the function return address.

figure3

Now if you remember, I ran the command ./format1 `perl -e ‘print “AAAA” . “%08x.”x200 at the beginning. Recall that at this juncture the call stack looks like this (bottom)main->vuln->printf. This means that we are reading from lower memory (the top of the stack) to higher memory toward the bottom of the stack. Since we called printf after we called vuln, we should see the arguments we passed to vuln. In our case this should include the string “AAAA” or in memory “\x41\x41\x41\x41”. I realized in my first run of GDB, I probably didn’t take it far enough. So I went a bit further.figure4You may notice our As got split. This happened because all strings are terminated with a null byte. So instead of being an even 4 bytes we ended up with 5 bytes.

Stack Padding

Here’s the big problem with this challenge: stack padding. In this particular architecture, things run more efficiently if they are aligned on 4 byte boundaries. Now you may notice in the output above there are an awful lot of \x25\x30\x38\x78\x2e sets. Well if you convert that to ascii you get “%08x.”… which is 5 characters… which isn’t even. So our program will be padded with random garbage to make it even. We will have to contend with this later.

Determining Distance and Exploitation

Our next step is to try to get our 41414141 to be the last thing printed from the stack. The reason for this is we want to use the %n specifier to arbitrarily write to the address of target. To obtain the address of target we can either use GDB or objdump. I just used objdump -t format1 | grep target. The -t option dumps the symbol table. This tells me the address of the target variable is 0x08049638. So I’m going to ultimately want an exploit that looks like this ./format `perl -e ‘print “\x38\x96\x04\x08” . “X”xSOME_NUMBER . “%x.”xSOME_NUMBER_2’`%n. So let me break this down. The four hex numbers are our address in reverse byte order, the X is padding (will explain later), and then we have our format specifier followed by a %n. The idea is that when we reach the %n it will read the address off the stack and print the number of bytes up to that point at that address thus modifying the target variable

First things first, we have to get our As to be the last thing printed on the stack. This will prove we can correctly control the address. So you might end up with something like this (by the way I just used guess and check – it was faster than calculating distance in GDB):

figure5

 

At first you might say the As aren’t last. But recall they are in reverse byte order. The beginning of our string is in the last byte and the rest of it with the null terminator is in the penultimate byte. DAMN YOU BYTE PADDING!!! You may have recalled I mentioned byte padding. Well, due to this evil byte padding our string will not line up as is. You can play with the string length as long as you like and never get it to work using the syntax I have above. You must add your own artificial padding like so:

figure6

You’ll notice I added that “X”x4 field. This is changing the way that the program is padded. You can use this to get your As to actually line up properly in memory. IMPORTANT IMPORTANT NOTE: Changing the number of %08x.s in your print out alters the amount of stack padding. You will have to play with both your padding and the number of percent formaters to get it to work. Finally you can put a %n in there and change the As to the address of target in reverse byte order.

figure7

IMPORTANT NOTE 2: I’m not really sure why this is, but I found you have to put the %n outside of your perl statement rather than just adding it as a concatenation. At present, I’m not sure why that is, but I just found I had to do it. The approach I used was to change the number of %xs I printed until I got it close to the last address in the listing. Once I saw at least one 41 in the last 4 bytes I used padding to get it to line up.

Hope this helps.

 

4 thoughts on “Protostar Exploit Challenges Format 1 Solution

  1. Reply

    Anonymous

    GREAT tutorial! Took me a while to understand the padding part because I had seen a couple of tutorials that hadn’t explained that and always made me wonder htf it got there…PFM!

    THanks!

    1. Reply

      grantcurell@gmail.com Post author

      Dude, I had the same problem. Also sorry I’m responding to this like a year and a half late :-p

  2. Reply

    xor

    You are freaking awesome dude! I tried for hours but didn’t get the ideo of using an additional padding (your X-Padding). You’re a saint to the community

    1. Reply

      grantcurell@gmail.com Post author

      hahaha glad I could help.

Leave a Reply