Re: [PATCH v2 13/13] arm64: efi: invoke EFI_RNG_PROTOCOL to supply KASLR randomness

Kees Cook
2016-01-07T19:08:03Z

On Thu, Jan 7, 2016 at 10:46 AM, Mark Rutland <mark.rutland@arm.com> wrote:
> Hi Ard,
>
> I had a go at testing this on Juno with a hacked-up PRNG, and while
> everything seems to work, I think we need to make the address selection
> more robust to sparse memory maps (which I believe they are going to be
> fairly common).
>
> Info dump below and suggestion below.
>
> Other than that, this looks really nice -- I'll do other review in a
> separate reply.
>
> On Wed, Dec 30, 2015 at 04:26:12PM +0100, Ard Biesheuvel wrote:
>> Since arm64 does not use a decompressor that supplies an execution
>> environment where it is feasible to some extent to provide a source of
>> randomness, the arm64 KASLR kernel depends on the bootloader to supply
>> some random bits in register x1 upon kernel entry.
>>
>> On UEFI systems, we can use the EFI_RNG_PROTOCOL, if supplied, to obtain
>> some random bits. At the same time, use it to randomize the offset of the
>> kernel Image in physical memory.
>>
>> Signed-off-by: Ard Biesheuvel <ard.biesheuvel@linaro.org>
>> ---
>> arch/arm64/kernel/efi-entry.S | 7 +-
>> drivers/firmware/efi/libstub/arm-stub.c | 1 -
>> drivers/firmware/efi/libstub/arm64-stub.c | 134 +++++++++++++++++---
>> include/linux/efi.h | 5 +-
>> 4 files changed, 127 insertions(+), 20 deletions(-)
>
> [...]
>
>> @@ -36,13 +106,42 @@ efi_status_t __init handle_kernel_image(efi_system_table_t *sys_table_arg,
>> if (preferred_offset < dram_base)
>> preferred_offset += SZ_2M;
>>
>> - /* Relocate the image, if required. */
>> kernel_size = _edata - _text;
>> - if (*image_addr != preferred_offset) {
>> - kernel_memsize = kernel_size + (_end - _edata);
>> + kernel_memsize = kernel_size + (_end - _edata);
>> +
>> + if (IS_ENABLED(CONFIG_ARM64_RELOCATABLE_KERNEL) && efi_rnd.phys_seed) {
>> + /*
>> + * If KASLR is enabled, and we have some randomness available,
>> + * locate the kernel at a randomized offset in physical memory.
>> + */
>> + u64 dram_top = dram_base;
>> +
>> + status = get_dram_top(sys_table_arg, &dram_top);
>> + if (status != EFI_SUCCESS) {
>> + pr_efi_err(sys_table_arg, "get_dram_size() failed\n");
>> + return status;
>> + }
>> +
>> + kernel_memsize += SZ_2M;
>> + nr_pages = round_up(kernel_memsize, EFI_ALLOC_ALIGN) /
>> + EFI_PAGE_SIZE;
>>
>> /*
>> - * First, try a straight allocation at the preferred offset.
>> + * Use the random seed to scale the size and add it to the DRAM
>> + * base. Note that this may give suboptimal results on systems
>> + * with discontiguous DRAM regions with large holes between them.
>> + */
>> + *reserve_addr = dram_base +
>> + ((dram_top - dram_base) >> 16) * (u16)efi_rnd.phys_seed;
>
> I think that "suboptimal" is somewhat an understatement. Across 10
> consecutive runs I ended up getting the same address 7 times:
>
> EFI stub: Seed is 0x0a82016804fdc064
> EFI stub: KASLR reserve address is 0x0000000832c48000
> EFI stub: Loading kernel to physical address 0x00000000fe080000
>
> EFI stub: Seed is 0x0a820168050c09b2
> EFI stub: KASLR reserve address is 0x00000000c59e0000
> EFI stub: Loading kernel to physical address 0x00000000c4e80000 *
>
> EFI stub: Seed is 0x0a8001680511c701
> EFI stub: KASLR reserve address is 0x00000007feb40000
> EFI stub: Loading kernel to physical address 0x00000000fe080000
>
> EFI stub: Seed is 0x0a8001680094d2a2
> EFI stub: KASLR reserve address is 0x0000000895bd0000
> EFI stub: Loading kernel to physical address 0x0000000895080000 *
>
> EFI stub: Seed is 0x88820167ea986527
> EFI stub: KASLR reserve address is 0x00000000bc570000
> EFI stub: Loading kernel to physical address 0x00000000bb880000 *
>
> EFI stub: Seed is 0x0882116805029414
> EFI stub: KASLR reserve address is 0x00000005955a0000
> EFI stub: Loading kernel to physical address 0x00000000fe080000
>
> EFI stub: Seed is 0x8a821168050104ab
> EFI stub: KASLR reserve address is 0x0000000639600000
> EFI stub: Loading kernel to physical address 0x00000000fe080000
>
> EFI stub: Seed is 0x08820168050671c6
> EFI stub: KASLR reserve address is 0x00000005250f0000
> EFI stub: Loading kernel to physical address 0x00000000fe080000
>
> EFI stub: Seed is 0x08821167ea67381f
> EFI stub: KASLR reserve address is 0x000000080e538000
> EFI stub: Loading kernel to physical address 0x00000000fe080000
>
> EFI stub: Seed is 0x0a801168050cb810
> EFI stub: KASLR reserve address is 0x00000006b20e0000
> EFI stub: Loading kernel to physical address 0x00000000fe080000
>
> My "Seed" here is just the CNTVCT value, with phys_seed being a xor of
> each of the 16 bit chunks (see diff at the end of hte email). Judging by
> the reserve addresses, I don't think the PRNG is to blame -- it's just
> that that gaps are large relative to the available RAM and swallow up
> much of the entropy, forcing a fall back to the same address.
>
> One thing we could do is to perform the address selection in the space
> of available memory, excluding gaps entirely. i.e. sum up the available
> memory, select the Nth available byte, then walk the memory map to
> convert that back to a real address. We might still choose an address
> that cannot be used (e.g. if the kernel would hang over the end of a
> region), but it'd be rarer than hitting a gap.

This is basically what I did on x86. I walk the memory map, counting
the number of positions that the kernel would fit into, then used the
random number to pick between position 0 and max position, then walked
the memory map again to spit out the memory address for that position.

Maybe this could be extracted into a lib for all architectures? Might
be more pain that it's worth, but at least there's no reason to write
it from scratch. See find_random_addr() and its helpers in
arch/x86/boot/compressed/aslr.c

-Kees

>
> Thoughts?
>
> For the above, my EFI memory map looks like:
>
> [ 0.000000] Processing EFI memory map:
> [ 0.000000] 0x000008000000-0x00000bffffff [Memory Mapped I/O |RUN| | | | | | | | | |UC]
> [ 0.000000] 0x00001c170000-0x00001c170fff [Memory Mapped I/O |RUN| | | | | | | | | |UC]
> [ 0.000000] 0x000080000000-0x00008000ffff [Loader Data | | | | | | | |WB|WT|WC|UC]
> [ 0.000000] 0x000080010000-0x00009fdfffff [Conventional Memory| | | | | | | |WB|WT|WC|UC]
> [ 0.000000] 0x00009fe00000-0x00009fe0ffff [Loader Data | | | | | | | |WB|WT|WC|UC]
> [ 0.000000] 0x00009fe10000-0x0000dfffffff [Conventional Memory| | | | | | | |WB|WT|WC|UC]
> [ 0.000000] 0x0000e00f0000-0x0000fde49fff [Conventional Memory| | | | | | | |WB|WT|WC|UC]
> [ 0.000000] 0x0000fde4a000-0x0000febc9fff [Loader Data | | | | | | | |WB|WT|WC|UC]
> [ 0.000000] 0x0000febca000-0x0000febcdfff [ACPI Reclaim Memory| | | | | | | |WB|WT|WC|UC]*
> [ 0.000000] 0x0000febce000-0x0000febcefff [ACPI Memory NVS | | | | | | | |WB|WT|WC|UC]*
> [ 0.000000] 0x0000febcf000-0x0000febd0fff [ACPI Reclaim Memory| | | | | | | |WB|WT|WC|UC]*
> [ 0.000000] 0x0000febd1000-0x0000feffffff [Boot Data | | | | | | | |WB|WT|WC|UC]
> [ 0.000000] 0x000880000000-0x0009f98aafff [Conventional Memory| | | | | | | |WB|WT|WC|UC]
> [ 0.000000] 0x0009f98ab000-0x0009f98acfff [Loader Data | | | | | | | |WB|WT|WC|UC]
> [ 0.000000] 0x0009f98ad000-0x0009fa42afff [Loader Code | | | | | | | |WB|WT|WC|UC]
> [ 0.000000] 0x0009fa42b000-0x0009faf6efff [Boot Code | | | | | | | |WB|WT|WC|UC]
> [ 0.000000] 0x0009faf6f000-0x0009fafa9fff [Runtime Data |RUN| | | | | | |WB|WT|WC|UC]*
> [ 0.000000] 0x0009fafaa000-0x0009ff767fff [Conventional Memory| | | | | | | |WB|WT|WC|UC]
> [ 0.000000] 0x0009ff768000-0x0009ff768fff [Boot Data | | | | | | | |WB|WT|WC|UC]
> [ 0.000000] 0x0009ff769000-0x0009ff76efff [Conventional Memory| | | | | | | |WB|WT|WC|UC]
> [ 0.000000] 0x0009ff76f000-0x0009ffdddfff [Boot Data | | | | | | | |WB|WT|WC|UC]
> [ 0.000000] 0x0009ffdde000-0x0009ffe72fff [Conventional Memory| | | | | | | |WB|WT|WC|UC]
> [ 0.000000] 0x0009ffe73000-0x0009fff6dfff [Boot Code | | | | | | | |WB|WT|WC|UC]
> [ 0.000000] 0x0009fff6e000-0x0009fffaefff [Runtime Code |RUN| | | | | | |WB|WT|WC|UC]*
> [ 0.000000] 0x0009fffaf000-0x0009ffffefff [Runtime Data |RUN| | | | | | |WB|WT|WC|UC]*
> [ 0.000000] 0x0009fffff000-0x0009ffffffff [Boot Data | | | | | | | |WB|WT|WC|UC]
>
> I've included my local hacks below in case they are useful.
>
> Thanks,
> Mark.
>
> ---->8----
> diff --git a/drivers/firmware/efi/libstub/arm64-stub.c b/drivers/firmware/efi/libstub/arm64-stub.c
> index 27a1a92..00c6640 100644
> --- a/drivers/firmware/efi/libstub/arm64-stub.c
> +++ b/drivers/firmware/efi/libstub/arm64-stub.c
> @@ -30,6 +30,34 @@ extern struct {
>
> extern bool kaslr;
>
> +static void log_hex(efi_system_table_t *sys_table_arg, unsigned long val)
> +{
> + const char hex[16] = "0123456789abcdef";
> + char *strp, str[] = "0x0000000000000000";
> + strp = str + 18;
> +
> + do {
> + *(--strp) = hex[val & 0xf];
> + } while (val >>= 4);
> +
> + efi_printk(sys_table_arg, str);
> +}
> +
> +static void dodgy_get_random_bytes(efi_system_table_t *sys_table)
> +{
> + u64 seed;
> + pr_efi(sys_table, "using UNSAFE NON-RANDOM number generator\n");
> +
> + asm volatile("mrs %0, cntvct_el0\n" : "=r" (seed));
> +
> + pr_efi(sys_table, "Seed is ");
> + log_hex(sys_table, seed);
> + efi_printk(sys_table, "\n");
> +
> + efi_rnd.virt_seed = seed;
> + efi_rnd.phys_seed = seed ^ (seed >> 16) ^ (seed >> 32) ^ (seed >> 48);
> +}
> +
> static int efi_get_random_bytes(efi_system_table_t *sys_table)
> {
> efi_guid_t rng_proto = EFI_RNG_PROTOCOL_GUID;
> @@ -40,6 +68,7 @@ static int efi_get_random_bytes(efi_system_table_t *sys_table)
> (void **)&rng);
> if (status == EFI_NOT_FOUND) {
> pr_efi(sys_table, "EFI_RNG_PROTOCOL unavailable, no randomness supplied\n");
> + dodgy_get_random_bytes(sys_table);
> return EFI_SUCCESS;
> }
>
> @@ -77,6 +106,17 @@ static efi_status_t get_dram_top(efi_system_table_t *sys_table_arg, u64 *top)
> return EFI_SUCCESS;
> }
>
> +static void log_kernel_address(efi_system_table_t *sys_table_arg,
> + unsigned long addr, unsigned long kaslr_addr)
> +{
> + pr_efi(sys_table_arg, "KASLR reserve address is ");
> + log_hex(sys_table_arg, kaslr_addr);
> + efi_printk(sys_table_arg, "\n");
> + pr_efi(sys_table_arg, "Loading kernel to physical address ");
> + log_hex(sys_table_arg, addr);
> + efi_printk(sys_table_arg, "\n");
> +}
> +
> efi_status_t __init handle_kernel_image(efi_system_table_t *sys_table_arg,
> unsigned long *image_addr,
> unsigned long *image_size,
> @@ -90,6 +130,7 @@ efi_status_t __init handle_kernel_image(efi_system_table_t *sys_table_arg,
> unsigned long nr_pages;
> void *old_image_addr = (void *)*image_addr;
> unsigned long preferred_offset;
> + unsigned long kaslr_address = 0;
>
> if (IS_ENABLED(CONFIG_RANDOMIZE_BASE)) {
> if (kaslr) {
> @@ -137,8 +178,9 @@ efi_status_t __init handle_kernel_image(efi_system_table_t *sys_table_arg,
> * base. Note that this may give suboptimal results on systems
> * with discontiguous DRAM regions with large holes between them.
> */
> - *reserve_addr = dram_base +
> + kaslr_address = dram_base +
> ((dram_top - dram_base) >> 16) * (u16)efi_rnd.phys_seed;
> + *reserve_addr = kaslr_address;
>
> status = efi_call_early(allocate_pages, EFI_ALLOCATE_MAX_ADDRESS,
> EFI_LOADER_DATA, nr_pages,
> @@ -179,6 +221,9 @@ efi_status_t __init handle_kernel_image(efi_system_table_t *sys_table_arg,
> }
> *image_addr = *reserve_addr + TEXT_OFFSET;
> }
> +
> + log_kernel_address(sys_table_arg, *image_addr, kaslr_address);
> +
> memcpy((void *)*image_addr, old_image_addr, kernel_size);
> *reserve_size = kernel_memsize;
>
>

--
Kees Cook
Chrome OS & Brillo Security