[RFC] Per-architecture randomization

[RFC] Per-architecture randomization

[John Richard Moser]

[-- Attachment #1.1: Type: text/plain, Size: 3107 bytes --]

Pavel Machek recommended per-architecture randomization defaults when I
poked a (very hackish) patch up here.  As follow-up, I have taken out
the command line parameter code and used the infrastructure I wrote to
implement per-architecture randomization settings.

Three #defines are needed per architecture, preferably in
include/asm-ARCH/processor.h or equivalent.  These defines are as follows:

 STACK_ALIGN -- Alignment of the stack, typically 16 (bytes).
    If not defined, stack randomization is carried out to page
    granularity
 ARCH_RANDOM_STACK_BITS -- Bits of entropy to apply to the stack.
    If not defined, stack randomization is disabled by defining this
    as 0.
 ARCH_RANDOM_MMAP_BITS -- Bits of entropy to apply to the mmap() base.
    If not defined, mmap() randomization is disabled by defining this
    as 0.

I have added these for each of i386 and x86-64.  In the case of x86-64,
the last two are complex ones similar to how TASK_SIZE is done.  Other
architectures need these defines, and I am certain I disabled
randomization everywhere else doing this; but as far as I can tell, the
code only was randomizing the stack at page-granularity anyway
everywhere else, since there were no randomized mmap_base() or
arch_align_stack() functions.

My arch_align_stack(), now in fs/exec.c, should be portable to all
platforms now.  Assuming my code works as intended, it's safe to enable
this on non-randomized archs; STACK_ALIGN will be PAGE_SIZE and so
arch_align_stack() effectively becomes an expensive NOP.  This also
happens if ARCH_RANDOM_STACK_BITS is 0.

This code probably makes it possible to collapse mmap_base() in
arch/x86_64/ia32/mmap32.c into arch_pick_mmap_layout() in
arch/x86_64/mm/mmap.c; as far as I can tell, there are 2 functions
because one applies 28 bits of entropy and one applies 8.  This patch
defines ARCH_RANDOM_MMAP_BITS as being based on the task type (32 or 64
bit), so the same function can complete the same randomization (I think...).

As before, this code makes it possible to insert hooks at a few key
points to control mmap() and stack entropy per-execution.  This could
later be added as SELinux policy controls if anyone is interested in
doing so.

This patch was coded very at-face and defines too many variables that
are used once in a couple functions.  I can probably rewrite those
sections to do the calculation steps in the same variable, and just note
what it's doing in comments.

This has yet to be compile-tested.

Questions?  Comments?  Flames?

-- 
All content of all messages exchanged herein are left in the
Public Domain, unless otherwise explicitly stated.

    Creative brains are a valuable, limited resource. They shouldn't be
    wasted on re-inventing the wheel when there are so many fascinating
    new problems waiting out there.
                                                 -- Eric Steven Raymond

    We will enslave their women, eat their children and rape their
    cattle!
                  -- Bosc, Evil alien overlord from the fifth dimension

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1.2: patch-2.6.16.16-rand_perarch-v1.diff --]
[-- Type: text/x-patch; name="patch-2.6.16.16-rand_perarch-v1.diff", Size: 19126 bytes --]

diff -urNp linux-2.6.16.16/Documentation/aslr.txt linux-2.6.16.16-randparam/Documentation/aslr.txt
--- linux-2.6.16.16/Documentation/aslr.txt	1969-12-31 19:00:00.000000000 -0500
+++ linux-2.6.16.16-randparam/Documentation/aslr.txt	2006-06-03 23:56:50.000000000 -0400
@@ -0,0 +1,119 @@
+Address space layout randomization is randomly selecting the base
+offsets of segments of memory in VMA.  It is used as a security tool
+to prevent sensitive attacks from being carried out by making important
+parameters to those attacks volatile and non-discoverable.
+
+Linux currently employs address space randomization in two places:
+
+1.  mmap() base
+ The base offset of libraries and anonymous mappings.  Randomization is
+ currently taken to the following degrees by default:
+
+  32-bit:  i386
+   Over 1MiB of VMA, giving 8 bits of entropy for 4096 byte pages.
+  64-bit:  x86-64
+   Over 1TiB of VMA, giving 28 bits of entropy for 4096 byte pages.
+
+ The maximum is over an area the size of TASK_SIZE / 12
+2.  stack base
+ The base offset of the stack.  Randomization is currently taken to the
+ following degrees by default:
+
+  32-bit:  i386
+   Over 8MiB of VMA, giving 19 bits of entropy, aligned to 16 bytes.
+  64-bit:  x86-64
+   Over 1TiB of VMA, giving 28 bits of entropy, aligned to 16 bytes.
+
+ The maximum allowed is over an area the size of TASK_SIZE / 12
+
+Linux does not employ heap randomization.
+
+Randomization is applied in the following places.
+
+
+STACK RANDOMIZATION
+
+fs/exec.c
+unsigned long arch_align_stack(unsigned long sp)
+
+ This function is called during process initialization to shuffle the
+ stack pointer to sub-page granularity.  It applies a portion of the
+ stack entropy.
+
+ This function calculates how much randomization to apply in the
+ following way:
+
+  - Divide PAGE_SIZE by STACK_ALIGN
+  - Take the long_log2() of that to get MAX_RANDOM_STACK_BITS_PER_PAGE
+  + If MAX_RANDOM_STACK_BITS_PER_PAGE > total bits of entropy
+   - page_random_bits = total bits of entropy
+  + If MAX_RANDOM_STACK_BITS_PER_PAGE <= total bits of entropy
+   - page_random_bits = MAX_RANDOM_STACK_BITS_PER_PAGE
+  - Raise 2^page_random_bits to get random_places
+  - Divide PAGE_SIZE by random_places to get random_interval
+  - (get_random_int() % random_places) * random_interval = offset
+  - Subtract offset from the stack pointer
+
+
+fs/binfmt_elf.c
+static unsigned long randomize_stack_top(unsigned long stack_top)
+
+ This function is called during process initialization to shuffle the
+ stack pointer to page granularity.  It applies a portion of the stack
+ entropy.
+
+ This function calculates how much randomization to apply in the
+ following way:
+
+  - Divide PAGE_SIZE by STACK_ALIGN
+  - Take the long_log2() of that to get MAX_RANDOM_STACK_BITS_PER_PAGE
+  + If MAX_RANDOM_STACK_BITS_PER_PAGE > total bits of entropy
+   - vma_random_bits = 0
+  + If MAX_RANDOM_STACK_BITS_PER_PAGE <= total bits of entropy
+   - vma_random_bits =
+               total bits entropy - MAX_RANDOM_STACK_BITS_PER_PAGE
+  - Multiply PAGE_SIZE by 2^random_bits to get random_range
+  - random_variable = get_random_int() % random_range
+  - Offset stack in VMA by random_variable and PAGE_ALIGN() result
+
+
+MMAP RANDOMIZATION
+
+arch/i386/mm/mmap.c
+static inline unsigned long mmap_base(struct mm_struct *mm)
+
+ This function is called during process initialization to shuffle the
+ mmap() baser to page granularity.  It applies full mmap() entropy.
+
+ This function is for i386 architectures.
+
+
+arch/x86_64/mm/mmap.c
+void arch_pick_mmap_layout(struct mm_struct *mm)
+
+ This function is called during process initialization to shuffle the
+ mmap() baser to page granularity.  It applies full mmap() entropy.
+ For IA-32 emulation it will call an IA-32 function.
+
+ This function is for x86-64 architectures.
+
+
+arch/x86_64/ia32/mmap32.c
+static inline unsigned long mmap_base(struct mm_struct *mm)
+
+
+ This function is called during process initialization to shuffle the
+ mmap() baser to page granularity.  It applies full mmap() entropy.
+
+ This function is for i386 architecture processes on x86-64.
+
+Also note the following:
+
+ - STACK_ALIGN is defined in include/arch-*/processor.h
+ - include/linux/mm.h defines STACK_ALIGN as PAGE_SIZE if it is not
+   defined
+ - ARCH_RANDOM_STACK_BITS and MMAP_RANDOM_STACK_BITS are defined in
+   include/arch-*/processor.h
+ - ARCH_RANDOM_STACK_BITS and MMAP_RANDOM_STACK_BITS are defined as
+   0 in include/linux/mm.h if not otherwise defined
+
diff -urNp linux-2.6.16.16/arch/i386/kernel/process.c linux-2.6.16.16-randparam/arch/i386/kernel/process.c
--- linux-2.6.16.16/arch/i386/kernel/process.c	2006-05-10 21:56:24.000000000 -0400
+++ linux-2.6.16.16-randparam/arch/i386/kernel/process.c	2006-05-21 03:23:40.000000000 -0400
@@ -905,9 +905,3 @@ asmlinkage int sys_get_thread_area(struc
 	return 0;
 }
 
