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 trying to understand ways to thwart buffer overflows.
I understand why we need NOP sleds when address randomization is used and how to write exploits but i have trouble in understanding the address calculation related to NOP sleds which is given in the book. I will quote it here:-
(Assume the starting addresses of a program on the stack have a range of 2^23 on a 32 bit system and 2^32 on a 64 bit system)
"If we set up a 256 byte NOP sled, then the randomization over n=2^23 can be cracked by enumerating 2^15 starting addresses which is entirely feasible for a determined attacker. For the 64 bit case, trying to enumerate 2^24 addresses is more daunting."
How did the authors come up with the figures 2^15 and 2^24 for the 32 and 64 bit case respectively? An explanation would be really helpful.
They are just assuming a max total shared memory (kbytes) on 32bit system which would be 8388608 which is where they came up with the 2^23
and the 2^15 is calculated by the following:
(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 sled could be anywhere within a range starting from 0x0 all the way to 0x800000 (which is 8388608 or 2^23). Because our NOP sled is 256 bytes long we don't need to increment by one for each guess/iteration/brute force but instead we count increasing by 256 each time giving us the results from the equation above 0x800000 / 256 = 32768 == 2^15. So we only need to brute force 32768 possible addresses because one of those addresses will land us at the start of our NOP sled and slide all the way down to our payload.
If our NOP sled was 500 bytes (assuming our exploit allowed us to fit a NOP sled that large) the equation would be:
0x8000000 / 500 = 268435 iterations to find the starting address of our NOP sled.
The reason why this approach is not so great for 64bit systems is because of the following equation:
2^32 / 256 = 16,777,216 (over 16 million possible addresses that our NOP sled could start at! And even if your NOP sled was 500 bytes and you divided by 500 you will still have over 8.5 million addresses where your NOP sled could start!)
0000
0000
NNNN
NNNN
NNNN
PPPP
PPPP
PPPP
0000
0000
If you imagine the above is my stack I have a total memory size of 40. I have a NOP sled (the N's) of 12 bytes and a payload (the P's) of 12 bytes. So my equation for this exploitable scenario would be:
40 / 12 = 3 giving me 3 possible addresses that my NOP sled could be found at (12, 24, 32 or in hex 0x0c, 0x18 and 0x20) in as few tries as possible.
So if my exploit just starts at the beginning of the stack and counts in increments of 12 then it will find my NOP sled on the first try (landing 4 bytes into my NOP sled).
Update based on comments:
The idea behind a NOP sled in terms of a bypass technique for address randomization is not to guess the start of a NOP sled - it's to calculate the least amount of addresses that will guarantee that you will land inside your NOP sled with as few address guesses/brute forces as possible. Sure, if you want to find the beginning of your NOP sled you could 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 the extra address to try you are no longer calculating the least amount of addresses to guess before you get payload execution (which is what myself and the book you are reading is calculating because that is the idea behind using a NOP sled).
If we revisit my small "stack" above it is true that there could be 4 total addresses at which the NOP sled could start but the equation calculates the 3 addresses that are guaranteed to find the NOP sled (in as few guesses as possible being the key). To make it more clear you could say that the exploit developer will try to make this number as small as possible by increasing the size of the NOP sled ( where possible ) so they won't be worrying about finding the start of the NOP sled - they just want to land inside the NOP sled.
The guess of index 12 will land you 4 bytes into your NOP sled giving you only 8 NOPs to execute before reaching the payload. The guess of index 24 will land you a few bytes into the payload causing a crash and the guess of index 32 will land you past the payload also causing a crash.
Let's use your approach (of using the total 4 addresses) to demonstrate why the extra address is not taking into consideration 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 stack layout as before:
40 / 12 = 3 + 1 = 4
So now we have 4 addresses to brute force to land in our NOP sled 0, 12, 24, 32. Because we have a NOP sled of 12 bytes there is still only 1 address (the address at index 12 whose address the original equation found) that will land in our NOP sled letting us start shellcode execution at the beginning of the shellcode. Index 0 lands us on the stack at data we don't control before our NOP sled. So by adding 1 more address to the mix doesn't help us find the NOP sled - it just increases the amount of addresses to try/brute/guess.
And yes you are correct - I am just incrementing addresses that are more intuitive for the example to make more sense but "counting" or "incrementing" address on the stack during your actual execution will start at the high addresses.