Follow @Openwall on Twitter for new release announcements and other news
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Tue,  1 Oct 2013 12:37:23 -0700
From: Kees Cook <keescook@...omium.org>
To: linux-kernel@...r.kernel.org
Cc: x86@...nel.org, kernel-hardening@...ts.openwall.com, adurbin@...gle.com,
        Eric Northup <digitaleric@...gle.com>, jln@...gle.com, wad@...gle.com,
        Mathias Krause <minipli@...glemail.com>,
        Zhang Yanfei <zhangyanfei@...fujitsu.com>,
        "H. Peter Anvin" <hpa@...or.com>, keescook@...omium.org
Subject: [PATCH 5/7] x86, kaslr: select memory region from e820 maps

Counts available alignment positions across all e820 maps, and chooses
one randomly for the new kernel base address.

Signed-off-by: Kees Cook <keescook@...omium.org>
---
 arch/x86/boot/compressed/aslr.c |  140 ++++++++++++++++++++++++++++++++++++---
 1 file changed, 130 insertions(+), 10 deletions(-)

diff --git a/arch/x86/boot/compressed/aslr.c b/arch/x86/boot/compressed/aslr.c
index 2f63f9f..ab0f8a3 100644
--- a/arch/x86/boot/compressed/aslr.c
+++ b/arch/x86/boot/compressed/aslr.c
@@ -2,6 +2,7 @@
 
 #ifdef CONFIG_RANDOMIZE_BASE
 #include <asm/msr.h>
+#include <asm/e820.h>
 
 #include <asm/archrandom.h>
 static inline int rdrand(unsigned long *v)
@@ -115,6 +116,130 @@ static unsigned long find_minimum_location(unsigned long input,
 	return output;
 }
 
+/*
+ * This routine is used to count how many aligned slots that can hold the
+ * kernel exist across all e820 entries. It is called in two phases, once
+ * to count valid memory regions available for the kernel image, and a
+ * second time to select one from those seen.
+ *
+ * It is first called with "counting" set to true, where it expects to be
+ * called once for each e820 entry. In this mode, it will update *count
+ * with how many slots are available in the given e820 entry. Once the walk
+ * across all e820 entries has finished, the caller will have a total count
+ * of all valid memory regions available for the kernel image.
+ *
+ * Once the first pass of entry walking is finished, the caller selects one
+ * of the possible slots (stored in *count), and performs a second walk,
+ * with "counting" set to false. In this mode, *count is decremented until
+ * the corresponding slot is found in a specific e820 region, at which
+ * point, the function returns that address, and the walk terminates.
+ */
+static unsigned long process_e820_entry(struct e820entry *entry, bool counting,
+					unsigned long minimum,
+					unsigned long image_size,
+					unsigned long *count)
+{
+	u64 addr, size;
+	unsigned long alignments;
+
+	/* Skip non-RAM entries. */
+	if (entry->type != E820_RAM)
+		return 0;
+
+	/* Ignore entries entirely above our maximum. */
+	if (entry->addr >= CONFIG_RANDOMIZE_BASE_MAX_OFFSET)
+		return 0;
+
+	/* Ignore entries entirely below our minimum. */
+	if (entry->addr + entry->size < minimum)
+		return 0;
+
+	size = entry->size;
+	addr = entry->addr;
+
+	/* Potentially raise address to minimum location. */
+	if (addr < minimum)
+		addr = minimum;
+
+	/* Potentially raise address to meet alignment requirements. */
+	addr = ALIGN(addr, CONFIG_PHYSICAL_ALIGN);
+
+	/* Did we raise the address above the bounds of this e820 region? */
+	if (addr > entry->addr + entry->size)
+		return 0;
+
+	/* Reduce size by any delta from the original address. */
+	size -= addr - entry->addr;
+
+	/* Reduce maximum image starting location to maximum limit. */
+	if (addr + size > CONFIG_RANDOMIZE_BASE_MAX_OFFSET)
+		size = CONFIG_RANDOMIZE_BASE_MAX_OFFSET - addr;
+
+	/* Ignore entries that cannot hold even a single kernel image. */
+	if (size < image_size)
+		return 0;
+
+	/*
+	 * Reduce size by kernel image size so we can see how many aligned
+	 * starting addresses will fit without running past the end of a
+	 * region. XXX: adjacent e820 regions are not detected, so up to
+	 * image_size / CONFIG_PHYSICAL_ALIGN slots may go unused across
+	 * adjacent regions.
+	 */
+	size -= image_size;
+
+	/* Now we know how many aligned slots can contain the image. */
+	alignments = (size / CONFIG_PHYSICAL_ALIGN) + 1;
+
+	/* In the first pass, just counting all the e820 entries? */
+	if (counting) {
+		*count += alignments;
+		return 0;
+	}
+
+	/* Otherwise we're counting down to find a specific aligned slot. */
+	if (*count < alignments) {
+		/* Desired region is in this entry. */
+		return addr + (CONFIG_PHYSICAL_ALIGN * *count);
+	} else {
+		/* Desired region is beyond this entry. */
+		*count -= alignments;
+		return 0;
+	}
+}
+
+static unsigned long find_random_e820(unsigned long minimum,
+				      unsigned long size)
+{
+	int i;
+	unsigned long addr, count;
+
+	/* Make sure minimum is aligned. */
+	minimum = ALIGN(minimum, CONFIG_PHYSICAL_ALIGN);
+
+	/* Verify potential e820 positions. */
+	count = 0;
+	for (i = 0; i < real_mode->e820_entries; i++) {
+		process_e820_entry(&real_mode->e820_map[i], true, minimum,
+				   size, &count);
+	}
+
+	/* Handle crazy case of nothing fitting. */
+	if (count == 0)
+		return 0;
+
+	count = get_random_long() % count;
+
+	/* Select desired e820 position. */
+	for (i = 0; i < real_mode->e820_entries; i++) {
+		addr = process_e820_entry(&real_mode->e820_map[i], false,
+					  minimum, size, &count);
+		if (addr)
+			return addr;
+	}
+	return 0;
+}
+
 unsigned char *choose_kernel_location(unsigned char *input,
 				      unsigned long input_size,
 				      unsigned char *output,
@@ -131,16 +256,11 @@ unsigned char *choose_kernel_location(unsigned char *input,
 	choice = find_minimum_location((unsigned long)input, input_size,
 				       (unsigned long)output, output_size);
 
-	/* XXX: Find an appropriate E820 hole, instead of adding offset. */
-	random = get_random_long();
-
-	/* Clip off top of the range. */
-	random &= (CONFIG_RANDOMIZE_BASE_MAX_OFFSET - 1);
-	while (random + output_size > CONFIG_RANDOMIZE_BASE_MAX_OFFSET)
-		random >>= 1;
-
-	/* Clip off bottom of range. */
-	random &= ~(choice - 1);
+	random = find_random_e820(choice, output_size);
+	if (!random) {
+		debug_putstr("KASLR could not find suitable E820 region...\n");
+		goto out;
+	}
 
 	/* Always enforce the minimum. */
 	if (random < choice)
-- 
1.7.9.5

Powered by blists - more mailing lists

Confused about mailing lists and their use? Read about mailing lists on Wikipedia and check out these guidelines on proper formatting of your messages.