Patch 0/6 virtual address space randomisation

Patch 0/6 virtual address space randomisation

[Arjan van de Ven]

The randomisation patch series introduces infrastructure and functionality
that causes certain parts of a process' virtual address space to be
different for each invocation of the process. The purpose of this is to
raise the bar on buffer overflow exploits; full randomisation makes it not
possible to use absolute addresses in the exploit.

This first series only does a partial randomisation, future series will
randomize other parts of the virtual address space as well.

01-sysctl-A0			- introduce a sysctl to enable/disable
02-randomize-infrastructure	- infrastructure helpers
03-PF_RANDOMIZE			- per process flag to enable/disable
04-stack			- start randomizing the stack pointer
05-mmap				- start randomizing mmap addresses
06-default-enable		- enable randomisation by default (for -mm testing only) 

This series does NOT randomize the brk() area and does not yet add support
for PIE binaries. This I will leave to a next series; this one should first
settle down.

Signed-off-by: Arjan van de Ven <arjan@infradead.org>

Re: Patch 1/6 introduce sysctl

[Arjan van de Ven]

This first patch of the series introduces a sysctl (default off) that
enables/disables the randomisation feature globally. Since randomisation may
make it harder to debug really tricky situations (reproducability goes
down), the sysadmin needs a way to disable it globally.

Signed-off-by: Arjan van de Ven <arjan@infradead.org>


diff -purN linux-2.6.11-rc2-bk4/include/linux/kernel.h linux-step-1/include/linux/kernel.h
--- linux-2.6.11-rc2-bk4/include/linux/kernel.h	2005-01-26 18:24:39.000000000 +0100
+++ linux-step-1/include/linux/kernel.h	2005-01-26 19:04:58.016540168 +0100
@@ -278,6 +278,9 @@ struct sysinfo {
 extern void BUILD_BUG(void);
 #define BUILD_BUG_ON(condition) do { if (condition) BUILD_BUG(); } while(0)
 
+
+extern int randomize_va_space; 
+
 /* Trap pasters of __FUNCTION__ at compile-time */
 #if __GNUC__ > 2 || __GNUC_MINOR__ >= 95
 #define __FUNCTION__ (__func__)
diff -purN linux-2.6.11-rc2-bk4/include/linux/sysctl.h linux-step-1/include/linux/sysctl.h
--- linux-2.6.11-rc2-bk4/include/linux/sysctl.h	2005-01-26 18:24:39.000000000 +0100
+++ linux-step-1/include/linux/sysctl.h	2005-01-26 19:01:13.640650488 +0100
@@ -135,6 +135,7 @@ enum
 	KERN_HZ_TIMER=65,	/* int: hz timer on or off */
 	KERN_UNKNOWN_NMI_PANIC=66, /* int: unknown nmi panic flag */
 	KERN_BOOTLOADER_TYPE=67, /* int: boot loader type */
+	KERN_RANDOMIZE=68, /* int: randomize virtual address space */
 };
 
 
diff -purN linux-2.6.11-rc2-bk4/kernel/sysctl.c linux-step-1/kernel/sysctl.c
--- linux-2.6.11-rc2-bk4/kernel/sysctl.c	2005-01-26 18:24:39.000000000 +0100
+++ linux-step-1/kernel/sysctl.c	2005-01-26 19:03:44.000000000 +0100
@@ -122,6 +122,8 @@ extern int sysctl_hz_timer;
 extern int acct_parm[];
 #endif
 
+int randomize_va_space = 0;
+
 static int parse_table(int __user *, int, void __user *, size_t __user *, void __user *, size_t,
 		       ctl_table *, void **);
 static int proc_doutsstring(ctl_table *table, int write, struct file *filp,
@@ -633,6 +635,15 @@ static ctl_table kern_table[] = {
 		.proc_handler	= &proc_dointvec,
 	},
 #endif
+	{
+		.ctl_name	= KERN_RANDOMIZE,
+		.procname	= "randomize_va_space",
+		.data		= &randomize_va_space,
+		.maxlen		= sizeof(int),
+		.mode		= 0644,
+		.proc_handler	= &proc_dointvec,
+	},
+
 	{ .ctl_name = 0 }
 };
 

Re: Patch 1/6 introduce sysctl

[Andi Kleen]

Arjan van de Ven <arjan@infradead.org> writes:

> This first patch of the series introduces a sysctl (default off) that
> enables/disables the randomisation feature globally. Since randomisation may
> make it harder to debug really tricky situations (reproducability goes
> down), the sysadmin needs a way to disable it globally.

A global sysctl doesn't make much sense to me for this. If you
want to get some program running you don't want to impact your
system daemons. And a non root user couldn't enable it anyways,
which can be annoying if it is needed to get some binary working.

If anything I would make it a personality flag so that it can
be set per process.

-Andi

Re: Patch 1/6 introduce sysctl

[Arjan van de Ven]

On Thu, 2005-01-27 at 11:36 +0100, Andi Kleen wrote:
> Arjan van de Ven <arjan@infradead.org> writes:
> 
> > This first patch of the series introduces a sysctl (default off) that
> > enables/disables the randomisation feature globally. Since randomisation may
> > make it harder to debug really tricky situations (reproducability goes
> > down), the sysadmin needs a way to disable it globally.
> 
> A global sysctl doesn't make much sense to me for this. If you
> want to get some program running you don't want to impact your
> system daemons. And a non root user couldn't enable it anyways,
> which can be annoying if it is needed to get some binary working.
> 
> If anything I would make it a personality flag so that it can
> be set per process.

I actually wanted both; eg a global "whack it off" and a per process
flag for all the reasons you state. 
I have no objection to remove the global "whack it off" flag, however,
for testing this stuff in -mm it might be useful to have a simple "turn
it off" option.

Re: Patch 1/6 introduce sysctl

[Pavel Machek]

Hi!

> This first patch of the series introduces a sysctl (default off) that
> enables/disables the randomisation feature globally. Since randomisation may
> make it harder to debug really tricky situations (reproducability goes
> down), the sysadmin needs a way to disable it globally.

Well, for distribution vendors, seeing "these reports from users are
same error" will becoe harder, too, and sysctl can not help there :-(.

								Pavel
-- 
People were complaining that M$ turns users into beta-testers...
...jr ghea gurz vagb qrirybcref, naq gurl frrz gb yvxr vg gung jnl!

Re: Patch 1/6 introduce sysctl

[Ingo Molnar]

* Pavel Machek <pavel@ucw.cz> wrote:

> Hi!
> 
> > This first patch of the series introduces a sysctl (default off) that
> > enables/disables the randomisation feature globally. Since randomisation may
> > make it harder to debug really tricky situations (reproducability goes
> > down), the sysadmin needs a way to disable it globally.
> 
> Well, for distribution vendors, seeing "these reports from users are
> same error" will becoe harder, too, and sysctl can not help there :-(.

this is true to a limited degree, but it's only part of the picture. 
When we first introduced address-space randomisation in Fedora 1 (almost
2 years ago) we were worried about this effect too, very much in fact. 

What happened is that the _debugging infrastructure_ improved. Fedora
introduced debug-info packages, so that we dont get any raw dumps of
bugs anymore - what we get are nice symbolic backtraces which are easy
to match up against each other.

also, we already have this effect in the mainline kernel - on P4's the
stack is already randomized. Also, prelink (even the non-randomized
variant) already creates a per-machine VM layout of libraries.

so, i'm glad to report, it's a non-issue. Sometimes developers want to
disable randomisation during development (quick'n'easy hacks get quicker
and easier - e.g. if you watch an address within gdb), so having the
capability for unprivileged users to disable randomisation on the fly is
useful and Fedora certainly offers that, but from a support and
bug-reporting POV it's not a problem.

	Ingo

Re: Patch 1/6 introduce sysctl

[Dave Jones]

On Thu, Jan 27, 2005 at 08:11:20PM +0100, Ingo Molnar wrote:

 > so, i'm glad to report, it's a non-issue. Sometimes developers want to
 > disable randomisation during development (quick'n'easy hacks get quicker
 > and easier - e.g. if you watch an address within gdb), so having the
 > capability for unprivileged users to disable randomisation on the fly is
 > useful and Fedora certainly offers that, but from a support and
 > bug-reporting POV it's not a problem.

It's worth noting that some users have found the randomisation disable useful
for running things like xine/mplayer etc with win32 codecs that seem
to just segfault otherwise.  These things seem to be incredibly fragile
to address space layout changes, which is a good argument for trying to
avoid these wierdo formats where possible in favour of free codecs.

		Dave

Re: Patch 1/6 introduce sysctl

[Ingo Molnar]

* Dave Jones <davej@redhat.com> wrote:

> On Thu, Jan 27, 2005 at 08:11:20PM +0100, Ingo Molnar wrote:
> 
>  > so, i'm glad to report, it's a non-issue. Sometimes developers want to
>  > disable randomisation during development (quick'n'easy hacks get quicker
>  > and easier - e.g. if you watch an address within gdb), so having the
>  > capability for unprivileged users to disable randomisation on the fly is
>  > useful and Fedora certainly offers that, but from a support and
>  > bug-reporting POV it's not a problem.
> 
> It's worth noting that some users have found the randomisation disable
> useful for running things like xine/mplayer etc with win32 codecs that
> seem to just segfault otherwise.  These things seem to be incredibly
> fragile to address space layout changes, which is a good argument for
> trying to avoid these wierdo formats where possible in favour of free
> codecs.

yes, this was by far the biggest problem randomisation caused. Note that
while Fedora offers a personality-hack to disable randomisation on the
fly, which Wine could have made use of to have the fix automatically;
Alexandre didnt want to rely on it in Wine because that flag's semantics
(PER_LINUX32) were not upstream. (and i very much agree with Alexandre
on that call).

But once something like this is upstream i believe Wine can (and will)
have a robust legacy-binary-format loader that is not affected by
randomisation effects, with minimal changes.

	Ingo

Re: Patch 1/6 introduce sysctl

[Arjan van de Ven]

On Thu, 2005-01-27 at 14:46 -0500, Dave Jones wrote:
> On Thu, Jan 27, 2005 at 08:11:20PM +0100, Ingo Molnar wrote:
> 
>  > so, i'm glad to report, it's a non-issue. Sometimes developers want to
>  > disable randomisation during development (quick'n'easy hacks get quicker
>  > and easier - e.g. if you watch an address within gdb), so having the
>  > capability for unprivileged users to disable randomisation on the fly is
>  > useful and Fedora certainly offers that, but from a support and
>  > bug-reporting POV it's not a problem.
> 
> It's worth noting that some users have found the randomisation disable useful
> for running things like xine/mplayer etc with win32 codecs that seem
> to just segfault otherwise.  These things seem to be incredibly fragile
> to address space layout changes, which is a good argument for trying to
> avoid these wierdo formats where possible in favour of free codecs.

actually that's because windows has a different initial stack alignment
that wine compensates but I guess xine/mplayer don't.
with p4's you get that anyway (and glibc and ..)

Re: Patch 1/6 introduce sysctl

[Benoit Boissinot]