-unsigned long arch_align_stack(unsigned long sp)
-{
-	if (randomize_va_space)
-		sp -= get_random_int() % 8192;
-	return sp & ~0xf;
-}
diff -urNp linux-2.6.16.16/arch/i386/mm/mmap.c linux-2.6.16.16-randparam/arch/i386/mm/mmap.c
--- linux-2.6.16.16/arch/i386/mm/mmap.c	2006-05-10 21:56:24.000000000 -0400
+++ linux-2.6.16.16-randparam/arch/i386/mm/mmap.c	2006-06-03 23:40:38.000000000 -0400
@@ -40,9 +40,30 @@ static inline unsigned long mmap_base(st
 {
 	unsigned long gap = current->signal->rlim[RLIMIT_STACK].rlim_cur;
 	unsigned long random_factor = 0;
+	long max_random_bits;
+	unsigned long random_bits;
 
-	if (current->flags & PF_RANDOMIZE)
-		random_factor = get_random_int() % (1024*1024);
+	random_bits = ARCH_RANDOM_MMAP_BITS;
+
+	/*XXX:  Place a hook here to adjust mmap() randomization;
+	 * this hook will change the value of random_bits */
+
+	/*
+	 * At most we should shift by 1/12 TASK_SIZE.  This is 256M on
+	 * 3GiB i386; 85M (64M, 14 bits) on 1GiB i386; 8TiB (31 bits)
+	 * on x86-64 with 47 bits of user VMA...
+	 */
+	max_random_bits = MAX_RANDOM_MMAP_BITS;
+	if (max_random_bits < random_bits)
+		random_bits = max_random_bits;
+
+	/*
+	 * PAGE_SIZE is 4096 usually.  mmap_random_bits means random bits
+	 * of entropy, not how long the range is.  If pages are suddenly
+	 * bigger some day, we're still randomizing this much....
+	 */
+	if (current->flags & PF_RANDOMIZE && (mmap_random_bits > 0))
+		random_factor = get_random_int() % (PAGE_SIZE << random_bits);
 
 	if (gap < MIN_GAP)
 		gap = MIN_GAP;
diff -urNp linux-2.6.16.16/arch/um/kernel/process_kern.c linux-2.6.16.16-randparam/arch/um/kernel/process_kern.c
--- linux-2.6.16.16/arch/um/kernel/process_kern.c	2006-05-10 21:56:24.000000000 -0400
+++ linux-2.6.16.16-randparam/arch/um/kernel/process_kern.c	2006-05-21 03:24:19.000000000 -0400
@@ -454,18 +454,3 @@ int singlestepping(void * t)
 	return 2;
 }
 
-/*
- * Only x86 and x86_64 have an arch_align_stack().
- * All other arches have "#define arch_align_stack(x) (x)"
- * in their asm/system.h
- * As this is included in UML from asm-um/system-generic.h,
- * we can use it to behave as the subarch does.
- */
-#ifndef arch_align_stack
-unsigned long arch_align_stack(unsigned long sp)
-{
-	if (randomize_va_space)
-		sp -= get_random_int() % 8192;
-	return sp & ~0xf;
-}
-#endif
diff -urNp linux-2.6.16.16/arch/x86_64/ia32/mmap32.c linux-2.6.16.16-randparam/arch/x86_64/ia32/mmap32.c
--- linux-2.6.16.16/arch/x86_64/ia32/mmap32.c	2006-05-10 21:56:24.000000000 -0400
+++ linux-2.6.16.16-randparam/arch/x86_64/ia32/mmap32.c	2006-06-03 23:41:56.000000000 -0400
@@ -42,9 +42,30 @@ static inline unsigned long mmap_base(st
 {
 	unsigned long gap = current->signal->rlim[RLIMIT_STACK].rlim_cur;
 	unsigned long random_factor = 0;
+	long max_random_bits;
+	unsigned long random_bits;
 
-	if (current->flags & PF_RANDOMIZE)
-		random_factor = get_random_int() % (1024*1024);
+	random_bits = ARCH_RANDOM_MMAP_BITS;
+
+	/*XXX:  Place a hook here to adjust mmap() randomization;
+	 * this hook will change the value of random_bits */
+
+	/*
+	 * At most we should shift by 1/12 TASK_SIZE.  This is 256M on
+	 * 3GiB i386; 85M (64M, 14 bits) on 1GiB i386; 8TiB (31 bits)
+	 * on x86-64 with 47 of user VMA...
+	 */
+	max_random_bits = MAX_RANDOM_MMAP_BITS;
+	if (max_random_bits < random_bits)
+		random_bits = max_random_bits;
+
+	/*
+	 * PAGE_SIZE is 4096 usually.  mmap_random_bits means random bits
+	 * of entropy, not how long the range is.  If pages are suddenly
+	 * bigger some day, we're still randomizing this much....
+	 */
+	if (current->flags & PF_RANDOMIZE && (mmap_random_bits > 0))
+		random_factor = get_random_int() % (PAGE_SIZE << random_bits);
 
 	if (gap < MIN_GAP)
 		gap = MIN_GAP;
diff -urNp linux-2.6.16.16/arch/x86_64/kernel/process.c linux-2.6.16.16-randparam/arch/x86_64/kernel/process.c
--- linux-2.6.16.16/arch/x86_64/kernel/process.c	2006-05-10 21:56:24.000000000 -0400
+++ linux-2.6.16.16-randparam/arch/x86_64/kernel/process.c	2006-05-21 03:24:06.000000000 -0400
@@ -839,9 +839,3 @@ int dump_task_regs(struct task_struct *t
 	return 1;
 }
 
-unsigned long arch_align_stack(unsigned long sp)
-{
-	if (randomize_va_space)
-		sp -= get_random_int() % 8192;
-	return sp & ~0xf;
-}
diff -urNp linux-2.6.16.16/arch/x86_64/mm/mmap.c linux-2.6.16.16-randparam/arch/x86_64/mm/mmap.c
--- linux-2.6.16.16/arch/x86_64/mm/mmap.c	2006-05-10 21:56:24.000000000 -0400
+++ linux-2.6.16.16-randparam/arch/x86_64/mm/mmap.c	2006-06-03 23:42:44.000000000 -0400
@@ -11,17 +11,44 @@
 
 void arch_pick_mmap_layout(struct mm_struct *mm)
 {
+	unsigned long random_factor = 0;
+	long max_random_bits;
+	unsigned long random_bits;
+
 #ifdef CONFIG_IA32_EMULATION
 	if (current_thread_info()->flags & _TIF_IA32)
 		return ia32_pick_mmap_layout(mm);
 #endif
+
 	mm->mmap_base = TASK_UNMAPPED_BASE;
+	
+	/*XXX:  I *think* this is right, but really I have no fucking
+	 * clue what I'm doing when we get around to 'rnd ='
+	 */
 	if (current->flags & PF_RANDOMIZE) {
-		/* Add 28bit randomness which is about 40bits of address space
+		unsigned rnd;
+		random_bits = ARCH_RANDOM_MMAP_BITS;
+
+		/*XXX:  Place a hook here to adjust mmap()
+		 * randomization; this hook will change the value of
+		 *  random_bits */
+
+		/*
+		 * At most we should shift by 1/12 TASK_SIZE.  This
+		 * is 256M on 3GiB i386; 85M (64M, 14 bits) on 1GiB
+		 * i386; 8TiB (31 bits) on x86-64 with 47 bits of user
+		 *  VMA...
+		 */
+		max_random_bits = MAX_RANDOM_MMAP_BITS;
+		if (max_random_bits < random_bits)
+			random_bits = max_random_bits;
+
+		/* Add our randomness.
+		   28 bits of randomness is about 40bits of address space
 		   because mmap base has to be page aligned.
  		   or ~1/128 of the total user VM
 	   	   (total user address space is 47bits) */
-		unsigned rnd = get_random_int() & 0xfffffff;
+		rnd = get_random_int() % (1 << random_bits);
 		mm->mmap_base += ((unsigned long)rnd) << PAGE_SHIFT;
 	}
 	mm->get_unmapped_area = arch_get_unmapped_area;
diff -urNp linux-2.6.16.16/fs/binfmt_elf.c linux-2.6.16.16-randparam/fs/binfmt_elf.c
--- linux-2.6.16.16/fs/binfmt_elf.c	2006-05-10 21:56:24.000000000 -0400
+++ linux-2.6.16.16-randparam/fs/binfmt_elf.c	2006-06-03 23:14:33.000000000 -0400
@@ -504,9 +504,49 @@ out:
 static unsigned long randomize_stack_top(unsigned long stack_top)
 {
 	unsigned int random_variable = 0;
+	unsigned int random_range = 0;
+	int page_random_bits = 0;
+	int vma_random_bits = 0;
+	long random_bits = 0;
+	long max_random_bits = 0;
 
-	if (current->flags & PF_RANDOMIZE)
-		random_variable = get_random_int() % (8*1024*1024);
+	random_bits = ARCH_RANDOM_STACK_BITS;
+	
+	/*XXX:  Place a hook here to adjust stack randomization;
+	 * this hook will change the value of random_bits */
+
+	/*
+	 * At most we should shift by 1/12 TASK_SIZE.  This is 256M on
+	 * 3GiB i386; 85M (64M, 14 bits) on 1GiB i386; 8TiB (31 bits)
+	 * on x86-64 with 47 bits of user VMA...
+	 */
+	max_random_bits = MAX_RANDOM_STACK_BITS;
+
+	if (max_random_bits < random_bits)
+		random_bits = max_random_bits;
+
+	/*
+	 * The code below relies on MAX_RANDOM_STACK_BITS_PER_PAGE,
+	 * which relies on STACK_ALIGN.  On architectures without
+	 * sub-page alignment, we're aligned to page boundaries.
+	 */
+	/*Cut the bits in the sub-page randomization out*/
+	page_random_bits = MAX_RANDOM_STACK_BITS_PER_PAGE;
+	if (random_bits <= page_random_bits)
+		vma_random_bits = 0;
+	else
+		vma_random_bits = random_bits - page_random_bits;
+
+	/*
+	 * Randomization happens here if doing more bits of entropy than
+	 * handled by sub-page randomization, otherwise look to process.c
+	 * only; the other bits are there.
+	 */
+	if (current->flags & PF_RANDOMIZE && vma_random_bits) {
+		/*Randomize with the bits we have times the page size*/
+		random_range = PAGE_SIZE * (1 << vma_random_bits);
+		random_variable = get_random_int() % (random_range);
+	}
 #ifdef CONFIG_STACK_GROWSUP
 	return PAGE_ALIGN(stack_top + random_variable);
 #else
diff -urNp linux-2.6.16.16/fs/exec.c linux-2.6.16.16-randparam/fs/exec.c
--- linux-2.6.16.16/fs/exec.c	2006-05-10 21:56:24.000000000 -0400
+++ linux-2.6.16.16-randparam/fs/exec.c	2006-06-03 23:15:09.000000000 -0400
@@ -49,6 +49,7 @@
 #include <linux/rmap.h>
 #include <linux/acct.h>
 #include <linux/cn_proc.h>
+#include <linux/random.h>
 
 #include <asm/uaccess.h>
 #include <asm/mmu_context.h>
@@ -1526,3 +1527,65 @@ fail_unlock:
 fail:
 	return retval;
 }
+
+/*
+ * Only x86 and x86_64 have an arch_align_stack().
+ * All other arches have "#define arch_align_stack(x) (x)"
+ * in their asm/system.h
+ * 
+ * In the case of UML, this is included from asm-um/system-generic.h;
+ * we can use it to behave as the subarch does.
+ */
+#ifndef arch_align_stack
+unsigned long arch_align_stack(unsigned long sp)
+{
+	unsigned int random_interval = 0;
+	unsigned int random_places = 0;
+	int page_random_bits = 0;
+	long random_bits = 0;
+	long max_random_bits = 0;
+
+	random_bits = ARCH_RANDOM_STACK_BITS;
+
+	/*XXX:  Place a hook here to adjust stack randomization;
+	 * this hook will change the value of random_bits */
+
+	/*
+	 * At most we should shift by 1/12 TASK_SIZE.  This is 256M on
+	 * 3GiB i386; 85M (64M, 14 bits) on 1GiB i386; 8TiB (31 bits)
+	 * on x86-64 with 47 bits of user VMA...
+	 */
+	max_random_bits = MAX_RANDOM_STACK_BITS;
+
+	if (random_bits > max_random_bits)
+		random_bits = max_random_bits;
+
+	/*What's the most randomness we can get in the page*/
+	page_random_bits = MAX_RANDOM_STACK_BITS_PER_PAGE;
+
+	/*Are we using less entropy than that?*/
+	if (page_random_bits > random_bits)
+		page_random_bits = random_bits;
+
+	/*
+	 * The stack is shifted around within PAGE_SIZE in intervals of
+	 * 16 bytes.
+	 *
+	 * The position of the stack in VMA is set in binfmt_elf.c
+	 */
+	if (randomize_va_space && (page_random_bits > 0)) {
+		/*Distance we move, typically 16 bytes unless less entropy*/
+		random_interval = PAGE_SIZE / (1 << page_random_bits);
+
+		/*How many positions can we have?*/
+		random_places = PAGE_SIZE / random_interval;
+
+		/*
+		 * get_random_int() % random_places = how many steps we move
+		 * Multiply this by random_interval to get our position.
+		 */
+		sp -= (get_random_int() % random_places) * random_interval;
+	}
+	return sp & ~0xf;
+}
+#endif
diff -urNp linux-2.6.16.16/include/asm-i386/processor.h linux-2.6.16.16-randparam/include/asm-i386/processor.h
--- linux-2.6.16.16/include/asm-i386/processor.h	2006-05-10 21:56:24.000000000 -0400
+++ linux-2.6.16.16-randparam/include/asm-i386/processor.h	2006-06-03 23:09:26.000000000 -0400
@@ -320,6 +320,13 @@ extern int bootloader_type;
  */
 #define TASK_SIZE	(PAGE_OFFSET)
 
+/*Interval in bytes to align the stack to*/
+#define STACK_ALIGN	16
+
+/*Random bits of stack and mmap()*/
+#define ARCH_RANDOM_STACK_BITS	19
+#define ARCH_RANDOM_MMAP_BITS	8
+
 /* This decides where the kernel will search for a free chunk of vm
  * space during mmap's.
  */
diff -urNp linux-2.6.16.16/include/asm-x86_64/processor.h linux-2.6.16.16-randparam/include/asm-x86_64/processor.h
--- linux-2.6.16.16/include/asm-x86_64/processor.h	2006-05-10 21:56:24.000000000 -0400
+++ linux-2.6.16.16-randparam/include/asm-x86_64/processor.h	2006-06-03 23:56:22.000000000 -0400
@@ -172,6 +172,23 @@ static inline void clear_in_cr4 (unsigne
 #define TASK_SIZE 		(test_thread_flag(TIF_IA32) ? IA32_PAGE_OFFSET : TASK_SIZE64)
 #define TASK_SIZE_OF(child) 	((test_tsk_thread_flag(child, TIF_IA32)) ? IA32_PAGE_OFFSET : TASK_SIZE64)
 
+/*Interval in bytes to align the stack to*/
+#define STACK_ALIGN	16
+
+/*Random bits of stack and mmap() in IA-32*/
+#define IA32_ARCH_RANDOM_STACK_BITS	19
+#define IA32_ARCH_RANDOM_MMAP_BITS	8
+
+/* Random bits of stack and mmap() in 64-bit mode.
+ * 28 bits is 40 bits of VMA, which is 1TiB, roughly 1/128
+ * of the address space. */
+#define ARCH_RANDOM_STACK_BITS64	28
+#define ARCH_RANDOM_MMAP_BITS64		28
+
+/*Random bits of stack and mmap()*/
+#define ARCH_RANDOM_STACK_BITS  (test_thread_flag(TIF_IA32) ? IA32_ARCH_RANDOM_STACK_BITS : ARCH_RANDOM_STACK_BITS64)
+#define ARCH_RANDOM_MMAP_BITS   (test_thread_flag(TIF_IA32) ? IA32_ARCH_RANDOM_MMAP_BITS : ARCH_RANDOM_MMAP_BITS64)
+
 #define TASK_UNMAPPED_BASE	PAGE_ALIGN(TASK_SIZE/3)
 
 /*
diff -urNp linux-2.6.16.16/include/linux/mm.h linux-2.6.16.16-randparam/include/linux/mm.h
--- linux-2.6.16.16/include/linux/mm.h	2006-05-10 21:56:24.000000000 -0400
+++ linux-2.6.16.16-randparam/include/linux/mm.h	2006-06-03 23:49:39.000000000 -0400
@@ -23,6 +23,38 @@ struct anon_vma;
 extern unsigned long max_mapnr;
 #endif
 
+/* Any arch not defining this is assumed to not know of
+ * sub-page stack alignment.
+ * Be sure to define these for each arch in
+ * include/asm-arch/processor.h */
+#ifndef STACK_ALIGN
+# define STACK_ALIGN	PAGE_SIZE
+#endif
+
+/* If these are not defined, disable randomization.
+ * Be sure to define these for each arch in
+ * include/asm-arch/processor.h */
+#ifndef ARCH_RANDOM_STACK_BITS
+# define ARCH_RANDOM_STACK_BITS	0
+#endif
+#ifndef ARCH_RANDOM_MMAP_BITS
+# define ARCH_RANDOM_MMAP_BITS	0
+#endif
+
+/*
+ * These are the biggest entropies we can have.
+ * Our original MAX_RANDOM_STACK_BITS was as below:
+ * 	long_log2((PAGE_SIZE / STACK_ALIGN) * (TASK_SIZE / 12) / PAGE_SIZE)
+ * This simplifies algebraicly to the below:
+ *   long_log2(TASK_SIZE / (12 * STACK_ALIGN))
+ */
+#define MAX_RANDOM_STACK_BITS \
+	long_log2(TASK_SIZE / (12 * STACK_ALIGN))
+#define MAX_RANDOM_STACK_BITS_PER_PAGE \
+	long_log2(PAGE_SIZE / STACK_ALIGN)
+#define MAX_RANDOM_MMAP_BITS \
+	long_log2((TASK_SIZE / 12) / PAGE_SIZE)
+
 extern unsigned long num_physpages;
 extern void * high_memory;
 extern unsigned long vmalloc_earlyreserve;

[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 892 bytes --]

Re: [RFC] Per-architecture randomization

[Arjan van de Ven]

On Sun, 2006-06-04 at 00:14 -0400, John Richard Moser wrote:
> Pavel Machek recommended per-architecture randomization defaults when I
> poked a (very hackish) patch up here.  As follow-up, I have taken out
> the command line parameter code and used the infrastructure I wrote to
> implement per-architecture randomization settings.
> 
> Three #defines are needed per architecture, preferably in
> include/asm-ARCH/processor.h or equivalent.  These defines are as follows:
> 
>  STACK_ALIGN -- Alignment of the stack, typically 16 (bytes).
>     If not defined, stack randomization is carried out to page
>     granularity
>  ARCH_RANDOM_STACK_BITS -- Bits of entropy to apply to the stack.
>     If not defined, stack randomization is disabled by defining this
>     as 0.
>  ARCH_RANDOM_MMAP_BITS -- Bits of entropy to apply to the mmap() base.
>     If not defined, mmap() randomization is disabled by defining this
>     as 0.


eh....

I think you missed a few things..
like
1) This is per architecture already for the most part!
   arch_align_stack() is obvious per architecture already
   the mmap randomisation also happens in arch/<foo>/mm
   and this is per arch by definition as well
2) you missed that the mmap randomization is *ON TOP OF*
   the stack randomization. So while you say "1Mb" in your
   doc in practice it is 8Mb

Also your patch is still full of XXX's and "other noise"... 
Also you probably should explain what the advantage is over the existing
per architecture approach. Just stating "it's per architecture" (as you
suggest) doesn't cut it since it is per architecture already for the
most part.

If all you want to do is turn 
-       if (current->flags & PF_RANDOMIZE)
-               random_variable = get_random_int() % (8*1024*1024);

that 8 into a per architecture thing.. then your patch is awefully big
and complex to just achieve that.

Re: [RFC] Per-architecture randomization

[John Richard Moser]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1



Arjan van de Ven wrote:
> On Sun, 2006-06-04 at 00:14 -0400, John Richard Moser wrote:
>> Pavel Machek recommended per-architecture randomization defaults when I
>> poked a (very hackish) patch up here.  As follow-up, I have taken out
>> the command line parameter code and used the infrastructure I wrote to
>> implement per-architecture randomization settings.
>>
>> Three #defines are needed per architecture, preferably in
>> include/asm-ARCH/processor.h or equivalent.  These defines are as follows:
>>
>>  STACK_ALIGN -- Alignment of the stack, typically 16 (bytes).
>>     If not defined, stack randomization is carried out to page
>>     granularity
>>  ARCH_RANDOM_STACK_BITS -- Bits of entropy to apply to the stack.
>>     If not defined, stack randomization is disabled by defining this
>>     as 0.
>>  ARCH_RANDOM_MMAP_BITS -- Bits of entropy to apply to the mmap() base.
>>     If not defined, mmap() randomization is disabled by defining this
>>     as 0.
> 
> 
> eh....
> 
> I think you missed a few things..
> like
> 1) This is per architecture already for the most part!
>    arch_align_stack() is obvious per architecture already

Yes you write a new one for each individual architecture, to tweak a few
variables in it.  Not that having the same function with the same blob
of code with 1 or 2 numbers in it changed matters, since only 1 is
generated to code...

>    the mmap randomisation also happens in arch/<foo>/mm
>    and this is per arch by definition as well

Yeah, same thing,
> 2) you missed that the mmap randomization is *ON TOP OF*
>    the stack randomization. So while you say "1Mb" in your
>    doc in practice it is 8Mb

This is fuzzy.  mmap() randomization is only 1MiB in most cases.  It's
only 9MiB if you don't already need the stack address to perform an attack.

The classical ret2libc attack requires a stack frame to carry out.  Your
two choices for this are injecting the stack frame into the heap (which
is fixed position on Linux), or injecting it into the stack.  You may
not always have a way to get it into a known position on the heap, so
cracking the stack may be the only choice.

Once your problem involves figuring out where the stack is, then the
added complexity of figuring out the location of mmap() is only 1MiB.  I
would dare say the stack's per-page alignment is all that counts*, and
this gives 2048 states; the mmap() randomization gives 256 states
itself, totaling 524,288 states to crack.  If mmap() was by its own
8MiB, this would be 2048 states for mmap() per stack state, giving
4,194,304 states total.

*If you can load 1 page of attack data, you can probably get it down to
2048, assuming a system() stack frame is less than 16 bytes.  Note that
we can discard the Return Pointer and SFP from the stack frames; they
can be filled with garbage.  We may be able to discard the local
variables as well, since whatever data is there is overwritten anyway.
This leaves us aligning the "passed arguments" part to 16 byte
boundaries.  This leaves 8 bytes "/bin/sh" and 4 bytes pointer to where
we hope it lands, 12 bytes.  Pad with 4 more bytes and set SFP to the
bottom of where you think it'll land, and (if you guessed VMA alignment
correct) any sub-page randomization value leads to a successful attack.

