Calculating addresses on NOP sleigh
I am currently reading Introduction to Computer Systems: A Programmer's Perspective ( http://www.amazon.com/Computer-Systems-Programmers-Perspective-2nd/dp/0136108040/ref = sr_1_2? S = books & ie = UTF8 & qid = 1421029641 & sr = 1-2 & keywords = introduction + to + computer + systems ) and tries to understand how to prevent buffer overflows.
I understand why we need NOP sledges, when address randomization is used and how to write exploits, but I am having trouble understanding the calculation of the addresses associated with NOP sleds given in the book. I will quote it here: -
(Suppose the starting addresses of the program on the stack are in the range of 2 ^ 23 on a 32-bit system and 2 ^ 32 on a 64-bit system)
"If we set up 256-byte NOP sleds, then the randomization to n = 2 ^ 23 can be cracked by listing 2 ^ 15 starting addresses, which are quite possible for a particular attacker. For the 64-bit case trying to list 2 ^ 24 addresses more difficult. "
How did the authors come up with the numbers 2 ^ 15 and 2 ^ 24 for the 32 and 64 bit case, respectively? An explanation will be really helpful.
source to share
They just accept the maximum total shared memory (kbytes) on a 32-bit system, which would be 8388608
where they came from2^23
and is 2^15
calculated as follows:
(8388608 / 256) = 32768 == 2^15
So in other words:
total_memory_size / NOP_sled_length = total_iterations_to_find_NOP_sled_in_memory
They calculated that based on the assumption that our NOP sleds could range anywhere from 0x0
up to 0x800000
(which is 8388608
or 2^23
). Since our NOP bitches are 256 bytes long, we don't need to increment by one for each guess / iteration / brute force, but instead we calculate an increment of 256 each time, giving us the results from the equation above 0x800000 / 256 = 32768 == 2^15
. So we only need to iterate over 32768 possible addresses, because one of those addresses will drop us off at the start of our NOP sled and descend all the way down to our payload.
If our NOP bitches were 500 bytes (assuming our exploit allowed us to fit NOP swipes that were large), this equation would be:
0x8000000 / 500 = 268435
iterate to find the starting address of our NOP sled.
The reason why this approach is not that great for 64-bit systems is explained by the following equation:
2^32 / 256 = 16,777,216
(over 16 million possible addresses that our NOP sledges can step on! And even if your NOP sled is 500 bytes, and you divide it by 500, you will have over 8.5 million addresses where your NOP sled can be installed !)
0000 0000 NNNN NNNN NNNN PPPP PPPP PPPP 0000 0000
If you fancy this is my stack, I have a total memory size of 40. I have a NOP-sled (N) of 12 bytes and a payload (P) of 12 bytes. So my equation for this scenario is:
40 / 12 = 3
gives me 3 possible addresses that my NOP sleds can be found in (12, 24, 32 or hex 0x0c, 0x18 and 0x20) in as few tries as possible.
So, if my exploit just starts at the beginning of the stack and is counted in increments of 12, then on the first try it will find my NOP sled (planting 4 bytes into my NOP sled).
Update based on comments :
The idea behind the NOP sled in terms of a traversal method for address randomization is not to guess the start of the NOP sled - to calculate the smallest number of addresses that will ensure you land inside your NOP sled with the least amount of address guessing / brute force. Of course, if you want to find the start of your NOP sled, you can use the following equation:
total_mem_size / NOP_size = least_amount_of_guesses_to_land_inside_payload + 1
But keep in mind that by adding an extra address to try, you no longer compute the smallest number of addresses to guess before you get the payload execution (this is what I and the book you are reading compute because that is the idea for the use of the NOP sled).
If we go to my little "stack" above, it is true that there may be 4 shared addresses where NOP sleds can be set, but the equation calculates 3 addresses that are guaranteed to find a NOP sled (in a few guesses how it is possible to be a key) ... To make it clearer, you can say that the exploit developer will try to keep this number as low as possible by increasing the size of the NOP sled (where possible) so they don't have to worry about finding the start of the NOP sled - they just want to land in the sled NOP.
Guessing the index 12
will land 4 bytes on you in the NOP salons, giving you just 8 NOPs to execute before reaching the payload. Guessing the index 24
will result in multiple bytes being allocated to the failing payload, and guessing the index 32
will overshoot the payload, which will also fail.
Use your approach (using all 4 addresses) to show why the additional address is not counted in the equation:
0000 0000 NNNN NNNN NNNN PPPP PPPP PPPP 0000 0000
Let's add 1 to our equation, giving us 4 possible addresses with the same stacking locations as before:
40 / 12 = 3 + 1 = 4
So now we have 4 brute force addresses to land in our NOP sled 0, 12, 24, 32
. Since we have a 12 byte NOP napkin, there is still only 1 address (the address at index 12, the address of which the original equation was found), which will land on our plumbing toboggan, allowing us to start executing the shellcode at the beginning of the shellcode. Index 0 pushes us onto the stack on data that we do not control in front of our sleigh. So by adding 1 more address to the mix, we can't find the NOP sled - it just increases the number of try / brute / guess addresses.
And yes, you're right - I'm just incrementing addresses, which are more intuitive for the example, to make more sense, but "counting" or "incrementing" the address on the stack during your actual execution will start at the higher addresses.
source to share