[PATCH] avoid entropy starvation due to stack protection

[PATCH] avoid entropy starvation due to stack protection

[Stephan Mueller]

Hi Ted, kernel hackers,

Some time ago, I noticed the fact that for every newly
executed process, the function create_elf_tables requests 16 bytes of
randomness from get_random_bytes. This is easily visible when calling

while [ 1 ]
do
	cat /proc/sys/kernel/random/entropy_avail
	sleep 1
done

You would expect that this number does not change significantly with the
call. But in fact, it does drop significantly -- it should drop
by 256 (bit) per loop count due to the exec of cat and sleep unless we
hit the lower boundary where nothing is copied from the input_pool. See
graph at http://www.eperm.de/entropy_estimator_time.png which indicates
the entropy counter on an Ubuntu with KDE installed (x-axis: time since
user space boot). Starting around 50 seconds, I log into lightdm which
spawns many processes.

Each request to get_random_bytes retrieves (good) entropy from the
input_pool, if available. The entire logic of getting 16 bytes per exec
depletes good quality entropy on a fast scale that also affects /dev/random.

This alone is already a burn of entropy that leaves the kernel starved
of entropy much more than we want it to.

The receiver of that entropy for this is the stack protector of glibc.
The patch that added this behavior is found in
http://mirror.lividpenguin.com/pub/linux/kernel/people/akpm/patches/2.6/2.6.28-rc2/2.6.28-rc2-mm1/broken-out/elf-implement-at_random-for-glibc-prng-seeding.patch

Even when considering an initial installation process, you assume it
generates massive entropy due to copying 100s of megabytes of data to
disk. That entropy can already be retained for the first reboot of the
system to ensure that already the first start has sufficient entropy
available (which for example may be used to generate missing
cryptographic keys, e.g. for OpenSSH).

However, analyzing the installation process and the entropy behavior
again showed very surprising results. See graph at
http://www.eperm.de/entropy_estimator_time_install.png (x-axis: time
since mount of root partition; red line: installed data in MB (rhs),
black/blue lines: estimated entropy in input_pool (lhs)). The graph is
for the entire installation process of the RHEL 6.2 minimal
installation. The spike of entropy at the end is caused *only* because
of the grub installation (see that there is no data added to the hard disk).

I would have expected that the entropy rises to the top of 4096 early on
in the install cycle and stayed there. But then, after thinking some
more, it is clear why this is not the case: when installing rpm packages
from anaconda, you exec many processes (rpm -Uhv, the pre/post install
scripts of the RPM packages).

So, if we would not have had the grub installation phase, our entropy
count would still be low.

Now my question to kernel hackers: may I propose the addition of a new
entropy pool solely used for purposes within the kernel? The entropy
pool has the following characteristics:

- it is non-blocking similarly to nonblocking_pool

- it has the same size as nonblocking_pool

- it draws from input_pool until the entropy counter in the kernel pool
reaches the maximum of poolinfo->poolwords. Starting at that point, we
assume that the pool is filled with entropy completely and the SHA-1
hash including the back-mixing ensures the entropy is preserved as much
as possible. The pulling of the entropy from input_pool is identical to
the nonblocking_pool.

- after reaching the entropy limit, it will never be seeded again.

Bottom line: before reaching the threshold, the kernel pool behaves
exactly like the nonblocking_pool. After reaching the threshold, it
decouples itself from the input_pool.

May I further propose to replace the get_random_bytes invocation from
create_elf_tables with a call to the retrieval of random numbers from
the kernel pool?

I think that approach satisfies the requirement for stack protection and
ASLR as there is still no prediction possible of the random number.
Maybe even other in-kernel users can use that for sufficient good random
numbers.

When testing the patch, the following behavior of the entropy estimator is seen: http://www.eperm.de/entropy_estimator_time_patch.png -- compare that to the initial graph! The first minute, you have the low numbers as the kernel pool needs to fill. Once it is filled, the entropy climbs. The sharp reductions are due to the start of Firefox which seems to pull entropy.

See patch attached. It applies against vanilla version 3.6.

Thanks
Stephan

Signed-off-by: Stephan Mueller <smueller@chronox.de>

---

diff -purN linux-3.6/drivers/char/random.c linux-3.6-sm/drivers/char/random.c
--- linux-3.6/drivers/char/random.c	2012-10-01 01:47:46.000000000 +0200
+++ linux-3.6-sm/drivers/char/random.c	2012-12-11 11:51:58.997172447 +0100
@@ -404,11 +404,12 @@ static bool debug;
 module_param(debug, bool, 0644);
 #define DEBUG_ENT(fmt, arg...) do { \
 	if (debug) \