On Thu, 27 Jan 2005 10:12:01 +0000, Arjan van de Ven
<arjan@infradead.org> wrote:
> 
> This first patch of the series introduces a sysctl (default off) that
> enables/disables the randomisation feature globally. Since randomisation may
> make it harder to debug really tricky situations (reproducability goes
> down), the sysadmin needs a way to disable it globally.
> 
> Signed-off-by: Arjan van de Ven <arjan@infradead.org>
> 
> diff -purN linux-2.6.11-rc2-bk4/include/linux/kernel.h linux-step-1/include/linux/kernel.h
> --- linux-2.6.11-rc2-bk4/include/linux/kernel.h 2005-01-26 18:24:39.000000000 +0100
> +++ linux-step-1/include/linux/kernel.h 2005-01-26 19:04:58.016540168 +0100
> @@ -278,6 +278,9 @@ struct sysinfo {
>  extern void BUILD_BUG(void);
>  #define BUILD_BUG_ON(condition) do { if (condition) BUILD_BUG(); } while(0)
> 
> +
> +extern int randomize_va_space;
> +
>  /* Trap pasters of __FUNCTION__ at compile-time */
>  #if __GNUC__ > 2 || __GNUC_MINOR__ >= 95
>  #define __FUNCTION__ (__func__)
> [snip]
>
> diff -purN linux-2.6.11-rc2-bk4/kernel/sysctl.c linux-step-1/kernel/sysctl.c
> --- linux-2.6.11-rc2-bk4/kernel/sysctl.c        2005-01-26 18:24:39.000000000 +0100
> +++ linux-step-1/kernel/sysctl.c        2005-01-26 19:03:44.000000000 +0100
> @@ -122,6 +122,8 @@ extern int sysctl_hz_timer;
>  extern int acct_parm[];
>  #endif
> 
> +int randomize_va_space = 0;
> +
>  static int parse_table(int __user *, int, void __user *, size_t __user *, void __user *, size_t,
>                        ctl_table *, void **);
>  static int proc_doutsstring(ctl_table *table, int write, struct file *filp,
>
> [snip]

This breaks the compilation with allnoconfig (since CONFIG_SYSCTL is
not defined):

arch/i386/kernel/built-in.o(.text+0xf92): In function `arch_align_stack':
: undefined reference to `randomize_va_space'

maybe randomize_va_space should be defined as extern in sysctl.c and
put elsewhere.

regards,

Benoit

Re: Patch 2/6 introduce helper infrastructure

[Arjan van de Ven]

The patch below introduces get_random_int() and randomize_range(), two
helpers used in later patches in the series. get_random_int() shares the
tcp/ip random number stuff so the CONFIG_INET ifdef needs to move slightly,
and to reduce the damange due to that, secure_ip_id() needs to move inside
random.c


Signed-off-by: Arjan van de Ven <arjan@infradead.org>


diff -purN step1/drivers/char/random.c step2/drivers/char/random.c
--- step1/drivers/char/random.c	2005-01-26 18:24:36.000000000 +0100
+++ step2/drivers/char/random.c	2005-01-27 11:03:01.000000000 +0100
@@ -1965,7 +1965,6 @@ static void sysctl_init_random(struct en
  *
  ********************************************************************/
 
-#ifdef CONFIG_INET
 /*
  * TCP initial sequence number picking.  This uses the random number
  * generator to pick an initial secret value.  This value is hashed
@@ -2202,6 +2201,31 @@ __u32 secure_tcpv6_sequence_number(__u32
 EXPORT_SYMBOL(secure_tcpv6_sequence_number);
 #endif
 
+/*  The code below is shamelessly stolen from secure_tcp_sequence_number().
+ *  All blames to Andrey V. Savochkin <saw@msu.ru>.
+ */
+__u32 secure_ip_id(__u32 daddr)
+{
+	struct keydata *keyptr;
+	__u32 hash[4];
+
+	keyptr = get_keyptr();
+
+	/*
+	 *  Pick a unique starting offset for each IP destination.
+	 *  The dest ip address is placed in the starting vector,
+	 *  which is then hashed with random data.
+	 */
+	hash[0] = daddr;
+	hash[1] = keyptr->secret[9];
+	hash[2] = keyptr->secret[10];
+	hash[3] = keyptr->secret[11];
+
+	return halfMD4Transform(hash, keyptr->secret);
+}
+
+#ifdef CONFIG_INET
+
 __u32 secure_tcp_sequence_number(__u32 saddr, __u32 daddr,
 				 __u16 sport, __u16 dport)
 {
@@ -2242,28 +2266,7 @@ __u32 secure_tcp_sequence_number(__u32 s
 
 EXPORT_SYMBOL(secure_tcp_sequence_number);
 
-/*  The code below is shamelessly stolen from secure_tcp_sequence_number().
- *  All blames to Andrey V. Savochkin <saw@msu.ru>.
- */
-__u32 secure_ip_id(__u32 daddr)
-{
-	struct keydata *keyptr;
-	__u32 hash[4];
-
-	keyptr = get_keyptr();
-
-	/*
-	 *  Pick a unique starting offset for each IP destination.
-	 *  The dest ip address is placed in the starting vector,
-	 *  which is then hashed with random data.
-	 */
-	hash[0] = daddr;
-	hash[1] = keyptr->secret[9];
-	hash[2] = keyptr->secret[10];
-	hash[3] = keyptr->secret[11];
 
-	return halfMD4Transform(hash, keyptr->secret);
-}
 
 /* Generate secure starting point for ephemeral TCP port search */
 u32 secure_tcp_port_ephemeral(__u32 saddr, __u32 daddr, __u16 dport)
@@ -2383,3 +2386,41 @@ __u32 check_tcp_syn_cookie(__u32 cookie,
 }
 #endif
 #endif /* CONFIG_INET */
+
+
+/*
+ * Get a random word for internal kernel use only. Similar to urandom but with the goal
+ * of minimal entropy pool depletion. As a result, the random value is not cryptographically
+ * secure but for several uses the cost of depleting entropy is too high
+ */
+unsigned int get_random_int(void)
+{
+	static unsigned int val = 0;
+
+	val += current->pid + jiffies;
+
+	/*
+	 * Use IP's RNG. It suits our purpose perfectly: it re-keys itself
+	 * every second, from the entropy pool (and thus creates a limited
+	 * drain on it), and uses halfMD4Transform within the second. We
+	 * also mix it with jiffies and the PID:
+	 */
+	return secure_ip_id(val);
+}
+
+/* 
+ * randomize_range() returns a start address such that
+ *
+ *    [...... <range> .....]
+ *  start                  end
+ *
+ * a <range> with size "len" starting at the return value is inside in the
+ * area defined by [start, end], but is otherwise randomized.
+ */
+unsigned long randomize_range(unsigned long start, unsigned long end, unsigned long len)
+{
+	unsigned long range = end - len - start;
+	if (end <= start + len)
+		return 0;
+	return PAGE_ALIGN(get_random_int() % range + start);
+}
diff -purN step1/include/linux/random.h step2/include/linux/random.h
--- step1/include/linux/random.h	2005-01-26 18:24:39.000000000 +0100
+++ step2/include/linux/random.h	2005-01-27 10:52:56.000000000 +0100
@@ -70,6 +70,9 @@ extern __u32 secure_tcpv6_sequence_numbe
 extern struct file_operations random_fops, urandom_fops;
 #endif
 
+unsigned int get_random_int(void);
+unsigned long randomize_range(unsigned long start, unsigned long end, unsigned long len);
+
 #endif /* __KERNEL___ */
 
 #endif /* _LINUX_RANDOM_H */

Re: Patch 2/6 introduce helper infrastructure

[Andi Kleen]

Arjan van de Ven <arjan@infradead.org> writes:
> +unsigned int get_random_int(void)
> +{
> +	static unsigned int val = 0;
> +
> +	val += current->pid + jiffies;

Shouldn't there be some kind of locking for this? It's random,
but still random corruption sounds a bit too random.

Also you probably have a very hot cache line here, which
may hurt on the bigger machines.

I think it would be better to just get a global random number
for each mm as it is created and then run a fast PRNG with that
state. Maybe even make it per task to improve performance on
multithreaded programs. Or alternatively per cpu state with
different starting points.

-Andi

Re: Patch 2/6 introduce helper infrastructure

[Arjan van de Ven]

On Thu, Jan 27, 2005 at 11:41:33AM +0100, Andi Kleen wrote:
> Arjan van de Ven <arjan@infradead.org> writes:
> > +unsigned int get_random_int(void)
> > +{
> > +	static unsigned int val = 0;
> > +
> > +	val += current->pid + jiffies;
> 
> Shouldn't there be some kind of locking for this? It's random,
> but still random corruption sounds a bit too random.
> 
> Also you probably have a very hot cache line here, which
> may hurt on the bigger machines.


actually the static was ther from a previous revision where the ip rng was
compiled out at times so it needed some RNG characteristic. Patch below just
removes the static; it's good enough.


The patch below introduces get_random_int() and randomize_range(), two
helpers used in later patches in the series. get_random_int() shares the
tcp/ip random number stuff so the CONFIG_INET ifdef needs to move slightly,
and to reduce the damange due to that, secure_ip_id() needs to move inside
random.c



diff -purN step1/drivers/char/random.c step2/drivers/char/random.c
--- step1/drivers/char/random.c	2005-01-26 18:24:36.000000000 +0100
+++ step2/drivers/char/random.c	2005-01-27 11:03:01.000000000 +0100
@@ -1965,7 +1965,6 @@ static void sysctl_init_random(struct en
  *
  ********************************************************************/
 
-#ifdef CONFIG_INET
 /*
  * TCP initial sequence number picking.  This uses the random number
  * generator to pick an initial secret value.  This value is hashed
@@ -2202,6 +2201,31 @@ __u32 secure_tcpv6_sequence_number(__u32
 EXPORT_SYMBOL(secure_tcpv6_sequence_number);
 #endif
 
+/*  The code below is shamelessly stolen from secure_tcp_sequence_number().
+ *  All blames to Andrey V. Savochkin <saw@msu.ru>.
+ */
+__u32 secure_ip_id(__u32 daddr)
+{
+	struct keydata *keyptr;
+	__u32 hash[4];
+
+	keyptr = get_keyptr();
+
+	/*
+	 *  Pick a unique starting offset for each IP destination.
+	 *  The dest ip address is placed in the starting vector,
+	 *  which is then hashed with random data.
+	 */
+	hash[0] = daddr;
+	hash[1] = keyptr->secret[9];
+	hash[2] = keyptr->secret[10];
+	hash[3] = keyptr->secret[11];
+
+	return halfMD4Transform(hash, keyptr->secret);
+}
+
+#ifdef CONFIG_INET
+
 __u32 secure_tcp_sequence_number(__u32 saddr, __u32 daddr,
 				 __u16 sport, __u16 dport)
 {
@@ -2242,28 +2266,7 @@ __u32 secure_tcp_sequence_number(__u32 s
 
 EXPORT_SYMBOL(secure_tcp_sequence_number);
 
-/*  The code below is shamelessly stolen from secure_tcp_sequence_number().
- *  All blames to Andrey V. Savochkin <saw@msu.ru>.
- */
-__u32 secure_ip_id(__u32 daddr)
-{
-	struct keydata *keyptr;
-	__u32 hash[4];
-
-	keyptr = get_keyptr();
-
-	/*
-	 *  Pick a unique starting offset for each IP destination.
-	 *  The dest ip address is placed in the starting vector,
-	 *  which is then hashed with random data.
-	 */
-	hash[0] = daddr;
-	hash[1] = keyptr->secret[9];
-	hash[2] = keyptr->secret[10];
-	hash[3] = keyptr->secret[11];
 
-	return halfMD4Transform(hash, keyptr->secret);
-}
 
 /* Generate secure starting point for ephemeral TCP port search */
 u32 secure_tcp_port_ephemeral(__u32 saddr, __u32 daddr, __u16 dport)
@@ -2383,3 +2386,41 @@ __u32 check_tcp_syn_cookie(__u32 cookie,
 }
 #endif
 #endif /* CONFIG_INET */
+
+
+/*
+ * Get a random word for internal kernel use only. Similar to urandom but with the goal
+ * of minimal entropy pool depletion. As a result, the random value is not cryptographically
+ * secure but for several uses the cost of depleting entropy is too high
+ */
+unsigned int get_random_int(void)
+{
+	unsigned int val;
+
+	val= current->pid + jiffies;
+
+	/*
+	 * Use IP's RNG. It suits our purpose perfectly: it re-keys itself
+	 * every second, from the entropy pool (and thus creates a limited
+	 * drain on it), and uses halfMD4Transform within the second. We
+	 * also mix it with jiffies and the PID:
+	 */
+	return secure_ip_id(val);
+}
+
+/* 
+ * randomize_range() returns a start address such that
+ *
+ *    [...... <range> .....]
+ *  start                  end
+ *
+ * a <range> with size "len" starting at the return value is inside in the
+ * area defined by [start, end], but is otherwise randomized.
+ */
+unsigned long randomize_range(unsigned long start, unsigned long end, unsigned long len)
+{
+	unsigned long range = end - len - start;
+	if (end <= start + len)
+		return 0;
+	return PAGE_ALIGN(get_random_int() % range + start);
+}
diff -purN step1/include/linux/random.h step2/include/linux/random.h
--- step1/include/linux/random.h	2005-01-26 18:24:39.000000000 +0100
+++ step2/include/linux/random.h	2005-01-27 10:52:56.000000000 +0100
@@ -70,6 +70,9 @@ extern __u32 secure_tcpv6_sequence_numbe
 extern struct file_operations random_fops, urandom_fops;
 #endif
 
+unsigned int get_random_int(void);
+unsigned long randomize_range(unsigned long start, unsigned long end, unsigned long len);
+
 #endif /* __KERNEL___ */
 
 #endif /* _LINUX_RANDOM_H */

Re: Patch 2/6 introduce helper infrastructure

[Andi Kleen]

On Thu, Jan 27, 2005 at 11:58:29AM +0000, Arjan van de Ven wrote:
> On Thu, Jan 27, 2005 at 11:41:33AM +0100, Andi Kleen wrote:
> > Arjan van de Ven <arjan@infradead.org> writes:
> > > +unsigned int get_random_int(void)
> > > +{
> > > +	static unsigned int val = 0;
> > > +
> > > +	val += current->pid + jiffies;
> > 
> > Shouldn't there be some kind of locking for this? It's random,
> > but still random corruption sounds a bit too random.
> > 
> > Also you probably have a very hot cache line here, which
> > may hurt on the bigger machines.
> 
> 
> actually the static was ther from a previous revision where the ip rng was
> compiled out at times so it needed some RNG characteristic. Patch below just
> removes the static; it's good enough.

I guess the per MM prng would be still faster, but it's probably
not worth tweaking unless it shows up as a problem.

> +	if (end <= start + len)
> +		return 0;
> +	return PAGE_ALIGN(get_random_int() % range + start);

Division through variable is often quite slow, it would be good if you
avoided it somehow.

-Andi

Re: Patch 2/6 introduce helper infrastructure

[Arjan van de Ven]

On Thu, 2005-01-27 at 13:27 +0100, Andi Kleen wrote:
> I guess the per MM prng would be still faster, but it's probably
> not worth tweaking unless it shows up as a problem.
> 
> > +	if (end <= start + len)
> > +		return 0;
> > +	return PAGE_ALIGN(get_random_int() % range + start);
> 
> Division through variable is often quite slow, it would be good if you
> avoided it somehow.

it'll be used once per exec() so while you're right I'll not be a huge
problem; rewriting the implementation of this function ought to be
independent of the (later to be introduced) users, the problem is quite
well defined.

Re: Patch 2/6 introduce helper infrastructure

[Matt Mackall]

On Thu, Jan 27, 2005 at 10:12:28AM +0000, Arjan van de Ven wrote:
> 
> 
> The patch below introduces get_random_int() and randomize_range(), two
> helpers used in later patches in the series. get_random_int() shares the
> tcp/ip random number stuff so the CONFIG_INET ifdef needs to move slightly,
> and to reduce the damange due to that, secure_ip_id() needs to move inside
> random.c

Sorry I'm a bit behind on the list, but this is going to conflict with
the random.c changes in -mm, where all the network-specific bits were
moved off to net/.

I'm not against adding a generic fast PRNG here, but this way is
backwards. Let's instead make a new function get_prng_int() and
convert the network bits to use it.

-- 
Mathematics is the supreme nostalgia of our time.

Re: Patch 3/6 per process flag

[Arjan van de Ven]

Even thoguh there is a global flag to disable randomisation, it's useful to
have a per process flag too; the patch below introduces this per process
flag and automatically sets it for "new" binaries.

Eventually we will want to tie this to the legacy-va-space personality

Signed-off-by: Arjan van de Ven <arjan@infradead.org>

diff -purN linux-step-4a/fs/binfmt_elf.c linux-step-5/fs/binfmt_elf.c
--- linux-step-3/fs/binfmt_elf.c	2005-01-26 21:18:49.000000000 +0100
+++ linux-step-2/fs/binfmt_elf.c	2005-01-27 09:08:41.000000000 +0100
@@ -757,6 +759,9 @@ static int load_elf_binary(struct linux_
 	if (elf_read_implies_exec(loc->elf_ex, have_pt_gnu_stack))
 		current->personality |= READ_IMPLIES_EXEC;
 
+	if (executable_stack == EXSTACK_DISABLE_X && randomize_va_space) {
+		current->flags |= PF_RANDOMIZE;
+	}
 	arch_pick_mmap_layout(current->mm);
 
 	/* Do this so that we can load the interpreter, if need be.  We will
diff -purN linux-step-3/fs/exec.c linux-step-2/fs/exec.c
--- linux-step-3/fs/exec.c	2005-01-26 18:24:38.762322000 +0100
+++ linux-step-2/fs/exec.c	2005-01-26 21:15:33.860310848 +0100
@@ -877,6 +877,7 @@ int flush_old_exec(struct linux_binprm *
 	tcomm[i] = '\0';
 	set_task_comm(current, tcomm);
 
+	current->flags &= ~PF_RANDOMIZE;
 	flush_thread();
 
 	if (bprm->e_uid != current->euid || bprm->e_gid != current->egid || 
diff -purN linux-step-3/include/linux/sched.h linux-step-2/include/linux/sched.h
--- linux-step-3/include/linux/sched.h	2005-01-26 18:24:39.606194000 +0100
+++ linux-step-2/include/linux/sched.h	2005-01-26 21:13:28.692339272 +0100
@@ -736,6 +736,7 @@ do { if (atomic_dec_and_test(&(tsk)->usa
 #define PF_LESS_THROTTLE 0x00100000	/* Throttle me less: I clean memory */
 #define PF_SYNCWRITE	0x00200000	/* I am doing a sync write */
 #define PF_BORROWED_MM	0x00400000	/* I am a kthread doing use_mm */
+#define PF_RANDOMIZE	0x00800000	/* randomize virtual address space */
 
 #ifdef CONFIG_SMP
 extern int set_cpus_allowed(task_t *p, cpumask_t new_mask);

Re: Patch 4/6 randomize the stack pointer

[Arjan van de Ven]

The patch below replaces the existing 8Kb randomisation of the userspace
stack pointer (which is currently only done for Hyperthreaded P-IVs) with a 
more general randomisation over a 64Kb range.

Signed-off-by: Arjan van de Ven <arjan@infradead.org>

diff -purN linux-step-2/arch/i386/kernel/process.c linux-step-4/arch/i386/kernel/process.c
--- linux-step-2/arch/i386/kernel/process.c	2005-01-26 18:24:35.472822000 +0100
+++ linux-step-4/arch/i386/kernel/process.c	2005-01-26 21:22:00.465537920 +0100
@@ -36,6 +36,7 @@
 #include <linux/module.h>
 #include <linux/kallsyms.h>
 #include <linux/ptrace.h>
+#include <linux/random.h>
 
 #include <asm/uaccess.h>
 #include <asm/pgtable.h>
@@ -828,3 +829,9 @@ 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() % 4096) << 4);
+	return sp & ~0xf;
+}
diff -purN linux-step-2/arch/x86_64/kernel/process.c linux-step-4/arch/x86_64/kernel/process.c
--- linux-step-2/arch/x86_64/kernel/process.c	2005-01-26 18:24:49.000000000 +0100
+++ linux-step-4/arch/x86_64/kernel/process.c	2005-01-26 20:48:02.000000000 +0100
@@ -743,3 +743,10 @@ int dump_task_regs(struct task_struct *t
  
 	return 1;
 }
+
+unsigned long arch_align_stack(unsigned long sp)
+{
+	if (randomize_vs_space)
+		sp -= ((get_random_int() % 4096) << 4);
+	return sp & ~0xf;
+}
diff -purN linux-step-2/fs/binfmt_elf.c linux-step-4/fs/binfmt_elf.c
--- linux-step-2/fs/binfmt_elf.c	2005-01-26 21:14:51.464755952 +0100
+++ linux-step-4/fs/binfmt_elf.c	2005-01-26 21:18:49.017642424 +0100
@@ -165,20 +165,14 @@ create_elf_tables(struct linux_binprm *b
 	if (k_platform) {
 		size_t len = strlen(k_platform) + 1;
 
-#ifdef CONFIG_X86_HT
+#ifdef __HAVE_ARCH_ALIGN_STACK
 		/*
 		 * In some cases (e.g. Hyper-Threading), we want to avoid L1
 		 * evictions by the processes running on the same package. One
 		 * thing we can do is to shuffle the initial stack for them.
-		 *
-		 * The conditionals here are unneeded, but kept in to make the
-		 * code behaviour the same as pre change unless we have
-		 * hyperthreaded processors. This should be cleaned up
-		 * before 2.6
 		 */
 	 
-		if (smp_num_siblings > 1)
-			STACK_ALLOC(p, ((current->pid % 64) << 7));
+		p = arch_align_stack((unsigned long)p);
 #endif
 		u_platform = (elf_addr_t __user *)STACK_ALLOC(p, len);
 		if (__copy_to_user(u_platform, k_platform, len))
diff -purN linux-step-2/fs/exec.c linux-step-4/fs/exec.c
--- linux-step-2/fs/exec.c	2005-01-26 21:15:33.860310848 +0100
+++ linux-step-4/fs/exec.c	2005-01-26 21:25:22.678796832 +0100
@@ -400,7 +400,12 @@ int setup_arg_pages(struct linux_binprm 
 	while (i < MAX_ARG_PAGES)
 		bprm->page[i++] = NULL;
 #else
-	stack_base = stack_top - MAX_ARG_PAGES * PAGE_SIZE;
+#ifdef __HAVE_ARCH_ALIGN_STACK
+	stack_base = arch_align_stack(STACK_TOP - MAX_ARG_PAGES*PAGE_SIZE);
+	stack_base = PAGE_ALIGN(stack_base);
+#else
+	stack_base = STACK_TOP - MAX_ARG_PAGES * PAGE_SIZE;
+#endif
 	bprm->p += stack_base;
 	mm->arg_start = bprm->p;
 	arg_size = stack_top - (PAGE_MASK & (unsigned long) mm->arg_start);
diff -purN linux-step-2/include/asm-i386/system.h linux-step-4/include/asm-i386/system.h
--- linux-step-2/include/asm-i386/system.h	2005-01-26 18:24:39.226252000 +0100
+++ linux-step-4/include/asm-i386/system.h	2005-01-26 20:49:59.000000000 +0100
@@ -468,4 +468,7 @@ void enable_hlt(void);
 extern int es7000_plat;
 void cpu_idle_wait(void);
 
+#define __HAVE_ARCH_ALIGN_STACK
+extern unsigned long arch_align_stack(unsigned long sp);
+
 #endif
diff -purN linux-step-2/include/asm-x86_64/system.h linux-step-4/include/asm-x86_64/system.h
--- linux-step-2/include/asm-x86_64/system.h	2005-01-26 18:24:39.000000000 +0100
+++ linux-step-4/include/asm-x86_64/system.h	2005-01-26 20:50:14.000000000 +0100
@@ -338,4 +338,7 @@ void enable_hlt(void);
 #define HAVE_EAT_KEY
 void eat_key(void);
 
+#define __HAVE_ARCH_ALIGN_STACK
+extern unsigned long arch_align_stack(unsigned long sp);
+
 #endif

Re: Patch 4/6 randomize the stack pointer

[Christoph Hellwig]

> -#ifdef CONFIG_X86_HT
> +#ifdef __HAVE_ARCH_ALIGN_STACK
>  		/*
>  		 * In some cases (e.g. Hyper-Threading), we want to avoid L1
>  		 * evictions by the processes running on the same package. One
>  		 * thing we can do is to shuffle the initial stack for them.
> -		 *
> -		 * The conditionals here are unneeded, but kept in to make the
> -		 * code behaviour the same as pre change unless we have
> -		 * hyperthreaded processors. This should be cleaned up
> -		 * before 2.6
>  		 */
>  	 
> -		if (smp_num_siblings > 1)
> -			STACK_ALLOC(p, ((current->pid % 64) << 7));
> +		p = arch_align_stack((unsigned long)p);
>  #endif
>  		u_platform = (elf_addr_t __user *)STACK_ALLOC(p, len);
>  		if (__copy_to_user(u_platform, k_platform, len))
> diff -purN linux-step-2/fs/exec.c linux-step-4/fs/exec.c
> --- linux-step-2/fs/exec.c	2005-01-26 21:15:33.860310848 +0100
> +++ linux-step-4/fs/exec.c	2005-01-26 21:25:22.678796832 +0100
> @@ -400,7 +400,12 @@ int setup_arg_pages(struct linux_binprm 
>  	while (i < MAX_ARG_PAGES)
>  		bprm->page[i++] = NULL;
>  #else
> -	stack_base = stack_top - MAX_ARG_PAGES * PAGE_SIZE;
> +#ifdef __HAVE_ARCH_ALIGN_STACK
> +	stack_base = arch_align_stack(STACK_TOP - MAX_ARG_PAGES*PAGE_SIZE);
> +	stack_base = PAGE_ALIGN(stack_base);
> +#else
> +	stack_base = STACK_TOP - MAX_ARG_PAGES * PAGE_SIZE;
> +#endif

Please kill the ifdefs and provide a dummy arch_align_stack() for
every architecture.

Re: Patch 4/6 randomize the stack pointer

[John Richard Moser]

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



Arjan van de Ven wrote:
> 
> The patch below replaces the existing 8Kb randomisation of the userspace
> stack pointer (which is currently only done for Hyperthreaded P-IVs) with a 
> more general randomisation over a 64Kb range.
> 

64k of stack randomization is trivial to evade.  Know the alignment, and
stick branch instructions (or a stream of no-ops if they align)
periodically so that....

[   ]|STACK---STACK---NONONOSHELLCODE
STACK---STACK---NONONOSHELLCODE
- ----------------------^
|
- -- You jump here in any case.

Now, in PaX, there's a randomization over something like a 256M range
for the stack IIRC.  Who does a 256M stack overflow?  It's several gigs
on 64 bit archs I think.  I think it's 16 bits with 4k (12 bit) pages,
so.... 28 bits... 268435456.... 256M, yes.  I'm pretty sure this is 24 +
12 on amd64 for example, so 64 gigs.

If your stack base is within 256M of ESP, you're safe.  It's also fairly
implausible--definitely non-trivial--to do a 256M stack buffer overflow.
 Programmatically it's no different; but in real life, that's 256M that
has to be in a corrupted jpeg, mp3 file, or network transmission.
Somebody's gonna notice.  64 gig doesn't happen.

Your patch 5/6 for mmap rand is also small.  1M is trivial, though I'd
imagine mmap() rand would pose a bit more confusion in some cases at
least, even for small ranges.

Still, this is a joke, like OpenBSD's stackgap.

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

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.0 (GNU/Linux)
Comment: Using GnuPG with Thunderbird - http://enigmail.mozdev.org

iD8DBQFB+ScghDd4aOud5P8RAk3zAJ9u3eav0l/Uhd3tQJ7uhDch+bepmACfeuYT
bQH8NCKkDXpmOPsXjVZ9cw4=
=e6OC
-----END PGP SIGNATURE-----

Re: Patch 4/6 randomize the stack pointer

[Arjan van de Ven]

On Thu, 2005-01-27 at 12:38 -0500, John Richard Moser wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
> 
> 
> 
> Arjan van de Ven wrote:
> > 
> > The patch below replaces the existing 8Kb randomisation of the userspace
> > stack pointer (which is currently only done for Hyperthreaded P-IVs) with a 
> > more general randomisation over a 64Kb range.
> > 
> 
> 64k of stack randomization is trivial to evade. 

I think you're focussing on the 64k number WAY too much. Yes it's too
small. But it's an initial number to show the infrastructure and get it
tested. Yes it should and will be increased later on in the patch
series.

Same for the other heap randomisation.

This thing is about getting the infrastructure in place and used. The
actual numbers are mere finetuning that can be done near the end.

Re: Patch 4/6 randomize the stack pointer

[John Richard Moser]

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

What the hell?

So instead of bringing something in that works, you bring something in
that does significantly less, and gives no savings on overhead or patch
complexity why?  So you can later come out and say "We're so great now
we've increased the randomization by tweaking one variable aren't we
cool!!!"?

Red Hat is all smoke and mirrors anyway when it comes to security, just
like Microsoft.  This just reaffirms that.

Arjan van de Ven wrote:
> On Thu, 2005-01-27 at 12:38 -0500, John Richard Moser wrote:
> 
>>-----BEGIN PGP SIGNED MESSAGE-----
>>Hash: SHA1
>>
>>
>>
>>Arjan van de Ven wrote:
>>
>>>The patch below replaces the existing 8Kb randomisation of the userspace
>>>stack pointer (which is currently only done for Hyperthreaded P-IVs) with a 
>>>more general randomisation over a 64Kb range.
>>>
>>
>>64k of stack randomization is trivial to evade. 
> 
> 
> I think you're focussing on the 64k number WAY too much. Yes it's too
> small. But it's an initial number to show the infrastructure and get it
> tested. Yes it should and will be increased later on in the patch
> series.
> 
> Same for the other heap randomisation.
> 
> This thing is about getting the infrastructure in place and used. The
> actual numbers are mere finetuning that can be done near the end.
> 
> 
> 

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

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.0 (GNU/Linux)
Comment: Using GnuPG with Thunderbird - http://enigmail.mozdev.org

iD8DBQFB+S0qhDd4aOud5P8RAquRAJ9FoWdhW6bpurTA6jObM6XEixTPFQCfbLvi
14Vp5H3Y//5kylroWGQRKek=
=o0Ra
-----END PGP SIGNATURE-----

Re: Patch 4/6 randomize the stack pointer

[Arjan van de Ven]

On Thu, 2005-01-27 at 13:04 -0500, John Richard Moser wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
> 
> What the hell?
> 
> So instead of bringing something in that works, you bring something in
> that does significantly less, and gives no savings on overhead or patch
> complexity why?  So you can later come out and say "We're so great now
> we've increased the randomization by tweaking one variable aren't we
> cool!!!"?

no it is called getting features in via a long incremental and
debuggable patch series.
Apparently you still don't understand that despite the long flamewar in
that other thread. I can't think of any more I can do to explain to you
why doing things in incremental steps is good on top of that.

> 
> Red Hat is all smoke and mirrors anyway when it comes to security, just
> like Microsoft.  This just reaffirms that.

I think you've been talking too much to another so called security
expert that has been spouting similar words on full-disclosure recently.

And I have to wonder.. where does Red Hat come in here?

Re: Patch 4/6 randomize the stack pointer

[Christoph Hellwig]

John,

coult you please piss off and troll elsewhere?

thanks

Re: Patch 4/6 randomize the stack pointer

[Linus Torvalds]

On Thu, 27 Jan 2005, John Richard Moser wrote:
> 
> What the hell?

John. Stop frothing at the mouth already!

Your suggestion of 256MB of randomization for the stack SIMPLY IS NOT 
ACCEPTABLE for a lot of uses. People on 32-bit archtiectures have issues 
with usable virtual memory areas etc.

> Red Hat is all smoke and mirrors anyway when it comes to security, just
> like Microsoft.  This just reaffirms that.

No. This just re-affirms that you are an inflexible person who cannot see 
the big picture. You concentrate on your issues to the point where 
everybody elses issues don't matter to you at all. That's a bad thing, in 
case you haven't realized.

Intelligent people are able to work constructively in a world with many 
different (and often contradictory) requirements. 

A person who cannot see outside his own sphere of interest can be very 
driven, and can be very useful - in the "please keep uncle Fred tinkering 
in the basement, but don't show him to any guests" kind of way. 

I have a clue for you: until PaX people can work with the rest of the
world, PaX is _never_ going to matter in the real world. Rigidity is a
total failure at all levels. 

Real engineering is about doing a good job balancing different issues.

Please remove me from the Cc when you start going off the deep end, btw.

		Linus

Re: Patch 4/6 randomize the stack pointer

[Linus Torvalds]

On Thu, 27 Jan 2005, Linus Torvalds wrote:
> 
> Real engineering is about doing a good job balancing different issues.

Btw, this is true of real security too. 

Being too strict "because it's the secure way" just means that people will 
disable you altogether, or start doing things that they know is wrong, 
because the right way of doing this may be secure, but they are also very 
inconvenient.

Thus a security person who doesn't take other aspects into account is 
actually HURTING security by insisting on things that may not be practical 
for a general vendor.

I've seen companies that had very strict firewalls in place, and didn't 
allow people to upload any internal data except by going through approved 
sites and having the data approved fist too. Secure? No. I was told people 
just connected modems to their local machines in their offices instead: 
the security measures didn't work for them, so they had to effectively 
disable them entirely. Everybody knew what was going on, but the security 
people were pig-headed idiots.

It's a classic mistake of doing totally the wrong thing, and I bet the
pig-headed idiots felt very good about themselves: they had the perfect
excuse for doing something stupid. Namely "we only implement the _best_
security we can do, and we refuse to do anything inferior". It's also a 
classic example of perfect being the enemy of good.

So John - next time you flame somebody, ask yourself whether maybe they 
had other issues. Maybe a vendor might care about not breaking existing 
programs, for example? Maybe a vendor knows that their users don't just 
use the programs _they_ provide (and test), but also use their own 
programs or programs that they got from the outside, and the vendor cannot 
test. Maybe such a vendor understands that you have to ease into things, 
and you can't just say "this is how it has to be done from now on".

			Linus

Re: Patch 4/6 randomize the stack pointer

[John Richard Moser]

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



Linus Torvalds wrote:
> 
> On Thu, 27 Jan 2005, Linus Torvalds wrote:
> 
>>Real engineering is about doing a good job balancing different issues.
> 
> 

[...]

> test. Maybe such a vendor understands that you have to ease into things, 
> and you can't just say "this is how it has to be done from now on".
> 

My idea of "Easing into things" is dropping the full model in the guy's
face and saying "Here, this is what we want to do.  It's there, you
don't have to use it, but you should be mindful because it's better and
in the future people will want it."  Then people will wait to turn it on
until everything is written to work with it--and every developer will
see it and know that that is there and that certain things need to be done.

You don't have to beat them with a crowbar until they listen, but you
have to show them what they're supposed to do.

> 			Linus
> 

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

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.0 (GNU/Linux)
Comment: Using GnuPG with Thunderbird - http://enigmail.mozdev.org

iD8DBQFB+TklhDd4aOud5P8RArG1AJ48Sno5o0MywWKcwFIF2n8GapOLrACffZDG
KzNjlsb8m2DWVaPEt+yfQ+k=
=BBA9
-----END PGP SIGNATURE-----

Re: Patch 4/6 randomize the stack pointer

[John Richard Moser]

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



Linus Torvalds wrote:
> 
> On Thu, 27 Jan 2005, John Richard Moser wrote:
> 
>>What the hell?
> 
> 
> John. Stop frothing at the mouth already!
> 

I'm coarse, I'm not angry.

> Your suggestion of 256MB of randomization for the stack SIMPLY IS NOT 
> ACCEPTABLE for a lot of uses. People on 32-bit archtiectures have issues 
> with usable virtual memory areas etc.
> 
> 

It never bothered me on my Barton core or Thoroughbred, or on the Duron,
or the Thoroughbred downstairs.  Then again, I cut a gig and a half out
on top of that too with SEGMEXEC, so I'm probably answering "most people
are afraid of firecrackers" with "I stood through an atomic explosion
and it didn't bother me."

If it's simply not acceptable to do more than a few megs of
randomization, then randomization is simply not acceptable.  Brute
forcing respawning/forking daemons is possible, and gets faster as your
entropy decreases.

I should probably test this, but in theory it'd also be possible to just
spew in a bunch of no-ops or aligned relative jumps and make a 64k or so
wide buffer that lets you jump to the same address regardless of
randomization and just wind up executing an extra N=rand(0,64k/ALIGN)
set of instructions before your actual shellcode.  It becomes
infeasible, then impossible, as the randomization gap gets bigger; if
your stack is 10 megs, you can't inject 256M of no-ops to get around a
random stack alignment.

>>Red Hat is all smoke and mirrors anyway when it comes to security, just
>>like Microsoft.  This just reaffirms that.
> 
> 
> No. This just re-affirms that you are an inflexible person who cannot see 
> the big picture. You concentrate on your issues to the point where 
> everybody elses issues don't matter to you at all. That's a bad thing, in 
> case you haven't realized.
> 
> Intelligent people are able to work constructively in a world with many 
> different (and often contradictory) requirements. 
> 

Of course.  I understand this, but I've come into the opinion that since
certain things are generally useful, they should be generally deployed.
 If they become a problem, the option to disable them becomes very
useful.  Even Exec Shield has PT_GNU_STACK AND a sysctl setting or 3 IIRC.

> A person who cannot see outside his own sphere of interest can be very 
> driven, and can be very useful - in the "please keep uncle Fred tinkering 
> in the basement, but don't show him to any guests" kind of way. 
> 

I'm actually very broad-minded; my opinions do change, when I see
something that changes my opinions.  Normally, though, my opinions are
developed from an analysis of facts; so you have to change the facts
(i.e. make one thing better and overtake the quality of the other) to
change my opinions.

I've been wrong before, on rare occasions.  Rare, but not impossible.
When it's displayed to me in a way that I actually understand that
certain facts I'm relying on are wrong, then I'm prone to re-evaluate my
decisions.

In the end, I've figured out that "not everybody likes pepsi," but also
that "diet soda is flavored with a dangerous neurotoxin and is bad for
EVERYBODY."  Until you pick another flavoring, I'm not going to have
good things to say about your product.  I do, however, know the
difference between "It's toxic to everyone" and "some people are alergic
to peanuts."

Not that that makes any connection to any existing system similar or
dissimilar to ES/PaX/W^X/etc (it intentionally does not).

> I have a clue for you: until PaX people can work with the rest of the
> world, PaX is _never_ going to matter in the real world. Rigidity is a
> total failure at all levels. 
> 

I'm not trying to get PaX in mainline, I'm just focused on the basic
concepts.

> Real engineering is about doing a good job balancing different issues.
> 
> Please remove me from the Cc when you start going off the deep end, btw.
> 

Sorry Linus, I normally don't read the CC list.  I'll be mindful in the
future of that.

This will likely be the last CC you get from me.

> 		Linus
> 

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

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.0 (GNU/Linux)
Comment: Using GnuPG with Thunderbird - http://enigmail.mozdev.org

iD8DBQFB+Te/hDd4aOud5P8RAmMdAJ0cRImvV0YGkBPMpaOAaTCyQkCWXACaAj1d
JRfUcY+9UPTe3ZVn517MUbU=
=WbU8
-----END PGP SIGNATURE-----

Re: Patch 4/6 randomize the stack pointer

[Linus Torvalds]

On Thu, 27 Jan 2005, John Richard Moser wrote:
> 
> > Your suggestion of 256MB of randomization for the stack SIMPLY IS NOT 
> > ACCEPTABLE for a lot of uses. People on 32-bit archtiectures have issues 
> > with usable virtual memory areas etc.
> 
> It never bothered me on my Barton core or Thoroughbred, or on the Duron,
> or the Thoroughbred downstairs.

Me, me, me, me! "I don't care about anybody else, if it works for me it 
must work for everybody else too".

See a possible logical fallacy there somewhere?

The fact is, different people have different needs. YOU only need to care
about yourself. That's not true for a vendor. A single case that doesn't
work ends up either (a) being ignored or (b) costing them money. See the 
problem? They can't win. Except by taking small steps, where the breakage 
is hopefully small too - and more importantly, because it's spread out 
over time, you hopefully know what broke it.

And when I say RH, I mean "me". That's the reason I personally hate
merging "D-day" things where a lot of things change. I much prefer merging
individual changes in small pieces. When things go wrong - and they will -
you can look at the individual pieces and say "ok, it's definitely not
that one" or "Hmm.. unlikely, but let's ask the reporter to check that
thing anyway" or "ok, that looks suspicious, let's start from there".

So for example, 3GB of virtual space is enough for most things. In fact, 
just 1GB is plenty for 99% of all things. But some programs will break, 
and they can break in surprising ways. Like "my email indexing stopped 
working" - because my combined mailboxes are currently 2.8GB, and it 
slurps them all in in one go to speed things up.

(That wasn't a made-up-example, btw. I had to write this stupid email
searcher for the SCO subpoena, and the fastest way was literally to index
everything in memory. Thank gods for 64-bit address spaces, because I
ended up avoiding having to be incredibly careful by just doing it on
another machine instead).

			Linus

Re: Patch 4/6 randomize the stack pointer

[Arjan van de Ven]

> The fact is, different people have different needs. YOU only need to care
> about yourself. That's not true for a vendor. A single case that doesn't
> work ends up either (a) being ignored or (b) costing them money. See the 
> problem? They can't win. Except by taking small steps, where the breakage 
> is hopefully small too - and more importantly, because it's spread out 
> over time, you hopefully know what broke it.
> 
> And when I say RH, I mean "me". That's the reason I personally hate
> merging "D-day" things where a lot of things change. I much prefer merging
> individual changes in small pieces. When things go wrong - and they will -
> you can look at the individual pieces and say "ok, it's definitely not
> that one" or "Hmm.. unlikely, but let's ask the reporter to check that
> thing anyway" or "ok, that looks suspicious, let's start from there".

this is exactly why the patch series I sent started with 64Kb. In fedora
we use 2Mb actually, and I know of some cornercases where that gives
issues (and the solution is a bit tricky). 64Kb is a nice safe start,
and it means the implementation can be quite simple. Later on, once this
patch has been proven solid and not to break stuff, adding a patch to
bring it up to 2Mb or so (I don't think more makes much sense, but I'm
open to debates about the ideal size for this, it's a tunable) that
needs to deal with stack rlimits < 2Mb and such can be done as a
separate step. Which then will in itself be quite simple again.

Re: Patch 4/6 randomize the stack pointer

[Linus Torvalds]

Btw, since you're clearly at the keyboard now: I do agree with Christoph
that it would be a lot cleaner to just say that all architectures have to
have a arch_align_stack() define, instead of having a
__HAVE_ARCH_ALIGN_STACK define.

After all, a trivial implementation would apparently just be

	#define arch_align_stack(x) (x)

which is not too much of a bother to maintain for an architecture that 
doesn't want to do this ;)

		Linus

Re: Patch 4/6 randomize the stack pointer

[Arjan van de Ven]

On Thu, 2005-01-27 at 11:59 -0800, Linus Torvalds wrote:
> 
> Btw, since you're clearly at the keyboard now: I do agree with Christoph
> that it would be a lot cleaner to just say that all architectures have to
> have a arch_align_stack() define, instead of having a
> __HAVE_ARCH_ALIGN_STACK define.
> 
> After all, a trivial implementation would apparently just be
> 
> 	#define arch_align_stack(x) (x)
> 
> which is not too much of a bother to maintain for an architecture that 
> doesn't want to do this ;)

yes I will make this change and post it a bit later
(I want to at least test compile it for a few)

Re: Patch 4/6 randomize the stack pointer

[John Richard Moser]

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



Linus Torvalds wrote:
> 
> On Thu, 27 Jan 2005, John Richard Moser wrote:
> 
>>>Your suggestion of 256MB of randomization for the stack SIMPLY IS NOT 
>>>ACCEPTABLE for a lot of uses. People on 32-bit archtiectures have issues 
>>>with usable virtual memory areas etc.
>>
>>It never bothered me on my Barton core or Thoroughbred, or on the Duron,
>>or the Thoroughbred downstairs.
> 
> 
> Me, me, me, me! "I don't care about anybody else, if it works for me it 
> must work for everybody else too".
> 

"Me" happens to be "Me sitting at a desk top doing word processing, IRC,
some Quake3 and Doom, listening to music, playing with Gimp, watching
videos, and running firefox."  I'm assuming "me" == "99% of all desktop
users," and that we also can't predict what all specialized machines need.

> See a possible logical fallacy there somewhere?

I see you're trying to lead me into saying we should be more focused on
supplying exactly what works for 100% of everybody, which we can't do.

> 
> The fact is, different people have different needs. YOU only need to care
> about yourself. That's not true for a vendor. A single case that doesn't
> work ends up either (a) being ignored or (b) costing them money. See the 
> problem? They can't win. Except by taking small steps, where the breakage 
> is hopefully small too - and more importantly, because it's spread out 
> over time, you hopefully know what broke it.

Something I wrote once

http://en.wikipedia.org/wiki/PaX

- --CLIP--
A DoS attack (or its equivalent) is generally an annoyance, and may in
some situations cause loss of time or resources (e.g. lost sales for a
business whose website is affected): however, no data should be
compromised when PaX intervenes, as no information will be improperly
copied elsewhere. Nevertheless, the equivalent of a DoS attack is in
some environments unacceptable; some businesses have level of service
contracts or other conditions which make successful intruder entry a
less costly problem than loss of or reduction in service. The PaX
approach is thus not well suited to all circumstances; however, in many
cases, it is an acceptable method of protecting confidential information
by preventing successful security breaches.
- --CLIP--

This doesn't just apply to PaX or Gr or whatever you want to claim I'm
trying to get into the kernel right now; it applies to everything.  In
some cases anything can be bad.  The idea is to realize that these are
*specialized* cases, and make a design decision:  A) allow a quick way
to disable the stuff (finegrained runtime with executable flags, or
disable in kernel); B) let the 1/100000000000000 people who this bothers
write a patch to change it themselves (RTLinux for example).

> 
> And when I say RH, I mean "me". That's the reason I personally hate
> merging "D-day" things where a lot of things change. I much prefer merging
> individual changes in small pieces. When things go wrong - and they will -
> you can look at the individual pieces and say "ok, it's definitely not
> that one" or "Hmm.. unlikely, but let's ask the reporter to check that
> thing anyway" or "ok, that looks suspicious, let's start from there".
> 
> So for example, 3GB of virtual space is enough for most things. In fact, 
> just 1GB is plenty for 99% of all things. But some programs will break, 
> and they can break in surprising ways. Like "my email indexing stopped 
> working" - because my combined mailboxes are currently 2.8GB, and it 
> slurps them all in in one go to speed things up.
> 

This is true.  I however have something like 300M of e-mail and I'm
subscribed to something like 15 or 20 mailing lists for about a year
now.  You of course have a work-around:  Don't try to load 800 gigs of
e-mail into memory all at once.  If you need to *quickly* parse this,
this may not be an acceptable work-around (though reading ahead and
dumping after processing, i.e. buffering, may be a good middle-ground).

Like I said, it's not something you'll hit every day on every machine,
and it's something that can be quickly worked around.  In the worst
case, disable all enhancements on the binary (using chpax or execstack
or whatever for whatever ASLR/NX system and God knows what else you're
using) for that binary or the system, depending on how fine-grained you
can control it.

I sympathise, really, but you're that one in ten-jillion.  :)

> (That wasn't a made-up-example, btw. I had to write this stupid email
> searcher for the SCO subpoena, and the fastest way was literally to index
> everything in memory. Thank gods for 64-bit address spaces, because I
> ended up avoiding having to be incredibly careful by just doing it on
> another machine instead).
> 

The fastest way is ALWAYS in memory :)  (unless you have $12000 SATA
drives with 2G of on-board cache and 500 track read-ahead)

> 			Linus
> 

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

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.0 (GNU/Linux)
Comment: Using GnuPG with Thunderbird - http://enigmail.mozdev.org

iD8DBQFB+Uo5hDd4aOud5P8RAr06AJsHU/vklnUxii8o7QZA78EFXy5lyACeJYIE
0M9rggfLgNHZMJGej8oLrbE=
=HN6I
-----END PGP SIGNATURE-----

Re: Patch 4/6 randomize the stack pointer

[linux-os]

Gentlemen,

Isn't the return address on the stack an offset in the
code (.text) segment?

How would a random stack-pointer value help? I think you would
need to start a program at a random offset, not the stack!
No stack-smasher that worked would care about the value of
the stack-pointer.

Cheers,
Dick Johnson
Penguin : Linux version 2.6.10 on an i686 machine (5537.79 BogoMips).
  Notice : All mail here is now cached for review by Dictator Bush.
                  98.36% of all statistics are fiction.

Re: Patch 4/6 randomize the stack pointer

[Julien TINNES]

> Gentlemen,
> 
> Isn't the return address on the stack an offset in the
> code (.text) segment?
> 
> How would a random stack-pointer value help? I think you would
> need to start a program at a random offset, not the stack!
> No stack-smasher that worked would care about the value of
> the stack-pointer.

While exploiting a stacks buffer overflow you can do at least two things:
* Changing the execution flow by overwriting return address or saved EBP.
* Injecting new executable code in the stack.

"Standard" stack smashing is doing both. The purpose of stack 
randomization is to make it harder to jump to code injected into the 
stack. If enough bits are randomized it's unlikely that an exploit will 
find the correct address at the first try. Now all you need is to make 
sure the vulnerable program won't be relaunched after a given number of 
crashes (or the chances that the exploit find the correct address will 
raise).

Of course you could inject code in other places or use existing code in 
address space (libc or running program) but this is at least a first 
layer of protection and adding layers is exactly what security is about.

-- 
Julien TINNES - & france telecom - R&D Division/MAPS/NSS
Research Engineer - Internet/Intranet Security
GPG: C050 EF1A 2919 FD87 57C4 DEDD E778 A9F0 14B9 C7D6

Re: Patch 4/6 randomize the stack pointer

[Arjan van de Ven]

On Thu, 2005-01-27 at 14:19 -0500, linux-os wrote:
> Gentlemen,
> 
> Isn't the return address on the stack an offset in the
> code (.text) segment?
> 
> How would a random stack-pointer value help? I think you would
> need to start a program at a random offset, not the stack!
> No stack-smasher that worked would care about the value of
> the stack-pointer.

the simple stack exploit works by overflowing a buffer ON THE STACK with
a "dirty payload and then also overwriting the return address to point
back into that buffer.

(all the security guys on this list will now cringe about this over
simplification; yes reality is more complex but lets keep the
explenation simple for Richard) 

pointing back into that buffer needs the address of that buffer. That
buffer is on the stack, which is now randomized.

Re: Patch 4/6 randomize the stack pointer

[John Richard Moser]

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

In other words, no :)

Here's self-exploiting code to discover its own return address offset
and exploit itself.  It'll lend some insight into how this stuff works.

Just a toy.

Arjan van de Ven wrote:
> On Thu, 2005-01-27 at 14:19 -0500, linux-os wrote:
> 
>>Gentlemen,
>>
>>Isn't the return address on the stack an offset in the
>>code (.text) segment?
>>
>>How would a random stack-pointer value help? I think you would
>>need to start a program at a random offset, not the stack!
>>No stack-smasher that worked would care about the value of
>>the stack-pointer.
> 
> 
> the simple stack exploit works by overflowing a buffer ON THE STACK with
> a "dirty payload and then also overwriting the return address to point
> back into that buffer.
> 
> (all the security guys on this list will now cringe about this over
> simplification; yes reality is more complex but lets keep the
> explenation simple for Richard) 
> 
> pointing back into that buffer needs the address of that buffer. That
> buffer is on the stack, which is now randomized.
> 
> 
> 

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


[-- Attachment #1.2: exploit.c --]
[-- Type: text/plain, Size: 1027 bytes --]

#include <string.h>
#include <stdio.h>
#include <stdlib.h>

int payload();
int exploit(char *d);


int main() {
	int distance;
	char a[512] = {0};
	distance = exploit(NULL);
	memset(a, 0xFF, distance);
	/*Get our payload address*/
	*(void**)(a + distance) = &payload;
	*(void**)(a + distance + sizeof(void*)) = 0; /*cap*/
	/*exploit the payload*/
	exploit(a);
	/*we never reach this*/
	return 255;
}

/*
 * exploit()
 * This overflows its own buffers and causes the return to jump to payload()
 */
int exploit(char *d) {
	char a[400] = {0};
	void *i;
	int distance = 0;
	char payld[sizeof(void*) + 1];
	void *myret;
	void *z;

	if (!d) {
		myret = __builtin_return_address(0);
		/*find the distance between a and myret*/
		for (i = (void*)a; *(void**)i != myret; i++) {
			distance++;
		}
		return distance;
	}
	/*We're passed a d buffer, so strcpy it unsafely*/
	strcpy(a,d);
	/*Return to payload()*/
	return 1;

}

int payload() {
	printf("Payload executed successfully!\n");
	/*0:  Unsafe; successful exploit*/
	_exit(0);
}

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

Re: Patch 4/6 randomize the stack pointer

[jnf]

>
> Here's self-exploiting code to discover its own return address offset
> and exploit itself.  It'll lend some insight into how this stuff works.
>
> Just a toy.
>

While I understand the point here, doesn't it become a moot point if:
a) the stack is reinitialized randomly on each execution
and
b) you have to execute that code from within the address space in order to
get the address of itself, therefore if you could already execute code,
then you don't really need the address and if you did wouldnt it be much
easier to do a (ia32) movl %esp pushl %esp ?

The point is to stop the code execution in the first place by randomizing
the addresses and making it hard to guess the offset, there are a ton of
ways to write code that can find the stack pointer or find itself, however
if you cannot execute that code then it becomes a moot point.

Of course I am not refering to causing loops and such in .text code to
brute force addresses.

cheers,

jnf

Re: Patch 4/6 randomize the stack pointer

[Paulo Marques]

John Richard Moser wrote:
> In other words, no :)
> 
> Here's self-exploiting code to discover its own return address offset
> and exploit itself.  It'll lend some insight into how this stuff works.

I really shouldn't feed the trolls, but this must be the most silly 
piece of code I saw on this mailing list in a very long time (and there 
have been some good examples over time).

The stack randomization doesn't prevent some sort of attacks (like 
return into libc, etc.) and given a small randomization it might be 
possible to write an exploit with a long sequence of NOP's and a return 
address somewhere in there (the attacker wouldn't know exactly where, 
but it wouldn't matter anyway). If we are able to write 'N' NOP's then 
we get a 'N'/64k chance that the exploit works.

Your code doesn't show any of this kinds of attacks. It just shows that 
if you're able to run code then.... you're able to run code?

What are you going to show next? That you can steal your own car? Are 
you going to blame the car manufacturer's for that?

As it was already pointed out this is a step into implementing a larger 
randomization, so that things don't break all at once. Even a large 
stack randomization is just another layer of protection, as there are 
still attacks that it doesn't prevent.... Duh.

>[...] 
> 		/*find the distance between a and myret*/
> 		for (i = (void*)a; *(void**)i != myret; i++) {
> 			distance++;
> 		}

And this must be "la piece de resistance". Some very obfuscated (and 
inefficient) way to do a simple unsigned subtraction...

-- 
Paulo Marques - www.grupopie.com

"A journey of a thousand miles begins with a single step."
Lao-tzu, The Way of Lao-tzu

Re: Patch 4/6 randomize the stack pointer

[John Richard Moser]

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



Paulo Marques wrote:
> John Richard Moser wrote:
> 
>> In other words, no :)
>>
>> Here's self-exploiting code to discover its own return address offset
>> and exploit itself.  It'll lend some insight into how this stuff works.
> 
> 
> I really shouldn't feed the trolls, but this must be the most silly
> piece of code I saw on this mailing list in a very long time (and there
> have been some good examples over time).
> 
> The stack randomization doesn't prevent some sort of attacks (like
> return into libc, etc.) and given a small randomization it might be
> possible to write an exploit with a long sequence of NOP's and a return
> address somewhere in there (the attacker wouldn't know exactly where,
> but it wouldn't matter anyway). If we are able to write 'N' NOP's then
> we get a 'N'/64k chance that the exploit works.

And the stack is a few megs, so you can write 64k of NOPs.  ;)

> 
> Your code doesn't show any of this kinds of attacks. It just shows that
> if you're able to run code then.... you're able to run code?
> 

The guy wanted to know how buffer overflows worked, so I showed him a
self-exploiting buffer overflow.  He didn't come in saying "I've got 500
years of experience writing buffer overflows, how would this stop it?"

It at least shows a buffer of length X overflowing into the return
pointer and changing it to address A of another function.  That's all I
wanted to do.

Interestingly enough, I used this code in real life for a test for the
IBM Stack Smash Protector.  It made a neat regression test.  The code
overflows into the return pointer and sets it to payload() 100% of the
time, even in the presence of NX protection and full ASLR (PaX' 256M or
(amd64) 64GiB, this 64k, or the HT 8k).  It DOES trigger SSP, which
halts the payload.

> What are you going to show next? That you can steal your own car? Are
> you going to blame the car manufacturer's for that?
> 

No, though it'd be interesting to show my car stealing itself :)

> As it was already pointed out this is a step into implementing a larger
> randomization, so that things don't break all at once. Even a large
> stack randomization is just another layer of protection, as there are
> still attacks that it doesn't prevent.... Duh.
> 
>> [...]         /*find the distance between a and myret*/
>>         for (i = (void*)a; *(void**)i != myret; i++) {
>>             distance++;
>>         }
> 
> 
> And this must be "la piece de resistance". Some very obfuscated (and
> inefficient) way to do a simple unsigned subtraction...
> 

Yeah, but I hate warnings.  It works without all the fancy casting, but
the compiler is like "OMFG WARNING WARNING DANGER WILL ROBINSON
ARITHMETIC ON POINTERS DR SMITH WANTS TO MOLEST YOU WARNING WARNING"

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

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.0 (GNU/Linux)
Comment: Using GnuPG with Thunderbird - http://enigmail.mozdev.org

iD8DBQFB+nujhDd4aOud5P8RAtc+AJ9t2EaQWQujOe3fyf/vg4jzUK9/TQCeMzBJ
Cjn/NUFS9+oxPJnU3u4XAsE=
=Vc2s
-----END PGP SIGNATURE-----

Re: Patch 4/6 randomize the stack pointer

[Ingo Molnar]

* Paulo Marques <pmarques@grupopie.com> wrote:

> I really shouldn't feed the trolls, but this must be the most silly
> piece of code I saw on this mailing list in a very long time (and
> there have been some good examples over time).

yeah.

> The stack randomization doesn't prevent some sort of attacks (like
> return into libc, etc.) and given a small randomization it might be
> possible to write an exploit with a long sequence of NOP's and a
> return address somewhere in there (the attacker wouldn't know exactly
> where, but it wouldn't matter anyway). If we are able to write 'N'
> NOP's then we get a 'N'/64k chance that the exploit works.

yeah. NOP techniques can always be used to 'chop off bits' from any
randomization, in case the address of the payload is not known. Both
instruction NOPs for shellcode and 'parameter NOPs' ("././././" strings
or "/bin/sh\0/bin/sh\0" strings) can be used.

but there is no fundamental theoretical difference between a 256 MB
randomization (as PaX uses) and a 2 MB randomization (Fedora) in terms
of characteristics: what is brute-force in one is brute-force in the
other as well, with a factor of overhead difference of 128. (which makes
the attack 128 times longer, but has no real difference to security.)

so the attempt of our beloved troll to paint 2 MB of randomization as
'weak' and 256 MB randomization as 'strong' is i believe misguided: both
are 'weak' in most of the threat models! (and even for threat types
where they might be considered 'strong' (e.g. whether a hole is suitable
to feed a destructive worm), they'll both be considered 'strong'.)

(obligatory note: the randomization we can get on 64-bit VMs is
different and probably completely adequate against all currently
existing remote threats, and maybe even against most of the practical
local threats.)

	Ingo

Re: Patch 4/6 randomize the stack pointer

[John Richard Moser]

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



Ingo Molnar wrote:
> * Paulo Marques <pmarques@grupopie.com> wrote:
> 
> 
>>I really shouldn't feed the trolls, but this must be the most silly
>>piece of code I saw on this mailing list in a very long time (and
>>there have been some good examples over time).
> 
> 
> yeah.
> 
> 
>>The stack randomization doesn't prevent some sort of attacks (like
>>return into libc, etc.) and given a small randomization it might be
>>possible to write an exploit with a long sequence of NOP's and a
>>return address somewhere in there (the attacker wouldn't know exactly
>>where, but it wouldn't matter anyway). If we are able to write 'N'
>>NOP's then we get a 'N'/64k chance that the exploit works.
> 
> 
> yeah. NOP techniques can always be used to 'chop off bits' from any
> randomization, in case the address of the payload is not known. Both
> instruction NOPs for shellcode and 'parameter NOPs' ("././././" strings
> or "/bin/sh\0/bin/sh\0" strings) can be used.
> 
> but there is no fundamental theoretical difference between a 256 MB
> randomization (as PaX uses) and a 2 MB randomization (Fedora) in terms
> of characteristics: what is brute-force in one is brute-force in the
> other as well, with a factor of overhead difference of 128. (which makes
> the attack 128 times longer, but has no real difference to security.)
> 

You said:

  yeah. NOP techniques can always be used to 'chop off bits' from any
  randomization, in case the address of the payload is not known. Both
  instruction NOPs for shellcode and 'parameter NOPs' ("././././"
  strings or "/bin/sh\0/bin/sh\0" strings) can be used.

Bear with me here, I'm out of things I've studied and researched, so now
we're going to go into "junk coming out of my head."  It's either going
to be very painful, or very funny, or both at the same time.  No, I
don't care that I'm about to look like an ass.

You're starting with 64K of randomization, and moving to 2M later.  The
stack is how big?  4-8M?  I don't know, I'm guessing; I saw earlier some
code that said that the stack was defined as having at least 8M in some
header, which "should be enough for most people" so I assume it's almost
if not over 2M.

Cut off however much data you know is going to be pushed already (which
is what we've been calling 'the size of the stack'), compare that with
the randomization, if it's bigger than the randomization period, you
have chopped off all randomization.  If not, you've probably got better
than a 50-50.

Because the size of a 'bit' grows as your entropy grows, chopping 2 megs
off the randomization at 256M is significantly less than 1 bit (128M is
1 bit), while it's about 9 bits when considering 2 megs of randomization.

Short version:  I've got a better chance of finding an exploit that lets
me just knock-off a couple megs of randomization than I do of brute
forcing it.  I've got a WAY better chance of brute-forcing in one or two
tries if I can knock most of the randomization off.

> so the attempt of our beloved troll to paint 2 MB of randomization as
> 'weak' and 256 MB randomization as 'strong' is i believe misguided: both
> are 'weak' in most of the threat models! (and even for threat types
> where they might be considered 'strong' (e.g. whether a hole is suitable
> to feed a destructive worm), they'll both be considered 'strong'.)
> 

Let's look at GrSecurity's brute force deterrance real quick.  I know
you don't want to hear it, but maybe you should.

The basic idea, and it's an ugly one but you have to forgive people for
trying to do stupid shit like LET BROKEN CODE RUN SAFELY, is to detect a
segfault (jump into unmapped ram, probably miss due to ASLR) or PaX kill
(should also detect a SIGILL) and then flag the highest parent (who is
found via magic I won't get into here).

When flagged with this particular flag, all fork() calls are queued so
that one fork() occurs every 30 seconds.  This is annoying and ugly as
shit, but we're trying to do the unspeakable:  Make broken,
security-hole ridden code safe to run in a hostile environment.

Suddenly the 216 second cycle to brute force PaX' ASLR becomes something
like 3 weeks!  :)


This randomization, after accounting for knocking off all the bits we
can, may take two or three, maybe ten or twenty tries.  This is what,
300-600 oh hell TEN MINUTES.  Yes, you did better than 216 seconds.

When brad first tried to bash the concept of his brute force deterrance
through my head, I kept poking at the 30 second interval and the idea of
making about 200 connections BEFORE slamming the server.  The server
will wait about a minute or two before timing you out, so this is fine,
as it takes 3-4 seconds.  He eventually got it through my skull that you
can do the first 200 hits; but then every fork() afterwards is QUEUED,
not executed in batch every 30 seconds.

This makes a difference.  It means you get a little boost with huge
randomization, but not that much.  In your model, however, that "little
boost" is bigger than the period needed to take it down anyway, so you
can't even deploy competant and working brute force deterrance as is.


Let me give you a hint.  A good one for you this time, not "PaX is
better and this is why you suck."

http://lkml.org/lkml/2005/1/28/194

This thread has given some good insight here.  Particularly, Andy
pointed this out:

  The 4G/4G patches (google for the lwn.net overview) change this,
  introducing a TLB flush on every syscall.  Better for some things
  because you get more VA space, worse for most things because it's
  slower.  (But it's "lots better for a few" versus "a little worse for
  everybody", so the tradeoff is often worthwhile.)

http://lkml.org/lkml/2005/1/28/272

"Lots better for a few" "a little worse for everybody," sound familiar?
 Bigger randomization and most of the address-space reducing/fragmenting
changes we've had discussions/flames about in this thread have fit this
description in reverse.  "Lots worse for some" "a little better for
[almost] everybody."  But this lends a more important insight here.

Why not compromise, if possible?  256M of randomization, but move the
split up to 3.5/0.5 gig, if possible.  I seem to recall seeing an option
(though I think it was UML) to do 3.5/0.5 before; and I'm used to "a
little worse" meaning "microbenches say it's worse, but you won't notice
it," so perhaps this would be a good compromise.  How well tuned can
3G/1G be?  Come on, 1G is just a big friggin' even number.

And yes, I saw the AGP/PCI stuff in that thread, which is where the "if
possible" comments came from.

> (obligatory note: the randomization we can get on 64-bit VMs is
> different and probably completely adequate against all currently
> existing remote threats, and maybe even against most of the practical
> local threats.)

Yes.  PaX does 64GiB on 64 bit VMs I *think*, and it's a 1TiB physical
and 256TiB virtual address space, so 64GiB is about 2 bytes in
comparison?  :)  (again with the bits-get-bigger-as-you-add-more philosophy)

> 
> 	Ingo
> -
> 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.

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.0 (GNU/Linux)
Comment: Using GnuPG with Thunderbird - http://enigmail.mozdev.org

iD8DBQFB+ydPhDd4aOud5P8RAkJGAJ49F/CiVaQ9nzYOJi1Yj4atEc9ZygCff4S5
ve3BdMmD5JfkKLq/pJ87xkA=
=iV8r
-----END PGP SIGNATURE-----

Re: Patch 4/6 randomize the stack pointer

[linux-os]

On Thu, 27 Jan 2005, Arjan van de Ven wrote:

> On Thu, 2005-01-27 at 14:19 -0500, linux-os wrote:
>> Gentlemen,
>>
>> Isn't the return address on the stack an offset in the
>> code (.text) segment?
>>
>> How would a random stack-pointer value help? I think you would
>> need to start a program at a random offset, not the stack!
>> No stack-smasher that worked would care about the value of
>> the stack-pointer.
>
> the simple stack exploit works by overflowing a buffer ON THE STACK with
> a "dirty payload and then also overwriting the return address to point
> back into that buffer.
>

Yes.

> (all the security guys on this list will now cringe about this over
> simplification; yes reality is more complex but lets keep the
> explenation simple for Richard)
>

Sure, be cute.

> pointing back into that buffer needs the address of that buffer. That
> buffer is on the stack, which is now randomized.
>

Wrong concept. Your exploit program simply needs fill with a guad-
byte offset such as 0x02020202 and put your payload at that
offset. You don't care where the stack-pointer is. You find
out how many bytes of 0x02 are necessary to get to that offset
on an experimental system, it is independent of the stack-pointer
value. It depends only upon the size of the buffer you are
exploiting, which needs to not change, of course.

When the return instruction occurs, one of those 0x02020202
will be encountered and your payload gets executed next.

Note that you should chose a different repeating-byte
than I have used here. Get the address of _end on a 'C'
program for hints.


Cheers,
Dick Johnson
Penguin : Linux version 2.6.10 on an i686 machine (5537.79 BogoMips).
  Notice : All mail here is now cached for review by Dictator Bush.
                  98.36% of all statistics are fiction.

Re: Patch 4/6 randomize the stack pointer

[John Richard Moser]

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


So 0x02020202 is a no-op?

(somebody finally gets why the randomization range must be > the size of
the stack?)

linux-os wrote:
[...]

>> pointing back into that buffer needs the address of that buffer. That
>> buffer is on the stack, which is now randomized.
>>
> 
> Wrong concept. Your exploit program simply needs fill with a guad-
> byte offset such as 0x02020202 and put your payload at that
> offset. You don't care where the stack-pointer is. You find
> out how many bytes of 0x02 are necessary to get to that offset
> on an experimental system, it is independent of the stack-pointer
> value. It depends only upon the size of the buffer you are
> exploiting, which needs to not change, of course.
> 
> When the return instruction occurs, one of those 0x02020202
> will be encountered and your payload gets executed next.
> 
> Note that you should chose a different repeating-byte
> than I have used here. Get the address of _end on a 'C'
> program for hints.
> 
> 
> Cheers,
> Dick Johnson
> Penguin : Linux version 2.6.10 on an i686 machine (5537.79 BogoMips).
>  Notice : All mail here is now cached for review by Dictator Bush.
>                  98.36% of all statistics are fiction.
> 

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

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.0 (GNU/Linux)
Comment: Using GnuPG with Thunderbird - http://enigmail.mozdev.org

iD8DBQFB+VLphDd4aOud5P8RAv5YAJ0QEBPyP+KMRS1Ua184KGJo3cw9EQCfc03J
SwDI0Zae2W5L03xHLXIkDdg=
=1+Xl
-----END PGP SIGNATURE-----

Re: Patch 4/6 randomize the stack pointer

[John Richard Moser]

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



Linus Torvalds wrote:
> 

[...]

> 
> Your suggestion of 256MB of randomization for the stack SIMPLY IS NOT 
> ACCEPTABLE for a lot of uses. People on 32-bit archtiectures have issues 
> with usable virtual memory areas etc.
> 

I feel the need to point something out here.

[TEXT][BRK][MMAP---------------][STACK]

Here's a normal layout.

[TEXT][BRK][MMAP-------][STACK][MMAP--]

Is this one any worse?  Just bias non-executable mappings above the
stack when, say, half of VMA is used up.  Prevent executable mappings
from being created up there because PaX' PAGEEXEC and Exec Shield's
emulation will be affected by a high-mapping (PaX falls back to
kernel-assisted MMU walking, which can be very high overhead; ES just
makes everything below the area executable).

So, you can do it without losing VMA, in theory.


[...]

> 

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

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.0 (GNU/Linux)
Comment: Using GnuPG with Thunderbird - http://enigmail.mozdev.org

iD8DBQFB+V94hDd4aOud5P8RAqv1AJ9iazEKh//yeaTdraUou9KLQCUG0wCfVbo2
kXYvkauZ8+wC7J3nN5IzoTY=
=tvyp
-----END PGP SIGNATURE-----

Re: Patch 4/6 randomize the stack pointer

[Arjan van de Ven]

> I feel the need to point something out here.
> 
> [TEXT][BRK][MMAP---------------][STACK]
> 
> Here's a normal layout.
> 
> [TEXT][BRK][MMAP-------][STACK][MMAP--]
> 
> Is this one any worse?

yes.

oracle, db2 and similar like to mmap 2Gb or more *in one chunk*.
moving the stack in the middle means the biggest chunk they can mmap
shrinks. 

Re: Patch 4/6 randomize the stack pointer

[John Richard Moser]

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



Arjan van de Ven wrote:
>>I feel the need to point something out here.
>>
>>[TEXT][BRK][MMAP---------------][STACK]
>>
>>Here's a normal layout.
>>
>>[TEXT][BRK][MMAP-------][STACK][MMAP--]
>>
>>Is this one any worse?
> 
> 
> yes.
> 
> oracle, db2 and similar like to mmap 2Gb or more *in one chunk*.
> moving the stack in the middle means the biggest chunk they can mmap
> shrinks. 
> 

Special case?

I never said these weren't out there.  But the point is, who runs
oracle?  Your internal production server, maybe even a cluster, run it
now.  Your desktops don't.  Your web server exposed to the net
shouldn't.  Both these are exactly where you *really* want this stuff:
desktops get exposed to the WWW (and IRC and AIM and God knows what
else), and web servers get exposed to the HTTP protocol (or ftp or
whatever).

Interesting, it's theoretically far less likely that an exploit occurs
on your server than on your desktop; and the special cases such as your
Oracle example aren't likely to be sharing a machine with your
promiscuous touching of everyone else on the Internet with a web browser
and IRC client, correct?

Can I get this put into perspective?  How much more important is "Good"
randomization versus "not breaking Oracle," which becomes "No
randomization" (for Oracle anyway, not for everything else on a
well-designed system)?  How much of an effect does "good" randomization
have on your web server and desktop machines versus on your internal,
isolated RDBMS server/cluster?

More pertainantly (believe it or not), do you even care to ponder these
questions, or is your next response going to be a stock response?

> 
> 

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

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.0 (GNU/Linux)
Comment: Using GnuPG with Thunderbird - http://enigmail.mozdev.org

iD8DBQFB+Wx8hDd4aOud5P8RAuriAJ0WYcesi/o5lOZIJ++UG8WbDu3PMACeKaB5
/YjzHR2n0aRiUrxUrca1gkU=
=0/hv
-----END PGP SIGNATURE-----

Re: Patch 4/6 randomize the stack pointer

[Rik van Riel]

On Thu, 27 Jan 2005, John Richard Moser wrote:
> Arjan van de Ven wrote:

>>> Is this one any worse?
>> yes.
>>
>> oracle, db2 and similar like to mmap 2Gb or more *in one chunk*.
>
> Special case?

Absolutely, but ...

> Can I get this put into perspective?  How much more important is "Good"
> randomization versus "not breaking Oracle," which becomes "No
> randomization"

1) quite a lot of Linux users do use Oracle, DB2 or do
    scientific calculations - distributions cannot afford
    to break those applications, the default has to work
    for everybody

2) "weaker" randomization (2MB) is still effective if the
    stack is non-executable, so the "load a bunch of NOPs"
    approach won't work - this is what Fedora and RHEL use

3) it is not as theoretically strong as what you propose,
    but having the "weaker" scheme enabled is definitely
    more secure than having the "stronger" scheme disabled
    because it breaks applications

-- 
"Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, you are,
by definition, not smart enough to debug it." - Brian W. Kernighan

Re: Patch 4/6 randomize the stack pointer

[John Richard Moser]

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



Rik van Riel wrote:
> On Thu, 27 Jan 2005, John Richard Moser wrote:
> 
>> Arjan van de Ven wrote:
> 
> 
>>>> Is this one any worse?
>>>
>>> yes.
>>>
>>> oracle, db2 and similar like to mmap 2Gb or more *in one chunk*.
>>
>>
>> Special case?
> 
> 
> Absolutely, but ...
> 
>> Can I get this put into perspective?  How much more important is "Good"
>> randomization versus "not breaking Oracle," which becomes "No
>> randomization"
> 
> 
> 1) quite a lot of Linux users do use Oracle, DB2 or do
>    scientific calculations - distributions cannot afford
>    to break those applications, the default has to work
>    for everybody
> 

So package oracle marked to not use the randomization.

> 2) "weaker" randomization (2MB) is still effective if the
>    stack is non-executable, so the "load a bunch of NOPs"
>    approach won't work - this is what Fedora and RHEL use
> 

"In some cases, this does nothing, so we'll leverage those cases as an
argument for why this should go in, even though we're effectively saying
'please add useless junk to the kernel'"

No dear, please, real ASLR has a point, try not to castrate it.

> 3) it is not as theoretically strong as what you propose,
>    but having the "weaker" scheme enabled is definitely
>    more secure than having the "stronger" scheme disabled
>    because it breaks applications
> 

*takes the glass pipe away*


Well, I'm going to give random constructive criticism on red hat as a
whole now, so try learning something from it instead of taking it as
flamebait.  I just ate and feel particularly like talking for no reason
about half-relavent topics.

I actually just tried to paxtest a fresh Fedora Core 3, unadultered,
that I installed, and it FAILED every test.  After a while, spender
reminded me about PT_GNU_STACK.  It failed everything but the Executable
Stack test after execstack -c *.  The randomization tests gave
13(heap-etexec), 16(heap-etdyn), 17(stack), and none for main exec
(etexec,et_dyn) or shared library randomization.

Also, before you say it, I read, comprehended, and anylized the source.
 This was PaXtest 0.9.6, and I did specific traces (after changing
body.c to prevent it from forking) to look for mprotect() and mmap()
calls and find out what they do (I saw probably glibc getting mmap()ed
in, there wasn't anything in the source doing the mmap() calls I saw).
There were no dirty tricks to mprotect() a high area of memory, which is
something Ingo called foul on in 0.9.5.

My point isn't that ES failed (the above discourse was to preempt Ingo
calling a technical foul on paxtest again); but that I forgot about
PT_GNU_STACK.  How many vendors are going to forget about PT_GNU_STACK
and its automatic markings and think they're protected?  Do they even
know/care?  "it works so we'll just keep doing what we're doing, if we
break the protection it'll adjust to let us" is pretty good strategy to
a lot of people who don't want to be assed with your security crap.

Another concern of mine, execstack gives X for PT_GNU_STACK and - for
cleared PT_GNU_STACK.  With many binaries i get shipped (flash and java
plug-ins), there's a ? when I check them, so I clear the flag and they
work.  Note that I'm referring to the Java PLUG-IN, not the JRE itself;
you can have full PaX restrictions on Firefox and have working Java in
Firefox, because java_vm is a separate process :) (you have to chpax
java itself).  Firefox happens to be a high-risk application too IMHO
(it's pointed at the net and exposes Gecko bugs for HTML and Javascript
parsing, libjpeg and libpng bugs, and God knows what else), and I don't
want it accidentally getting an executable stack.

Finally, although an NX stack is nice, you should probably take into
account IBM's stack smash protector, ProPolice.  Any attack that can
evade SSP reliably can evade an NX stack; but ProPolice protects from
other overflows.  Now I'm sure RH is over there inventing something that
detects buffer overflows at compile time and misses or warns about the
ones it can't identify:

if (strlen(a) > 4)
  a[5] = '\0';
foo(a);

void foo(char *a) {
   char b[5];
   strcpy(b,a);
}

This code is safe, but you can't tell from looking at foo().  You don't
get a look at every other object being compiled against this one that
may call foo() either.  So compile time buffer overflow detection is a
best-effort at best.

ProPolice protects local variables with 0 overhead; passed arguments
with a few instructions; and the return pointer and stack frame pointer
with a couple instructions.  At runtime.  Want to impress me?  Actually
deploy ProPolice instead of showing up 3 years from now waving around
your own patch that you wrote that half-impliments half of it.  If you
want "something better," it's GPL, so grab it and start hacking.

Anyway, that's my far-far-far offtopic rant for the day.
- --
All content of all messages exchanged herein are left in the
Public Domain, unless otherwise explicitly stated.

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.0 (GNU/Linux)
Comment: Using GnuPG with Thunderbird - http://enigmail.mozdev.org

iD8DBQFB+y3RhDd4aOud5P8RAofVAJ9ulaCZmV9rzQTkSNEgbjOG9VD7xACfXSfF
JJlZyXVYtwXTFMotQm3YrV0=
=hrWP
-----END PGP SIGNATURE-----

Re: Patch 4/6 randomize the stack pointer

[Arjan van de Ven]

> I actually just tried to paxtest a fresh Fedora Core 3, unadultered,
> that I installed, and it FAILED every test.  After a while, spender
> reminded me about PT_GNU_STACK.  It failed everything but the Executable
> Stack test after execstack -c *.  The randomization tests gave
> 13(heap-etexec), 16(heap-etdyn), 17(stack), and none for main exec
> (etexec,et_dyn) or shared library randomization.

because you ran prelink.
and you did not compile paxtest with -fPIE -pie to make it a PIE
executable.

> 
> Also, before you say it, I read, comprehended, and anylized the source.
>  This was PaXtest 0.9.6, and I did specific traces (after changing
> body.c to prevent it from forking) to look for mprotect() and mmap()
> calls and find out what they do (I saw probably glibc getting mmap()ed
> in, there wasn't anything in the source doing the mmap() calls I saw).
> There were no dirty tricks to mprotect() a high area of memory, which is
> something Ingo called foul on in 0.9.5.

there is one actually if you look careful enough.


> 
> if (strlen(a) > 4)
>   a[5] = '\0';
> foo(a);
> 
> void foo(char *a) {
>    char b[5];
>    strcpy(b,a);
> }
> 
> This code is safe, but you can't tell from looking at foo().  You don't
> get a look at every other object being compiled against this one that
> may call foo() either.  So compile time buffer overflow detection is a
> best-effort at best.

actually this one gets caught, since this will be turned into a checking
strcpy which aborts after the 5th character.

Re: Patch 4/6 randomize the stack pointer

[Arjan van de Ven]

On Sat, 2005-01-29 at 11:21 -0500, John Richard Moser wrote:
> -----BEGIN PGP SIGNED MESSAGE-----

> These are the only places mprotect() is mentioned; a visual scan
> confirms no trickery:
> 
>         if( fork() == 0 ) {
>                 /* Perform a dirty (but not unrealistic) trick to circumvent
>                  * the kernel protection.
>                  */
>                 if( paxtest_mode == 1 ) {
>                         pthread_t thread;
>                         pthread_create(&thread, NULL, test_thread, dummy);
>                         doit();
>                         pthread_kill(thread, SIGTERM);
>                 } else {

> So, there you have it.  These tests do not intentionally kill
> exec-shield based on its known issue with tracking the upper limit of
> the code segment.


here they do.
dummy is a local NESTED function, which causes the stack to *correctly*
be marked executable, due to the need of trampolines. 
That disables execshield for any tests that use dummy.o, which most of
them are.

Re: Patch 4/6 randomize the stack pointer

[John Richard Moser]

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





Arjan van de Ven wrote:
> On Sat, 2005-01-29 at 11:21 -0500, John Richard Moser wrote:
> 
>>-----BEGIN PGP SIGNED MESSAGE-----
> 
> 
>>These are the only places mprotect() is mentioned; a visual scan
>>confirms no trickery:
>>
>>        if( fork() == 0 ) {
>>                /* Perform a dirty (but not unrealistic) trick to circumvent
>>                 * the kernel protection.
>>                 */
>>                if( paxtest_mode == 1 ) {
>>                        pthread_t thread;
>>                        pthread_create(&thread, NULL, test_thread, dummy);
>>                        doit();
>>                        pthread_kill(thread, SIGTERM);
>>                } else {
> 
> 
>>So, there you have it.  These tests do not intentionally kill
>>exec-shield based on its known issue with tracking the upper limit of
>>the code segment.
> 
> 
> 
> here they do.
> dummy is a local NESTED function, which causes the stack to *correctly*
> be marked executable, due to the need of trampolines. 
> That disables execshield for any tests that use dummy.o, which most of
> them are.
> 

Only in "Blackhat" mode.  I ran in Kiddie and Blackhat mode, and my
second batch of tests (tests.txt, my errata) was run after execstack -c.

> 

root@iceslab:/mnt/redhat/root/paxtest-0.9.6 # strace ./execstack 2>&1 |
grep mprotect
mprotect(0x20822000, 4096, PROT_NONE)   = 0
root@iceslab:/mnt/redhat/root/paxtest-0.9.6 # strace ./execstack 2>&1 |
grep EXEC
old_mmap(NULL, 64996, PROT_READ|PROT_EXEC, MAP_PRIVATE, 3, 0) = 0x265d9000
old_mmap(NULL, 1232332, PROT_READ|PROT_EXEC, MAP_PRIVATE, 3, 0) = 0x265e9000
mmap2(NULL, 8392704, PROT_READ|PROT_WRITE|PROT_EXEC,
MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x26716000

I killed the fork() line and straced it.
0x26716000 is only ~600 megs up,  I find my stack at ~1.5G under
segmexec, I'd guess it'd be at ~3G under normal things like execshield.
 You know what *looks*

getstack1:  0xfefcead7
getstack1:  0xfefe9947
getstack1:  0xfeedd4f7
getstack1:  0xfefe6e37
getstack1:  0xfee412b7
getstack1:  0xfee71737

Yeah it's pretty high under exec shield.

none of these are doing ANYTHING weird (grepping for EXEC and scanning
for PROT_EXEC and related addresses), aside from the normal mapping of
libraries by the system, which is probably what's killing Exec Shield's
anonymous mapping, heap, data, bss, library data, library bss. . .

To put it bluntly, you're wrong.  The tests are valid.

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

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.0 (GNU/Linux)
Comment: Using GnuPG with Thunderbird - http://enigmail.mozdev.org

iD8DBQFB+8DuhDd4aOud5P8RAscYAKCErG3KB5M9gMwZ1BRqTDBKyYYLrACfcYeb
0ptJYTE+uUx0QYSHmKXWlsA=
=PL8+
-----END PGP SIGNATURE-----

Re: Patch 4/6 randomize the stack pointer

[Arjan van de Ven]

On Sat, 2005-01-29 at 11:21 -0500, John Richard Moser wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
> 
> 
> 
> Arjan van de Ven wrote:
> >>I actually just tried to paxtest a fresh Fedora Core 3, unadultered,
> >>that I installed, and it FAILED every test.  After a while, spender
> >>reminded me about PT_GNU_STACK.  It failed everything but the Executable
> >>Stack test after execstack -c *.  The randomization tests gave
> >>13(heap-etexec), 16(heap-etdyn), 17(stack), and none for main exec
> >>(etexec,et_dyn) or shared library randomization.
> > 
> > 
> > because you ran prelink.
> > and you did not compile paxtest with -fPIE -pie to make it a PIE
> > executable.
> > 

what I get is

Executable anonymous mapping             : Killed
Executable bss                           : Killed
Executable data                          : Vulnerable
Executable heap                          : Killed
Executable stack                         : Killed
Executable anonymous mapping (mprotect)  : Vulnerable
Executable bss (mprotect)                : Vulnerable
Executable data (mprotect)               : Vulnerable
Executable heap (mprotect)               : Vulnerable
Executable shared library bss (mprotect) : Vulnerable
Executable shared library data (mprotect): Vulnerable
Executable stack (mprotect)              : Vulnerable
Anonymous mapping randomisation test     : No randomisation
Heap randomisation test (ET_EXEC)        : 13 bits (guessed)
Heap randomisation test (ET_DYN)         : 13 bits (guessed)
Main executable randomisation (ET_EXEC)  : 12 bits (guessed)
Main executable randomisation (ET_DYN)   : 12 bits (guessed)
Shared library randomisation test        : 12 bits (guessed)
Stack randomisation test (SEGMEXEC)      : 17 bits (guessed)
Stack randomisation test (PAGEEXEC)      : 17 bits (guessed)
Return to function (strcpy)              : paxtest: bad luck, try
different compiler options.
Return to function (strcpy, RANDEXEC)    : paxtest: bad luck, try
different compiler options.
Return to function (memcpy)              : Vulnerable
Return to function (memcpy, RANDEXEC)    : Vulnerable
Executable shared library bss            : Killed
Executable shared library data           : Killed
Writable text segments                   : Vulnerable


I'm not entirely happy yet (it shows a bug in mmap randomisation) but
it's way better than what you get in your tests (this is the desabotaged
0.9.6 version fwiw)

Re: Patch 4/6 randomize the stack pointer

[John Richard Moser]

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



Arjan van de Ven wrote:
> On Sat, 2005-01-29 at 11:21 -0500, John Richard Moser wrote:
> 
>>-----BEGIN PGP SIGNED MESSAGE-----
>>Hash: SHA1
>>
>>
>>
>>Arjan van de Ven wrote:
>>
>>>>I actually just tried to paxtest a fresh Fedora Core 3, unadultered,
>>>>that I installed, and it FAILED every test.  After a while, spender
>>>>reminded me about PT_GNU_STACK.  It failed everything but the Executable
>>>>Stack test after execstack -c *.  The randomization tests gave
>>>>13(heap-etexec), 16(heap-etdyn), 17(stack), and none for main exec
>>>>(etexec,et_dyn) or shared library randomization.
>>>
>>>
>>>because you ran prelink.
>>>and you did not compile paxtest with -fPIE -pie to make it a PIE
>>>executable.
>>>
> 
> 
> what I get is
> 
> Executable anonymous mapping             : Killed
> Executable bss                           : Killed
> Executable data                          : Vulnerable
> Executable heap                          : Killed
> Executable stack                         : Killed
> Executable anonymous mapping (mprotect)  : Vulnerable
> Executable bss (mprotect)                : Vulnerable
> Executable data (mprotect)               : Vulnerable
> Executable heap (mprotect)               : Vulnerable
> Executable shared library bss (mprotect) : Vulnerable
> Executable shared library data (mprotect): Vulnerable
> Executable stack (mprotect)              : Vulnerable
> Anonymous mapping randomisation test     : No randomisation
> Heap randomisation test (ET_EXEC)        : 13 bits (guessed)
> Heap randomisation test (ET_DYN)         : 13 bits (guessed)
> Main executable randomisation (ET_EXEC)  : 12 bits (guessed)
> Main executable randomisation (ET_DYN)   : 12 bits (guessed)
> Shared library randomisation test        : 12 bits (guessed)
> Stack randomisation test (SEGMEXEC)      : 17 bits (guessed)
> Stack randomisation test (PAGEEXEC)      : 17 bits (guessed)
> Return to function (strcpy)              : paxtest: bad luck, try
> different compiler options.
> Return to function (strcpy, RANDEXEC)    : paxtest: bad luck, try
> different compiler options.
> Return to function (memcpy)              : Vulnerable
> Return to function (memcpy, RANDEXEC)    : Vulnerable
> Executable shared library bss            : Killed
> Executable shared library data           : Killed
> Writable text segments                   : Vulnerable
> 
> 
> I'm not entirely happy yet (it shows a bug in mmap randomisation) but
> it's way better than what you get in your tests (this is the desabotaged
> 0.9.6 version fwiw)
> 

I used 0.9.6 too, it had a slight bug in the randomization test
(getmain.c), which I pointed out in another post.

void foo( int unused )
{
        printf( "%p\n", __builtin_return_address(0) );
        //printf( "0x%08x\n", ((unsigned long*)&unused)[-1] );
}

I'm curious as to what the hell you're doing to get these results.  Exec
Shield came with the sysctl sys/kernel/exec-shield = 1 and
sys/kernel/exec-shield-randomize = 1.  I tried exec-shield = 0, 1, 2,
and 3 and couldn't get anything but the stack to kill on a Barton cored
32 bit athlon xp.

The tests I did were on a Fedora Core 3 i net-installed last night, no
adulteration.  Whatever black magic you're doing, it's not working here.
> 
> 

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

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.0 (GNU/Linux)
Comment: Using GnuPG with Thunderbird - http://enigmail.mozdev.org

iD8DBQFB+8H/hDd4aOud5P8RAlIEAJkBwhIxdrXZ+jNz46oRg1SoSPmOHQCgiWfJ
HxzCBB43i6iLLhli5boKzoM=
=etT7
-----END PGP SIGNATURE-----

Re: Patch 4/6 randomize the stack pointer

[Jakub Jelinek]

On Sat, Jan 29, 2005 at 01:31:46AM -0500, John Richard Moser wrote:
> Finally, although an NX stack is nice, you should probably take into
> account IBM's stack smash protector, ProPolice.  Any attack that can
> evade SSP reliably can evade an NX stack; but ProPolice protects from
> other overflows.  Now I'm sure RH is over there inventing something that
> detects buffer overflows at compile time and misses or warns about the
> ones it can't identify:
> 
> if (strlen(a) > 4)
>   a[5] = '\0';
> foo(a);
> 
> void foo(char *a) {
>    char b[5];
>    strcpy(b,a);
> }
> 
> This code is safe, but you can't tell from looking at foo().  You don't
> get a look at every other object being compiled against this one that
> may call foo() either.  So compile time buffer overflow detection is a
> best-effort at best.

If strlen(a) > 4 above, then -D_FORTIFY_SOURCE={1,2} compiled program
will be terminated in the strcpy call.  At compile time it computes
that the strcpy call can fill in at most 5 bytes and if it copies more,
then it terminates.

> ProPolice protects local variables with 0 overhead; passed arguments
> with a few instructions; and the return pointer and stack frame pointer
> with a couple instructions.  At runtime.  Want to impress me?  Actually
> deploy ProPolice instead of showing up 3 years from now waving around
> your own patch that you wrote that half-impliments half of it.  If you
> want "something better," it's GPL, so grab it and start hacking.

__builtin_object_size () checking/-D_FORTIFY_SOURCE=n changes are (partly)
orthogonal to ProPolice.  There are exploits prevented by
-D_FORTIFY_SOURCE={1,2} checking and not ProPolice and vice versa.
Things that the former protects and the latter does not are e.g.
some non-automatic buffer overflows or heap overflows, some format string
vulnerabilities and for automatic variables e.g. those that don't
overflow into another function's frame, but just overwrite other local
variables in the same function.  ProPolice on the other side will detect
stack overflows that overflow into another function's frame, even if they
aren't done through string operations (<string.h>, s*printf, gets, etc.)
or if the compiler can't figure out what certain arguments to these
functions points to (and where) at compile time.

The ideas in IBM's ProPolice changes are good and worth
implementing, but the current implementation is bad.

FYI, you can find some details about -D_FORTIFY_SOURCE=n in
http://gcc.gnu.org/ml/gcc-patches/2004-09/msg02055.html

	Jakub

Re: Patch 4/6 randomize the stack pointer

[John Richard Moser]

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



Jakub Jelinek wrote:
> On Sat, Jan 29, 2005 at 01:31:46AM -0500, John Richard Moser wrote:
> 
>>Finally, although an NX stack is nice, you should probably take into
>>account IBM's stack smash protector, ProPolice.  Any attack that can
>>evade SSP reliably can evade an NX stack; but ProPolice protects from
>>other overflows.  Now I'm sure RH is over there inventing something that
>>detects buffer overflows at compile time and misses or warns about the
>>ones it can't identify:
>>
>>if (strlen(a) > 4)
>>  a[5] = '\0';
>>foo(a);
>>
>>void foo(char *a) {
>>   char b[5];
>>   strcpy(b,a);
>>}
>>
>>This code is safe, but you can't tell from looking at foo().  You don't
>>get a look at every other object being compiled against this one that
>>may call foo() either.  So compile time buffer overflow detection is a
>>best-effort at best.
> 
> 
> If strlen(a) > 4 above, then -D_FORTIFY_SOURCE={1,2} compiled program
> will be terminated in the strcpy call.  At compile time it computes
> that the strcpy call can fill in at most 5 bytes and if it copies more,
> then it terminates.

And somehow you check every operation like this with less overhead than
propolice?

> 
> 
>>ProPolice protects local variables with 0 overhead; passed arguments
>>with a few instructions; and the return pointer and stack frame pointer
>>with a couple instructions.  At runtime.  Want to impress me?  Actually
>>deploy ProPolice instead of showing up 3 years from now waving around
>>your own patch that you wrote that half-impliments half of it.  If you
>>want "something better," it's GPL, so grab it and start hacking.
> 
> 
> __builtin_object_size () checking/-D_FORTIFY_SOURCE=n changes are (partly)
> orthogonal to ProPolice.  There are exploits prevented by
> -D_FORTIFY_SOURCE={1,2} checking and not ProPolice and vice versa.

So a belt-and-suspenders approach is better.

> Things that the former protects and the latter does not are e.g.
> some non-automatic buffer overflows or heap overflows, some format string
> vulnerabilities and for automatic variables e.g. those that don't
> overflow into another function's frame, but just overwrite other local
> variables in the same function.  ProPolice on the other side will detect
> stack overflows that overflow into another function's frame,

or past the top of any buffer by at most 2 ints (I didn't check with 1
int or 1 char when I wrote my regression suite), definitely before it
hits the SFP and return pointer

> even if they
> aren't done through string operations (<string.h>, s*printf, gets, etc.)
> or if the compiler can't figure out what certain arguments to these
> functions points to (and where) at compile time.
> 
> The ideas in IBM's ProPolice changes are good and worth
> implementing, but the current implementation is bad.
> 

Lies.  I've read the paper on the current implementation, it's
definitely good.  It only operates on C/C++ code though, but that's the
scope of it.

> FYI, you can find some details about -D_FORTIFY_SOURCE=n in
> http://gcc.gnu.org/ml/gcc-patches/2004-09/msg02055.html
> 
> 	Jakub
> 

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

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.0 (GNU/Linux)
Comment: Using GnuPG with Thunderbird - http://enigmail.mozdev.org

iD8DBQFB+8yPhDd4aOud5P8RAsekAJsGklzrgWi7ymrRmfhXpqv2LjB//gCeNBDy
8sCZBhtzy6l6L/WDjQpMq6A=
=4/Dz
-----END PGP SIGNATURE-----

Re: Patch 4/6 randomize the stack pointer

[Christoph Hellwig]

On Sat, Jan 29, 2005 at 12:49:05PM -0500, John Richard Moser wrote:
> > The ideas in IBM's ProPolice changes are good and worth
> > implementing, but the current implementation is bad.
> > 
> 
> Lies.  I've read the paper on the current implementation, it's
> definitely good.  It only operates on C/C++ code though, but that's the
> scope of it.

Yeah, I guess your extensive compiler internals experience and knowledge
of gcc internals weights a lot more than the opinion of the gcc team..

Re: Patch 4/6 randomize the stack pointer

[John Richard Moser]

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



Christoph Hellwig wrote:
> On Sat, Jan 29, 2005 at 12:49:05PM -0500, John Richard Moser wrote:
> 
>>>The ideas in IBM's ProPolice changes are good and worth
>>>implementing, but the current implementation is bad.
>>>
>>
>>Lies.  I've read the paper on the current implementation, it's
>>definitely good.  It only operates on C/C++ code though, but that's the
>>scope of it.
> 
> 
> Yeah, I guess your extensive compiler internals experience and knowledge
> of gcc internals weights a lot more than the opinion of the gcc team..
> 

I read "implementation" as "the way it's implemented," not as "the
quality of the code."

Did I miss the target?  *Aims in the other direction then?*

> 

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

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.0 (GNU/Linux)
Comment: Using GnuPG with Thunderbird - http://enigmail.mozdev.org

iD8DBQFB+9GthDd4aOud5P8RAm/FAJwNvbrxPP8fcJmMM//vcYL10nMXTACggi57
jOKfS4FU1sdPL7AjKRgMmBg=
=igR0
-----END PGP SIGNATURE-----

Re: Patch 4/6 randomize the stack pointer

[Rik van Riel]

On Sat, 29 Jan 2005, John Richard Moser wrote:

> Did I miss the target?  *Aims in the other direction then?*

Depends.  If you aimed to kick your own arse, you did pretty well.

-- 
"Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, you are,
by definition, not smart enough to debug it." - Brian W. Kernighan

Re: Patch 4/6 randomize the stack pointer

[Christoph Hellwig]

On Sat, Jan 29, 2005 at 01:10:54PM -0500, John Richard Moser wrote:
> > Yeah, I guess your extensive compiler internals experience and knowledge
> > of gcc internals weights a lot more than the opinion of the gcc team..
> > 
> 
> I read "implementation" as "the way it's implemented," not as "the
> quality of the code."

Doesn't really matter, it'd fit for both.

> 
> Did I miss the target?  *Aims in the other direction then?*

Yes.  Try to search for propolice in the gcc mailglist archives
as a start.  Doing a little bit of research before calling someone
a liar is usually considered a good idea.

Re: Patch 4/6 randomize the stack pointer

[John Richard Moser]

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

Alright, I'll bite.

Someone told me to bring this up after reading all the complaints about
breakage, so again we get back to PaX.  I'm more interested in "this
patch is bad" than "PaX is better" for this argument, but whatever.


Compatibility has been repetedly mentioned here.  Breaking things has
been mentioned.  Things inside the distro won't break becaues the distro
maintainers mark them; third party vendors should mark them too.  If
they don't, they STILL won't break, if the distribution is crafted to do
really ugly things I hate to enter ultimate-global-super-compatibility-mode.

Last year I started on my master's thesis for computer security.
Granted, next semester i'm *hoping* to get my AS in computer science,
but I wanted to start writing early.  So out of the 18 pages, I'll pull
one little bit from section 4 (Deployment) subsection 2 (Executable
Space Protections).  This'll be a big read.

- ---CUT---
2.  Executable Space Protections

Executable Space Protections can be deployed on many architectures using
PaX.  A number of methods of deployment could be used, each ranging its
own ratio of security vs. compatibility.  The recommended course of
action is to allow the administrator to control how protections are
applied, either by setting an automatic default method or by being asked
where protections should be applied on a case by case basis.

Any binary which may function under full restrictions should be set to
function under full restrictions automatically, without asking.  There
may be an option to ask the administrator in every case including those
where the greatest security is used by default; but in most cases, the
administrator will not want to be bothered unless a security concern is
raised.

There are three states for restrictions.  In the Default state, the
restriction is not explicitly enabled or disabled; PaX decides whether
to use the restriction based on the Softmode setting.  If the system is
in Softmode, PaX does not enable restrictions in the Default state; if
the system is not in Softmode, PaX enables restrictions in the Default
state.  Contrastingly, restrictions in the Enabled state are enabled
under PaX regardless of Softmode, while restrictions in the Disabled
state are disabled under PaX regardless of Softmode.

Here, the term "compatibility" is used to indicate how much software
doesn't work.  A system with low compatibility will have software that
does not run due to security restrictions; while a system with high
compatibility will run most if not all software, including third party
software.

There are four basic methods of PaX flag control, each detailed briefly
below.  As stated above, the administrator should choose which method to
employ.

A.  Manual Control

  Manual Control is not recommended as a default.  Under Manual Control,
  all restrictions remain in the Default state on all binaries at
  installation time.  This imposes the most added administrative duty
  and the least compatibility.

B.  Selective Disable

  Selective Disable is the most basic form of control, allowing the
  implementation to ship with everything working.  Under Selective
  Disable, binaries known to break due to PaX restrictions have those
  restrictions set to the Disabled state when installed, leaving the
  rest in the Default state.  This relieves most administrative duty and
  increases compatibility, although third party binaries may not come
  marked.

C.  Inheritive Selective Disable

  Inheritive Selective Disable is similar to Selective Disable, except
  that libraries are also marked and tabs are kept on these.  When
  software is installed which uses a library, the Disabled features of
  the executable and each library are masked together to come up with
  the final mask to apply to the executable.  These masks can later be
  generated for third party programs with an administrative tool in
  order to enhance compatibility further; although third party programs
  and libraries requiring other markings in themselves not also needed
  by other libraries will still break.

D.  Selective Enable

  Selective Enable is the only method leveraging Softmode to enhance
  compatibility.  It is also the only method which will leave third
  party binaries completely exposed with no reason aside from that they
  are not explicitly packaged with a set of listed restrictions.  Under
  Selective Enable, executable binaries have all restrictions except
  those known to break them set to Enabled, leaving the rest in the
  Default state.  Third party binaries which come with no markings will
  have no restrictions in Softmode, and so full compatibility is reached
  with the maximum justifiable trade-off in the range of executables
  protected by PaX.

The above methods become progressively more compatible, but at the same
time less secure.  Both the standard and Inheritive variations of the
Selective Disable method are about on par in principle; the
administrator will obviously disable protections on third party software
that breaks, so attempting to preempt this by identifying what
absolutely will break the software may prevent shotgunning (disabling
everything that could possibly cause a problem).  This is a best-effort
compatibility model; anything obviously incompatible is adjusted, but
some things may be missed.

The Selective Enable method, on the other hand, will take compatibility
out to its edge and switch completely to a best-effort security model,
where anything obviously compatible is secured, but anything not defined
is left alone to avoid breakage.  Microsoft's implementation of NX
protections on 64 bit Windows XP SP2 allows a mode which is akin to
this, in which only core system software is protected[24].

In any protection method, third party vendors can mark their binaries to
explicitly enable and disable protections to be compatible under any
method.  If this additional information could be guaranteed from third
party vendors, the Inheritive Selective Disable method could be
completed by masking the still Enabled protections with the inherited
Disabled protections to produce the final mask, giving guaranteed
compatibility with least privileges.
- ---CUT---

Blah blah blah blah with softmode, PaX can be made to function only on
the programs that the distribution maintainers have touched.  This
provides better protection for the base system, and removes all
protection for third party binaries, which makes the system infinitely
compatible with third party software.

Reminder, I hate option (D).  You take the security away from the huge
realm of third party software to save yourself 3 seconds of `chpax
- -psemrx` or `paxctl -psemrx` which would do the same thing to most lkely
exactly one or at least less than ten special cases.

I believe that if you want your product to work, you should mark it for
PaX, since (hey!) the kernel ignores EI_PAX and PT_PAX_FLAGS anyway
unless it has PaX (I've tested this, and in fact Gentoo I believe
compiles with PT_PAX_FLAGS regardless of kernel used, but I'm not sure).

Now of course if vendors are forced to "release a patch" and continue to
maintain their product with a little extra command in the build/package
process, they'll just have to do it; but we wouldn't want to burden them
with 5 seconds more work (somebody always clips me on this one with "and
another 5 seconds, and another, until it takes 1000 years to release a
product").

Then again, a quick google will probably turn up "Oracle breaks on
<insert OS with protection that breaks oracle here>"  "This is easy,
there's a command called 'paxctl'....."  I mean hell, how many "tweaks"
are there that idiots put into there computer that start with "Microsoft
packages a tool with Windows called 'regedit'"?

This thread and this argument isn't about PaX.  My point is that coarse,
mid, and fine-grained control should all be available to let a large
bane of power be weielded with respect.  PaX does this by allowing you
to completely disable PaX (kernel compilation, not runtime; I'd love to
see runtime as well); set its exec protections into "softmode" where it
only goes for explicit "On" tristates for options on individual
binaries; explicitly disable protections on individual binaries; or
disable ASLR for the entire system.

Maybe I just like being able to fiddle with little knobs too much, but
it seems to me that I don't have to fiddle with them just because
they're there; my distribution can do it for me, and that's important to
me.  *I* want to toy with them, but *you* shouldn't have to.

. . . what was my point?  Oh yeah.  it's possible to deploy huge
randomization and VM splitting and crap without breaking third party
software, see above for explaination.

Linus Torvalds wrote:
> 
> On Thu, 27 Jan 2005, John Richard Moser wrote:
> 
>>What the hell?
> 
> 
> John. Stop frothing at the mouth already!
> 
> Your suggestion of 256MB of randomization for the stack SIMPLY IS NOT 
> ACCEPTABLE for a lot of uses. People on 32-bit archtiectures have issues 
> with usable virtual memory areas etc.
> 
> 
>>Red Hat is all smoke and mirrors anyway when it comes to security, just
>>like Microsoft.  This just reaffirms that.
> 
> 
> No. This just re-affirms that you are an inflexible person who cannot see 
> the big picture. You concentrate on your issues to the point where 
> everybody elses issues don't matter to you at all. That's a bad thing, in 
> case you haven't realized.
> 
> Intelligent people are able to work constructively in a world with many 
> different (and often contradictory) requirements. 
> 
> A person who cannot see outside his own sphere of interest can be very 
> driven, and can be very useful - in the "please keep uncle Fred tinkering 
> in the basement, but don't show him to any guests" kind of way. 
> 
> I have a clue for you: until PaX people can work with the rest of the
> world, PaX is _never_ going to matter in the real world. Rigidity is a
> total failure at all levels. 
> 
> Real engineering is about doing a good job balancing different issues.
> 
> Please remove me from the Cc when you start going off the deep end, btw.
> 
> 		Linus
> -
> 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.

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.0 (GNU/Linux)
Comment: Using GnuPG with Thunderbird - http://enigmail.mozdev.org

iD8DBQFB+z9ShDd4aOud5P8RAgOBAJ9ABXCQQDMKL2rcxDTZbAMKiGP8/QCfQ8HS
Pp3qP1W1Mi2CD9V1OgC61J8=
=i2Bl
-----END PGP SIGNATURE-----

Re: Patch 4/6 randomize the stack pointer

[Felipe Alfaro Solana]

On 27 Jan 2005, at 19:04, John Richard Moser wrote:

> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> What the hell?
>
> So instead of bringing something in that works, you bring something in
> that does significantly less, and gives no savings on overhead or patch
> complexity why?  So you can later come out and say "We're so great now
> we've increased the randomization by tweaking one variable aren't we
> cool!!!"?
>
> Red Hat is all smoke and mirrors anyway when it comes to security, just
> like Microsoft.  This just reaffirms that.

Please, keep politics out of this list and, instead, keep contributing 
with practical ideas and code.

Re: Patch 4/6 randomize the stack pointer

[Jirka Kosina]

On Thu, 27 Jan 2005, John Richard Moser wrote:

> Your patch 5/6 for mmap rand is also small.  1M is trivial, though I'd
> imagine mmap() rand would pose a bit more confusion in some cases at
> least, even for small ranges.
> Still, this is a joke, like OpenBSD's stackgap.

Also, besides security implications of stack randomization, there is one 
more aspect that should not be forgotten - stack randomization (even for 
quite small range) could be useful to distribute a pressure on cache 
(which may not be fully associative in all cases), so if everyone runs 
with stack on the same address, it could impose quite noticeable stress on 
some cachelines (those representing stack addresses), while other will 
be idling unused.

I thought that this was the original purpose of the "stack randomization" 
which is shipped for example by RedHat kernels, as the randomization is 
quite small and easy to bruteforce, so it can't serve too much as a buffer 
overflow protection.

-- 
JiKos.

Re: Patch 4/6 randomize the stack pointer

[Ingo Molnar]

* Jirka Kosina <jikos@jikos.cz> wrote:

> Also, besides security implications of stack randomization, there is
> one more aspect that should not be forgotten - stack randomization
> (even for quite small range) could be useful to distribute a pressure
> on cache (which may not be fully associative in all cases), so if
> everyone runs with stack on the same address, it could impose quite
> noticeable stress on some cachelines (those representing stack
> addresses), while other will be idling unused.
> 
> I thought that this was the original purpose of the "stack
> randomization" which is shipped for example by RedHat kernels, as the
> randomization is quite small and easy to bruteforce, so it can't serve
> too much as a buffer overflow protection.

Fedora kernels have 2MB of stack randomization. If 2MB is easy to
brute-force then 256MB is easy to brute-force nearly as much. But the
difference between _zero_ randomisation and 2MB randomisation is much
bigger than the difference between 2MB and 256MB of randomisation.

example: if there is no randomisation and e.g. there's an up to 100
bytes buffer-overflow in a UDP based service, then a single-packet
remote attack may become possible, and an automated worm has an easy
'vector to spread'. (worms these days are mainly limited by bandwidth,
so the number of packets it needs to spread is crutial. Also,
detection/prevention of a worm is easier if the attacker has to send
multiple packets in a row.)

some quick calculations about how the economics of attack look like if
there is randomisation in place:

If the hole has a possibility to inject a 'padding invariant' into the
attack (either NOPs into the shell code, so that a jump address can be
'fuzzy', or e.g. "././././" padding into a pathname/URL attack string),
so that the attack can use a 'fuzzy' address accurate only to the size
of padding, then the brute-forcing can be reduced to ~2MB/100bytes==20
thousand tries. If there is randomisation then a single-packet remote
attack needs to become a ~20-thousand packets brute-force attack. The
box is by no means in the clear against attacks, but worms become
uneconomic.

if the attack needs a specific address (or offset) to the stack and
there is no invariant then 2MB of of randomisation requires 2 million
tries to do the brute-force-attack.

with 256MB of randomisation and the possibility of an invariant, the
same attack would become a 2 million packets brute-force attack. A site
that didnt notice a 10-thousand packets attack probably wont notice a 2
million packets attack either. Plus the site is still vulnerable: 2
million packets (which with a 100 bytes attack size takes ~20 minutes
over broadband) and it's gone.

with no invariant and 256 million packets needed for an attack, it will
take over a day (over broadband) to brute-force a box - and security
purists would still consider the box vulnerable.

conclusion: stack randomisation (and other VM randomisations) are not a
tool against local attacks (which are much easier and faster to
brute-force) or against targeted remote attacks, but mainly a tool to
degrade the economy of automated remote attacks.

256 MB of stack randomisation negatively impacts the VM layout and
creates all sorts of problems, so it's really impractical. If your only
goal is to maximize security, then clearly, the more randomisation, the
better. If you have other goals as well (e.g. my goal is to make
security as painless as possible, so that _other_ people who dont
usually care about security end up using our stuff too) then you will
settle for somewhere inbetween. We started with 8MB in Fedora but that
already caused some problems so we decreased it to 2MB and that worked
pretty well on 32-bit systems. 64K is probably too low but is still a
good start and much better than nothing.

Note that 64-bit systems are different, there we can do a pretty good
grade of randomisation as VM space is plenty.

	Ingo

Re: Patch 4/6 randomize the stack pointer

[David Lang]

even requireing a 64k attack to defeat randomization changes an attack 
from N packets to ~45+N packets. This many packets gives a firewall/IDS a 
pretty solid signature to use to identify the difference between an attack 
and legitiamate traffic, it also gives a reactive IDS system a chance to 
terminate the connection before the attack payload (which is in the N 
packets) arrives.

David Lang

On Fri, 28 Jan 2005, Ingo Molnar wrote:

> Date: Fri, 28 Jan 2005 06:58:35 +0100
> From: Ingo Molnar <mingo@elte.hu>
> To: Jirka Kosina <jikos@jikos.cz>
> Cc: Arjan van de Ven <arjan@infradead.org>, linux-kernel@vger.kernel.org,
>     akpm@osdl.org, torvalds@osdl.org
> Subject: Re: Patch 4/6  randomize the stack pointer
> 
>
> * Jirka Kosina <jikos@jikos.cz> wrote:
>
>> Also, besides security implications of stack randomization, there is
>> one more aspect that should not be forgotten - stack randomization
>> (even for quite small range) could be useful to distribute a pressure
>> on cache (which may not be fully associative in all cases), so if
>> everyone runs with stack on the same address, it could impose quite
>> noticeable stress on some cachelines (those representing stack
>> addresses), while other will be idling unused.
>>
>> I thought that this was the original purpose of the "stack
>> randomization" which is shipped for example by RedHat kernels, as the
>> randomization is quite small and easy to bruteforce, so it can't serve
>> too much as a buffer overflow protection.
>
> Fedora kernels have 2MB of stack randomization. If 2MB is easy to
> brute-force then 256MB is easy to brute-force nearly as much. But the
> difference between _zero_ randomisation and 2MB randomisation is much
> bigger than the difference between 2MB and 256MB of randomisation.
>
> example: if there is no randomisation and e.g. there's an up to 100
> bytes buffer-overflow in a UDP based service, then a single-packet
> remote attack may become possible, and an automated worm has an easy
> 'vector to spread'. (worms these days are mainly limited by bandwidth,
> so the number of packets it needs to spread is crutial. Also,
> detection/prevention of a worm is easier if the attacker has to send
> multiple packets in a row.)
>
> some quick calculations about how the economics of attack look like if
> there is randomisation in place:
>
> If the hole has a possibility to inject a 'padding invariant' into the
> attack (either NOPs into the shell code, so that a jump address can be
> 'fuzzy', or e.g. "././././" padding into a pathname/URL attack string),
> so that the attack can use a 'fuzzy' address accurate only to the size
> of padding, then the brute-forcing can be reduced to ~2MB/100bytes==20
> thousand tries. If there is randomisation then a single-packet remote
> attack needs to become a ~20-thousand packets brute-force attack. The
> box is by no means in the clear against attacks, but worms become
> uneconomic.
>
> if the attack needs a specific address (or offset) to the stack and
> there is no invariant then 2MB of of randomisation requires 2 million
> tries to do the brute-force-attack.
>
> with 256MB of randomisation and the possibility of an invariant, the
> same attack would become a 2 million packets brute-force attack. A site
> that didnt notice a 10-thousand packets attack probably wont notice a 2
> million packets attack either. Plus the site is still vulnerable: 2
> million packets (which with a 100 bytes attack size takes ~20 minutes
> over broadband) and it's gone.
>
> with no invariant and 256 million packets needed for an attack, it will
> take over a day (over broadband) to brute-force a box - and security
> purists would still consider the box vulnerable.
>
> conclusion: stack randomisation (and other VM randomisations) are not a
> tool against local attacks (which are much easier and faster to
> brute-force) or against targeted remote attacks, but mainly a tool to
> degrade the economy of automated remote attacks.
>
> 256 MB of stack randomisation negatively impacts the VM layout and
> creates all sorts of problems, so it's really impractical. If your only
> goal is to maximize security, then clearly, the more randomisation, the
> better. If you have other goals as well (e.g. my goal is to make
> security as painless as possible, so that _other_ people who dont
> usually care about security end up using our stuff too) then you will
> settle for somewhere inbetween. We started with 8MB in Fedora but that
> already caused some problems so we decreased it to 2MB and that worked
> pretty well on 32-bit systems. 64K is probably too low but is still a
> good start and much better than nothing.
>
> Note that 64-bit systems are different, there we can do a pretty good
> grade of randomisation as VM space is plenty.
>
> 	Ingo
> -
> 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/
>

-- 
There are two ways of constructing a software design. One way is to make it so simple that there are obviously no deficiencies. And the other way is to make it so complicated that there are no obvious deficiencies.
  -- C.A.R. Hoare

Re: Patch 4/6 randomize the stack pointer

[Arjan van de Ven]

> I thought that this was the original purpose of the "stack randomization" 
> which is shipped for example by RedHat kernels, as the randomization is 
> quite small and easy to bruteforce, so it can't serve too much as a buffer 
> overflow protection.

correct; that was for the p4 hyperthreading case (that code fwiw is
still in the 2.6 mainline kernel and active; it randomizes over an 8k
region for this purpose)

Re: Patch 4/6 randomize the stack pointer

[Julien TINNES]

Not very important but ((get_random_int() % 4096) << 4) could be 
optimized into get_random_int() & 0xFFF0. Because 4096 is a power of 2 
you won't loose any entropy by doing  & 0xFFF instead of %4096

Regards,

-- 
Julien TINNES - & france telecom - R&D Division/MAPS/NSS
Research Engineer - Internet/Intranet Security
GPG: C050 EF1A 2919 FD87 57C4 DEDD E778 A9F0 14B9 C7D6

Re: Patch 4/6 randomize the stack pointer

[H. Peter Anvin]

Followup to:  <41F94462.7080108@francetelecom.REMOVE.com>
By author:    Julien TINNES <julien.tinnes.NOSPAM@francetelecom.REMOVE.com>
In newsgroup: linux.dev.kernel
>
> Not very important but ((get_random_int() % 4096) << 4) could be 
> optimized into get_random_int() & 0xFFF0. Because 4096 is a power of 2 
> you won't loose any entropy by doing  & 0xFFF instead of %4096
> 

.. and gcc knows that.

: tazenda 8 ; cat testme.c
extern unsigned int get_random_int(void);

unsigned int test(void)
{
  return (get_random_int() % 4096) << 4;
}
: tazenda 9 ; objdump -dr testme.o

testme.o:     file format elf64-x86-64

Disassembly of section .text:

0000000000000000 <test>:
   0:   48 83 ec 08             sub    $0x8,%rsp
   4:   e8 00 00 00 00          callq  9 <test+0x9>
                        5: R_X86_64_PC32
   get_random_int+0xfffffffffffffffc
   9:   25 ff 0f 00 00          and    $0xfff,%eax
   e:   48 83 c4 08             add    $0x8,%rsp
  12:   c1 e0 04                shl    $0x4,%eax
  15:   c3                      retq
: tazenda 10 ; gcc -m32 -O2 -fomit-frame-pointer -g -c testme.c
: tazenda 11 ; objdump -dr testme.o

testme.o:     file format elf32-i386

Disassembly of section .text:

00000000 <test>:
   0:   83 ec 0c                sub    $0xc,%esp
   3:   e8 fc ff ff ff          call   4 <test+0x4>
                        4: R_386_PC32   get_random_int
   8:   25 ff 0f 00 00          and    $0xfff,%eax
   d:   83 c4 0c                add    $0xc,%esp
  10:   c1 e0 04                shl    $0x4,%eax
  13:   c3                      ret
: tazenda 12 ;

Re: Patch 4/6 randomize the stack pointer

[Roland Dreier]

    Julien> Not very important but ((get_random_int() % 4096) << 4)
    Julien> could be optimized into get_random_int() & 0xFFF0.

    HPA> .. and gcc knows that.

    HPA>    8:   25 ff 0f 00 00          and    $0xfff,%eax
    HPA>    d:   83 c4 0c                add    $0xc,%esp
    HPA>   10:   c1 e0 04                shl    $0x4,%eax

Actually gcc isn't quite that smart (since it obviously can't
understand the semantics of get_random int()).  The original point was
that the "shl $0x4" can be avoided by directly &'ing with 0xfff0, not
that "% 4096" can be strength reduced to "& 0xfff".

 - R.

Re: Patch 4/6 randomize the stack pointer

[H. Peter Anvin]

Roland Dreier wrote:
>     Julien> Not very important but ((get_random_int() % 4096) << 4)
>     Julien> could be optimized into get_random_int() & 0xFFF0.
> 
>     HPA> .. and gcc knows that.
> 
>     HPA>    8:   25 ff 0f 00 00          and    $0xfff,%eax
>     HPA>    d:   83 c4 0c                add    $0xc,%esp
>     HPA>   10:   c1 e0 04                shl    $0x4,%eax
> 
> Actually gcc isn't quite that smart (since it obviously can't
> understand the semantics of get_random int()).  The original point was
> that the "shl $0x4" can be avoided by directly &'ing with 0xfff0, not
> that "% 4096" can be strength reduced to "& 0xfff".
> 

Oh, right.  D'oh!  :)

	-hpa

Re: Patch 4/6 randomize the stack pointer

[Horst von Brand]

Julien TINNES <julien.tinnes.NOSPAM@francetelecom.REMOVE.com> said:
> Not very important but ((get_random_int() % 4096) << 4) could be 
> optimized into get_random_int() & 0xFFF0.

Check first if the compiler doesn't do it by itself.
-- 
Dr. Horst H. von Brand                   User #22616 counter.li.org
Departamento de Informatica                     Fono: +56 32 654431
Universidad Tecnica Federico Santa Maria              +56 32 654239
Casilla 110-V, Valparaiso, Chile                Fax:  +56 32 797513

Re: Patch 4/6 randomize the stack pointer

[Julien TINNES]

Horst von Brand wrote:
> Julien TINNES <julien.tinnes.NOSPAM@francetelecom.REMOVE.com> said:
> 
>>Not very important but ((get_random_int() % 4096) << 4) could be 
>>optimized into get_random_int() & 0xFFF0.
> 
> 
> Check first if the compiler doesn't do it by itself.

The compiler cannot guess that get_random_int() gives a random result. 
%4096 and & 0xFFF is'nt the same operation. But (get_random_int() % 
4096) and (get_random_int() & 0xFFF) gives the same result: a random 
number between 0 and 4095, without loss of entropy because 0xFFF has no 
0 bit.

-- 
Julien TINNES - & france telecom - R&D Division/MAPS/NSS
Research Engineer - Internet/Intranet Security
GPG: C050 EF1A 2919 FD87 57C4 DEDD E778 A9F0 14B9 C7D6

Re: Patch 4/6 randomize the stack pointer

[Christoph Hellwig]

> +		p = arch_align_stack((unsigned long)p);

looking at the code p already is unsigned long, so the cast is not needed.

Re: Patch 4/6 randomize the stack pointer

[Arjan van de Ven]

On Thu, Jan 27, 2005 at 08:23:35PM +0000, Christoph Hellwig wrote:
> > +		p = arch_align_stack((unsigned long)p);
> 
> looking at the code p already is unsigned long, so the cast is not needed.

yeah

how about this one instead ?


The patch below replaces the existing 8Kb randomisation of the userspace
stack pointer (which is currently only done for Hyperthreaded P-IVs) with a
more general randomisation over a 64Kb range. 64Kb is not a lot, but it's a
start and once the dust settles we can increase this value to a more
agressive value.


Signed-off-by Arjan van de Ven <arjanv@redhat.com>

diff -purN step1/arch/i386/kernel/process.c step2/arch/i386/kernel/process.c
--- step1/arch/i386/kernel/process.c	2005-01-26 18:24:35.000000000 +0100
+++ step2/arch/i386/kernel/process.c	2005-01-27 21:10:19.000000000 +0100
@@ -36,6 +36,7 @@
 #include <linux/module.h>
 #include <linux/kallsyms.h>
 #include <linux/ptrace.h>
+#include <linux/random.h>
 
 #include <asm/uaccess.h>
 #include <asm/pgtable.h>
@@ -828,3 +829,9 @@ 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() % 4096) << 4);
+	return sp & ~0xf;
+}
diff -purN step1/arch/x86_64/kernel/process.c step2/arch/x86_64/kernel/process.c
--- step1/arch/x86_64/kernel/process.c	2005-01-26 18:24:49.000000000 +0100
+++ step2/arch/x86_64/kernel/process.c	2005-01-27 21:10:19.000000000 +0100
@@ -743,3 +743,10 @@ int dump_task_regs(struct task_struct *t
  
 	return 1;
 }
+
+unsigned long arch_align_stack(unsigned long sp)
+{
+	if (randomize_vs_space)
+		sp -= ((get_random_int() % 4096) << 4);
+	return sp & ~0xf;
+}
diff -purN step1/fs/binfmt_elf.c step2/fs/binfmt_elf.c
--- step1/fs/binfmt_elf.c	2005-01-27 21:09:32.000000000 +0100
+++ step2/fs/binfmt_elf.c	2005-01-27 21:18:58.000000000 +0100
@@ -165,21 +165,14 @@ create_elf_tables(struct linux_binprm *b
 	if (k_platform) {
 		size_t len = strlen(k_platform) + 1;
 
-#ifdef CONFIG_X86_HT
 		/*
 		 * In some cases (e.g. Hyper-Threading), we want to avoid L1
 		 * evictions by the processes running on the same package. One
 		 * thing we can do is to shuffle the initial stack for them.
-		 *
-		 * The conditionals here are unneeded, but kept in to make the
-		 * code behaviour the same as pre change unless we have
-		 * hyperthreaded processors. This should be cleaned up
-		 * before 2.6
 		 */
 	 
-		if (smp_num_siblings > 1)
-			STACK_ALLOC(p, ((current->pid % 64) << 7));
-#endif
+		p = arch_align_stack(p);
+
 		u_platform = (elf_addr_t __user *)STACK_ALLOC(p, len);
 		if (__copy_to_user(u_platform, k_platform, len))
 			return -EFAULT;
diff -purN step1/fs/exec.c step2/fs/exec.c
--- step1/fs/exec.c	2005-01-27 21:09:32.000000000 +0100
+++ step2/fs/exec.c	2005-01-27 21:18:37.000000000 +0100
@@ -400,7 +400,8 @@ int setup_arg_pages(struct linux_binprm 
 	while (i < MAX_ARG_PAGES)
 		bprm->page[i++] = NULL;
 #else
-	stack_base = stack_top - MAX_ARG_PAGES * PAGE_SIZE;
+	stack_base = arch_align_stack(STACK_TOP - MAX_ARG_PAGES*PAGE_SIZE);
+	stack_base = PAGE_ALIGN(stack_base);
 	bprm->p += stack_base;
 	mm->arg_start = bprm->p;
 	arg_size = stack_top - (PAGE_MASK & (unsigned long) mm->arg_start);
diff -purN step1/include/asm-alpha/system.h step2/include/asm-alpha/system.h
--- step1/include/asm-alpha/system.h	2004-12-24 22:34:58.000000000 +0100
+++ step2/include/asm-alpha/system.h	2005-01-27 21:16:20.000000000 +0100
@@ -621,4 +621,6 @@ __cmpxchg(volatile void *ptr, unsigned l
 
 #endif /* __ASSEMBLY__ */
 
+#define arch_align_stack(x) (x)
+
 #endif
diff -purN step1/include/asm-arm/system.h step2/include/asm-arm/system.h
--- step1/include/asm-arm/system.h	2004-12-24 22:34:00.000000000 +0100
+++ step2/include/asm-arm/system.h	2005-01-27 21:16:37.000000000 +0100
@@ -383,6 +383,8 @@ static inline unsigned long __xchg(unsig
 
 #endif /* __ASSEMBLY__ */
 
+#define arch_align_stack(x) (x)
+
 #endif /* __KERNEL__ */
 
 #endif
diff -purN step1/include/asm-arm26/system.h step2/include/asm-arm26/system.h
--- step1/include/asm-arm26/system.h	2005-01-26 18:24:39.000000000 +0100
+++ step2/include/asm-arm26/system.h	2005-01-27 21:16:33.000000000 +0100
@@ -245,6 +245,8 @@ static inline unsigned long __xchg(unsig
 
 #endif /* __ASSEMBLY__ */
 
+#define arch_align_stack(x) (x)
+
 #endif /* __KERNEL__ */
 
 #endif
diff -purN step1/include/asm-cris/system.h step2/include/asm-cris/system.h
--- step1/include/asm-cris/system.h	2004-12-24 22:34:58.000000000 +0100
+++ step2/include/asm-cris/system.h	2005-01-27 21:16:41.000000000 +0100
@@ -69,4 +69,6 @@ extern inline unsigned long __xchg(unsig
   return x;
 }
 
+#define arch_align_stack(x) (x)
+
 #endif
diff -purN step1/include/asm-frv/system.h step2/include/asm-frv/system.h
--- step1/include/asm-frv/system.h	2005-01-26 18:24:39.000000000 +0100
+++ step2/include/asm-frv/system.h	2005-01-27 21:16:46.000000000 +0100
@@ -120,4 +120,6 @@ do {						\
 extern void die_if_kernel(const char *, ...) __attribute__((format(printf, 1, 2)));
 extern void free_initmem(void);
 
+#define arch_align_stack(x) (x)
+
 #endif /* _ASM_SYSTEM_H */
diff -purN step1/include/asm-h8300/system.h step2/include/asm-h8300/system.h
--- step1/include/asm-h8300/system.h	2004-12-24 22:34:33.000000000 +0100
+++ step2/include/asm-h8300/system.h	2005-01-27 21:16:49.000000000 +0100
@@ -144,4 +144,6 @@ static inline unsigned long __xchg(unsig
         asm("jmp @@0");			\
 })
 
+#define arch_align_stack(x) (x)
+
 #endif /* _H8300_SYSTEM_H */
diff -purN step1/include/asm-i386/system.h step2/include/asm-i386/system.h
--- step1/include/asm-i386/system.h	2005-01-26 18:24:39.000000000 +0100
+++ step2/include/asm-i386/system.h	2005-01-27 21:13:41.000000000 +0100
@@ -468,4 +468,6 @@ void enable_hlt(void);
 extern int es7000_plat;
 void cpu_idle_wait(void);
 
+extern unsigned long arch_align_stack(unsigned long sp);
+
 #endif
diff -purN step1/include/asm-ia64/system.h step2/include/asm-ia64/system.h
--- step1/include/asm-ia64/system.h	2005-01-26 18:24:39.000000000 +0100
+++ step2/include/asm-ia64/system.h	2005-01-27 21:17:08.000000000 +0100
@@ -285,6 +285,9 @@ do {						\
 #define ia64_platform_is(x) (strcmp(x, platform_name) == 0)
 
 void cpu_idle_wait(void);
+
+#define arch_align_stack(x) (x)
+
 #endif /* __KERNEL__ */
 
 #endif /* __ASSEMBLY__ */
diff -purN step1/include/asm-m32r/system.h step2/include/asm-m32r/system.h
--- step1/include/asm-m32r/system.h	2005-01-26 18:24:39.000000000 +0100
+++ step2/include/asm-m32r/system.h	2005-01-27 21:17:13.000000000 +0100
@@ -294,4 +294,6 @@ static __inline__ unsigned long __xchg(u
 #define set_mb(var, value) do { xchg(&var, value); } while (0)
 #define set_wmb(var, value) do { var = value; wmb(); } while (0)
 
+#define arch_align_stack(x) (x)
+
 #endif  /* _ASM_M32R_SYSTEM_H */
diff -purN step1/include/asm-m68k/system.h step2/include/asm-m68k/system.h
--- step1/include/asm-m68k/system.h	2004-12-24 22:35:23.000000000 +0100
+++ step2/include/asm-m68k/system.h	2005-01-27 21:17:25.000000000 +0100
@@ -194,6 +194,8 @@ static inline unsigned long __cmpxchg(vo
 					(unsigned long)(n),sizeof(*(ptr))))
 #endif
 
+#define arch_align_stack(x) (x)
+
 #endif /* __KERNEL__ */
 
 #endif /* _M68K_SYSTEM_H */
diff -purN step1/include/asm-m68knommu/system.h step2/include/asm-m68knommu/system.h
--- step1/include/asm-m68knommu/system.h	2004-12-24 22:35:00.000000000 +0100
+++ step2/include/asm-m68knommu/system.h	2005-01-27 21:17:21.000000000 +0100
@@ -281,5 +281,6 @@ cmpxchg(volatile int *p, int old, int ne
 })
 #endif
 #endif
+#define arch_align_stack(x) (x)
 
 #endif /* _M68KNOMMU_SYSTEM_H */
diff -purN step1/include/asm-mips/system.h step2/include/asm-mips/system.h
--- step1/include/asm-mips/system.h	2004-12-24 22:34:32.000000000 +0100
+++ step2/include/asm-mips/system.h	2005-01-27 21:17:29.000000000 +0100
@@ -433,4 +433,6 @@ do {						\
 #define finish_arch_switch(rq, prev)	spin_unlock_irq(&(prev)->switch_lock)
 #define task_running(rq, p) 		((rq)->curr == (p) || spin_is_locked(&(p)->switch_lock))
 
+#define arch_align_stack(x) (x)
+
 #endif /* _ASM_SYSTEM_H */
diff -purN step1/include/asm-parisc/system.h step2/include/asm-parisc/system.h
--- step1/include/asm-parisc/system.h	2005-01-26 18:24:39.000000000 +0100
+++ step2/include/asm-parisc/system.h	2005-01-27 21:17:36.000000000 +0100
@@ -205,4 +205,6 @@ extern spinlock_t pa_tlb_lock;
 
 #endif
 
+#define arch_align_stack(x) (x)
+
 #endif
diff -purN step1/include/asm-ppc/system.h step2/include/asm-ppc/system.h
--- step1/include/asm-ppc/system.h	2005-01-26 18:24:39.000000000 +0100
+++ step2/include/asm-ppc/system.h	2005-01-27 21:17:43.000000000 +0100
@@ -201,5 +201,7 @@ __cmpxchg(volatile void *ptr, unsigned l
 				    (unsigned long)_n_, sizeof(*(ptr))); \
   })
 
+#define arch_align_stack(x) (x)
+
 #endif /* __KERNEL__ */
 #endif /* __PPC_SYSTEM_H */
diff -purN step1/include/asm-ppc64/system.h step2/include/asm-ppc64/system.h
--- step1/include/asm-ppc64/system.h	2005-01-26 18:24:39.000000000 +0100
+++ step2/include/asm-ppc64/system.h	2005-01-27 21:17:39.000000000 +0100
@@ -300,5 +300,7 @@ __cmpxchg(volatile void *ptr, unsigned l
  */
 #define NET_IP_ALIGN   0
 
+#define arch_align_stack(x) (x)
+
 #endif /* __KERNEL__ */
 #endif
diff -purN step1/include/asm-s390/system.h step2/include/asm-s390/system.h
--- step1/include/asm-s390/system.h	2005-01-26 18:24:39.000000000 +0100
+++ step2/include/asm-s390/system.h	2005-01-27 21:17:46.000000000 +0100
@@ -461,6 +461,8 @@ extern void (*_machine_restart)(char *co
 extern void (*_machine_halt)(void);
 extern void (*_machine_power_off)(void);
 
+#define arch_align_stack(x) (x)
+
 #endif /* __KERNEL__ */
 
 #endif
diff -purN step1/include/asm-sh/system.h step2/include/asm-sh/system.h
--- step1/include/asm-sh/system.h	2004-12-24 22:35:28.000000000 +0100
+++ step2/include/asm-sh/system.h	2005-01-27 21:17:55.000000000 +0100
@@ -259,4 +259,6 @@ static __inline__ unsigned long __xchg(u
 void disable_hlt(void);
 void enable_hlt(void);
 
+#define arch_align_stack(x) (x)
+
 #endif
diff -purN step1/include/asm-sh64/system.h step2/include/asm-sh64/system.h
--- step1/include/asm-sh64/system.h	2004-12-24 22:35:15.000000000 +0100
+++ step2/include/asm-sh64/system.h	2005-01-27 21:17:51.000000000 +0100
@@ -191,4 +191,6 @@ extern void print_seg(char *file,int lin
 
 #define PL() printk("@ <%s,%s:%d>\n",__FILE__,__FUNCTION__,__LINE__)
 
+#define arch_align_stack(x) (x)
+
 #endif /* __ASM_SH64_SYSTEM_H */
diff -purN step1/include/asm-sparc/system.h step2/include/asm-sparc/system.h
--- step1/include/asm-sparc/system.h	2004-12-24 22:35:23.000000000 +0100
+++ step2/include/asm-sparc/system.h	2005-01-27 21:18:04.000000000 +0100
@@ -257,4 +257,6 @@ extern void die_if_kernel(char *str, str
 
 #endif /* __ASSEMBLY__ */
 
+#define arch_align_stack(x) (x)
+
 #endif /* !(__SPARC_SYSTEM_H) */
diff -purN step1/include/asm-sparc64/system.h step2/include/asm-sparc64/system.h
--- step1/include/asm-sparc64/system.h	2004-12-24 22:33:48.000000000 +0100
+++ step2/include/asm-sparc64/system.h	2005-01-27 21:17:59.000000000 +0100
@@ -337,4 +337,6 @@ __cmpxchg(volatile void *ptr, unsigned l
 
 #endif /* !(__ASSEMBLY__) */
 
+#define arch_align_stack(x) (x)
+
 #endif /* !(__SPARC64_SYSTEM_H) */
diff -purN step1/include/asm-v850/system.h step2/include/asm-v850/system.h
--- step1/include/asm-v850/system.h	2004-12-24 22:35:23.000000000 +0100
+++ step2/include/asm-v850/system.h	2005-01-27 21:18:11.000000000 +0100
@@ -106,6 +106,9 @@ extern inline unsigned long __xchg (unsi
 	local_irq_restore (flags);
 
 	return tmp;
+
 }
 
+#define arch_align_stack(x) (x)
+
 #endif /* __V850_SYSTEM_H__ */
diff -purN step1/include/asm-x86_64/system.h step2/include/asm-x86_64/system.h
--- step1/include/asm-x86_64/system.h	2005-01-26 18:24:39.000000000 +0100
+++ step2/include/asm-x86_64/system.h	2005-01-27 21:13:49.000000000 +0100
@@ -338,4 +338,6 @@ void enable_hlt(void);
 #define HAVE_EAT_KEY
 void eat_key(void);
 
+extern unsigned long arch_align_stack(unsigned long sp);
+
 #endif

Re: Patch 4/6 randomize the stack pointer

[Christoph Hellwig]

> The patch below replaces the existing 8Kb randomisation of the userspace
> stack pointer (which is currently only done for Hyperthreaded P-IVs) with a
> more general randomisation over a 64Kb range. 64Kb is not a lot, but it's a
> start and once the dust settles we can increase this value to a more
> agressive value.

Why are we doing this for x86 only, btw? 

> +unsigned long arch_align_stack(unsigned long sp)
> +{
> +	if (randomize_va_space)
> +		sp -= ((get_random_int() % 4096) << 4);
> +	return sp & ~0xf;
> +}

this looks like it'd work nicely on all architectures.

Re: Patch 4/6 randomize the stack pointer

[Arjan van de Ven]

On Thu, 2005-01-27 at 20:32 +0000, Christoph Hellwig wrote:
> > The patch below replaces the existing 8Kb randomisation of the userspace
> > stack pointer (which is currently only done for Hyperthreaded P-IVs) with a
> > more general randomisation over a 64Kb range. 64Kb is not a lot, but it's a
> > start and once the dust settles we can increase this value to a more
> > agressive value.
> 
> Why are we doing this for x86 only, btw? 
> 
> > +unsigned long arch_align_stack(unsigned long sp)
> > +{
> > +	if (randomize_va_space)
> > +		sp -= ((get_random_int() % 4096) << 4);
> > +	return sp & ~0xf;
> > +}
> 
> this looks like it'd work nicely on all architectures.

the problem is that the <<4 is the minimum x86 stack pointer alignment.
That value differs per architecture afaics.....

Re: Patch 4/6 randomize the stack pointer

[Rik van Riel]

On Thu, 27 Jan 2005, Christoph Hellwig wrote:

>> +unsigned long arch_align_stack(unsigned long sp)
>> +{
>> +	if (randomize_va_space)
>> +		sp -= ((get_random_int() % 4096) << 4);
>> +	return sp & ~0xf;
>> +}
>
> this looks like it'd work nicely on all architectures.

I guess it should work for all architectures using ELF,
not sure if it might break some of the more obscure
architectures ...

-- 
"Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, you are,
by definition, not smart enough to debug it." - Brian W. Kernighan

Re: Patch 4/6 randomize the stack pointer

[Christoph Hellwig]

On Thu, Jan 27, 2005 at 03:40:48PM -0500, Rik van Riel wrote:
> On Thu, 27 Jan 2005, Christoph Hellwig wrote:
> 
> >>+unsigned long arch_align_stack(unsigned long sp)
> >>+{
> >>+	if (randomize_va_space)
> >>+		sp -= ((get_random_int() % 4096) << 4);
> >>+	return sp & ~0xf;
> >>+}
> >
> >this looks like it'd work nicely on all architectures.
> 
> I guess it should work for all architectures using ELF,
> not sure if it might break some of the more obscure
> architectures ...

So it works for all CONFIG_MMU architectures.  Arjan mentioned that
the minimum stack alignment might be different, so the 4 should
become a per-arch constant and we can make the code unconditional
for CONFIG_MMU?

Re: Patch 4/6 randomize the stack pointer

[Arjan van de Ven]

On Thu, 2005-01-27 at 20:42 +0000, Christoph Hellwig wrote:
> On Thu, Jan 27, 2005 at 03:40:48PM -0500, Rik van Riel wrote:
> > On Thu, 27 Jan 2005, Christoph Hellwig wrote:
> > 
> > >>+unsigned long arch_align_stack(unsigned long sp)
> > >>+{
> > >>+	if (randomize_va_space)
> > >>+		sp -= ((get_random_int() % 4096) << 4);
> > >>+	return sp & ~0xf;
> > >>+}
> > >
> > >this looks like it'd work nicely on all architectures.
> > 
> > I guess it should work for all architectures using ELF,
> > not sure if it might break some of the more obscure
> > architectures ...
> 
> So it works for all CONFIG_MMU architectures.  Arjan mentioned that
> the minimum stack alignment might be different, so the 4 should
> become a per-arch constant and we can make the code unconditional
> for CONFIG_MMU?

and then there are architectures with an upward growing stack....
and maybe the alignment will even vary per cpu type (runtime) for some
architectures? Maybe arch maintainers can jump in quickly to say if a
scheme with a per arch shift factor would be sufficient or if all kinds
of horrors would creep up for them  (in which case a per arch function
would be more suitable)

Re: Patch 4/6 randomize the stack pointer

[Linus Torvalds]

On Thu, 27 Jan 2005, Arjan van de Ven wrote:
> 
> and then there are architectures with an upward growing stack....
> and maybe the alignment will even vary per cpu type (runtime) for some
> architectures? Maybe arch maintainers can jump in quickly to say if a
> scheme with a per arch shift factor would be sufficient or if all kinds
> of horrors would creep up for them  (in which case a per arch function
> would be more suitable)

I think it's much nicer to just have the generic randomization hook, and 
not try to do something fancy. It's not like this is complex, and it's a 
lot better to have the same (simple) code duplicated five times than it is 
to make a (much more complex) interface to have things shared.

		Linus

Re: Patch 5/6 randomize mmap addresses

[Arjan van de Ven]

The patch below randomizes the starting point of the mmap area.
This has the effect that all non-prelinked shared libaries and all bigger
malloc()s will be randomized between various invocations of the binary.
Prelinked binaries get a address-hint from ld.so in their mmap and are thus
exempt from this randomisation, in order to not break the prelink advantage.
The randomisation range is 1 megabyte (this is bigger than the stack
randomisation since the stack randomisation only needs 16 bytes alignment
while the mmap needs page alignment, a 64kb range would not have given
enough entropy to be effective)

Signed-off-by: Arjan van de Ven <arjan@infradead.org>


diff -purN linux-step/arch/i386/mm/mmap.c linux-step5/arch/i386/mm/mmap.c
--- linux-step/arch/i386/mm/mmap.c	2004-12-24 22:34:33.000000000 +0100
+++ linux-step5/arch/i386/mm/mmap.c	2005-01-27 10:23:17.000000000 +0100
@@ -26,6 +26,7 @@
 
 #include <linux/personality.h>
 #include <linux/mm.h>
+#include <linux/random.h>
 
 /*
  * Top of mmap area (just below the process stack).
@@ -38,13 +39,17 @@
 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;
+
+	if (current->flags & PF_RANDOMIZE)
+		random_factor = get_random_int() % (1024*1024);
 
 	if (gap < MIN_GAP)
 		gap = MIN_GAP;
 	else if (gap > MAX_GAP)
 		gap = MAX_GAP;
 
-	return TASK_SIZE - (gap & PAGE_MASK);
+	return PAGE_ALIGN(TASK_SIZE - gap - random_factor);
 }
 
 /*

Re: Patch 6/6 default enable randomisation for -mm

[Arjan van de Ven]

For -mm only to increease testing; enable the randomisations by default

Signed-off-by: Arjan van de Ven <arjan@infradead.org>

diff -purN linux-step5/kernel/sysctl.c linux-step6/kernel/sysctl.c
--- linux-step5/kernel/sysctl.c	2005-01-27 10:22:14.000000000 +0100
+++ linux-step6/kernel/sysctl.c	2005-01-27 10:35:31.000000000 +0100
@@ -122,7 +122,7 @@ extern int sysctl_hz_timer;
 extern int acct_parm[];
 #endif
 
-int randomize_va_space = 0;
+int randomize_va_space = 1;
 
 static int parse_table(int __user *, int, void __user *, size_t __user *, void __user *, size_t,
 		       ctl_table *, void **);

Re: Patch 0/6 virtual address space randomisation

[Julien TINNES]

Arjan van de Ven wrote:
> The randomisation patch series introduces infrastructure and functionality
> that causes certain parts of a process' virtual address space to be
> different for each invocation of the process. The purpose of this is to
> raise the bar on buffer overflow exploits; full randomisation makes it not
> possible to use absolute addresses in the exploit.
> 

I think it is worth mentioning that this is part of PaX ASLR, but with 
some changes and simplification.
I have some questions about the changes:

for RANDMMAP why doing randomization in mmap_base() and not in 
arch_pick_mmap_layout? You miss a whole case here where legacy layout is 
used.

-- 
Julien TINNES - & france telecom - R&D Division/MAPS/NSS
Research Engineer - Internet/Intranet Security
GPG: C050 EF1A 2919 FD87 57C4 DEDD E778 A9F0 14B9 C7D6

Re: Patch 0/6 virtual address space randomisation

[Arjan van de Ven]

On Thu, 2005-01-27 at 12:45 +0100, Julien TINNES wrote:
> Arjan van de Ven wrote:
> > The randomisation patch series introduces infrastructure and functionality
> > that causes certain parts of a process' virtual address space to be
> > different for each invocation of the process. The purpose of this is to
> > raise the bar on buffer overflow exploits; full randomisation makes it not
> > possible to use absolute addresses in the exploit.
> > 
> 
> I think it is worth mentioning that this is part of PaX ASLR, but with 
> some changes and simplification.

it actually came from Exec-Shield not PaX

> I have some questions about the changes:
> 
> for RANDMMAP why doing randomization in mmap_base() and not in 
> arch_pick_mmap_layout? You miss a whole case here where legacy layout is 
> used.

legacy layout will want a different randomisation; it'll come in a
separate, incremental patch.

Re: Patch 0/6 virtual address space randomisation

[John Richard Moser]

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



Arjan van de Ven wrote:
> On Thu, 2005-01-27 at 12:45 +0100, Julien TINNES wrote:
> 
>>Arjan van de Ven wrote:
>>
>>>The randomisation patch series introduces infrastructure and functionality
>>>that causes certain parts of a process' virtual address space to be
>>>different for each invocation of the process. The purpose of this is to
>>>raise the bar on buffer overflow exploits; full randomisation makes it not
>>>possible to use absolute addresses in the exploit.
>>>
>>
>>I think it is worth mentioning that this is part of PaX ASLR, but with 
>>some changes and simplification.
> 
> 
> it actually came from Exec-Shield not PaX
> 

Yeah, if it came from PaX the randomization would actually be useful.
Sorry, I've just woken up and already explained in another post.

[...]

> 
> -
> 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.

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.0 (GNU/Linux)
Comment: Using GnuPG with Thunderbird - http://enigmail.mozdev.org

iD8DBQFB+SfwhDd4aOud5P8RArzvAJ91+7oeFvQyhfH5ovHkkWG7FQcazgCfchDA
4lxXXLmMA5PcZuICxoxnQGU=
=oXcE
-----END PGP SIGNATURE-----

Re: Patch 0/6 virtual address space randomisation

[Julien TINNES]

> 
> Yeah, if it came from PaX the randomization would actually be useful.
> Sorry, I've just woken up and already explained in another post.
> 

Please, no hard feelings.

Speaking about implementation of the non executable pages semantics on 
IA32, PaX and Exec-Shield are very different (well not that much since 
2.6 in fact because PAGEEXEC is now "segmentation when I can").
But when it comes to ASLR it's pretty much the same thing.

The only difference may be the (very small) randomization of the brk() 
managed heap on ET_EXEC (which is probably the more "hackish" feature of 
PaX ASLR) but it seems that Arjan is even going to propose a patch for 
that (Is this in ES too ?).

I think it's a great opportunity here to get the same basis for ASLR in 
PaX and ES merged into the vanilla kernel.
If it's only a matter of changing the number of randomized bits in an 
additional PaX patch, it's no problem! It's more important to have a 
correct basis, focus on that.

-- 
Julien TINNES - & france telecom - R&D Division/MAPS/NSS
Research Engineer - Internet/Intranet Security
GPG: C050 EF1A 2919 FD87 57C4 DEDD E778 A9F0 14B9 C7D6

Re: Patch 0/6 virtual address space randomisation

[John Richard Moser]

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



Julien TINNES wrote:
> 
>>
>> Yeah, if it came from PaX the randomization would actually be useful.
>> Sorry, I've just woken up and already explained in another post.
>>
> 
> Please, no hard feelings.
> 
> Speaking about implementation of the non executable pages semantics on
> IA32, PaX and Exec-Shield are very different (well not that much since
> 2.6 in fact because PAGEEXEC is now "segmentation when I can").
> But when it comes to ASLR it's pretty much the same thing.
> 
> The only difference may be the (very small) randomization of the brk()
> managed heap on ET_EXEC (which is probably the more "hackish" feature of
> PaX ASLR) but it seems that Arjan is even going to propose a patch for
> that (Is this in ES too ?).
> 
> I think it's a great opportunity here to get the same basis for ASLR in
> PaX and ES merged into the vanilla kernel.
> If it's only a matter of changing the number of randomized bits in an
> additional PaX patch, it's no problem! It's more important to have a
> correct basis, focus on that.
> 

I'm not at all familiar with the code, though PaX uses more fine-grained
binary markings in PT_PAX_FLAGS (requires a patched binutils, though I
guess a PaX system could just nuke PT_GNU_STACK from .load and replace
it with PT_PAX_FLAGS).  *shrug*

. . . ok so I've hacked at PaX' source a few times for fun, but I forgot
everything I saw, I swear. :)

whatever, at this point I've lost interest, as I'm starting to wonder
where my next meal will come from.

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

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.0 (GNU/Linux)
Comment: Using GnuPG with Thunderbird - http://enigmail.mozdev.org

iD4DBQFB+UeohDd4aOud5P8RAra3AJsEs0fJiQvqbp45ySUbUQT/TJkDRACYoYzq
nzy0VdUXiT84DEzzkPDVVQ==
=exFr
-----END PGP SIGNATURE-----

Re: Patch 0/6 virtual address space randomisation

[Arjan van de Ven]

On Thu, 2005-01-27 at 20:34 +0100, Julien TINNES wrote:
> > 
> > Yeah, if it came from PaX the randomization would actually be useful.
> > Sorry, I've just woken up and already explained in another post.
> > 
> 
> Please, no hard feelings.
> 
> Speaking about implementation of the non executable pages semantics on 
> IA32, PaX and Exec-Shield are very different (well not that much since 
> 2.6 in fact because PAGEEXEC is now "segmentation when I can").
> But when it comes to ASLR it's pretty much the same thing.
> 
> The only difference may be the (very small) randomization of the brk() 
> managed heap on ET_EXEC (which is probably the more "hackish" feature of 
> PaX ASLR) but it seems that Arjan is even going to propose a patch for 
> that (Is this in ES too ?).

Exec shield randomized brk() too yes.
However that is a both more dangerous and more invasive change to do
correctly (you have no idea how hard it is to get that right for
emacs...) so that's reserved for the second batch of patches once this
first batch is dealt with.

Re: Patch 0/6 virtual address space randomisation

[David Weinehall]

On Thu, Jan 27, 2005 at 09:13:04PM +0100, Arjan van de Ven wrote:
> On Thu, 2005-01-27 at 20:34 +0100, Julien TINNES wrote:
> > > 
> > > Yeah, if it came from PaX the randomization would actually be useful.
> > > Sorry, I've just woken up and already explained in another post.
> > > 
> > 
> > Please, no hard feelings.
> > 
> > Speaking about implementation of the non executable pages semantics on 
> > IA32, PaX and Exec-Shield are very different (well not that much since 
> > 2.6 in fact because PAGEEXEC is now "segmentation when I can").
> > But when it comes to ASLR it's pretty much the same thing.
> > 
> > The only difference may be the (very small) randomization of the brk() 
> > managed heap on ET_EXEC (which is probably the more "hackish" feature of 
> > PaX ASLR) but it seems that Arjan is even going to propose a patch for 
> > that (Is this in ES too ?).
> 
> Exec shield randomized brk() too yes.
> However that is a both more dangerous and more invasive change to do
> correctly (you have no idea how hard it is to get that right for
> emacs...) so that's reserved for the second batch of patches once this
> first batch is dealt with.

Oh, so you mean that we can both get a more secure system, *and* make
emacs stop working?  A win-win situation! =)


Regards: David Weinehall
-- 
 /) David Weinehall <tao@acc.umu.se> /) Northern lights wander      (\
//  Maintainer of the v2.0 kernel   //  Dance across the winter sky //
\)  http://www.acc.umu.se/~tao/    (/   Full colour fire           (/

Re: Patch 4/6 randomize the stack pointer

[linux]

> Why not compromise, if possible?  256M of randomization, but move the
> split up to 3.5/0.5 gig, if possible.  I seem to recall seeing an option
> (though I think it was UML) to do 3.5/0.5 before; and I'm used to "a
> little worse" meaning "microbenches say it's worse, but you won't notice
> it," so perhaps this would be a good compromise.  How well tuned can
> 3G/1G be?  Come on, 1G is just a big friggin' even number.

Ah, grasshopper, so much you have to learn...
In particular, prople these days are more likely to want to move the
split DOWN rather than UP.

First point: it is important that the split happens at an "even" boundary
for the highest-level page table.  This makes it as simple as possible to
copy the shared global pages into each process' page tables.

On typical x86, each table is 1024 entries long, so the top table maps
4G/1024 = 4M sections.

However, with PAE (Physical Address Extensions), a 32-bit page table
entry is no longer enough to hold the 36-bit physical address.  Instead,
the entries are 64 bits long, so only 512 fit into a page.  With a
4K page and 18 more bits from page tables, two levels will map only
30 bits of the 32-bit virtual address space.  So Intel added a small,
4-entry third-level page table.

With PAE, you are indeed limited to 1G boundaries.  (Unless you want to
seriously overhaul mm setup and teardown.)


Secondly, remember that, unless you want to pay a performance penalty
for enabling one of the highmem options, you have to fit ALL of physical
memory, PLUS memory-mapped IO (say around 128M) into the kernel's portion
of the address space.  512M of kernel space isn't enough unless you have
less than 512M (like 384M) of memory to keep track of.

That is getting less common, *especially* on servers.  (Which are
presumably an important target audience for buffer overflow defenses.)


Indeed, if you have a lot of RAM and you don't have a big database that
needs tons of virtual address space, it's usually worth moving the
split DOWN.


Now, what about the case where you have gobs of RAM and need a highmem
option anyway?  Well, there's a limit to what you can use high mem for.
Application memory and page cache, yes.  Kernel data structures, no.
You can't use it for dcache or inodes or network sockets or page
tables or the struct page array.

And the mem_map array of struct pages (on x86, it's 32 bytes per page,
or 1/128 of physical memory; 32M for a 4G machine) is a fixed overhead
that's subtracted before you even start.  Fully-populated 64G x86
machines need 512M of mem_map, and the remaining space isn't enough to
really run well in.

If you crunch kernel lowmem too tightly, that becomes the
performance-limiting resource.


Anyway, the split between user and kernel address space is mandated
by:
- Kernel space wants to be as bit as physical RAM if possible, or not
  more than 10x smaller if not.
- User space really depends on the application, but larger than 2-3x
  physical memory is pointless, as trying to actually use it all will
  swap you to death.

So for 1G of physical RAM, 3G:1G is pretty close to perfect.  It was
NOT pulled out of a hat.  Depending on your applications, you may be
able to get away with a smaller user virtual address space, which could
allow you to work with more RAM without needing to slow the kernel with
highmem code.



You'll find another discussion of the issues at
http://kerneltrap.org/node/2450
http://lwn.net/Articles/75174/

Finally, could I suggest a little more humility when addressing the
assembled linux-kernel developers?  I've seen Linus have to eat his
words a time or two, and I know I can't do as well.
http://marc.theaimsgroup.com/?m=91723854823435

Re: Patch 4/6 randomize the stack pointer

[John Richard Moser]

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



linux@horizon.com wrote:
>>Why not compromise, if possible?  256M of randomization, but move the
>>split up to 3.5/0.5 gig, if possible.  I seem to recall seeing an option
>>(though I think it was UML) to do 3.5/0.5 before; and I'm used to "a
>>little worse" meaning "microbenches say it's worse, but you won't notice
>>it," so perhaps this would be a good compromise.  How well tuned can
>>3G/1G be?  Come on, 1G is just a big friggin' even number.
> 
> 
> Ah, grasshopper, so much you have to learn...

I'm always learning, that's why I'm not stupid.  I hate dumb people who
just sit around and go "what?"  "OK it works like--"  "shut up I don't
care!  . . . . wut now?"

> In particular, prople these days are more likely to want to move the
> split DOWN rather than UP.
> 
> First point: it is important that the split happens at an "even" boundary
> for the highest-level page table.  This makes it as simple as possible to
> copy the shared global pages into each process' page tables.
> 
> On typical x86, each table is 1024 entries long, so the top table maps
> 4G/1024 = 4M sections.
> 
> However, with PAE (Physical Address Extensions), a 32-bit page table
> entry is no longer enough to hold the 36-bit physical address.  Instead,
> the entries are 64 bits long, so only 512 fit into a page.  With a
> 4K page and 18 more bits from page tables, two levels will map only
> 30 bits of the 32-bit virtual address space.  So Intel added a small,
> 4-entry third-level page table.
> 

Interesting.

> With PAE, you are indeed limited to 1G boundaries.  (Unless you want to
> seriously overhaul mm setup and teardown.)
> 

Yiiiiii x.x

> 
> Secondly, remember that, unless you want to pay a performance penalty
> for enabling one of the highmem options, you have to fit ALL of physical
> memory, PLUS memory-mapped IO (say around 128M) into the kernel's portion
> of the address space.  512M of kernel space isn't enough unless you have
> less than 512M (like 384M) of memory to keep track of.
> 
> That is getting less common, *especially* on servers.  (Which are
> presumably an important target audience for buffer overflow defenses.)
> 

Semantics, you can skip this but here's my understanding about the
situation:

ASLR is a code injection/ret2libc exploit defense, not a buffer overflow
bug defense.  True buffer overflow defense occurs in userspace.

ASLR and proper NX protections provide a more wide-ranged defense which
stops format string and heap/stack buffer overflow based attacks (and
possibly others) from using ret2libc or code injection exploits.

Stack based buffer overflow protection is available in userspace and
actually prevents some things not protected by kernel-level protections.
 ProPolice for example protects local pointers and local variables;
sometimes changing the contents of a variable (say a filename, or an
integer containing an encoded IP address) can give you a quick and dirty
information leak.

All defenses are important everywhere, not just on servers; although
they're probably less important on internal servers behind your
firewall/IDS/security net/DMZ because you need an insider to access
those, which often means someone skilled enough or with enough info
(passwords, etc) to bypass your security anyway (not that you shouldn't
make the best effort possible to stop them).

Some people don't agree with me (in fact I'm probably alone in this line
of thinking), but I'm of the persuasion that the best protection is most
important on the desktop; and second but roughly equal on exposed
servers (web/ftp servers).

This is because attackers can use desktops as drones, and they're very
exposed due to web browsers, ftp clients, IM clients, and P2P apps, not
to mention tons of other stuff that comes in contact with foreign data.
 Web servers have a few choice daemons, so there's a much smaller
codebase touching things that come from outside, meaning less of a
chance of an open bug touching the outside world.

Anyway, that's my rant :)

> 
> Indeed, if you have a lot of RAM and you don't have a big database that
> needs tons of virtual address space, it's usually worth moving the
> split DOWN.
> 

Or you have a big database that wants tons of virtual address space and
so you buy an amd64.  ;)

> 
> Now, what about the case where you have gobs of RAM and need a highmem
> option anyway?  Well, there's a limit to what you can use high mem for.
> Application memory and page cache, yes.  Kernel data structures, no.
> You can't use it for dcache or inodes or network sockets or page
> tables or the struct page array.
> 

o.o

> And the mem_map array of struct pages (on x86, it's 32 bytes per page,
> or 1/128 of physical memory; 32M for a 4G machine) is a fixed overhead
> that's subtracted before you even start.  Fully-populated 64G x86
> machines need 512M of mem_map, and the remaining space isn't enough to
> really run well in.
> 
> If you crunch kernel lowmem too tightly, that becomes the
> performance-limiting resource.
> 

ok so short version:  You don't need the VA on a low-end system, you
can't have the VA on a high-end system.  Solution:  Buy a 64 bit system.

> 
> Anyway, the split between user and kernel address space is mandated
> by:
> - Kernel space wants to be as bit as physical RAM if possible, or not
>   more than 10x smaller if not.
> - User space really depends on the application, but larger than 2-3x
>   physical memory is pointless, as trying to actually use it all will
>   swap you to death.
> 
> So for 1G of physical RAM, 3G:1G is pretty close to perfect.  It was
> NOT pulled out of a hat.  Depending on your applications, you may be
> able to get away with a smaller user virtual address space, which could
> allow you to work with more RAM without needing to slow the kernel with
> highmem code.
> 
> 
> 
> You'll find another discussion of the issues at
> http://kerneltrap.org/node/2450
> http://lwn.net/Articles/75174/
> 
> Finally, could I suggest a little more humility when addressing the
> assembled linux-kernel developers?  I've seen Linus have to eat his
> words a time or two, and I know I can't do as well.
> http://marc.theaimsgroup.com/?m=91723854823435
> 

I've been somewhat unfriendly, and should have approached things a
little more calmly; but I still hold firm on my assertions.  My attitude
may have been wrong, but I'm pretty sure everything I said was right.
(I know I got something wrong, but I'm not sure if it was on here, and
I'm pretty sure I fired off the erratta after finding my mistake.)

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

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.0 (GNU/Linux)
Comment: Using GnuPG with Thunderbird - http://enigmail.mozdev.org

iD8DBQFB/mq9hDd4aOud5P8RAjtvAJ0V5ofEhFwBLMHDZDynNWXuWe8M+wCfdDIy
hhAvW7ijrWhqXmW8FkMx2II=
=SvU6
-----END PGP SIGNATURE-----