In Linux kernel exploitation, side-channel attacks are sometimes used to leak kernel addresses. To make such exploits more efficient, it’s essential to accelerate the leak process and verify if the leaked address falls within the expected range. This post will explore how KASLR performs its randomization.

1. Ktext Randomization

The randomization of the kernel image is implemented during the boot phase. The bootloader calls extract_kernel() function to decompress and extract the kernel image.

#define PMD_SHIFT 21
#define MIN_KERNEL_ALIGN_LG2 PMD_SHIFT
#define MIN_KERNEL_ALIGN (_AC(1, UL) << MIN_KERNEL_ALIGN_LG2)

const unsigned long kernel_total_size = VO__end - VO__text;

asmlinkage __visible void *extract_kernel(void *rmode, unsigned char *output)
{
    needed_size = max_t(unsigned long, output_len /* [1] */, kernel_total_size /* [2] */);
    needed_size = ALIGN(needed_size, MIN_KERNEL_ALIGN /* [3] */);

    // [...]
    choose_random_location((unsigned long)input_data, input_len,
                            (unsigned long *)&output,
                            needed_size,
                            &virt_addr);

    // [...]
    entry_offset = decompress_kernel(output, virt_addr, error);

    // [...]
}
  • output_len [1]: This value is generated by the mkpiggy tool. You need to compile the kernel and retrieve value from the file arch/x86/boot/compressed/piggy.S.
    • Unfortunately, I am not sure how to obtain this value when only the vmlinux binary is available.
  • kernel_total_size [2]: This is calculated by substracting the _stext value from _end value.
  • MIN_KERNEL_ALIGN [3]: This value is set to 0x200000 (1 << 21).

The randomization process is divided into two parts: the first is for direct mapping [4], and the second is for the kernel text [5].

void choose_random_location(unsigned long input,
                unsigned long input_size,
                unsigned long *output,
                unsigned long output_size,
                unsigned long *virt_addr)
{
    unsigned long random_addr, min_addr;
    // [...]

    // the offset in "direct mapping"
    random_addr = find_random_phys_addr(min_addr /* 0x1000000 */, output_size); // [4]
    *output = random_addr;

    // ktext (0xffffffff80000000) random offset
    random_addr = find_random_virt_addr(LOAD_PHYSICAL_ADDR /* 0x1000000 */, output_size); // [5]
    *virt_addr = random_addr;
}

Our focus is on the ktext one. The find_random_virt_addr() function determines the number of slots [6] and selects one randomly to serve as the randomized address.

static unsigned long find_random_virt_addr(unsigned long minimum,
                       unsigned long image_size)
{
    unsigned long slots, random_addr;

    slots = 1 + (KERNEL_IMAGE_SIZE /* 0x40000000 */ - minimum /* 0x1000000 */ - image_size)
                                                    / CONFIG_PHYSICAL_ALIGN /* 0x1000000 */; // [6]
    random_addr = kaslr_get_random_long("Virtual") % slots;
    return random_addr * CONFIG_PHYSICAL_ALIGN + minimum;
}

However, when relocating kernel, the handle_relocations() function uses virt_addr - LOAD_PHYSICAL_ADDR as relocation delta [7].

unsigned long decompress_kernel(unsigned char *outbuf, unsigned long virt_addr,
                void (*error)(char *x))
{
    // [...]
    entry = parse_elf(outbuf);
    handle_relocations(outbuf, output_len, virt_addr); // <----------
    // [...]
}

static void handle_relocations(void *output, unsigned long output_len,
                   unsigned long virt_addr)
{
    // [...]
    unsigned long delta, map, ptr;
    unsigned long min_addr = (unsigned long)output;
    
    // [...]
    delta = virt_addr - LOAD_PHYSICAL_ADDR; // [7]

    // handle relocation with delta
    // [...]
}

Summary:

  • Base Address: 0xffffffff80000000
  • Offset Unit: 0x1000000 (CONFIG_PHYSICAL_ALIGN)
  • Range: 1 ~ (64 - (image_size / 0x1000000))

2. Kheap Randomization

The kernel heap is randomized by the kernel_randomize_memory() function. The backtrace for this process is as follows:

  • x86_64_start_kernel()
  • x86_64_start_reservations()
  • setup_arch()
  • kernel_randomize_memory()

In addition to the kernel heap, kernel_randomize_memory() also handles the randomization of the vmalloc (vmalloc/ioremap space) [1] and vmemmap [2] (virtual memory map).

By default, the virtual memory layout reserves a 2TB memory space (from vaddr_start to vaddr_end) for KASLR, referred to as variable remain_entropy. In the beginning, these three regions have padding between them, so the remain_entropy value needs to exclude these gaps [3].

The function then enters a for-loop to iterate through all regions. For each iteration:

  1. It retrieves the entropy value for the current round [4].
  2. It generates a random value [5].
  3. A MOD operation is applied to constrain the random value within the entropy range [6].
  4. Finally, an OR operation with the PUD mask (~((1 << 30) - 1)) [7] is performed to compute the randomized base address.
static __initdata struct kaslr_memory_region {
    unsigned long *base;
    unsigned long *end;
    unsigned long size_tb;
} kaslr_regions[] = {
    {
        .base    = &page_offset_base,
        .end     = &physmem_end,
    },
    {
        .base    = &vmalloc_base, // [1]
    },
    {
        .base    = &vmemmap_base, // [2]
    },
};

void __init kernel_randomize_memory(void)
{
    // [...]
    vaddr = vaddr_start;
    // [...]
    remain_entropy = vaddr_end /* 0xfffffe0000000000 */ - vaddr_start /* 0xffff888000000000 */;
    // remain_entropy = 0x758000000000
    for (i = 0; i < ARRAY_SIZE(kaslr_regions); i++)
        remain_entropy -= get_padding(&kaslr_regions[i]); // [3]
    // remain_entropy is 0x498000000000 now
    // [...]
    for (i = 0; i < ARRAY_SIZE(kaslr_regions); i++) {
        unsigned long entropy;
        
        // i == 0, remain_entropy / 3, 0x188000000000
        // i == 1, remain_entropy' / 2
        // i == 2, remain_entropy''
        entropy = remain_entropy / (ARRAY_SIZE(kaslr_regions) - i); // [4]
        prandom_bytes_state(&rand_state, &rand, sizeof(rand)); // [5]
        entropy = (rand % (entropy + 1)) & PUD_MASK; // [6, 7]
        
        vaddr += entropy;
        *kaslr_regions[i].base = vaddr;

        vaddr += get_padding(&kaslr_regions[i]);
        // [...]
        vaddr = round_up(vaddr + 1, PUD_SIZE);
        remain_entropy -= entropy;
    }
}

Summary:

  • Base Address: 0xffff888000000000
  • Offset Unit: 0x40000000 (PUD_SIZE)
  • Range: 0 ~ 25088 (0x188000000000, first round entropy)

3. Others

I don’t know how to debug bootloader with source code, nor getting the address of target function to set breakpoint. Instead, I use for loops as makeshift breakpoints [1] and warn() function [2] to show variable or macro value [2]. While this may not be the best way, but it works well enough for debugging 🙂.

void choose_random_location(/* ... */)
{
    // [...]
    for (volatile int i = 0; i < 0x41414141; i++) {} // [1]
    warn((const char *)LOAD_PHYSICAL_ADDR); // [2]
}