In the previous post I demonstrated how to bypass Microsoft’s RFG, a.k.a. “Shadow Stack”, assuming we can locate the shadow stack. In this post I’ll fill up the missing details, and will describe how to find “Shadow” memory sections in a process’s virtual address space. While the technique works both in Windows and Linux, and it will demonstrate some key differences between the two operating systems.
Motivation
Microsoft’s software implementation of Intel’s “Shadow Stack” is a great example for the need of a cartography phase during the exploit: we need to find the stack in order to write on it. Hiding security-related memory sections is quite a common defensive precaution, one such example is hiding security canaries. Basic cartography steps are relatively easy to accomplish, since the virtual address space is filled with memory pointers, pointing from almost any interesting section to another.
However, sometimes there are simply no pointers to the desired location. In the RFG scenario, Microsoft took great care so that there won’t be even a single pointer to the shadow stack, that is accessed using “FS:[RSP]”. So, can we find even “shadow” memory sections that where hidden in our process’s virtual address space?
Fixed allocations
Counting up the bits
Although 64-bit virtual address space might seem like a massive search space, there are some technical details that can help us:
- Intel only uses 48 bits of the 64 bit address – cutting 16 bits of the address space
- The kernel traditionally uses the upper half of the memory – cutting 1 more bit
And so, we have actually 47 bits in our address space, not a very big change from the “old” 32 bit address spaces.
Checking the limitations
Most operating systems supports fixed memory allocations, in our case the mmap() / VirtualAlloc() functions. Any such allocation attempt can teach us about our virtual address space:
- Allocation Succeeded? the memory range was vacant
- Allocation Failed? an existent memory allocation, somewhere in our allocation range, blocked our new allocation attempt
In theory, we can start from address = 0, and try to cover the virtual address space with fixed allocations, to try and learn about the already mapped memory sections.
Reserve my memory please, oh forget it
Apparently, both mmap() and VirtualAlloc(), allow us to reserve up to 1GB of memory per function call. The reserved space is cheap, because we don’t actually use it the operating system won’t really allocate it for our process. By reserving one chunk at a time, and releasing it right after we finished our check, our scanning algorithm will practically use no memory as far as the operating system is concerned.
In addition, we just learned that we can sample a range of up to 1GB (= 30 bits) in every step. This means we can scan the entire virtual address space using only 47 – 30 = 17 bits of function calls. And 17 bits of system calls can be done almost in no time with current CPUs, suddenly it seems possible.
Divide and Conquer
Since every sample state uses a huge range of 1GB, we will need to know where in that range there was an allocation that caused our allocation to fail. This can easily be done by dividing our allocation size by 2, and checking the lower half and the upper half of the original allocation range.
First technique – conclusion
Using a simple for loop, fixed memory reservations, and a minor recursion we can find the allocation status of every page in our virtual address space. And the overall cost is 17 bits of syscalls + the costs of the recursion from 30 bits to 12 bits (page size), 1 bit at a time. Here we can use the fact that the address space is sparse, keeping the recursion cost low.
This solution works on both Windows and Linux. However, in Windows we can do even better.
Just ask the OS
Windows supports the VirtualQuery() function, and MSDN tells us that the function:
Retrieves information about a range of pages in the virtual address space of the calling process.
The details are:
- PVOID BaseAddress
- PVOID AllocationBase
- DWORD AllocationProtect
- SIZE_T RegionSize
- DWORD State
- DWORD Protect
- DWORD Type
In short, by querying the address X, we can learn almost everything we need:
- Is this address points to an allocated page? (protect == 1)
- How many bytes, starting from X, are there in the memory section? (RegionSize)
And since windows treat free memory just as it treats any other memory section, by querying the address “0” one can find the amount of free bytes until the 1st memory allocation. In addition, we receive the entire protection mask of the entire allocation range, allowing us to check for READ, WRITE, and EXECUTE permissions too.
Just to be sure, VirtualQuery() is CFG enabled, meaning we can even use it without CFG blocking our cartography phase.
Query Algorithm
- For pos = 0 to the end of our 47 bits of address space
- VirtualQuery(pos, &info, sizeof(info))
- pos += info.RegionSize
And this is the only logic we need, achieving a full-mapping of our entire virtual address space.
Lighting up the shadows
Both cartography techniques give us a complete memory map of our address space. We even know the size of each logical allocation. Now we only need to scan the map’s entries in search of our shadow stack:
- The shadow stack has the same size as the regular stack
- Reading from the shadow stack should reveal only 0’s and return values
- These can be compared to the regular stack to check for a match
And thus Windows enables us to achieve a fast search algorithm looking for the shadow stack, hidden some where in our memory.
Conclusion
It seems that the current design of modern operation systems is just not built to block cartography attempts done by the user. Although there are differences between Linux and Windows, in both cases the task of hiding a “shadow” section from the user, inside it’s virtual address space, is simply impossible.
Since shadow sections can be integrated in many mitigation mechanisms, developers of operating systems will need to re-think about their current design choices. As for the attackers, it seems that our cartography attempts will continue to work without any major interference.
Eyal Itkin 