binfmt_elf.c: Introduce a wrapper of get_random_int() to fix entropy depleting

Hello,

We have observed entropy quickly depleting under normal I/O between 2.6.30 to upstream, 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

It has been occurred with fs/binfmt_elf.c: create_elf_tables()->get_random_bytes() was introduced began at 2.6.30.
/*
* Generate 16 random bytes for userspace PRNG seeding.
*/
get_random_bytes(k_rand_bytes, sizeof(k_rand_bytes));

This proposal patch is trying to introduce a wrapper of get_random_int() which has lower overhead than calling get_random_bytes() directly.

Entropy increased 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

v3->v2:
-------
Remove redundant bits mask and shift upon the random variable according to Kees's review.

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

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

Many thanks to Andreas, Andrew as well as Kees for reviewing the patch of past.

-Jeff

Signed-off-by Jie Liu <[email protected]>

Cc John Sobecki <[email protected]>

CC Andrew Morton <[email protected]>

Cc Al Viro <[email protected]>

Cc Andreas Dilger <[email protected]>

Cc Alan Cox <[email protected]>

Cc Arnd Bergmann <[email protected]>

Cc James Morris <[email protected]>

Cc Ted Ts'o <[email protected]>

Cc Greg Kroah-Hartman <[email protected]>

Cc Kees Cook <[email protected]>

Cc Jakub Jelinek <[email protected]>

Cc Ulrich Drepper <[email protected]>

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

fs/binfmt_elf.c +23 -1

index fbd9f60..9c36e50 100644
@@ -48,6 +48,7 @@ static int load_elf_binary(struct linux_binprm *bprm, struct pt_regs *regs);
 static int load_elf_library(struct file *);
 static unsigned long elf_map(struct file *, unsigned long, struct elf_phdr *,
 				int, int, unsigned long);
