December 14, 2012 at 15:43Internal ASLR in Windows 8
ASLR is Address Space Layout Randomization, address space randomization. This is a security mechanism that includes the randomization of virtual memory addresses of various attack-sensitive data structures. The location in the memory of the target structure is difficult to predict, so the attacker's chances of success are small. Windows ASLR implementation is closely related to the relocation mechanism of executable images. Relocation allows a PE file to load not only on a fixed preferred base. The relocation section in the PE file is the key structure when moving the image. It describes what changes need to be made to certain elements of the code and data to ensure the correct functioning of the application at a different base address.
A key role in the work of ASLR is played by a random number generator and a couple of functions that modify the base address of the loaded PE file.
Windows 8 relies on a random number generator, which is essentially a delayed Fibonacci generator with parameters j = 24 and k = 55. Its kernel is initialized in the winload.exe module at system startup. Winload.exe collects entropy from various sources: registry keys, TPM, current time, ACPI, as well as using the new rdrand instruction. The initialization of the nuclear random number generator is described in detail in the source [1].
Let's take a closer look at the new rdrand statement. In processors based on the Ivy Bridge architecture, Intel Secure Key technology was introduced to generate high-quality pseudorandom numbers. It is implemented using a hardware digital random number generator (DRNG) and rdrand instructions for programmatically extracting values from it.
From a hardware point of view, DRNG is a separate module on a processor chip. It works asynchronously with the processor cores at 3 GHz. DRNG uses thermal noise as a source of entropy; in addition, it has an integrated testing system that performs a series of quality checks of extracted random values. In the event of an unsatisfactory test result, the DRNG stops generating random values.
The rdrand instruction is used to extract random numbers from DRNG. The documentation for it noted that theoretically DRNG can return zero values in the event of an unsatisfactory test result or an empty internal queue of random values. However, in practice it was not possible to empty the DRNG.
Intel Secure Key is a powerful random number generator that produces high-quality random values at a very high speed. It is almost impossible to predict the initial state of the generator initialized using the rdrand instruction (unlike other sources of entropy).
The internal interface function of the nuclear PRNG is ExGenRandom (). It also has an exported wrapper function RtlRandomEx (). ASLR on Windows 8 uses ExGenRandom () - unlike previous versions that relied on the rdtsc instruction. The latter is used to obtain a time counter on the CPU, which varies linearly and, therefore, cannot provide the proper quality of the generated values, which is unsafe.
The main function of the ASLR mechanism is MiSelectImageBase (). In Windows 8, it can be described by the following pseudo-code.
#define MI_64K_ALIGN(x) (x + 0x0F) >> 4
#define MmHighsetUserAddress 0x7FFFFFEFFFF
typedef PIMAGE_BASE ULONG_PTR;
typedef enum _MI_MEMORY_HIGHLOW
{
MiMemoryHigh = 0,
MiMemoryLow = 1,
MiMemoryHighLow = 2
} MI_MEMORY_HIGHLOW, *PMI_MEMORY_HIGHLOW;
MI_MEMORY_HIGHLOW MiSelectBitMapForImage(PSEGMENT pSeg)
{
if (!(pSeg->SegmentFlags & FLAG_BINARY32)) // WOW binary
{
if (!(pSeg->ImageInformation->ImageFlags & FLAG_BASE_BELOW_4GB))
{
if (pSeg->BasedAddress > 0x100000000)
{
return MiMemoryHighLow;
}
else
{
return MiMemoryLow;
}
}
}
return MiMemoryHigh;
}
PIMAGE_BASE MiSelectImageBase(void* a1, PSEGMENT pSeg)
{
MI_MEMORY_HIGHLOW ImageBitmapType;
ULONG ImageBias;
RTL_BITMAP *pImageBitMap;
ULONG_PTR ImageTopAddress;
ULONG RelocationSizein64k;
MI_SECTION_IMAGE_INFORMATION *pImageInformation;
ULONG_PTR RelocDelta;
PIMAGE_BASE Result = NULL;
// rsi = rcx
// rcx = rdx
// rdi = rdx
pImageInformation = pSeg->ImageInformation;
ImageBitmapType = MiSelectBitMapForImage(pSeg);
a1->off_40h = ImageBitmapType;
if (ImageBitmapType == MiMemoryLow)
{
// 64-bit executable with image base below 4 GB
ImageBias = MiImageBias64Low;
pImageBitMap = MiImageBitMap64Low;
ImageTopAddress = 0x78000000;
}
else
{
if (ImageBitmapType == MiMemoryHighLow)
{
// 64-bit executable with image base above 4 GB
ImageBias = MiImageBias64High;
pImageBitMap = MiImageBitMap64High;
ImageTopAddress = 0x7FFFFFE0000;
}
else
{
// MiMemoryHigh 32-bit executable image
ImageBias = MiImageBias;
pImageBitMap = MiImageBitMap;
ImageTopAddress = 0x78000000;
}
}
// pSeg->ControlArea->BitMap ^= (pSeg->ControlArea->BitMap ^ (ImageBitmapType << 29)) & 0x60000000;
// or bitfield form
pSeg->ControlArea.BitMap = ImageBitmapType;
RelocationSizein64k = MI_64K_ALIGN(pSeg->TotalNumberOfPtes);
if (pSeg->ImageInformation->ImageCharacteristics & IMAGE_FILE_DLL)
{
ULONG StartBit = 0;
ULONG GlobalRelocStartBit = 0;
StartBit = RtlFindClearBits(pImageBitMap, RelocationSizein64k, ImageBias);
if (StartBit != 0xFFFFFFFF)
{
StartBit = MiObtainRelocationBits(pImageBitMap, RelocationSizein64k, StartBit, 0);
if (StartBit != 0xFFFFFFFF)
{
Result = ImageTopAddress - (((RelocationSizein64k) + StartBit) << 0x10);
if (Result == (pSeg->BasedAddress - a1->SelectedBase))
{
GlobalRelocStartBit = MiObtainRelocationBits(pImageBitMap, RelocationSizein64k, StartBit, 1);
StartBit = (GlobalRelocStartBit != 0xFFFFFFFF) ? GlobalRelocStartBit : StartBit;
Result = ImageTopAddress - (RelocationSizein64k + StartBit) << 0x10;
}
a1->RelocStartBit = StartBit;
a1->RelocationSizein64k = RelocationSizein64k;
pSeg->ControlArea->ImageRelocationStartBit = StartBit;
pSeg->ControlArea->ImageRelocationSizeIn64k = RelocationSizein64k;
return Result;
}
}
}
else
{
// EXE image
if (a1->SelectedBase != NULL)
{
return pSeg->BasedAddress;
}
if (ImageBitmapType == MiMemoryHighLow)
{
a1->RelocStartBit = 0xFFFFFFFF;
a1->RelocationSizein64k = (WORD)RelocationSizein64k;
pSeg->ControlArea->ImageRelocationStartBit = 0xFFFFFFFF;
pSeg->ControlArea->ImageRelocationSizeIn64k = (WORD)RelocationSizein64k;
return ((DWORD)(ExGenRandom(1) % (0x20001 - RelocationSizein64k)) + 0x7F60000) << 16;
}
}
ULONG RandomVal = ExGenRandom(1);
RandomVal = (RandomVal % 0xFE + 1) << 0x10;
RelocDelta = pSeg->BasedAddress - a1->SelectedBase;
if (RelocDelta > MmHighsetUserAddress)
{
return 0;
}
if ((RelocationSizein64k << 0x10) > MmHighsetUserAddress)
{
return 0;
}
if (RelocDelta + (RelocationSizein64k << 0x10) <= RelocDelta)
{
return 0;
}
if (RelocDelta + (RelocationSizein64k << 0x10) > MmHighsetUserAddress)
{
return 0;
}
if (a1->SelectedBase + RandomVal == 0)
{
Result = pSeg->BasedAddress;
}
else
{
if (RelocDelta > RandomVal)
{
Result = RelocDelta - RandomVal;
}
else
{
Result = RelocDelta + RandomVal;
if (Result < RelocDelta)
{
return 0;
}
if (((RelocationSizein64k << 0x10) + RelocDelta + RandomVal) > 0x7FFFFFDFFFF)
{
return 0;
}
if (((RelocationSizein64k << 0x10) + RelocDelta + RandomVal) < (RelocDelta + (RelocationSizein64k << 0x10))))
{
return 0;
}
}
}
//random_epilog
a1->RelocStartBit = 0xFFFFFFFF;
a1->RelocationSizein64k = RelocationSizein64k;
pSeg->ControlArea->ImageRelocationStartBit = 0xFFFFFFFF;
pSeg->ControlArea->ImageRelocationSizeIn64k = RelocationSizein64k;
return Result;
}
As you can see, there are three different image bitmaps. The first is for 32-bit executable applications, the second is for 64-bit, the third is for 64-bit applications with a base higher than 4 GB, which gives them a virtual address with high entropy.
The randomization of executable images directly affects their base address. In the case of loading libraries, ASLR is part of the module relocation process: the random variable when choosing a new base address is the ImageBias variable, which is initialized at system startup.
VOID MiInitializeRelocations()
{
MiImageBias = ExGenRandom(1) % 256;
MiImageBias64Low = ExGenRandom(1) % MiImageBitMap64Low.SizeOfBitMap;
MiImageBias64High = ExGenRandom(1) % MiImageBitMap64High.SizeOfBitMap;
return;
}
Bitmaps of executable images display the address space of current user processes. The executable image gets the base address at boot time; it will be reloaded into other processes at the same base address. This behavior of the bootloader is most effective in terms of speed and memory saving due to the use of executable images of the copy-on-write mechanism.
The current ASLR implementation in Windows 8 allows you to randomize the base address of applications that do not support randomization. The table below shows the behavior of the bootloader depending on the combination of linker flags associated with ASLR.
* It is not possible to assemble an image using MSVS, because the / DYNAMICBASE flag requires the / FIXED: NO flag, which generates a relocations section
You can notice a change in the behavior of the bootloader, typical for Windows 8: if the executable image has a relocation section, then it will be loaded anyway. This is another evidence of the relationship between ASLR and the relocation mechanism.
In general, we can say that the implementation of the new ASLR functions in Windows 8 does not significantly affect the logic of the code, so it is difficult to find useful vulnerabilities in it. Increasing the entropy for randomizing various objects is essentially a replacement for the constant expression in the code. In addition, the code graphs may include a code inspection.
Sources
[1] Valasek Ch., Mandt T. Windows 8 Heap Internals. 2012.
[2] Johnson K., Miller M. Exploit Mitigation Improvements in Windows 8. Slides, Black Hat USA, 2012.
[3] Intel. Intel Digital Random Number Generator (DRNG): Software Implementation Guide. Intel Corporation, 2012.
[4] Whitehouse O. An Analysis of Address Space Layout Randomization on Windows Vista. Symantec Advances Threat Research, 2007.
[5] Sotirov A., Dowd M. Bypassing Browser Memory Protections. 2008.
Authors: Artyom Shishkin ( honorarybot ) and Ilya Smith ( blackzert ), Positive Research Center.