Of course without PIE, you can in theory return to an address where
there's a 'call system' in the main executable and if stack pointer is
pointed in the right direction, it'll complete the call.  This of course
assumes that the code is 'get_system_from_got; call system;' and not
'get_system_from_got; build_stack_frame; call system;'.  If I remember
right, actually calling a function from PIC involves jumping into the
PLT at the proper offset into a strip of code that does the actual call,
rather than retrieving an address out of the GOT based on an offset.
That should make this attack feasible.

At any rate, with the PIE attack you still have to crack the stack
before you can go anywhere.  mmap() randomization is 1MiB, stack
randomization is 8MiB, both have to be cracked along the way.

If you load your stack frame into the heap and try to use RETP to hit
the function directly, you're going to need to break the stack; as you
said, this is 11.17 bits of randomization anyway (2304 possible positions).

If you load your stack frame into the heap and use the main executable
attack, you have a known RETP and SFP value to use and randomization is
pointless.

> 
> Also your patch is still full of XXX's and "other noise"... 

Yeah, that's why I did [RFC] instead of [PATCH] this time.  I jumped the
gun last time.

My patch is also full of infrastructure like "hey if we have entropy >
what we think is sane cut it off."  We don't need that for per-arch
randomization because we can assume the #define is sane, it's coming
from the kernel devs.  We need it for i.e. SELinux policy or command
line or /proc, but none of that is in this patch.