+static void randomize_stack_user(unsigned char *buf, size_t nbytes);
 
 /*
  * If we don't support core dumping, then supply a NULL so we

@@ -200,7 +201,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));
+	randomize_stack_user(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)))

@@ -558,6 +559,27 @@ static unsigned long randomize_stack_top(unsigned long stack_top)
 #endif
 }
 
+/*
+ * A wrapper of get_random_int() to generate random bytes which has lower
+ * overhead than calling get_random_bytes() directly.
+ * create_elf_tables() call this function to generate 16 random bytes for
+ * userspace PRNG seeding.
+ */
+static void randomize_stack_user(unsigned char *buf, size_t nbytes)
+{
+	unsigned char *p = buf;
+
+	while (nbytes) {
+		unsigned int random_variable;
+		size_t chunk = min(nbytes, sizeof(unsigned int));
+
+		random_variable = get_random_int();
+		memcpy(p, &random_variable, chunk);
+		p += chunk;
+		nbytes -= chunk;
+	}
+}
+
 static int load_elf_binary(struct linux_binprm *bprm, struct pt_regs *regs)
 {
 	struct file *interpreter = NULL; /* to shut gcc up */

Hello,

This is the revised patch for fix entropy depleting.

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

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

Many thanks to Andreas, Andrew as well as Kees for reviewing the patch of past! -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.

Signed-off-by Jie Liu <[email protected]>

Cc John Sobecki <[email protected]>

Cc Al Viro <[email protected]>

Cc Andreas Dilger <[email protected]>

Cc Alan Cox <[email protected]>

Cc Arnd Bergmann <[email protected]>

Cc James Morris <[email protected]>

Cc Ted Ts'o <[email protected]>

Cc Greg Kroah-Hartman <[email protected]>

Cc Kees Cook <[email protected]>

Cc Jakub Jelinek <[email protected]>

Cc Ulrich Drepper <[email protected]>

Signed-off-by Andrew Morton <[email protected]>

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

fs/binfmt_elf.c +0 -0

index fbd9f60..b6c59f6 100644

fs/binfmt_elf.c +1 -1

 /*
  * If we don't support core dumping, then supply a NULL so we

@@ -200,7 +201,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));
+       randomize_stack_user(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)))

fs/binfmt_elf.c +6 -1

+               memcpy(p, &random_variable, chunk);
+               p += chunk;
+               nbytes -= chunk;
+       }
+}
+
 static int load_elf_binary(struct linux_binprm *bprm, struct pt_regs *regs)
 {
        struct file *interpreter = NULL; /* to shut gcc up */
--

1.7.4.1

Quoted 72 lines · Jeff Liu

Hello,

This is the revised patch for fix entropy depleting.

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

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

Many thanks to Andreas, Andrew as well as Kees for reviewing the patch of past! -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.

Signed-off-by Jie Liu <[email protected]>

Cc John Sobecki <[email protected]>

Cc Al Viro <[email protected]>

Cc Andreas Dilger <[email protected]>

Cc Alan Cox <[email protected]>

Cc Arnd Bergmann <[email protected]>

Cc James Morris <[email protected]>

Cc Ted Ts'o <[email protected]>

Cc Greg Kroah-Hartman <[email protected]>

Cc Kees Cook <[email protected]>

Cc Jakub Jelinek <[email protected]>

Cc Ulrich Drepper <[email protected]>

Signed-off-by Andrew Morton <[email protected]>

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

fs/binfmt_elf.c static int load_elf_binary(struct linux_binprm *bprm, struct pt_regs *regs); · line 51

Quoted 9 lines

fs/binfmt_elf.c +1 -0

index fbd9f60..b6c59f6 100644
@@ -48,6 +48,7 @@ static int load_elf_binary(struct linux_binprm *bprm, struct pt_regs *regs);
 static int load_elf_library(struct file *);
 static unsigned long elf_map(struct file *, unsigned long, struct elf_phdr *,
                                int, int, unsigned long);
+static void randomize_stack_user(unsigned char *buf, size_t nbytes);

I think it would be easier to just move the function ahead of its use to avoid the predeclaration.

Quoted 17 lines

fs/binfmt_elf.c +1 -1

 /*
  * If we don't support core dumping, then supply a NULL so we

@@ -200,7 +201,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));
+       randomize_stack_user(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)))

@@ -558,6 +559,25 @@ static unsigned long randomize_stack_top(unsigned long stack_top)
 #endif
 }
 

fs/binfmt_elf.c static unsigned long randomize_stack_top(unsigned long stack_top) · line 566

Quoted 5 lines

fs/binfmt_elf.c +5 -0

+/*
+ * Use get_random_int() to implement AT_RANDOM while avoiding depletion
+ * of the entropy pool.
+ */
+static void randomize_stack_user(unsigned char *buf, size_t nbytes)

I think this name needs changing -- it has nothing to do with the stack except that that's where it ends up in userspace. Perhaps "get_atrandom_bytes"?

fs/binfmt_elf.c static unsigned long randomize_stack_top(unsigned long stack_top) · line 574

Quoted 9 lines

fs/binfmt_elf.c +8 -0

+{
+       unsigned char *p = buf;
+
+       while (nbytes) {
+               unsigned int random_variable;
+               size_t chunk = min(nbytes, sizeof(unsigned int));
+
+               random_variable = get_random_int();

I still want to hear at least from Ted about this changes -- we would be potentially increasing the predictability of these bytes...

Quoted 11 lines

fs/binfmt_elf.c +6 -1

+               memcpy(p, &random_variable, chunk);
+               p += chunk;
+               nbytes -= chunk;
+       }
+}
+
 static int load_elf_binary(struct linux_binprm *bprm, struct pt_regs *regs)
 {
        struct file *interpreter = NULL; /* to shut gcc up */
--

Quoted 1 line

1.7.4.1

-Kees

Quoted 2 lines · Kees Cook

I still want to hear at least from Ted about this changes -- we would be potentially increasing the predictability of these bytes...

We would not increasing that if this routine would be used for AT_RANDOM only(and if the array keeping aligned to 4 bytes). Otherwise, it would be, so let's waiting for further feedbacks.

Quoted 4 lines · Jeff Liu

Quoted 2 lines · Kees Cook

I still want to hear at least from Ted about this changes -- we would be potentially increasing the predictability of these bytes...

Quoted 3 lines

We would not increasing that if this routine would be used for AT_RANDOM only(and if the array keeping aligned to 4 bytes). Otherwise, it would be, so let's waiting for further feedbacks.

get_random_int() comes from a different pool than get_random_bytes(), IIUC. I'd like to hear some convincing reasoning as to why this change doesn't compromise predictability. :)

Quoted 9 lines · On Tue, 6 Nov 2012 23:13:54 -0800 Kees Cook <[email protected]> wrote:

Quoted 7 lines · Jeff Liu

Quoted 2 lines · Kees Cook

I still want to hear at least from Ted about this changes -- we would be potentially increasing the predictability of these bytes...

We would not increasing that if this routine would be used for AT_RANDOM only(and if the array keeping aligned to 4 bytes). Otherwise, it would be, so let's waiting for further feedbacks.

Quoted 3 lines

get_random_int() comes from a different pool than get_random_bytes(), IIUC. I'd like to hear some convincing reasoning as to why this change doesn't compromise predictability. :)

But the original "ELF: implement AT_RANDOM for glibc PRNG seeding" compromised predictability. That's the whole point of this patch.

What was so important about that patch that justified gobbling down so much of the system's entropy accumulation?