-		printk(KERN_DEBUG "random %04d %04d %04d: " \
+		printk(KERN_DEBUG "random %04d %04d %04d %04d: " \
 		fmt,\
 		input_pool.entropy_count,\
 		blocking_pool.entropy_count,\
 		nonblocking_pool.entropy_count,\
+		kernel_pool.entropy_count,\
 		## arg); } while (0)
 #else
 #define DEBUG_ENT(fmt, arg...) do {} while (0)
@@ -428,7 +429,11 @@ struct entropy_store {
 	__u32 *pool;
 	const char *name;
 	struct entropy_store *pull;
-	int limit;
+	int limit;	/* 0 -> no limit when extracting data (nonblocking)
+			 * 1 -> limit extracted data based on entropy counter
+			 * 2 -> no limit when extracting data and disabling
+			 *      use of seed source once pool has full entropy
+			 */
 
 	/* read-write data: */
 	spinlock_t lock;
@@ -443,6 +448,7 @@ struct entropy_store {
 static __u32 input_pool_data[INPUT_POOL_WORDS];
 static __u32 blocking_pool_data[OUTPUT_POOL_WORDS];
 static __u32 nonblocking_pool_data[OUTPUT_POOL_WORDS];
+static __u32 kernel_pool_data[OUTPUT_POOL_WORDS];
 
 static struct entropy_store input_pool = {
 	.poolinfo = &poolinfo_table[0],
@@ -469,6 +475,15 @@ static struct entropy_store nonblocking_
 	.pool = nonblocking_pool_data
 };
 
+static struct entropy_store kernel_pool = {
+	.poolinfo = &poolinfo_table[1],
+	.name = "kernel",
+	.limit = 2,
+	.pull = &input_pool,
+	.lock = __SPIN_LOCK_UNLOCKED(&kernel_pool.lock),
+	.pool = kernel_pool_data
+};
+
 static __u32 const twist_table[8] = {
 	0x00000000, 0x3b6e20c8, 0x76dc4190, 0x4db26158,
 	0xedb88320, 0xd6d6a3e8, 0x9b64c2b0, 0xa00ae278 };
@@ -613,6 +628,15 @@ retry:
 			r->initialized = 1;
 	}
 
+	/*
+	 * An entropy pool that is marked with limit 2 will only be
+	 * seeded by the input_pool until it is full of entropy.
+	 */
+	if (r->limit == 2 && r->entropy_count >= r->poolinfo->poolwords)
+	{
+		r->pull = NULL;
+	}
+
 	trace_credit_entropy_bits(r->name, nbits, entropy_count,
 				  r->entropy_total, _RET_IP_);
 
@@ -652,6 +676,8 @@ void add_device_randomness(const void *b
 	mix_pool_bytes(&input_pool, &time, sizeof(time), NULL);
 	mix_pool_bytes(&nonblocking_pool, buf, size, NULL);
 	mix_pool_bytes(&nonblocking_pool, &time, sizeof(time), NULL);
+	mix_pool_bytes(&kernel_pool, buf, size, NULL);
+	mix_pool_bytes(&kernel_pool, &time, sizeof(time), NULL);
 }
 EXPORT_SYMBOL(add_device_randomness);
 
@@ -820,7 +846,7 @@ static void xfer_secondary_pool(struct e
 	if (r->pull && r->entropy_count < nbytes * 8 &&
 	    r->entropy_count < r->poolinfo->POOLBITS) {
 		/* If we're limited, always leave two wakeup worth's BITS */
-		int rsvd = r->limit ? 0 : random_read_wakeup_thresh/4;
+		int rsvd = r->limit == 1 ? 0 : random_read_wakeup_thresh/4;
 		int bytes = nbytes;
 
 		/* pull at least as many as BYTES as wakeup BITS */
@@ -868,7 +894,7 @@ static size_t account(struct entropy_sto
 		nbytes = 0;
 	} else {
 		/* If limited, never pull more than available */
-		if (r->limit && nbytes + reserved >= r->entropy_count / 8)
+		if (r->limit == 1 && nbytes + reserved >= r->entropy_count / 8)
 			nbytes = r->entropy_count/8 - reserved;
 
 		if (r->entropy_count / 8 >= nbytes + reserved)
@@ -883,7 +909,7 @@ static size_t account(struct entropy_sto
 	}
 
 	DEBUG_ENT("debiting %d entropy credits from %s%s\n",
-		  nbytes * 8, r->name, r->limit ? "" : " (unlimited)");
+		  nbytes * 8, r->name, r->limit == 1 ? "" : " (unlimited)");
 
 	spin_unlock_irqrestore(&r->lock, flags);
 
@@ -1037,6 +1063,21 @@ void get_random_bytes(void *buf, int nby
 EXPORT_SYMBOL(get_random_bytes);
 
 /*
+ * This function exports the kernel random number pool. It is of
+ * slightly less quality than the nonblocking_pool exported by
+ * the function get_random_bytes because once it is filled completely
+ * with entropy, it is never seeded again. Yet, the quality of the
+ * random bytes depend on the SHA-1 hash and should be sufficient
+ * for purposes like ASLR and stack protection.
+ */
+void get_random_kernel_bytes(void *buf, int nbytes)
+{
+	extract_entropy(&kernel_pool, buf, nbytes, 0, 0);
+}
+EXPORT_SYMBOL(get_random_kernel_bytes);
+
+
+/*
  * This function will use the architecture-specific hardware random
  * number generator if it is available.  The arch-specific hw RNG will
  * almost certainly be faster than what we can do in software, but it
@@ -1110,6 +1151,7 @@ static int rand_initialize(void)
 	init_std_data(&input_pool);
 	init_std_data(&blocking_pool);
 	init_std_data(&nonblocking_pool);
+	init_std_data(&kernel_pool);
 	return 0;
 }
 module_init(rand_initialize);
@@ -1239,6 +1281,9 @@ static ssize_t random_write(struct file
 	ret = write_pool(&nonblocking_pool, buffer, count);
 	if (ret)
 		return ret;
+	ret = write_pool(&kernel_pool, buffer, count);
+	if (ret)
+		return ret;
 
 	return (ssize_t)count;
 }
diff -purN linux-3.6/fs/binfmt_elf.c linux-3.6-sm/fs/binfmt_elf.c
--- linux-3.6/fs/binfmt_elf.c	2012-10-01 01:47:46.000000000 +0200
+++ linux-3.6-sm/fs/binfmt_elf.c	2012-12-11 10:25:36.357094685 +0100
@@ -193,7 +193,7 @@ create_elf_tables(struct linux_binprm *b
 	/*
 	 * Generate 16 random bytes for userspace PRNG seeding.
 	 */
-	get_random_bytes(k_rand_bytes, sizeof(k_rand_bytes));
+	get_random_kernel_bytes(k_rand_bytes, sizeof(k_rand_bytes));
 	u_rand_bytes = (elf_addr_t __user *)
 		       STACK_ALLOC(p, sizeof(k_rand_bytes));
 	if (__copy_to_user(u_rand_bytes, k_rand_bytes, sizeof(k_rand_bytes)))
diff -purN linux-3.6/include/linux/random.h linux-3.6-sm/include/linux/random.h
--- linux-3.6/include/linux/random.h	2012-10-01 01:47:46.000000000 +0200
+++ linux-3.6-sm/include/linux/random.h	2012-12-11 10:31:45.033100217 +0100
@@ -54,6 +54,7 @@ extern void add_input_randomness(unsigne
 extern void add_interrupt_randomness(int irq, int irq_flags);
 
 extern void get_random_bytes(void *buf, int nbytes);
+extern void get_random_kernel_bytes(void *buf, int nbytes);
 extern void get_random_bytes_arch(void *buf, int nbytes);
 void generate_random_uuid(unsigned char uuid_out[16]);
 

Re: [PATCH] avoid entropy starvation due to stack protection

[Stephan Mueller]

On 11.12.2012 13:33:04, +0100, Stephan Mueller <smueller@chronox.de> wrote:

Hi,

I just noticed a misuse of a variable in my initial patch
> +	if (r->limit == 2 && r->entropy_count >= r->poolinfo->poolwords)

Instead of r->entropy_count, the code should use entropy_count.

Please see new patch attached.

Signed-off-by: Stephan Mueller <smueller@chronox.de>

---

diff -purN linux-3.6/drivers/char/random.c
linux-3.6-sm/drivers/char/random.c
--- linux-3.6/drivers/char/random.c    2012-10-01 01:47:46.000000000 +0200
+++ linux-3.6-sm/drivers/char/random.c    2012-12-12 11:06:23.443403746
+0100
@@ -404,11 +404,12 @@ static bool debug;
 module_param(debug, bool, 0644);
 #define DEBUG_ENT(fmt, arg...) do { \
     if (debug) \
-        printk(KERN_DEBUG "random %04d %04d %04d: " \
+        printk(KERN_DEBUG "random %04d %04d %04d %04d: " \
         fmt,\
         input_pool.entropy_count,\
         blocking_pool.entropy_count,\
         nonblocking_pool.entropy_count,\
+        kernel_pool.entropy_count,\
         ## arg); } while (0)
 #else
 #define DEBUG_ENT(fmt, arg...) do {} while (0)
@@ -428,7 +429,11 @@ struct entropy_store {
     __u32 *pool;
     const char *name;
     struct entropy_store *pull;
-    int limit;
+    int limit;    /* 0 -> no limit when extracting data (nonblocking)
+             * 1 -> limit extracted data based on entropy counter
+             * 2 -> no limit when extracting data and disabling
+             *      use of seed source once pool has full entropy
+             */
 
     /* read-write data: */
     spinlock_t lock;
@@ -443,6 +448,7 @@ struct entropy_store {
 static __u32 input_pool_data[INPUT_POOL_WORDS];
 static __u32 blocking_pool_data[OUTPUT_POOL_WORDS];
 static __u32 nonblocking_pool_data[OUTPUT_POOL_WORDS];
+static __u32 kernel_pool_data[OUTPUT_POOL_WORDS];
 
 static struct entropy_store input_pool = {
     .poolinfo = &poolinfo_table[0],
@@ -469,6 +475,15 @@ static struct entropy_store nonblocking_
     .pool = nonblocking_pool_data
 };
 
+static struct entropy_store kernel_pool = {
+    .poolinfo = &poolinfo_table[1],
+    .name = "kernel",
+    .limit = 2,
+    .pull = &input_pool,
+    .lock = __SPIN_LOCK_UNLOCKED(&kernel_pool.lock),
+    .pool = kernel_pool_data
+};
+
 static __u32 const twist_table[8] = {
     0x00000000, 0x3b6e20c8, 0x76dc4190, 0x4db26158,
     0xedb88320, 0xd6d6a3e8, 0x9b64c2b0, 0xa00ae278 };
@@ -613,6 +628,15 @@ retry:
             r->initialized = 1;
     }
 
+    /*
+     * An entropy pool that is marked with limit 2 will only be
+     * seeded by the input_pool until it is full of entropy.
+     */
+    if (r->limit == 2 && entropy_count >= r->poolinfo->poolwords)
+    {
+        r->pull = NULL;
+    }
+
     trace_credit_entropy_bits(r->name, nbits, entropy_count,
                   r->entropy_total, _RET_IP_);
 
@@ -652,6 +676,8 @@ void add_device_randomness(const void *b
     mix_pool_bytes(&input_pool, &time, sizeof(time), NULL);
     mix_pool_bytes(&nonblocking_pool, buf, size, NULL);
     mix_pool_bytes(&nonblocking_pool, &time, sizeof(time), NULL);
+    mix_pool_bytes(&kernel_pool, buf, size, NULL);
+    mix_pool_bytes(&kernel_pool, &time, sizeof(time), NULL);
 }
 EXPORT_SYMBOL(add_device_randomness);
 
@@ -820,7 +846,7 @@ static void xfer_secondary_pool(struct e
     if (r->pull && r->entropy_count < nbytes * 8 &&
         r->entropy_count < r->poolinfo->POOLBITS) {
         /* If we're limited, always leave two wakeup worth's BITS */
-        int rsvd = r->limit ? 0 : random_read_wakeup_thresh/4;
+        int rsvd = r->limit == 1 ? 0 : random_read_wakeup_thresh/4;
         int bytes = nbytes;
 
         /* pull at least as many as BYTES as wakeup BITS */
@@ -868,7 +894,7 @@ static size_t account(struct entropy_sto
         nbytes = 0;
     } else {
         /* If limited, never pull more than available */
-        if (r->limit && nbytes + reserved >= r->entropy_count / 8)
+        if (r->limit == 1 && nbytes + reserved >= r->entropy_count / 8)
             nbytes = r->entropy_count/8 - reserved;
 
         if (r->entropy_count / 8 >= nbytes + reserved)
@@ -883,7 +909,7 @@ static size_t account(struct entropy_sto
     }
 
     DEBUG_ENT("debiting %d entropy credits from %s%s\n",
-          nbytes * 8, r->name, r->limit ? "" : " (unlimited)");
+          nbytes * 8, r->name, r->limit == 1 ? "" : " (unlimited)");
 
     spin_unlock_irqrestore(&r->lock, flags);
 
@@ -1037,6 +1063,21 @@ void get_random_bytes(void *buf, int nby
 EXPORT_SYMBOL(get_random_bytes);
 
 /*
+ * This function exports the kernel random number pool. It is of
+ * slightly less quality than the nonblocking_pool exported by
+ * the function get_random_bytes because once it is filled completely
+ * with entropy, it is never seeded again. Yet, the quality of the
+ * random bytes depend on the SHA-1 hash and should be sufficient
+ * for purposes like ASLR and stack protection.
+ */
+void get_random_kernel_bytes(void *buf, int nbytes)
+{
+    extract_entropy(&kernel_pool, buf, nbytes, 0, 0);
+}
+EXPORT_SYMBOL(get_random_kernel_bytes);
+
+
+/*
  * This function will use the architecture-specific hardware random
  * number generator if it is available.  The arch-specific hw RNG will
  * almost certainly be faster than what we can do in software, but it
@@ -1110,6 +1151,7 @@ static int rand_initialize(void)
     init_std_data(&input_pool);
     init_std_data(&blocking_pool);
     init_std_data(&nonblocking_pool);
+    init_std_data(&kernel_pool);
     return 0;
 }
 module_init(rand_initialize);
@@ -1239,6 +1281,9 @@ static ssize_t random_write(struct file
     ret = write_pool(&nonblocking_pool, buffer, count);
     if (ret)
         return ret;
+    ret = write_pool(&kernel_pool, buffer, count);
+    if (ret)
+        return ret;
 
     return (ssize_t)count;
 }
diff -purN linux-3.6/fs/binfmt_elf.c linux-3.6-sm/fs/binfmt_elf.c
--- linux-3.6/fs/binfmt_elf.c    2012-10-01 01:47:46.000000000 +0200
+++ linux-3.6-sm/fs/binfmt_elf.c    2012-12-11 10:25:36.357094685 +0100
@@ -193,7 +193,7 @@ create_elf_tables(struct linux_binprm *b
     /*
      * Generate 16 random bytes for userspace PRNG seeding.
      */
-    get_random_bytes(k_rand_bytes, sizeof(k_rand_bytes));
+    get_random_kernel_bytes(k_rand_bytes, sizeof(k_rand_bytes));
     u_rand_bytes = (elf_addr_t __user *)
                STACK_ALLOC(p, sizeof(k_rand_bytes));
     if (__copy_to_user(u_rand_bytes, k_rand_bytes, sizeof(k_rand_bytes)))
diff -purN linux-3.6/include/linux/random.h
linux-3.6-sm/include/linux/random.h
--- linux-3.6/include/linux/random.h    2012-10-01 01:47:46.000000000 +0200
+++ linux-3.6-sm/include/linux/random.h    2012-12-11 10:31:45.033100217
+0100
@@ -54,6 +54,7 @@ extern void add_input_randomness(unsigne
 extern void add_interrupt_randomness(int irq, int irq_flags);
 
 extern void get_random_bytes(void *buf, int nbytes);
+extern void get_random_kernel_bytes(void *buf, int nbytes);
 extern void get_random_bytes_arch(void *buf, int nbytes);
 void generate_random_uuid(unsigned char uuid_out[16]);
 

Re: [PATCH] avoid entropy starvation due to stack protection

[Andrew Morton]

On Tue, 11 Dec 2012 13:33:04 +0100
Stephan Mueller <smueller@chronox.de> wrote:

> Some time ago, I noticed the fact that for every newly
> executed process, the function create_elf_tables requests 16 bytes of
> randomness from get_random_bytes. This is easily visible when calling
> 
> while [ 1 ]
> do
> 	cat /proc/sys/kernel/random/entropy_avail
> 	sleep 1
> done

Please see
http://ozlabs.org/~akpm/mmotm/broken-out/binfmt_elfc-use-get_random_int-to-fix-entropy-depleting.patch

That patch is about one week from a mainline merge, btw.

Re: [PATCH] avoid entropy starvation due to stack protection

[Stephan Mueller]

On 13.12.2012 01:43:21, +0100, Andrew Morton
<akpm@linux-foundation.org> wrote:

Hi Andrew,
> On Tue, 11 Dec 2012 13:33:04 +0100
> Stephan Mueller <smueller@chronox.de> wrote:
>
>> Some time ago, I noticed the fact that for every newly
>> executed process, the function create_elf_tables requests 16 bytes of
>> randomness from get_random_bytes. This is easily visible when calling
>>
>> while [ 1 ]
>> do
>> 	cat /proc/sys/kernel/random/entropy_avail
>> 	sleep 1
>> done
> Please see
> http://ozlabs.org/~akpm/mmotm/broken-out/binfmt_elfc-use-get_random_int-to-fix-entropy-depleting.patch
>
> That patch is about one week from a mainline merge, btw.

Initially I was also thinking about get_random_int. But stack protection
depends on non-predictable numbers to ensure it cannot be defeated. As
get_random_int depends on MD5 which is assumed to be broken now, I
discarded the idea of using get_random_int.

Moreover, please consider that get_cycles is an architecture-specific
function that on some architectures only returns 0 (For all
architectures where this is implemented, you have no guarantee that it
increments as a high-resolution timer). So, the quality of
get_random_int is questionable IMHO for the use as a stack protector.

Also note, that other in-kernel users of get_random_bytes may be
converted to using the proposed kernel pool to avoid more entropy drainage.

Please note that the suggested approach of fully seeding a deterministic
RNG never followed by a re-seeding is used elsewhere (e.g. the OpenSSL
RNG). Therefore, I think the suggested approach is viable.

Ciao
Stephan

Re: [PATCH] avoid entropy starvation due to stack protection

[Stephan Mueller]

On 13.12.2012 08:44:36, +0100, Stephan Mueller <smueller@chronox.de> wrote:

Hi Andrew,
> On 13.12.2012 01:43:21, +0100, Andrew Morton
> <akpm@linux-foundation.org> wrote:
>
> Hi Andrew,
>> On Tue, 11 Dec 2012 13:33:04 +0100
>> Stephan Mueller <smueller@chronox.de> wrote:
>>
>>> Some time ago, I noticed the fact that for every newly
>>> executed process, the function create_elf_tables requests 16 bytes of
>>> randomness from get_random_bytes. This is easily visible when calling
>>>
>>> while [ 1 ]
>>> do
>>> 	cat /proc/sys/kernel/random/entropy_avail
>>> 	sleep 1
>>> done
>> Please see
>> http://ozlabs.org/~akpm/mmotm/broken-out/binfmt_elfc-use-get_random_int-to-fix-entropy-depleting.patch
>>
>> That patch is about one week from a mainline merge, btw.
> Initially I was also thinking about get_random_int. But stack protection
> depends on non-predictable numbers to ensure it cannot be defeated. As
> get_random_int depends on MD5 which is assumed to be broken now, I
> discarded the idea of using get_random_int.
>
> Moreover, please consider that get_cycles is an architecture-specific
> function that on some architectures only returns 0 (For all
> architectures where this is implemented, you have no guarantee that it
> increments as a high-resolution timer). So, the quality of
> get_random_int is questionable IMHO for the use as a stack protector.
>
> Also note, that other in-kernel users of get_random_bytes may be
> converted to using the proposed kernel pool to avoid more entropy drainage.
>
> Please note that the suggested approach of fully seeding a deterministic
> RNG never followed by a re-seeding is used elsewhere (e.g. the OpenSSL
> RNG). Therefore, I think the suggested approach is viable.

I would like to add one more thing to consider. As the get_random_int
state depends on a relatively predictable timer reading, especially on
architectures without get_cycles(), hashed by MD5, it gains strength
(read unpredictability, entropy) over time. I.e. the more random numbers
are *randomly* extracted, the more random the value is.

Since many applications that are intended to benefit from stack
protection are started during boot time (e.g. the SSH daemon, Web
servers, Mail servers, other networking servers), I would conclude that
at the time these applications need random values, the strength behind
get_random_int is very low.

With my proposed patch, we have a similar strength than /dev/urandom but
without the drag on entropy during normal operation time -- i.e. the
time when cryptography comes into play triggered by normal users. Only
at that time the system needs to conserve entropy.
>
> Ciao
> Stephan
>

-- 
| Cui bono? |

Re: [PATCH] avoid entropy starvation due to stack protection

[Ondřej Bílka]

Why not use nonblocking pool and seed nonblocking pool only with half of
collected entropy to get /dev/random in almost all practical scenarios
nonblocking?

On Thu, Dec 13, 2012 at 08:44:36AM +0100, Stephan Mueller wrote:
> On 13.12.2012 01:43:21, +0100, Andrew Morton
> <akpm@linux-foundation.org> wrote:
> 
> Hi Andrew,
> > On Tue, 11 Dec 2012 13:33:04 +0100
> > Stephan Mueller <smueller@chronox.de> wrote:
> >
> >> Some time ago, I noticed the fact that for every newly
> >> executed process, the function create_elf_tables requests 16 bytes of
> >> randomness from get_random_bytes. This is easily visible when calling
> >>
> >> while [ 1 ]
> >> do
> >> 	cat /proc/sys/kernel/random/entropy_avail
> >> 	sleep 1
> >> done
> > Please see
> > http://ozlabs.org/~akpm/mmotm/broken-out/binfmt_elfc-use-get_random_int-to-fix-entropy-depleting.patch
> >
> > That patch is about one week from a mainline merge, btw.
> 
> Initially I was also thinking about get_random_int. But stack protection
> depends on non-predictable numbers to ensure it cannot be defeated. As
> get_random_int depends on MD5 which is assumed to be broken now, I
> discarded the idea of using get_random_int.
> 
> Moreover, please consider that get_cycles is an architecture-specific
> function that on some architectures only returns 0 (For all
> architectures where this is implemented, you have no guarantee that it
> increments as a high-resolution timer). So, the quality of
> get_random_int is questionable IMHO for the use as a stack protector.
> 
> Also note, that other in-kernel users of get_random_bytes may be
> converted to using the proposed kernel pool to avoid more entropy drainage.
> 
> Please note that the suggested approach of fully seeding a deterministic
> RNG never followed by a re-seeding is used elsewhere (e.g. the OpenSSL
> RNG). Therefore, I think the suggested approach is viable.
> 
> Ciao
> Stephan
> 
> --
> 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/

-- 

It's those computer people in X {city of world}.  They keep stuffing things up.

Re: [PATCH] avoid entropy starvation due to stack protection

[Stephan Müller]

Am 15.12.2012 20:15, schrieb Ondřej Bílka:
> Why not use nonblocking pool and seed nonblocking pool only with half of
> collected entropy to get /dev/random in almost all practical scenarios
> nonblocking?

I would not recommend changing /dev/urandom. First, we would change the 
characteristic of a kernel interface a lot of user space cryptographic 
components rely on. According to Linus that is typically a no-go. 
Moreover, the question can be raised, where do we pick the number of 
50%, why not 30% or 70%, why (re)seeding it at all?

Also, let us assume we pick 50% and we leave the create_elf_tables 
function as is (i.e. it pulls from get_random_bytes), I fear that we do 
not win at all. Our discussed problem is the depletion of the entropy 
via nonblocking_pool due to every execve() syscall requires 128 bits of 
data from nonblocking_pool. Even if we seed nonblocking_pool more 
rarely, we still deplete the entropy of the input_pool and thus deplete 
the entropy we want for cryptographic purposes a particular user has.

Thus, my recommendation is to disconnect the system entropy requirements 
from the user entropy requirements as much as possible. I am aware that 
there are in-kernel cryptographic requirements that must seed itself via 
the good entropy. And those users shall be rather left untouched -- i.e. 
they should still call get_random_bytes.

But for users that do not require cryptographic strength, but a strength 
against guessing of a random number on the local system for a decent 
time (like the stack protection or ASLR), we can use a slightly less 
perfect DRNG which is seeded with good entropy and never thereafter.

Ciao
Stephan
>
> On Thu, Dec 13, 2012 at 08:44:36AM +0100, Stephan Mueller wrote:
>> On 13.12.2012 01:43:21, +0100, Andrew Morton
>> <akpm@linux-foundation.org>  wrote:
>>
>> Hi Andrew,
>>> On Tue, 11 Dec 2012 13:33:04 +0100
>>> Stephan Mueller<smueller@chronox.de>  wrote:
>>>
>>>> Some time ago, I noticed the fact that for every newly
>>>> executed process, the function create_elf_tables requests 16 bytes of
>>>> randomness from get_random_bytes. This is easily visible when calling
>>>>
>>>> while [ 1 ]
>>>> do
>>>> 	cat /proc/sys/kernel/random/entropy_avail
>>>> 	sleep 1
>>>> done
>>> Please see
>>> http://ozlabs.org/~akpm/mmotm/broken-out/binfmt_elfc-use-get_random_int-to-fix-entropy-depleting.patch
>>>
>>> That patch is about one week from a mainline merge, btw.
>> Initially I was also thinking about get_random_int. But stack protection
>> depends on non-predictable numbers to ensure it cannot be defeated. As
>> get_random_int depends on MD5 which is assumed to be broken now, I
>> discarded the idea of using get_random_int.
>>
>> Moreover, please consider that get_cycles is an architecture-specific
>> function that on some architectures only returns 0 (For all
>> architectures where this is implemented, you have no guarantee that it
>> increments as a high-resolution timer). So, the quality of
>> get_random_int is questionable IMHO for the use as a stack protector.
>>
>> Also note, that other in-kernel users of get_random_bytes may be
>> converted to using the proposed kernel pool to avoid more entropy drainage.
>>
>> Please note that the suggested approach of fully seeding a deterministic
>> RNG never followed by a re-seeding is used elsewhere (e.g. the OpenSSL
>> RNG). Therefore, I think the suggested approach is viable.
>>
>> Ciao
>> Stephan
>>
>> --
>> 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/

Re: [PATCH] avoid entropy starvation due to stack protection

[Theodore Ts'o]

On Fri, Dec 14, 2012 at 06:36:41PM +0100, Stephan Mueller wrote:
> >> That patch is about one week from a mainline merge, btw.
> > Initially I was also thinking about get_random_int. But stack protection
> > depends on non-predictable numbers to ensure it cannot be defeated. As
> > get_random_int depends on MD5 which is assumed to be broken now, I
> > discarded the idea of using get_random_int.

The original use of get_random_int() was for applications where the
speed impact of using a heavierweight cryptographic primitive was not
something which could be tolerated.

However, the strength of get_random_int() is actually pretty good.
Note that we never expose the full MD5 hash; we only export the first
32-bits of the hash.   So even if you ignore the effects of:

	hash[0] += current->pid + jiffies + get_cycles();

What we effectively have is a deterministic RNG which is using MD5,
where the secret "key" is an initially seeded random value, and the
state counter is the MD5 hash accumulator, where we only expose the
first 32-bits with each turn of the crank.  Now, MD5 has been cracked,
but it's been cracked as a cryptographic checksum --- that is, given a
particular MD5 hash, it is possible to find an input value which will
result in that hash.  That doesn't necessarily mean that it can be
possible to take a stream of numbers produced by using the MD5 core in
this particular RNG configuration, and determine the secret value used
for the RNG (a collision attack allows you to find a possible input
value; that value may not be the one used as the secret).

That being said, it's not a question which has been studied
extensively by cryptographers, and so I can easily see how people
might be paranoid about whether this approach is good enough.

In the case of initializing 16 bits of randomness passed to userspace
after a exec(), performance is presumably not as important, so if
someone wanted to use something that was stronger from a
certificational point of view than get_random_int(), that's certainly
understandable.  However, it's not clear to me that replicating the
full /dev/random pool infrastructure if you're never going to mix in
any additional randomness is the best way to go about things.

What I would do instead is use an AES-based cryptographic random
number generator.  That is, at boot time, grab enough randomness to
for an AES key, and then use that key to create a cryptographic random
number generator by encrypting a counter with said AES key.  This is a
cryptographic primitive which has been very carefully studied, and for
architectures where you have a hardware support for AES (including
ARMv8, Power 7, Sparc T4, as well as x86 processors with the AES-NI
instructions), this will be much faster and require much less memory
and CPU resources than replicating the /dev/urandom infrastructure.

Whether or not we really need this level of paranoia for hardening
stack randomization I'll leave for someone else to decide.
Personally, my philosophy is if someone has managed to get
unprivileged shell acess, trying to protect against a privilege
escalation attack is largely hopeless on most Linux systems.  The name
of the game is to protect against someone who does not yet have the
ability to run arbitrary unprivileged code on the system of interest.
In that case, the attacker isn't going to be able to get access to the
output of get_random_int(), so even if there was a cryptographic
weakness where an attacker who had access to the get_random_int()
output stream could guess the internal state of the MD5-based RNG, in
the case of a remote attacker, they wouldn't have access to the output
of the RNG in the first place.

Regards,

						- Ted

Re: [PATCH] avoid entropy starvation due to stack protection

[Stephan Müller]

Am 16.12.2012 01:30, schrieb Theodore Ts'o:
> On Fri, Dec 14, 2012 at 06:36:41PM +0100, Stephan Mueller wrote:
>>>> That patch is about one week from a mainline merge, btw.
>>> Initially I was also thinking about get_random_int. But stack protection
>>> depends on non-predictable numbers to ensure it cannot be defeated. As
>>> get_random_int depends on MD5 which is assumed to be broken now, I
>>> discarded the idea of using get_random_int.
> The original use of get_random_int() was for applications where the
> speed impact of using a heavierweight cryptographic primitive was not
> something which could be tolerated.
>
> However, the strength of get_random_int() is actually pretty good.
> Note that we never expose the full MD5 hash; we only export the first
> 32-bits of the hash.   So even if you ignore the effects of:
>
> 	hash[0] += current->pid + jiffies + get_cycles();

I see that, but I consider that just getting some time stamps, where the 
interesting high-resolution time stamp is not guaranteed to exist, 
calculate a broken hash and take some parts of that hash as a random 
value does not sound very promising, even for stack protection.

...
>
> What I would do instead is use an AES-based cryptographic random
> number generator.  That is, at boot time, grab enough randomness to
> for an AES key, and then use that key to create a cryptographic random
> number generator by encrypting a counter with said AES key.  This is a
> cryptographic primitive which has been very carefully studied, and for
> architectures where you have a hardware support for AES (including
> ARMv8, Power 7, Sparc T4, as well as x86 processors with the AES-NI
> instructions), this will be much faster and require much less memory
> and CPU resources than replicating the /dev/urandom infrastructure.

Well, we already have such an RNG in the kernel: the ansi_cprng out of 
the kernel crypto API. That RNG implements an ANSI X9.31 RNG with an AES 
core.

Maybe that RNG should be given more centerstage where it is seeded with 
good entropy where the seed key and the seed is at least having each 256 
bits of entropy? In this case we have a standard CSPRNG seeded with 
hardware-based entropy.

>
> Whether or not we really need this level of paranoia for hardening
> stack randomization I'll leave for someone else to decide.
> Personally, my philosophy is if someone has managed to get
> unprivileged shell acess, trying to protect against a privilege
> escalation attack is largely hopeless on most Linux systems.  The name

I would not concur with that statement because it would render all 
attempts to make the local system more secure irrelevant. ;-)

But that is just my view.

> of the game is to protect against someone who does not yet have the
> ability to run arbitrary unprivileged code on the system of interest.
> In that case, the attacker isn't going to be able to get access to the
> output of get_random_int(), so even if there was a cryptographic
> weakness where an attacker who had access to the get_random_int()
> output stream could guess the internal state of the MD5-based RNG, in
> the case of a remote attacker, they wouldn't have access to the output
> of the RNG in the first place.

Ciao
Stephan

Re: [PATCH] avoid entropy starvation due to stack protection

[Ondřej Bílka]

On Sat, Dec 15, 2012 at 11:59:46PM +0100, Stephan Müller wrote:
> Am 15.12.2012 20:15, schrieb Ondřej Bílka:
> >Why not use nonblocking pool and seed nonblocking pool only with half of
> >collected entropy to get /dev/random in almost all practical scenarios
> >nonblocking?
> 
> I would not recommend changing /dev/urandom. First, we would change
> the characteristic of a kernel interface a lot of user space
> cryptographic components rely on. 
How it would change characteristic more than swapping a hard disk for a
ssd? Should we display a message "Please type more slowly to maintain
kernel interface."?

> According to Linus that is
> typically a no-go. Moreover, the question can be raised, where do we
> pick the number of 50%, why not 30% or 70%, why (re)seeding it at
> all?
And does this argument make any difference?
> 
> Also, let us assume we pick 50% and we leave the create_elf_tables
> function as is (i.e. it pulls from get_random_bytes), I fear that we
> do not win at all. Our discussed problem is the depletion of the
> entropy via nonblocking_pool due to every execve() syscall requires
> 128 bits of data from nonblocking_pool. Even if we seed
> nonblocking_pool more rarely, we still deplete the entropy of the
> input_pool and thus deplete the entropy we want for cryptographic
> purposes a particular user has.
This is only correct upto thus part. As blocking pool would get full
after 8096 bytes would be generated, stayed full until needed and won't 
be affected by input pool. As long as we would generate at least twice
entropy than blocking pool consumes we would be fine.

Re: [PATCH] avoid entropy starvation due to stack protection

[Ondřej Bílka]

On Sat, Dec 15, 2012 at 07:30:20PM -0500, Theodore Ts'o wrote:
> 
> What I would do instead is use an AES-based cryptographic random
> number generator.  That is, at boot time, grab enough randomness to
> for an AES key, and then use that key to create a cryptographic random
> number generator by encrypting a counter with said AES key.  This is a
> cryptographic primitive which has been very carefully studied, and for
> architectures where you have a hardware support for AES (including
> ARMv8, Power 7, Sparc T4, as well as x86 processors with the AES-NI
> instructions), this will be much faster and require much less memory
> and CPU resources than replicating the /dev/urandom infrastructure.
> 
I was suggesting in another thread different approach.

Use AES-based cryptographic random number generator as replacement of 
/dev/urandom. Reseeding would get done by changing both aes key and
data.

This would with hardware support make /dev/urandom much faster than its now.

Re: [PATCH] avoid entropy starvation due to stack protection

[Theodore Ts'o]

On Fri, Dec 21, 2012 at 09:07:35PM +0100, Ondřej Bílka wrote:
> I was suggesting in another thread different approach.
> 
> Use AES-based cryptographic random number generator as replacement of 
> /dev/urandom. Reseeding would get done by changing both aes key and
> data.
> 
> This would with hardware support make /dev/urandom much faster than its now.

You can do this in userspace.  And in fact, if you need huge numbers
of random session keys, such as in a Kerberos KDC or an IPSEC IKE
daemon, that's what I would recommand (and what most of them do
already).

The original goal and intent for /dev/random was really for long-term
keys where we are trying to leverage randomness available from
hardware, which only the kernel would be able to collect.  It was not
intended as a high speed random number generator; the best use of it
is either for the generation of a long-term public key, or other
secret (such as a Kerberos master key), or to seed a cryptographic
random number generator which then operates in userspace.

If you need speed, then by all means, use a cryptographic random
number generator in userspace, or if it's for a monte carlo simulator,
use a good userspace PRNG.

						- Ted