> Also you probably should explain what the advantage is over the existing
> per architecture approach. Just stating "it's per architecture" (as you
> suggest) doesn't cut it since it is per architecture already for the
> most part.

1.  I can get away with exactly 1 mmap() randomization function, instead
of 1 function per architecture.
  - Less code to maintain
  - The entropy levels are #defined per arch instead of hard-coded into
    functions (more readable in the future)
2.  I can get away with exactly 1 arch_align_stack() function, instead
of 1 per architecture.
  - Less code to maintain
  - STACK_ALIGN can be used to figure out sub-page alignment per
    architecture (more readable in the future)
3.  Entropy levels are rather easy to adjust and tweak per-architecture
    or per-compile or per-execve().  This just leaves adding code to do
    it, i.e. SELinux hooks.

> 
> If all you want to do is turn 
> -       if (current->flags & PF_RANDOMIZE)
> -               random_variable = get_random_int() % (8*1024*1024);
> 
> that 8 into a per architecture thing.. then your patch is awefully big
> and complex to just achieve that.

Yes, you're right.  I will work on making it smaller, it's around 300
lines of code from around 10-15 lines of code.

Part of the bulk stems from the fact that I didn't do randomization
based on range, but based on bits of entropy.  I became more comfortable
with looking at entropy based on entropy instead of period*entropy
mostly from reading through the PaX documents**.  It doesn't really
matter, the code will be a lot less complex if I write it per range; we
can always put /*28 bits of entropy on x86-64*/ in processor.h or whatnot.

**But notice the difference between 8MiB and 9MiB randomization is 0.17
bits of entropy; and the difference between 16MiB and 17MiB of entropy
is 0.09 bits.  The amount of added time between (entropy1) and
(entropy2) is 2^(entropy2 - entropy1) times the time it takes to break
(entropy1), with entropies in bits.  Raw ranges quickly become mostly
meaningless, except for use as big numbers to impress people who don't
really understand what they're dealing with.

Also like I said, a lot of my calculations are somewhat ugly.  I define
4 variables named to show what I'm calculating and then calculate them
together to get what I'm after; the kernel isn't elementary mathematics
in C, it doesn't need to lead the reader through steps.

I'll work on it a bit.  May post a new one today or tomorrow.

> 
> -
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at  http://www.tux.org/lkml/
> 

- --
All content of all messages exchanged herein are left in the
Public Domain, unless otherwise explicitly stated.

    Creative brains are a valuable, limited resource. They shouldn't be
    wasted on re-inventing the wheel when there are so many fascinating
    new problems waiting out there.
                                                 -- Eric Steven Raymond

    We will enslave their women, eat their children and rape their
    cattle!
                  -- Bosc, Evil alien overlord from the fifth dimension
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2.2 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iQIVAwUBRIMHAQs1xW0HCTEFAQIBaA//WUjVz2WogaBrn0FNxDOyh59r/Bqp12E9
hqXIbnYwK4ZFWWI15Q2nFwKug9OzWrYDhPWRSa9j/mxuU9Qnfebxna3zNN43l+2F
f+VTPG6kMU9AzcMB7+LLGGMCJMk6djoJQUHH9zIK/zUdKz8xXW+tUBtsc0XYfYgq
iQ3+nBOpllxU0ORL8FMVjE1QooMTNSJKbd7u0QVms21aR7T0heNuKYGEC3AvpFv1
NAESyoaOBtEAj/q+xOSn4McMsiiKlKTQn0fQ6SeDnL0+TgJ4ACHKBsVpZeU3ic+T
HAwMEjpfgI6I8QuS+9diSiccJQWuiC4V8JzV1EgAMu1j3F4O6Sf8VhlOuFzdgQaj
1Ypq9HBWfDERPf3wrb/S7tnR6oDqDY3N8upH5kfYDt2veDADYtXw2MFaCkwVo2eD
Yx21MXlKm/+z3ddmMu9yRArxS4XSlwEelxUrx5HXwcMypImg46lTiiZ0QOCPMHzd
JmFPa0QhsSLtHGvpJHuU92FO4Y0rSMy6qHAv9flWuyOsnqMo9rWSSrjg90mZa5Ka
BYOzvfz3EZXElx/Esu1zz9+vH0mMkOESDG6O075pMzYbc0qh/KIFCSzFWlbjJdYj
S3K2c654GP2A94ibNamjS3FVRUZkwyGP65SHq2vTS9SuMztFwyRA29qQwEiV4Rwn
1OiSkiEw/d4=
=9myZ
-----END PGP SIGNATURE-----

Re: [RFC] Per-architecture randomization

[Arjan van de Ven]

On Sun, 2006-06-04 at 12:14 -0400, John Richard Moser wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
> 
> 
> 
> Arjan van de Ven wrote:
> > On Sun, 2006-06-04 at 00:14 -0400, John Richard Moser wrote:
> >> Pavel Machek recommended per-architecture randomization defaults when I
> >> poked a (very hackish) patch up here.  As follow-up, I have taken out
> >> the command line parameter code and used the infrastructure I wrote to
> >> implement per-architecture randomization settings.
> >>
> >> Three #defines are needed per architecture, preferably in
> >> include/asm-ARCH/processor.h or equivalent.  These defines are as follows:
> >>
> >>  STACK_ALIGN -- Alignment of the stack, typically 16 (bytes).
> >>     If not defined, stack randomization is carried out to page
> >>     granularity
> >>  ARCH_RANDOM_STACK_BITS -- Bits of entropy to apply to the stack.
> >>     If not defined, stack randomization is disabled by defining this
> >>     as 0.
> >>  ARCH_RANDOM_MMAP_BITS -- Bits of entropy to apply to the mmap() base.
> >>     If not defined, mmap() randomization is disabled by defining this
> >>     as 0.
> > 
> > 
> > eh....
> > 
> > I think you missed a few things..
> > like
> > 1) This is per architecture already for the most part!
> >    arch_align_stack() is obvious per architecture already
> 
> Yes you write a new one for each individual architecture, to tweak a few
> variables in it.  Not that having the same function with the same blob
> of code with 1 or 2 numbers in it changed matters, since only 1 is
> generated to code...

well stack alignment IS a per architecture property, and on some
architectures it'll be more complex than a single one-liner (think about
a 32 bit userspace needing different alignment than 64 bit as a simple
example of this).

It's a 2 or 3 line function for the simple cases like x86 so... why
bother making it really complex.


> > Also you probably should explain what the advantage is over the existing
> > per architecture approach. Just stating "it's per architecture" (as you
> > suggest) doesn't cut it since it is per architecture already for the
> > most part.
> 
> 1.  I can get away with exactly 1 mmap() randomization function, instead
> of 1 function per architecture.

which needs to be there for other reasons anyway; VA space layout is a
per architecture thing no matter what (just look at ia64 or ppc on how
complex things can get), randomization within each region is, as a
result of that, also a per architecture thing; with different rules for
different part of the VA space sometimes (ia64/ppc64) or on the type of
userspace that happens to be running (on all architectures that also
have a compat arch)

>   - Less code to maintain

we're talking less than a handful lines of code again, most of which is
NOT shareable.

>   - The entropy levels are #defined per arch instead of hard-coded into
>     functions (more readable in the future)

that's a separate thing; if you want to use a define rather than an open
coded value, fair enough, but make that a separate patch really;
especially since that is basically a "one line to a header + one line
code delta" which is then trivial to review for identity.

> 2.  I can get away with exactly 1 arch_align_stack() function, instead
> of 1 per architecture.

I don't think that that is fundamentally possible, see above.

> 3.  Entropy levels are rather easy to adjust and tweak per-architecture
>     or per-compile or per-execve().

this I don't get; you change a per arch thing to.. a per arch thing.


> Part of the bulk stems from the fact that I didn't do randomization
> based on range, but based on bits of entropy.  

I don't understand why you want to do that. It will make code a lot more
complex, and at the same time it limits you to powers-of-two in
practice.

> I became more comfortable
> with looking at entropy based on entropy instead of period*entropy
> mostly from reading through the PaX documents**.  

Using bits-of-entropy in documentation is fine, you can do fractions
there as well for example. No objection from me on that, but it
shouldn't have to complicate or limit the code. For code, "range" is a
native principle much more than "bits of". 

Re: [RFC] Per-architecture randomization

[John Richard Moser]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1



Arjan van de Ven wrote:
> On Sun, 2006-06-04 at 12:14 -0400, John Richard Moser wrote:
>> -----BEGIN PGP SIGNED MESSAGE-----
>> Hash: SHA1
>>
>>
>>
>> Arjan van de Ven wrote:
>>> On Sun, 2006-06-04 at 00:14 -0400, John Richard Moser wrote:
>>>> Pavel Machek recommended per-architecture randomization defaults when I
>>>> poked a (very hackish) patch up here.  As follow-up, I have taken out
>>>> the command line parameter code and used the infrastructure I wrote to
>>>> implement per-architecture randomization settings.
>>>>
>>>> Three #defines are needed per architecture, preferably in
>>>> include/asm-ARCH/processor.h or equivalent.  These defines are as follows:
>>>>
>>>>  STACK_ALIGN -- Alignment of the stack, typically 16 (bytes).
>>>>     If not defined, stack randomization is carried out to page
>>>>     granularity
>>>>  ARCH_RANDOM_STACK_BITS -- Bits of entropy to apply to the stack.
>>>>     If not defined, stack randomization is disabled by defining this
>>>>     as 0.
>>>>  ARCH_RANDOM_MMAP_BITS -- Bits of entropy to apply to the mmap() base.
>>>>     If not defined, mmap() randomization is disabled by defining this
>>>>     as 0.
>>>
>>> eh....
>>>
>>> I think you missed a few things..
>>> like
>>> 1) This is per architecture already for the most part!
>>>    arch_align_stack() is obvious per architecture already
>> Yes you write a new one for each individual architecture, to tweak a few
>> variables in it.  Not that having the same function with the same blob
>> of code with 1 or 2 numbers in it changed matters, since only 1 is
>> generated to code...
> 
> well stack alignment IS a per architecture property, and on some
> architectures it'll be more complex than a single one-liner (think about
> a 32 bit userspace needing different alignment than 64 bit as a simple
> example of this).

