Continuing with the previous Getting Physical blog posts series (CanSec2016's presentation), this time I'm going to talk about what paging implementation has been chosen by Windows and how it works. At the same time and according to Alex Ionescu's blog post, it's interesting to see that Microsoft has started to make some changes on the last Windows 10 Preview versions (Red Stone), specifically talking about paging tables randomization. Starting with the technical writing, the way that Microsoft adopted for paging management is by using the "self-ref entry" technique which I'm going to explain now.
Self-ref entry technique
This technique consists of using one entry at the highest paging level by pointing to itself. In 32 bits, this entry is usually located in the PAGE DIRECTORY, even with PAE enabled. In 64 bits, this entry is located in the PML4. Talking specifically about 64 bits, the physical address used by an ARBITRARY self-referential entry should have to point to the physical address of the PML4 table base, which is exactly the same address pointed by the CR3 register. The trick behind this is that, when a paging structure entry points to the same table that contains it, this gives as a result a re-used entry in the four paging levels, which means that this is used by the CPU as PML4 entry, PDPT entry, Page Directory entry and Page Table entry at the same time. Because in the lowest level there is a Page Table entry and this one points to itself, the result is a virtual address that maps the PML4 physical address. This means that, when the CPU accesses this virtual address, it will be able to read or write the PML4, depending on the protection (R/RW) set by the same self-referential entry. Let's see this in two examples. Using the self-ref entry located at the PML4 position number 0 (zero):
Using the self-ref entry located at the PML4 position number 0x1FF (511):
It's clear that any of 512 entries of the PML4 could be used for this purpose. On the other hand, we could say that this technique could be used in any paging table level, which makes it NOT necessary to use the HIGHEST LEVEL.
Self-ref entry - Example
To explain this, let's use as an example a 64-bit operating system with a PML4 with only 3 entries used, where the entry 0x0 is used for USER SPACE, the entry 0x1FF is used for KERNEL SPACE and the entry 0x100 is self-referential and it's used for Paging Management. The virtual memory ranges assigned by the operating system are: - USER SPACE: 0 ~ 0x7F'FFFFFFFF (512GB*entry 0x0 + 0x512GB) - PAGING MANAGMENT: 0xFFFF8000'00000000 ~ 0xFFFF807F'FFFFFFFF (512GB*entry 0x100 + 0x512GB) - KERNEL SPACE: 0xFFFFFF80'00000000 ~ 0xFFFFFFFF'FFFFFFFF (512GB*entry 0x1FF + 0x512GB) According to the previous explanation, if we do the following calculation: - ( 512GB * 1GB * 2MB * 4KB ) * 0x100 (self-ref entry) we obtain the value 0x8040'20100000, then we add the canonical address 0xFFFF0000'00000000 and finally we obtain the virtual address MAPPED by the self-ref entry: 0xFFFF8040'20100000 It means that the PML4 is located at this virtual address, so, if the operating system has to "manage" some entry located in the PML4, it would have to reference some address within the 4KB of this memory page. To read/write the USER SPACE entry, the operating system has to reference the address 0xFFFF8040'20100000 + 0x0. To read/write the KERNEL SPACE entry, the operating system has to reference the address 0xFFFF8040'20100000 + 0xFF8. If we want to do the reverse calculation to prove that this entry is self-referential, we could decompose the virtual address in 9-bit parts (2^9=512 decimal) starting from the 12th bit. Every 9-bit part represents an index inside of a related paging table and the last 12 bits (4KB) represent an offset inside the memory page mapped by the Page Table entry. This calculation can be done by the following python script:
entry_size = 8 address = 0xFFFF804020100000 shifted_address = address >> 12 pte_offset = shifted_address & 0x1ff shifted_address = shifted_address >> 9 pde_offset = shifted_address & 0x1ff shifted_address = shifted_address >> 9 pdpte_offset = shifted_address & 0x1ff shifted_address = shifted_address >> 9 pmle_offset = shifted_address & 0x1ff print ( "entry: PML4:0x%x PDPT:0x%x PD:0x%x PT:0x%x" % ( pmle_offset , pdpte_offset , pde_offset , pte_offset ) ) print ( "offset: PML4:0x%x PDPT:0x%x PD:0x%x PT:0x%x" % ( pmle_offset * entry_size , pdpte_offset * entry_size , pde_offset * entry_size , pte_offset * entry_size ) )
And the result is this one:
entry: PML4:0x100 PDPT:0x100 PD:0x100 PT:0x100 offset: PML4:0x800 PDPT:0x800 PD:0x800 PT:0x800
The previous script can be used to calculate the paging tables used by any 64-bit valid virtual address.
Self-ref entry - Paging Managment trick
If we analize this mechanism in depth, we can see that an almost magical solution appears before our eyes, and it appears as a side-effect of the technique itself. According to the explained above, if the CPU accesses to a virtual address that uses the SAME entry number in the four paging levels and this entry is declared as self-referential, the CPU will be able to access to the paging table that contains it. In the previous example, this table is located at 0xFFFF8040'20100000. Knowing that the operating system given as an example uses the entry 0x100 as self-referential and every PML4 entry maps up to 512 gigabytes of virtual memory, the question is, what would happen if instead of reading the address 0xFFFF8040'20100000 (PML4 address), we would read the BASE address mapped by this entry (0xFFFF8000'00000000) ? An interesting effect appears here, where we can see the great benefits of this technique. Let's analyze this one by using the previous operating system example. Let's suppose that in USER SPACE, this operating system has mapped the virtual address 0x00000000'00000000 (NULL address). At the same time, it has mapped the self-ref entry mentioned above. It would be the picture that represents the paging tables:
According to the picture, when the CPU accesses to the virtual address 0, it will follow the following path:: - PML4e(0) --> PDPTe(0) --> PDe(0) -->PTe(0). Now, when the CPU accesses to the address 0xFFFF8000'00000000, the path will be this: - PML4e(0x100) --> PDPTe(0) --> PDe(0) -->PTe(0). Knowing that the PML4 entry 0x100 is self-referential, when the CPU accesses to the previous address, it will repeat the first level (PML4) and then, it will take the branch of the paging tables that map the virtual address 0. The trick here is that the paging tables used are shifted, and that the real path to follow is this : - PML4e(0x100) --> PDPTe(PML4e(0)) --> PDe(PDPTe(0)) --> PTe(PDe(0)).
If we look at the lowest level, the PT entry associated with the address 0xFFFF8000'00000000 is the PHYSICAL address pointed by the PAGE DIRECTORY entry number 0 used to map the memory range 0~2MB. Which means that, when the CPU reads the address 0xFFFF8000'00000000, it will read all the PAGE TABLE entries used to map this memory range. Let's see another example by using the address 0xFFFF807F'FFFFF000. This address points to the last 4KB of the 512GB assigned for PAGING MANAGMENT. The path to be followed by the CPU is this: - PML4e(0x100) --> PDPTe(0x1FF) --> PDe(0x1FF) --> PTe(0x1FF). Which it is the same to: - PML4e(0x100) --> PDPTe(PML4e(0x1FF)) --> PDe(PDPTe(0x1FF)) --> PTe(PDe(0x1FF)). As a result, the CPU will have access to the PAGE TABLE used to map the highest 4MB of the virtual address memory range addressable by 64-bit Intel processors, located at 0xFFFFFFFF'FFC00000~0xFFFFFFFF'FFFFFFFF. Thus, the CPU, and obviously the operating system, are able to access to any paging level, what is absolutely necessary for manage them. Depending on which address it's chosen within the memory range 0xFFFF8000'00000000~0xFFFF807F'FFFFFFFF, the operating system is able to access to any paging table used to map virtual memory in the valid 48 bits of the virtual memory range allowed by Intel's x64 CPUs. Is short, this mechanism makes a DOBLE USE of paging tables, because on one hand these are usually used to map virtual memory, and at the same time are re-used by shifting one or more paging levels, when the CPU accesses them through a self-ref entry. This technique is really eficient because it only uses 8 bytes (one entry) to be able to manage ALL paging tables declared by the operation system.
Self-ref entry - Weakness
While this technique is highly efficient, nothing is perfect. There is an implicit "problem" in the use of self-ref entries related to the absolute lack of randomization. We could give a formal definition like this: "Given a self-ref entry, it's possible to calculate the virtual address of any paging table mapped by the operating system". Let's see an example using the self-ref entry number 0x100. This entry maps the memory range: 512GB * 0x100 ~ 512GB * 0x101 Using real numbers, the virtual memory range is: - 0xFFFF0000'00000000 + 0x8000000000 ( 512GB ) * 0x100 ~ 0xFFFF0000'00000000 + 0x8000000000 ( 512GB ) * 0x101 What is the same to 0xFFFF8000'00000000~0xFFFF8080'00000000, which it's used for Paging Managment. Now, we want to get the PAGE TABLE that maps the virtual memory range 0~2MB: - PML4e(0x100) --> PDPTe(PML4e(0)) --> PDe(PDPTe(0)) --> PTe(PDe(0)). What it's the same to: - 0xFFFF0000'00000000 + 512GB * 0x100 (self -ref entry) + (1GB * 2MB * 4KB ) * 0x0 = 0xFFFF8000'00000000 So, it means that the PAGE TABLE sought is located at the virtual address 0xFFFF8000'00000000. --------------------- Now let's try the self-ref entry number 0x101 . This entry maps the memory range: 512GB ~ 512GB * * 0x101 0x102 Using real numbers, the virtual memory range is: - 0xFFFF0000'00000000 + 0x8000000000 ( 512GB ) * 0x101 ~ 0xFFFF0000'00000000 + 0x8000000000 ( 512GB ) * 0x102 What is the same to 0xFFFF8080'00000000 ~ 0xFFFF8100'00000000, which it's used for Paging Managment. Now, we want to get again the PAGE TABLE that maps the virtual memory range 0~2MB: - PML4e(0x101) --> PDPTe(PML4e(0)) --> PDe(PDPTe(0)) --> PTe(PDe(0)). What it's the same to: - 0xFFFF0000'00000000 + 512GB * 0x101 (self -ref entry) + (1GB * 2MB * 4KB ) * 0x0 = 0xFFFF8080'00000000 So, it means that this PAGE TABLE is located at the virtual address 0xFFFF8080'00000000. --------------------- If we compare the PAGE TABLE addresses obtained previously, we get a difference of 0x80'00000000, which is the same to 512GB. It means that, the difference between the PML4 entry 0x100 and the PML4 entry 0x101 is 512GB. So, if an operating system uses a different self-ref entry, it's possible to calculate exactly where the PAGE TABLE that maps the memory range 0~2MB is. This is true for any of the 512 entries availables in the PML4, which these can be abused by an attacker that knows the number of the self-ref entry used by the operating system. So, the only way to implement KASLR (Kernel randomization) for paging tables is by randomizing the position of the PML4 self-ref entry. Thus, an attacker is not able to calculate exactly where the paging tables are, although it could in theory, because the PML4 has only 512 entries which, in general, only the 256 highest entries are intended for KERNEL SPACE. Yes well 1/256 possibilities is not a big number to protect a system, but this is still better than 1/1 ;-) In short, there is no way of paging tables randomization when the position of the self-ref entry is fixed.
Windows Paging implementation
As I said at the beginning, Microsoft decided to use the self-ref technique for Windows Paging Management, both for 32 and 64 bits. Talking about Windows 64 bits, the first 256 PML4 entries are used for USER SPACE and the next 256 entries for KERNEL SPACE. The PML4 self-ref entry chosen by Microsoft is the entry 0x1ED (493), located in kernel space, obviously. To obtain the PML4 Windows address, we have to do the same calculation explained above: - ( 512GB * 1GB * 2MB * 4KB ) * 0x1ED (self-ref entry) = 0xF6FB'7DBED000 Adding the canonical address 0xFFFF0000'00000000, we obtain the virtual address 0xFFFFF6FB'7DBED000. It can be easily proved by using the previous python script:
entry: PML4:0x1ed PDPT:0x1ed PD:0x1ed PT:0x1ed offset: PML4:0xf68 PDPT:0xf68 PD:0xf68 PT:0xf68
Windows Paging implementation - Weakness
The fact that Windows uses a fixed PML4 self-referential entry for all running processes, it makes that an attacker can calculate exactly where the paging tables/entries are, independently of the physical address used by everyone. In this way, an attacker is able to modify valid entries or add new ones. This is valid for LOCAL and REMOTE attacks against the Windows kernel, independently if it's Windows 2000 or Windows 10. In few words, this throws overboard the whole Windows kernel randomization (KASLR). A good example of "modify valid entries" can be seen in our "Windows SMEP bypass: U=S" Ekoparty presentation. To be continued ...