binfmt_elf.c: use get_random_int() to fix entropy depleting

Hello,

The problems have been fixed in this version as per Kees's comments for v3.

Hi Kees,
Would you please ACK this patch if you think it is ok except the strength of these various RNGs you are concerned?

Changes:
--------
v4->v3:
- s/random_stack_user()/get_atrandom_bytes()/
- Move this function to ahead of its use to avoid the predeclaration.

v3->v2:
- Tweak code comments of random_stack_user().
- Remove redundant bits mask and shift upon the random variable.

v2->v1:
- Fix random copy to check up buffer length that are not 4-byte multiples.

v3 can be found at:
http://www.spinics.net/lists/linux-fsdevel/msg59597.html
v2 can be found at:
http://www.spinics.net/lists/linux-fsdevel/msg59418.html
v1 can be found at:
http://www.spinics.net/lists/linux-fsdevel/msg59128.html

Thanks,
-Jeff

Entropy is quickly depleted under normal operations like ls(1), cat(1), etc... between 2.6.30 to current mainline, for instance:

$ cat /proc/sys/kernel/random/entropy_avail
3428
$ cat /proc/sys/kernel/random/entropy_avail
2911
$cat /proc/sys/kernel/random/entropy_avail
2620

We observed this problem has been occurring since 2.6.30 with fs/binfmt_elf.c: create_elf_tables()->get_random_bytes(), introduced by f06295b44c296c8f ("ELF: implement AT_RANDOM for glibc PRNG seeding").

/*
* Generate 16 random bytes for userspace PRNG seeding. */
get_random_bytes(k_rand_bytes, sizeof(k_rand_bytes));

The patch introduces a wrapper around get_random_int() which has lower overhead than calling get_random_bytes() directly.

With this patch applied:

$ cat /proc/sys/kernel/random/entropy_avail
2731
$ cat /proc/sys/kernel/random/entropy_avail
2802
$ cat /proc/sys/kernel/random/entropy_avail
2878

Analyzed by John Sobecki.

---
 fs/binfmt_elf.c |   21 ++++++++++++++++++++-
 1 files changed, 20 insertions(+), 1 deletions(-)

index fbd9f60..ab4428e 100644
@@ -139,6 +139,25 @@ static int padzero(unsigned long elf_bss)
 #define ELF_BASE_PLATFORM NULL
 #endif
 
+/*
+ * Use get_random_int() to implement AT_RANDOM while avoiding depletion
+ * of the entropy pool.
+ */
+static void get_atrandom_bytes(unsigned char *buf, size_t nbytes)
+{
+	unsigned char *p = buf;
+
+	while (nbytes) {
+		unsigned int random_variable;
+		size_t chunk = min(nbytes, sizeof(random_variable));
+
+		random_variable = get_random_int();
+		memcpy(p, &random_variable, chunk);
+		p += chunk;
+		nbytes -= chunk;
+	}
+}
+
 static int
 create_elf_tables(struct linux_binprm *bprm, struct elfhdr *exec,
 		unsigned long load_addr, unsigned long interp_load_addr)

@@ -200,7 +219,7 @@ create_elf_tables(struct linux_binprm *bprm, struct elfhdr *exec,
 	/*
 	 * Generate 16 random bytes for userspace PRNG seeding.
 	 */
-	get_random_bytes(k_rand_bytes, sizeof(k_rand_bytes));
+	get_atrandom_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)))

1.7.4.1

-Kees

Kees Cook
Chrome OS Security

Hi Stephan,

As per your previous comments for this fix, you have promised another approach which is promising to avoid entropy starvation, I got this info from the following thread:
[PATCH] avoid entropy starvation due to stack protection
https://lkml.org/lkml/2012/12/14/267

My current fix has been merged into Andrew's tree(marked in "stuck" state) for a long time, and it also works well in our internal specific kernel, I'd like to know if there is any update from you, so that we can move it along for mainline. :)

Thanks,
-Jeff

This:

From: Jeff Liu <[email protected]>
Subject: binfmt_elf.c: use get_random_int() to fix entropy depleting

Entropy is quickly depleted under normal operations like ls(1), cat(1), etc... between 2.6.30 to current mainline, for instance:

$ cat /proc/sys/kernel/random/entropy_avail
3428
$ cat /proc/sys/kernel/random/entropy_avail
2911
$cat /proc/sys/kernel/random/entropy_avail
2620

We observed this problem has been occurring since 2.6.30 with fs/binfmt_elf.c: create_elf_tables()->get_random_bytes(), introduced by f06295b44c296c8f ("ELF: implement AT_RANDOM for glibc PRNG seeding").

/*
* Generate 16 random bytes for userspace PRNG seeding. */
get_random_bytes(k_rand_bytes, sizeof(k_rand_bytes));

The patch introduces a wrapper around get_random_int() which has lower overhead than calling get_random_bytes() directly.

With this patch applied:

$ cat /proc/sys/kernel/random/entropy_avail
2731
$ cat /proc/sys/kernel/random/entropy_avail
2802
$ cat /proc/sys/kernel/random/entropy_avail
2878

Analyzed by John Sobecki.

This has been applied on a specific Oracle kernel and has been running on the customer's production environment (the original bug reporter) for several months; it has worked fine until now.

---

 fs/binfmt_elf.c |   21 ++++++++++++++++++++-
 1 file changed, 20 insertions(+), 1 deletion(-)

diff -puN fs/binfmt_elf.c~binfmt_elfc-use-get_random_int-to-fix-entropy-depleting fs/binfmt_elf.c
@@ -140,6 +140,25 @@ static int padzero(unsigned long elf_bss
 #define ELF_BASE_PLATFORM NULL
 #endif
 
+/*
+ * Use get_random_int() to implement AT_RANDOM while avoiding depletion
+ * of the entropy pool.
+ */
+static void get_atrandom_bytes(unsigned char *buf, size_t nbytes)
+{
+	unsigned char *p = buf;
+
+	while (nbytes) {
+		unsigned int random_variable;
+		size_t chunk = min(nbytes, sizeof(random_variable));
+
+		random_variable = get_random_int();
+		memcpy(p, &random_variable, chunk);
+		p += chunk;
+		nbytes -= chunk;
+	}
+}
+
 static int
 create_elf_tables(struct linux_binprm *bprm, struct elfhdr *exec,
 		unsigned long load_addr, unsigned long interp_load_addr)

@@ -201,7 +220,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_atrandom_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)))

_

Am Donnerstag, 7. November 2013, 12:14:17 schrieb Jeff Liu:

Hi Jeff,

There are several solutions:

- Ted is trying to prevent a constant reseeding of the nonblocking_pool from the input_pool with a set of patches. I am unsure whether these patches find their way into the kernel. With those patches, we can happily keep get_random_bytes without too much strain on the input_pool entropy -- i.e. drop the conversion to get_random_int.

- The begin of the email thread contains a patch that adds a new pool which I called the kernel_pool that is just just for kernel internal purposes. With Teds proposed changes to nonblocking_pool, nonblocking_pool would behave almost like my kernel_pool and thus my kernel_pool patch would not be needed.

- Lastly I am trying to add a new seed source to random.c and kernel crypto API which could also be used as a stand-alone noise source. That proposed noise source would effectively alleviate a lot of entropy problems. The discussion for inclusion is raging at
http://lkml.org/lkml/2013/10/11/582. Ted is having concerns and we are in a discussion to address those.

Ciao
Stephan

Thanks for your prompt response!

Yup, that's would be great if we can solve this problem without that.

I spent a few hours reading through the thread through some contents are beyond my understanding. Looks the proposed approach has already been widely tested on various platforms, but there still have concerns like the random numbers which are generated via the jitter "entropy collector" probably can not be convinced to be more secure.

Thanks for your efforts and I'll keep a close eye on it's progress.

Regards,
-Jeff