I did this already in the patch I sent with bits of entropy.  It's also
done with TASK_SIZE.  The alignment uses STACK_ALIGN and does the
calculations on the fly in the code.

Stack and mmap() VMA alignment is based on PAGE_SIZE.

> 
> It's a 2 or 3 line function for the simple cases like x86 so... why
> bother making it really complex.
> 

Yeah, my mmap() base randomization calculation now is 5 lines (not
including variable declarations, comments, or return), mmap_base() from
arch/i386/mm/mmap.c is 5 lines (not including etc etc),
arch_align_stack() is 5 lines (not including etc etc).

I guess slowing down process start-up by a few tens of nanoseconds is a
bit complex though.
> 
>>> Also you probably should explain what the advantage is over the existing
>>> per architecture approach. Just stating "it's per architecture" (as you
>>> suggest) doesn't cut it since it is per architecture already for the
>>> most part.
>> 1.  I can get away with exactly 1 mmap() randomization function, instead
>> of 1 function per architecture.
> 
> which needs to be there for other reasons anyway; VA space layout is a
> per architecture thing no matter what (just look at ia64 or ppc on how
> complex things can get), randomization within each region is, as a
> result of that, also a per architecture thing; with different rules for
> different part of the VA space sometimes (ia64/ppc64) or on the type of
> userspace that happens to be running (on all architectures that also
> have a compat arch)

I handled the different types of userspace already.  The solution is the
same solution x86-64 uses for TASK_SIZE.

Explain "randomization within each region."  I thought mmap()
randomization just shifted the mmap() base around at process start?

> 
>>   - Less code to maintain
> 
> we're talking less than a handful lines of code again, most of which is
> NOT shareable.
> 

The relevant parts are sharable.  I just moved this stuff out into
fs/exec.c:

/* Produce a random shift for mmap() base
 * The output of this function should always be page aligned*/
unsigned long mmap_base_random_factor() {
        unsigned long random_factor = 0;
        unsigned long random_bits = ARCH_RANDOM_MMAP_BITS;

        /*XXX:  Place a hook here to adjust mmap() randomization;
         * this hook will change the value of random_bits */

        if (random_bits > MAX_RANDOM_MMAP_BITS)
                random_bits = MAX_RANDOM_MMAP_BITS;

        /* randomize in range 2^random_bits * PAGE_SIZE */
        if (current->flags & PF_RANDOMIZE)
                random_factor = get_random_int() % (1 << random_bits);
        random_factor *= PAGE_SIZE;

        return PAGE_ALIGN(random_factor);
}

I'm pretty sure that last PAGE_ALIGN() is unnecessary.  The guts between
variable declaration and return are 5 lines of code.  Also, the
MAX_RANDOM_MMAP_BITS checks here can probably be removed until someone
decides to implement some sort of tunable, such as a LSM hook.  Even
then we should probably let the tunable do that check... well, that's a
design decision that could go either way.

Here's from arch/i386/mm/mmap.c:

static inline unsigned long mmap_base(struct mm_struct *mm)
{
        unsigned long gap = current->signal->rlim[RLIMIT_STACK].rlim_cur;
        unsigned long random_factor = 0;

        random_factor = mmap_base_random_factor();

        if (gap < MIN_GAP)
                gap = MIN_GAP;
        else if (gap > MAX_GAP)
                gap = MAX_GAP;

        return PAGE_ALIGN(TASK_SIZE - gap - random_factor);
}

And from arch/x86_64/mm/mmap.c:

void arch_pick_mmap_layout(struct mm_struct *mm)
{
#ifdef CONFIG_IA32_EMULATION
        if (current_thread_info()->flags & _TIF_IA32)
                return ia32_pick_mmap_layout(mm);
#endif

        mm->mmap_base = TASK_UNMAPPED_BASE;

        if (current->flags & PF_RANDOMIZE) {
                unsigned long random_factor = 0;
                /* Add our randomness. */
                random_factor = mmap_base_random_factor();
                mm->mmap_base += random_factor;
        }
        mm->get_unmapped_area = arch_get_unmapped_area;
        mm->unmap_area = arch_unmap_area;
}

and from include/asm-x86_64/processor.h:

/*Random bits of stack and mmap() in IA-32*/
#define IA32_ARCH_RANDOM_STACK_BITS     19
#define IA32_ARCH_RANDOM_MMAP_BITS      8

/* Random bits of stack and mmap() in 64-bit mode.
 * 28 bits is 40 bits of VMA, which is 1TiB, roughly 1/128
 * of the address space. */
#define ARCH_RANDOM_STACK_BITS64        28
#define ARCH_RANDOM_MMAP_BITS64         28

/*Random bits of stack and mmap()*/
#define ARCH_RANDOM_STACK_BITS  (test_thread_flag(TIF_IA32) ? \
	IA32_ARCH_RANDOM_STACK_BITS : ARCH_RANDOM_STACK_BITS64)
#define ARCH_RANDOM_MMAP_BITS   (test_thread_flag(TIF_IA32) ? \
	IA32_ARCH_RANDOM_MMAP_BITS : ARCH_RANDOM_MMAP_BITS64)

Yes, this is the same solution as with TASK_SIZE (which is about 3 lines
above this...)

>>   - The entropy levels are #defined per arch instead of hard-coded into
>>     functions (more readable in the future)
> 
> that's a separate thing; if you want to use a define rather than an open
> coded value, fair enough, but make that a separate patch really;
> especially since that is basically a "one line to a header + one line
> code delta" which is then trivial to review for identity.
> 

Easy enough to do for mmap(); for the stack there's ... complexity.

>> 2.  I can get away with exactly 1 arch_align_stack() function, instead
>> of 1 per architecture.
> 
> I don't think that that is fundamentally possible, see above.

Did it already, for any STACK_ALIGN, any PAGE_SIZE, any level of
entropy, and for stacks that grow up and down.  The only situations that
I haven't handled are stacks that grow up and down at the same time, and
stacks that teleport data to other dimensional planes.

> 
>> 3.  Entropy levels are rather easy to adjust and tweak per-architecture
>>     or per-compile or per-execve().
> 
> this I don't get; you change a per arch thing to.. a per arch thing.
> 

I'm thinking ahead to the possibility of tweaking entropy via SELinux
policy.  Some of us out here would rather apply MASSIVE_LEVEL_OF_ENTROPY
to Gaim and Firefox and Apache and
TINY_ENTROPY_LEVEL_THAT_WONT_BREAK_ORACLE to Oracle.

The level of stack entropy was definitely not per-architecture; the
level of mmap()... well, you had code for it in 3 places (i386, x86_64,
x86_64 IA-32 emul) that I found.

> 
>> Part of the bulk stems from the fact that I didn't do randomization
>> based on range, but based on bits of entropy.  
> 
> I don't understand why you want to do that. It will make code a lot more
> complex, and at the same time it limits you to powers-of-two in
> practice.
> 

In practice if you can assume an attacker can reasonably break 17 bits
of entropy, then you can assume that he can possibly (but unlikely)
double his attack efficiency and break 18 bits.  You would want to step
it up to 20 bits or so to get a few steps beyond "unlikely" into "we are
pretty confident this is impossible."

A fraction of a bit helps as much as a fraction of a slice of bread
helps complete a sandwich.

That being said, let me shrink this code down a bit first and then I'll
worry about switching to ranges.  In any case it's not really any more
restrictive than what the kernel currently has-- everything is aligned
to powers-of-two already AND HARD CODED.

>> I became more comfortable
>> with looking at entropy based on entropy instead of period*entropy
>> mostly from reading through the PaX documents**.  
> 
> Using bits-of-entropy in documentation is fine, you can do fractions
> there as well for example. No objection from me on that, but it
> shouldn't have to complicate or limit the code. For code, "range" is a
> native principle much more than "bits of". 

Right now I'm not so sure how to deal with less-than-a-page stack
randomization ranges ;)  (Handling all possible situations)

Sure VMA is easy to randomize over range and PAGE_ALIGN; but what the
hell do I do about sub-page randomization if PAGE_SIZE > RANDOM_RANGE >
0?  Complain that someone broke me?

My current thinking on this follows two schools of thought:

 1.  Something is obviously broken.  Ignore it and don't randomize.

 2.  Randomize to RANDOM_RANGE, divide by STACK_ALIGN, multiply by
     STACK_ALIGN.  With integers this will align the result to
     STACK_ALIGN.

> 
> 
> -
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at  http://www.tux.org/lkml/
> 

- --
All content of all messages exchanged herein are left in the
Public Domain, unless otherwise explicitly stated.

    Creative brains are a valuable, limited resource. They shouldn't be
    wasted on re-inventing the wheel when there are so many fascinating
    new problems waiting out there.
                                                 -- Eric Steven Raymond

    We will enslave their women, eat their children and rape their
    cattle!
                  -- Bosc, Evil alien overlord from the fifth dimension
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2.2 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iQIVAwUBRIMn6gs1xW0HCTEFAQK1+g//S87sCgbqxSdXD/HL2FCiLIDMIH708efb
y0xz0DKxnvuWhi5VlnJVcxDwSe+7lhVXp7khE9tRLGq46tQ2sHh+p8ZmwxhfdmQd
Bj7NQbk6zU+LXF1R7CqfI0N/FwS5R4te5KnZDe6oZbgvww/vL6bgj7oej+kYQXp1
fdQ4LEhMnqX4fD7C1XNw3cBm6cGtp2TugsiAvJl/yamllRNnJKuMS3Ut1ffA3Cqq
r7SfXmgGKaPIYKbk31b1KgC7kPWomP5D0K6mJPDth005TXiC4MbRGldTCCu6SQ6P
wATDlAPxl1XHxZ+vBqaRTm4bOrKi9zeSlKPnfe/ik/VvBVFiDfHaDJjJZURYvyE5
7/XAZqHoxcXly1wcqee17EXwcx8AnQTEr+wBCORF1cRnOIDsulT4bcBxYtD745z7
DtjCiZhNqCniHBUjUSijmiAHhp4aDyf3pzrmSZOPcTdSrknoFP3TXWksDXyA+qHr
S1Gl+OdbMcbrQv1o6bsi9LXXHLhoFgbfgaJKRutxGUV6V9nu3Iu/tzvVzAEqi1pv
phAD/Av1oqKB4AQ5aMFXdCzXQ309JGd3OgM7UxPabWJ0iVgn0i11PaZKY43ekTi6
faXQCPhTwD0CA72AcT7WkN4h1i5qbmEbLb0mjYFc0JliZkr4ogubeTaxggiifSwo
TO1w5wlWyGk=
=tezi
-----END PGP SIGNATURE-----

Re: [RFC] Per-architecture randomization

[John Richard Moser]

[-- Attachment #1.1: Type: text/plain, Size: 1758 bytes --]

Alright, trying again.  This patch is a bit smaller, easier to read,
more streamline.  randomize_stack_top() had code pulled out and put into
a static inline just before it; and the mmap() randomization
calculations are in fs/exec.c now. arch_align_stack() should also work
on stack-grows-up architectures like HPPA, not that it'll be used there
right now.


I am considering the following changes:

 - Base randomization on ranges, as suggested by Arjan van de Ven.  That
supersets current functionality, and we can implement entropy in bits
abstractly anyway (i.e. range = PAGE_SIZE * powr(2,ENTROPY_IN_BITS)).

 - Remove validation like 'if (random_bits > MAX_RANDOM_STACK_BITS)'.
These are not immediately useful; if SELinux hooks are added or such,
they would be, but they could also be added into the SELinux code for
those policy elements anyway.

 - Remove /*XXX: Put SELinux hooks here*/ comments.  This isn't hard to
figure out, anyone who wants to add SELinux hooks can figure this out then.

So before doing that, here's the current version.  Again, this has not
yet been compile tested, it's just scribbled out on paper.

Questions?  Comments?  Flames?  Pictures of your girlfriends?

-- 
All content of all messages exchanged herein are left in the
Public Domain, unless otherwise explicitly stated.

    Creative brains are a valuable, limited resource. They shouldn't be
    wasted on re-inventing the wheel when there are so many fascinating
    new problems waiting out there.
                                                 -- Eric Steven Raymond

    We will enslave their women, eat their children and rape their
    cattle!
                  -- Bosc, Evil alien overlord from the fifth dimension

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1.2: patch-2.6.16.16-rand_perarch-v2.diff --]
[-- Type: text/x-patch; name="patch-2.6.16.16-rand_perarch-v2.diff", Size: 16657 bytes --]

diff -urNp linux-2.6.16.16/Documentation/aslr.txt linux-2.6.16.16-randparam/Documentation/aslr.txt
--- linux-2.6.16.16/Documentation/aslr.txt	1969-12-31 19:00:00.000000000 -0500
+++ linux-2.6.16.16-randparam/Documentation/aslr.txt	2006-06-04 14:35:15.000000000 -0400
@@ -0,0 +1,111 @@
+Address space layout randomization is randomly selecting the base
+offsets of segments of memory in VMA.  It is used as a security tool
+to prevent sensitive attacks from being carried out by making important
+parameters to those attacks volatile and non-discoverable.
+
+Linux currently employs address space randomization in two places:
+
+1.  mmap() base
+ The base offset of libraries and anonymous mappings.  Randomization is
+ currently taken to the following degrees by default:
+
+  32-bit:  i386
+   Over 1MiB of VMA, giving 8 bits of entropy for 4096 byte pages.
+  64-bit:  x86-64
+   Over 1TiB of VMA, giving 28 bits of entropy for 4096 byte pages.
+
+ The maximum is over an area the size of TASK_SIZE / 12
+2.  stack base
+ The base offset of the stack.  Randomization is currently taken to the
+ following degrees by default:
+
+  32-bit:  i386
+   Over 8MiB of VMA, giving 19 bits of entropy, aligned to 16 bytes.
+  64-bit:  x86-64
+   Over 1TiB of VMA, giving 28 bits of entropy, aligned to 16 bytes.
+
+ The maximum allowed is over an area the size of TASK_SIZE / 12
+
+Linux does not employ heap randomization.
+
+Randomization is applied in the following places.
+
+
+STACK RANDOMIZATION
+
+fs/exec.c
+unsigned long arch_align_stack(unsigned long sp)
+
+ This function is called during process initialization to shuffle the
+ stack pointer to sub-page granularity.  It applies a portion of the
+ stack entropy.
+
+ This function calculates how much randomization to apply in the
+ following way:
+
+  - Divide PAGE_SIZE by STACK_ALIGN
+  - Take the long_log2() of that to get MAX_RANDOM_STACK_BITS_PER_PAGE
+  + If MAX_RANDOM_STACK_BITS_PER_PAGE > total bits of entropy
+   - page_random_bits = total bits of entropy
+  + If MAX_RANDOM_STACK_BITS_PER_PAGE <= total bits of entropy
+   - page_random_bits = MAX_RANDOM_STACK_BITS_PER_PAGE
+  - Raise 2^page_random_bits to get random_places
+  - Divide PAGE_SIZE by random_places to get random_interval
+  - (get_random_int() % random_places) * random_interval = offset
+  + If stack grows down
+   - Subtract offset from the stack pointer
+  + If stack grows up
+   - Add offset to the stack pointer
+
+
+fs/binfmt_elf.c
+static unsigned long randomize_stack_top(unsigned long stack_top)
+
+ This function is called during process initialization to shuffle the
+ stack pointer to page granularity.  It applies a portion of the stack
+ entropy.
+
+ This function gets the number of possible states, i.e. positions the
+ stack can be in, and choses a random number in that range.  It then
+ multiplies the result by PAGE_SIZE to get the stack offset.
+
+
+fs/binfmt_elf.c
+static inline unsigned long randomize_stack_top_states()
+
+ This function is used by randomize_stack_top() to get how many
+ states stack randomization supplies.
+
+ This function calculates how much randomization to apply in the
+ following way:
+
+  - Divide PAGE_SIZE by STACK_ALIGN
+  - Take the long_log2() of that to get MAX_RANDOM_STACK_BITS_PER_PAGE
+  + If MAX_RANDOM_STACK_BITS_PER_PAGE > total bits of entropy
+   - vma_random_bits = 0
+  + If MAX_RANDOM_STACK_BITS_PER_PAGE <= total bits of entropy
+   - vma_random_bits =
+               total bits entropy - MAX_RANDOM_STACK_BITS_PER_PAGE
+  - Multiply PAGE_SIZE by 2^random_bits to get random_range
+  - random_variable = get_random_int() % random_range
+  - Offset stack in VMA by random_variable and PAGE_ALIGN() result
+
+
+MMAP RANDOMIZATION
+
+fs/exec.c
+unsigned long mmap_base_random_factor()
+
+ This function is called during process initialization to shuffle the
+ mmap() baser to page granularity.  It applies full mmap() entropy.
+
+Also note the following:
+
+ - STACK_ALIGN is defined in include/asm-*/processor.h
+ - include/linux/mm.h defines STACK_ALIGN as PAGE_SIZE if it is not
+   defined
+ - ARCH_RANDOM_STACK_BITS and MMAP_RANDOM_STACK_BITS are defined in
+   include/arch-*/processor.h
+ - ARCH_RANDOM_STACK_BITS and MMAP_RANDOM_STACK_BITS are defined as
+   0 in include/linux/mm.h if not otherwise defined
+
diff -urNp linux-2.6.16.16/arch/i386/kernel/process.c linux-2.6.16.16-randparam/arch/i386/kernel/process.c
--- linux-2.6.16.16/arch/i386/kernel/process.c	2006-05-10 21:56:24.000000000 -0400
+++ linux-2.6.16.16-randparam/arch/i386/kernel/process.c	2006-05-21 03:23:40.000000000 -0400
@@ -905,9 +905,3 @@ asmlinkage int sys_get_thread_area(struc
 	return 0;
 }
 
-unsigned long arch_align_stack(unsigned long sp)
-{
-	if (randomize_va_space)
-		sp -= get_random_int() % 8192;
-	return sp & ~0xf;
-}
diff -urNp linux-2.6.16.16/arch/i386/mm/mmap.c linux-2.6.16.16-randparam/arch/i386/mm/mmap.c
--- linux-2.6.16.16/arch/i386/mm/mmap.c	2006-05-10 21:56:24.000000000 -0400
+++ linux-2.6.16.16-randparam/arch/i386/mm/mmap.c	2006-06-04 13:11:17.000000000 -0400
@@ -41,8 +41,7 @@ static inline unsigned long mmap_base(st
 	unsigned long gap = current->signal->rlim[RLIMIT_STACK].rlim_cur;
 	unsigned long random_factor = 0;
 
-	if (current->flags & PF_RANDOMIZE)
-		random_factor = get_random_int() % (1024*1024);
+	random_factor = mmap_base_random_factor();
 
 	if (gap < MIN_GAP)
 		gap = MIN_GAP;
diff -urNp linux-2.6.16.16/arch/um/kernel/process_kern.c linux-2.6.16.16-randparam/arch/um/kernel/process_kern.c
--- linux-2.6.16.16/arch/um/kernel/process_kern.c	2006-05-10 21:56:24.000000000 -0400
+++ linux-2.6.16.16-randparam/arch/um/kernel/process_kern.c	2006-05-21 03:24:19.000000000 -0400
@@ -454,18 +454,3 @@ int singlestepping(void * t)
 	return 2;
 }
 
-/*
- * Only x86 and x86_64 have an arch_align_stack().
- * All other arches have "#define arch_align_stack(x) (x)"
- * in their asm/system.h
- * As this is included in UML from asm-um/system-generic.h,
- * we can use it to behave as the subarch does.
- */
-#ifndef arch_align_stack
-unsigned long arch_align_stack(unsigned long sp)
-{
-	if (randomize_va_space)
-		sp -= get_random_int() % 8192;
-	return sp & ~0xf;
-}
-#endif
diff -urNp linux-2.6.16.16/arch/x86_64/ia32/mmap32.c linux-2.6.16.16-randparam/arch/x86_64/ia32/mmap32.c
--- linux-2.6.16.16/arch/x86_64/ia32/mmap32.c	2006-05-10 21:56:24.000000000 -0400
+++ linux-2.6.16.16-randparam/arch/x86_64/ia32/mmap32.c	2006-06-04 13:14:12.000000000 -0400
@@ -43,8 +43,7 @@ static inline unsigned long mmap_base(st
 	unsigned long gap = current->signal->rlim[RLIMIT_STACK].rlim_cur;
 	unsigned long random_factor = 0;
 
-	if (current->flags & PF_RANDOMIZE)
-		random_factor = get_random_int() % (1024*1024);
+	random_factor = mmap_base_random_factor();
 
 	if (gap < MIN_GAP)
 		gap = MIN_GAP;
diff -urNp linux-2.6.16.16/arch/x86_64/kernel/process.c linux-2.6.16.16-randparam/arch/x86_64/kernel/process.c
--- linux-2.6.16.16/arch/x86_64/kernel/process.c	2006-05-10 21:56:24.000000000 -0400
+++ linux-2.6.16.16-randparam/arch/x86_64/kernel/process.c	2006-05-21 03:24:06.000000000 -0400
@@ -839,9 +839,3 @@ int dump_task_regs(struct task_struct *t
 	return 1;
 }
 
-unsigned long arch_align_stack(unsigned long sp)
-{
-	if (randomize_va_space)
-		sp -= get_random_int() % 8192;
-	return sp & ~0xf;
-}
diff -urNp linux-2.6.16.16/arch/x86_64/mm/mmap.c linux-2.6.16.16-randparam/arch/x86_64/mm/mmap.c
--- linux-2.6.16.16/arch/x86_64/mm/mmap.c	2006-05-10 21:56:24.000000000 -0400
+++ linux-2.6.16.16-randparam/arch/x86_64/mm/mmap.c	2006-06-04 13:17:49.000000000 -0400
@@ -15,14 +15,14 @@ void arch_pick_mmap_layout(struct mm_str
 	if (current_thread_info()->flags & _TIF_IA32)
 		return ia32_pick_mmap_layout(mm);
 #endif
+
 	mm->mmap_base = TASK_UNMAPPED_BASE;
+	
 	if (current->flags & PF_RANDOMIZE) {
-		/* Add 28bit randomness which is about 40bits of address space
-		   because mmap base has to be page aligned.
- 		   or ~1/128 of the total user VM
-	   	   (total user address space is 47bits) */
-		unsigned rnd = get_random_int() & 0xfffffff;
-		mm->mmap_base += ((unsigned long)rnd) << PAGE_SHIFT;
+		unsigned long random_factor = 0;
+		/* Add our randomness. */
+		random_factor = mmap_base_random_factor();
+		mm->mmap_base += random_factor;
 	}
 	mm->get_unmapped_area = arch_get_unmapped_area;
 	mm->unmap_area = arch_unmap_area;
diff -urNp linux-2.6.16.16/fs/binfmt_elf.c linux-2.6.16.16-randparam/fs/binfmt_elf.c
--- linux-2.6.16.16/fs/binfmt_elf.c	2006-05-10 21:56:24.000000000 -0400
+++ linux-2.6.16.16-randparam/fs/binfmt_elf.c	2006-06-04 14:36:21.000000000 -0400
@@ -500,13 +500,42 @@ out:
 #define INTERPRETER_AOUT 1
 #define INTERPRETER_ELF 2
 
+/* number of states accounted for by the stack, i.e.
+ * the number of random positions it can be in.
+ * Currently we find this via bits of entropy. */
+static inline unsigned long randomize_stack_top_states() {
+	long vma_random_bits = 0;
+	long random_bits = ARCH_RANDOM_STACK_BITS;
+
+	/* XXX: Place a hook here to adjust stack randomization;
+	 * this hook will change the value of random_bits */
+
+	if (random_bits > MAX_RANDOM_STACK_BITS)
+		random_bits = MAX_RANDOM_STACK_BITS;
+
+	/* Cut the bits in the sub-page randomization out */
+	if (random_bits <= MAX_RANDOM_STACK_BITS_PER_PAGE)
+		vma_random_bits = 0;
+	else
+		vma_random_bits = random_bits
+		       	- MAX_RANDOM_STACK_BITS_PER_PAGE;
+
+	/* 2^vma_random_bits */
+	return (1 << vma_random_bits);
+}
 
 static unsigned long randomize_stack_top(unsigned long stack_top)
 {
 	unsigned int random_variable = 0;
 
-	if (current->flags & PF_RANDOMIZE)
-		random_variable = get_random_int() % (8*1024*1024);
+	/*Randomization
+	 * Pick from 0 to how many states there are and multiply
+	 * PAGE_SIZE to get an aligned random stack base.
+	 */
+	if (current->flags & PF_RANDOMIZE) {
+		random_variable = get_random_int() % (randomize_stack_top_states());
+		random_variable *= PAGE_SIZE;
+	}
 #ifdef CONFIG_STACK_GROWSUP
 	return PAGE_ALIGN(stack_top + random_variable);
 #else
diff -urNp linux-2.6.16.16/fs/exec.c linux-2.6.16.16-randparam/fs/exec.c
--- linux-2.6.16.16/fs/exec.c	2006-05-10 21:56:24.000000000 -0400
+++ linux-2.6.16.16-randparam/fs/exec.c	2006-06-04 14:38:23.000000000 -0400
@@ -49,6 +49,7 @@
 #include <linux/rmap.h>
 #include <linux/acct.h>
 #include <linux/cn_proc.h>
+#include <linux/random.h>
 
 #include <asm/uaccess.h>
 #include <asm/mmu_context.h>
@@ -1526,3 +1527,69 @@ fail_unlock:
 fail:
 	return retval;
 }
+
+/*
+ * This arch_align_stack() is universal and should work across all
+ * architectures.  Most architectures still have a
+ * '#define arch_align_stack(x) (x)' somewhere anyway.
+ */
+#ifndef arch_align_stack
+unsigned long arch_align_stack(unsigned long sp)
+{
+	long page_random_bits = 0;
+	unsigned long random_factor = 0;
+	long random_bits = ARCH_RANDOM_STACK_BITS;
+
+	if (randomize_va_space && (page_random_bits > 0)) {
+		/*XXX: Place a hook here to adjust stack randomization;
+		 * this hook will change the value of random_bits */
+
+		/*What's the most randomness we can get in the page*/
+		page_random_bits = MAX_RANDOM_STACK_BITS_PER_PAGE;
+
+		/*Are we using less entropy than that?*/
+		if (page_random_bits > random_bits)
+			page_random_bits = random_bits;
+
+		/*
+		 * The stack is shifted around within PAGE_SIZE in
+		 * intervals of STACK_ALIGN bytes.  Intervals may be
+		 * bigger than STACK_ALIGN if entropy is less than
+		 * MAX_RANDOM_STACK_BITS_PER_PAGE.
+		 *
+		 * The position of the stack in VMA is set in binfmt_elf.c
+		 *
+		 * We can have (1 << page_random_bits) positions,
+		 * aligned to PAGE_SIZE / (1 << page_random_bits)
+		 */
+		random_factor = (get_random_int() % (1 << page_random_bits))
+			* (PAGE_SIZE / (1 << page_random_bits));
+#ifdef CONFIG_STACK_GROWSUP
+		sp += random_factor;
+#else
+		sp -= random_factor;
+#endif
+	}
+	return sp; /*Should already be aligned*/
+}
+#endif
+
+/* Produce a random shift for mmap() base
+ * The output of this function should always be page aligned*/
+unsigned long mmap_base_random_factor() {
+	unsigned long random_factor = 0;
+	unsigned long random_bits = ARCH_RANDOM_MMAP_BITS;
+
+	/*XXX:  Place a hook here to adjust mmap() randomization;
+	 * this hook will change the value of random_bits */
+
+	if (random_bits > MAX_RANDOM_MMAP_BITS)
+		random_bits = MAX_RANDOM_MMAP_BITS;
+
+	/* randomize in range 2^random_bits * PAGE_SIZE */
+	if (current->flags & PF_RANDOMIZE)
+		random_factor = get_random_int() % (1 << random_bits);
+	random_factor *= PAGE_SIZE;
+
+	return PAGE_ALIGN(random_factor);
+}
diff -urNp linux-2.6.16.16/include/asm-i386/processor.h linux-2.6.16.16-randparam/include/asm-i386/processor.h
--- linux-2.6.16.16/include/asm-i386/processor.h	2006-05-10 21:56:24.000000000 -0400
+++ linux-2.6.16.16-randparam/include/asm-i386/processor.h	2006-06-03 23:09:26.000000000 -0400
@@ -320,6 +320,13 @@ extern int bootloader_type;
  */
 #define TASK_SIZE	(PAGE_OFFSET)
 
+/*Interval in bytes to align the stack to*/
+#define STACK_ALIGN	16
+
+/*Random bits of stack and mmap()*/
+#define ARCH_RANDOM_STACK_BITS	19
+#define ARCH_RANDOM_MMAP_BITS	8
+
 /* This decides where the kernel will search for a free chunk of vm
  * space during mmap's.
  */
diff -urNp linux-2.6.16.16/include/asm-x86_64/processor.h linux-2.6.16.16-randparam/include/asm-x86_64/processor.h
--- linux-2.6.16.16/include/asm-x86_64/processor.h	2006-05-10 21:56:24.000000000 -0400
+++ linux-2.6.16.16-randparam/include/asm-x86_64/processor.h	2006-06-03 23:56:22.000000000 -0400
@@ -172,6 +172,23 @@ static inline void clear_in_cr4 (unsigne
 #define TASK_SIZE 		(test_thread_flag(TIF_IA32) ? IA32_PAGE_OFFSET : TASK_SIZE64)
 #define TASK_SIZE_OF(child) 	((test_tsk_thread_flag(child, TIF_IA32)) ? IA32_PAGE_OFFSET : TASK_SIZE64)
 
+/*Interval in bytes to align the stack to*/
+#define STACK_ALIGN	16
+
+/*Random bits of stack and mmap() in IA-32*/
+#define IA32_ARCH_RANDOM_STACK_BITS	19
+#define IA32_ARCH_RANDOM_MMAP_BITS	8
+
+/* Random bits of stack and mmap() in 64-bit mode.
+ * 28 bits is 40 bits of VMA, which is 1TiB, roughly 1/128
+ * of the address space. */
+#define ARCH_RANDOM_STACK_BITS64	28
+#define ARCH_RANDOM_MMAP_BITS64		28
+
+/*Random bits of stack and mmap()*/
+#define ARCH_RANDOM_STACK_BITS  (test_thread_flag(TIF_IA32) ? IA32_ARCH_RANDOM_STACK_BITS : ARCH_RANDOM_STACK_BITS64)
+#define ARCH_RANDOM_MMAP_BITS   (test_thread_flag(TIF_IA32) ? IA32_ARCH_RANDOM_MMAP_BITS : ARCH_RANDOM_MMAP_BITS64)
+
 #define TASK_UNMAPPED_BASE	PAGE_ALIGN(TASK_SIZE/3)
 
 /*
diff -urNp linux-2.6.16.16/include/linux/mm.h linux-2.6.16.16-randparam/include/linux/mm.h
--- linux-2.6.16.16/include/linux/mm.h	2006-05-10 21:56:24.000000000 -0400
+++ linux-2.6.16.16-randparam/include/linux/mm.h	2006-06-04 13:11:09.000000000 -0400
@@ -23,6 +23,44 @@ struct anon_vma;
 extern unsigned long max_mapnr;
 #endif
 
+/* Any arch not defining this is assumed to not know of
+ * sub-page stack alignment.
+ * Be sure to define these for each arch in
+ * include/asm-arch/processor.h */
+#ifndef STACK_ALIGN
+# define STACK_ALIGN	PAGE_SIZE
+#endif
+
+/* If these are not defined, disable randomization.
+ * Be sure to define these for each arch in
+ * include/asm-arch/processor.h */
+#ifndef ARCH_RANDOM_STACK_BITS
+# define ARCH_RANDOM_STACK_BITS	0
+#endif
+#ifndef ARCH_RANDOM_MMAP_BITS
+# define ARCH_RANDOM_MMAP_BITS	0
+#endif
+
+/*
+ * These are the biggest entropies we can have.
+ * Our original MAX_RANDOM_STACK_BITS was as below:
+ * 	long_log2((PAGE_SIZE / STACK_ALIGN) * (TASK_SIZE / 12) / PAGE_SIZE)
+ * This simplifies algebraicly to the below:
+ *   long_log2(TASK_SIZE / (12 * STACK_ALIGN))
+ *
+ * At most we should shift by 1/12 TASK_SIZE.  This is 256M on
+ * 3GiB i386; 85M (64M, 14 bits) on 1GiB i386; 8TiB (31 bits)
+ * on x86-64 with 47 bits of user VMA...
+ */
+#define MAX_RANDOM_STACK_BITS \
+	long_log2(TASK_SIZE / (12 * STACK_ALIGN))
+#define MAX_RANDOM_STACK_BITS_PER_PAGE \
+	long_log2(PAGE_SIZE / STACK_ALIGN)
+#define MAX_RANDOM_MMAP_BITS \
+	long_log2((TASK_SIZE / 12) / PAGE_SIZE)
+
+unsigned long mmap_base_random_factor();
+
 extern unsigned long num_physpages;
 extern void * high_memory;
 extern unsigned long vmalloc_earlyreserve;

[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 892 bytes --]

Re: [RFC] Per-architecture randomization

[Arjan van de Ven]

On Sun, 2006-06-04 at 14:35 -0400, John Richard Moser wrote:

> Stack and mmap() VMA alignment is based on PAGE_SIZE.

which breaks ppc64 for hugetlbs at least.

> Explain "randomization within each region."  I thought mmap()
> randomization just shifted the mmap() base around at process start?

ia64 and iirc also ppc64 have different regions in the VA space for
different types of mmaps. Hugetlb, executable, non-cachable etc etc.


> 
> > 
> >>   - Less code to maintain
> > 
> > we're talking less than a handful lines of code again, most of which is
> > NOT shareable.
> > 
> 
> The relevant parts are sharable.  I just moved this stuff out into
> fs/exec.c:

... and made it a lot more complex.

> Yes, this is the same solution as with TASK_SIZE (which is about 3 lines
> above this...)

the rules for mmap_base vary per architecture, and even per binary time.
In fact the meaning of it is very much free for the architecture to
determine/use.
> >> 2.  I can get away with exactly 1 arch_align_stack() function, instead
> >> of 1 per architecture.
> > 
> > I don't think that that is fundamentally possible, see above.
> 
> Did it already, for any STACK_ALIGN, any PAGE_SIZE, any level of
> entropy, and for stacks that grow up and down.  The only situations that
> I haven't handled are stacks that grow up and down at the same time,

ok so you haven't dealt with ia64 yet ;)

>  and
> stacks that teleport data to other dimensional planes.

and with stacks that need different alignment based on binary type (mips
has 4 or so of those) or .. or ..


> The level of stack entropy was definitely not per-architecture; 

no but it COULD be. I haven't looked at the ia64 randomization, but I'd
not be surprised if it was different


> >> Part of the bulk stems from the fact that I didn't do randomization
> >> based on range, but based on bits of entropy.  
> > 
> > I don't understand why you want to do that. It will make code a lot more
> > complex, and at the same time it limits you to powers-of-two in
> > practice.
> > 
> 
> In practice if you can assume an attacker can reasonably break 17 bits
> of entropy, then you can assume that he can possibly (but unlikely)
> double his attack efficiency and break 18 bits.  You would want to step
> it up to 20 bits or so to get a few steps beyond "unlikely" into "we are
> pretty confident this is impossible."

I think you totally missed the point. *I DON'T CARE ABOUT "BITS OF
ENTROPY" IN THE CODE*. The code cares about how much it is in actual
bytes. Sure when talking about it in documents or analysis it may make
sense to do the bits math. BUT NOT IN THE CODE.

That was my point, and all there was to it. You add complexity and
limitations TO THE CODE for no good reason at all.

Re: [RFC] Per-architecture randomization

[John Richard Moser]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1



Arjan van de Ven wrote:
> On Sun, 2006-06-04 at 14:35 -0400, John Richard Moser wrote:
> 
>> Stack and mmap() VMA alignment is based on PAGE_SIZE.
> 
> which breaks ppc64 for hugetlbs at least.
> 
>> Explain "randomization within each region."  I thought mmap()
>> randomization just shifted the mmap() base around at process start?
> 
> ia64 and iirc also ppc64 have different regions in the VA space for
> different types of mmaps. Hugetlb, executable, non-cachable etc etc.
> 

Whoa.

Looks like I need a little education on this subject before I can come
up with a solution to this one.

> 
>>>>   - Less code to maintain
>>> we're talking less than a handful lines of code again, most of which is
>>> NOT shareable.
>>>
>> The relevant parts are sharable.  I just moved this stuff out into
>> fs/exec.c:
> 
> ... and made it a lot more complex.
> 

My mm.h macros are a lot more complex, probably.  Although it would help
if you pointed out where "complexity" shows up; honestly for the most
part it looks clean and neat to me, besides a few rough edges and
excessive commenting.

>> Yes, this is the same solution as with TASK_SIZE (which is about 3 lines
>> above this...)
> 
> the rules for mmap_base vary per architecture, and even per binary time.
> In fact the meaning of it is very much free for the architecture to
> determine/use.

So the base can't just be randomized once?

>>>> 2.  I can get away with exactly 1 arch_align_stack() function, instead
>>>> of 1 per architecture.
>>> I don't think that that is fundamentally possible, see above.
>> Did it already, for any STACK_ALIGN, any PAGE_SIZE, any level of
>> entropy, and for stacks that grow up and down.  The only situations that
>> I haven't handled are stacks that grow up and down at the same time,
> 
> ok so you haven't dealt with ia64 yet ;)
> 

So far IA-64 sounds like "we designed this while on acid," but fair
enough.  Explain.

>>  and
>> stacks that teleport data to other dimensional planes.
> 
> and with stacks that need different alignment based on binary type (mips
> has 4 or so of those) or .. or ..

Use the same solution as TASK_SIZE, although 4 binary types is going to
become painful yes.  You can do it with a #define but I'm getting the
feeling that these parts may need per-architecture and per-binary-type
functions to sort it out (in the same way that there was an mmap_base()
for IA-32 and x86-64 in x86-64).

> 
> 
>> The level of stack entropy was definitely not per-architecture; 
> 
> no but it COULD be. I haven't looked at the ia64 randomization, but I'd
> not be surprised if it was different

VMA stack entropy was in fs/binfmt_elf.c and rather hard coded.

> 
> 
>>>> Part of the bulk stems from the fact that I didn't do randomization
>>>> based on range, but based on bits of entropy.  
>>> I don't understand why you want to do that. It will make code a lot more
>>> complex, and at the same time it limits you to powers-of-two in
>>> practice.
>>>
>> In practice if you can assume an attacker can reasonably break 17 bits
>> of entropy, then you can assume that he can possibly (but unlikely)
>> double his attack efficiency and break 18 bits.  You would want to step
>> it up to 20 bits or so to get a few steps beyond "unlikely" into "we are
>> pretty confident this is impossible."
> 
> I think you totally missed the point. *I DON'T CARE ABOUT "BITS OF
> ENTROPY" IN THE CODE*. The code cares about how much it is in actual
> bytes. Sure when talking about it in documents or analysis it may make
> sense to do the bits math. BUT NOT IN THE CODE.

I was only addressing the "it limits you to powers-of-two" part, not
code complexity.  The point was that strictly speaking it's not that
great to be able to do it more fine-grained.  This doesn't mean people
wouldn't want to (hey I may want my stack and mmap() to move around by a
gig on i386, it'll barely work and X will break half the time, but WHY
would I want to?).

> 
> That was my point, and all there was to it. You add complexity and
> limitations TO THE CODE for no good reason at all.
> 

I'll address those in the next pass.  It will involve a little integer
multiplication/division to provide proper sub-page alignment for the
stack; VMA alignment can use PAGE_ALIGN().

> 
> 
> 

- --
All content of all messages exchanged herein are left in the
Public Domain, unless otherwise explicitly stated.

    Creative brains are a valuable, limited resource. They shouldn't be
    wasted on re-inventing the wheel when there are so many fascinating
    new problems waiting out there.
                                                 -- Eric Steven Raymond

    We will enslave their women, eat their children and rape their
    cattle!
                  -- Bosc, Evil alien overlord from the fifth dimension
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2.2 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iQIVAwUBRIMwPws1xW0HCTEFAQK5aQ//W9m6h2DbSXP0yrNRKGgv7SCzZDbacsds
eXubeG8l1OAnMmsDaAYgnX5g/aAb0md7xNi39CT5x4dgQiM+dyCX7TYIG/TaaN5+
lLLKt/xQZm73hUxk7s4pKiBN7OY8n5YwaEiP5JpfZZi/27KxV0DR8s1VDsRj8xGz
3uuEF6hsZXZZKIuG46pG6nwHphJNQkCZp6G8tZdQWC+LuclulB50PNxNMzUxe31S
13M7q81icGcbHnOvUvA7EHexa1Ru22VCl8NjTwogTwP/eIVcN/acE17EO/m/xfIz
g9JXCgeF+soIk3SQTydR70CZwGENxs/mrYTXksWMDRsGmOK2qg5pSo7sr4V98g5P
jF6x/044JAKWB/fmlEr5QxFCGFHuPSDSqeZHPiRWQnbn8nH2VB9aSRGK/mpx+rpJ
/xIZrJLndFc06CdLe71inrjlBIhAQ58XuSd5pGGmLiKmwXiOGCDaWS5Qb0YChV2i
hujNZ4AhuuPT9TiMhi842NR3Dd8NTy/mY1JlqUtao8ofnhQqf6GndDuwTrIn3TOL
lm6X7EBuVbhXggsnjnQiaK10k90qU5Pgy9eqJYL8vybbuLu5uOwlxsuBM4ceIUya
oyVxOYnySND2FpxhH55IfAnxTC2I1avd+V4vvuIc3hJEWUbugf6iUzX72/0rYo88
HL5S4HK8UbQ=
=zZEn
-----END PGP SIGNATURE-----