Re: + binfmt_elfc-use-get_random_int-to-fix-entropy-depleting.patch added to -mm tree

Re: + binfmt_elfc-use-get_random_int-to-fix-entropy-depleting.patch added to -mm tree

[Kees Cook]

Hrm, I don't like this. get_random_int() specifically says: "Get a
random word for internal kernel use only." The intent of AT_RANDOM is
for userspace pRNG seeding (though glibc currently uses it directly
for stack protector and pointer mangling), which is not "internal
kernel use only". :) Though I suppose this is already being used for
the randomize_stack_top(), but I think it'd still be better to use
higher quality bits.

Notes below...

On Tue, Nov 6, 2012 at 4:16 PM,  <akpm@linux-foundation.org> wrote:
>
> The patch titled
>      Subject: binfmt_elf.c: use get_random_int() to fix entropy depleting
> has been added to the -mm tree.  Its filename is
>      binfmt_elfc-use-get_random_int-to-fix-entropy-depleting.patch
>
> Before you just go and hit "reply", please:
>    a) Consider who else should be cc'ed
>    b) Prefer to cc a suitable mailing list as well
>    c) Ideally: find the original patch on the mailing list and do a
>       reply-to-all to that, adding suitable additional cc's
>
> *** Remember to use Documentation/SubmitChecklist when testing your code ***
>
> The -mm tree is included into linux-next and is updated
> there every 3-4 working days
>
> ------------------------------------------------------
> From: Jeff Liu <jeff.liu@oracle.com>
> 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.
>
> Signed-off-by: Jie Liu <jeff.liu@oracle.com>
> Cc: John Sobecki <john.sobecki@oracle.com>
> Cc: Al Viro <viro@zeniv.linux.org.uk>
> Cc: Andreas Dilger <aedilger@gmail.com>
> Cc: Alan Cox <alan@linux.intel.com>
> Cc: Arnd Bergmann <arnn@arndb.de>
> Cc: James Morris <james.l.morris@oracle.com>
> Cc: Ted Ts'o <tytso@mit.edu>
> Cc: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
> Cc: Kees Cook <keescook@chromium.org>
> Cc: Jakub Jelinek <jakub@redhat.com>
> Cc: Ulrich Drepper <drepper@redhat.com>
> Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
> ---
>
>  fs/binfmt_elf.c |   26 +++++++++++++++++++++++++-
>  1 file changed, 25 insertions(+), 1 deletion(-)
>
> diff -puN fs/binfmt_elf.c~binfmt_elfc-use-get_random_int-to-fix-entropy-depleting fs/binfmt_elf.c
> --- a/fs/binfmt_elf.c~binfmt_elfc-use-get_random_int-to-fix-entropy-depleting
> +++ a/fs/binfmt_elf.c
> @@ -48,6 +48,7 @@ static int load_elf_binary(struct linux_
>  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 *b
>         /*
>          * 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,29 @@ static unsigned long randomize_stack_top
>  #endif
>  }
>
> +/*
> + * A wrapper of get_random_int() to generate random bytes which has lower
> + * overhead than call 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() & STACK_RND_MASK;
> +               random_variable <<= PAGE_SHIFT;

Why is this using STACK_RND_MASK? That's not sensible. And the shift
is especially odd. AIUI, these two lines should just be:

random_variable = get_random_int();

> +
> +               memcpy(p, &random_variable, chunk);
> +               p += chunk;
> +               nbytes -= chunk;
> +       }
> +}
> +
>  static int load_elf_binary(struct linux_binprm *bprm)
>  {
>         struct file *interpreter = NULL; /* to shut gcc up */
> _
>
> Patches currently in -mm which might be from jeff.liu@oracle.com are
>
> documentation-cgroups-memorytxt-s-mem_cgroup_charge-mem_cgroup_change_common.patch
> mm-vmscanc-try_to_freeze-returns-boolean.patch
> binfmt_elfc-use-get_random_int-to-fix-entropy-depleting.patch
> binfmt_elfc-use-get_random_int-to-fix-entropy-depleting-fix.patch
>

-Kees

-- 
Kees Cook
Chrome OS Security

Re: + binfmt_elfc-use-get_random_int-to-fix-entropy-depleting.patch added to -mm tree

[Jeff Liu]

Hi Andrew and Kees,

Great thanks for both your comments!

On 11/07/2012 09:11 AM, Kees Cook wrote:
> Hrm, I don't like this. get_random_int() specifically says: "Get a
> random word for internal kernel use only." The intent of AT_RANDOM is
> for userspace pRNG seeding (though glibc currently uses it directly
> for stack protector and pointer mangling), which is not "internal
> kernel use only". :) Though I suppose this is already being used for
> the randomize_stack_top(), but I think it'd still be better to use
> higher quality bits.
Btw Kees, does it sounds make sense if we just return the 16 bytes
uninitialized stack array if the user disable the stack randomize via
"/proc/sys/kernel/randomize_va_space = 0" or via the related sysctl, or
even specified norandmaps on boot?

I guess this sounds more stupid since some scripts kids would like it
for writing exploits. :-P
> 
> Notes below...
> 
> On Tue, Nov 6, 2012 at 4:16 PM,  <akpm@linux-foundation.org> wrote:
>>
>> The patch titled
>>      Subject: binfmt_elf.c: use get_random_int() to fix entropy depleting
>> has been added to the -mm tree.  Its filename is
>>      binfmt_elfc-use-get_random_int-to-fix-entropy-depleting.patch
>>
>> Before you just go and hit "reply", please:
>>    a) Consider who else should be cc'ed
>>    b) Prefer to cc a suitable mailing list as well
>>    c) Ideally: find the original patch on the mailing list and do a
>>       reply-to-all to that, adding suitable additional cc's
>>
>> *** Remember to use Documentation/SubmitChecklist when testing your code ***
>>
>> The -mm tree is included into linux-next and is updated
>> there every 3-4 working days
>>
>> ------------------------------------------------------
>> From: Jeff Liu <jeff.liu@oracle.com>
>> 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.
>>
>> Signed-off-by: Jie Liu <jeff.liu@oracle.com>
>> Cc: John Sobecki <john.sobecki@oracle.com>
>> Cc: Al Viro <viro@zeniv.linux.org.uk>
>> Cc: Andreas Dilger <aedilger@gmail.com>
>> Cc: Alan Cox <alan@linux.intel.com>
>> Cc: Arnd Bergmann <arnn@arndb.de>
>> Cc: James Morris <james.l.morris@oracle.com>
>> Cc: Ted Ts'o <tytso@mit.edu>
>> Cc: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
>> Cc: Kees Cook <keescook@chromium.org>
>> Cc: Jakub Jelinek <jakub@redhat.com>
>> Cc: Ulrich Drepper <drepper@redhat.com>
>> Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
>> ---
>>
>>  fs/binfmt_elf.c |   26 +++++++++++++++++++++++++-
>>  1 file changed, 25 insertions(+), 1 deletion(-)
>>
>> diff -puN fs/binfmt_elf.c~binfmt_elfc-use-get_random_int-to-fix-entropy-depleting fs/binfmt_elf.c
>> --- a/fs/binfmt_elf.c~binfmt_elfc-use-get_random_int-to-fix-entropy-depleting
>> +++ a/fs/binfmt_elf.c
>> @@ -48,6 +48,7 @@ static int load_elf_binary(struct linux_
>>  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 *b
>>         /*
>>          * 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,29 @@ static unsigned long randomize_stack_top
>>  #endif
>>  }
>>
>> +/*
>> + * A wrapper of get_random_int() to generate random bytes which has lower
>> + * overhead than call 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() & STACK_RND_MASK;
>> +               random_variable <<= PAGE_SHIFT;
> 
> Why is this using STACK_RND_MASK? That's not sensible. And the shift
> is especially odd. AIUI, these two lines should just be:
Definitely! I copied it from randomize_stack_top(), it's not proper to
use here, will fix it accordingly.

Thanks,
-Jeff
> 
> random_variable = get_random_int();
> 
>> +
>> +               memcpy(p, &random_variable, chunk);
>> +               p += chunk;
>> +               nbytes -= chunk;
>> +       }
>> +}
>> +
>>  static int load_elf_binary(struct linux_binprm *bprm)
>>  {
>>         struct file *interpreter = NULL; /* to shut gcc up */
>> _
>>
>> Patches currently in -mm which might be from jeff.liu@oracle.com are
>>
>> documentation-cgroups-memorytxt-s-mem_cgroup_charge-mem_cgroup_change_common.patch
>> mm-vmscanc-try_to_freeze-returns-boolean.patch
>> binfmt_elfc-use-get_random_int-to-fix-entropy-depleting.patch
>> binfmt_elfc-use-get_random_int-to-fix-entropy-depleting-fix.patch
>>
> 
> -Kees
> 

Re: + binfmt_elfc-use-get_random_int-to-fix-entropy-depleting.patch added to -mm tree

[Kees Cook]

On Tue, Nov 6, 2012 at 8:21 PM, Jeff Liu <jeff.liu@oracle.com> wrote:
> Hi Andrew and Kees,
>
> Great thanks for both your comments!
>
> On 11/07/2012 09:11 AM, Kees Cook wrote:
>> Hrm, I don't like this. get_random_int() specifically says: "Get a
>> random word for internal kernel use only." The intent of AT_RANDOM is
>> for userspace pRNG seeding (though glibc currently uses it directly
>> for stack protector and pointer mangling), which is not "internal
>> kernel use only". :) Though I suppose this is already being used for
>> the randomize_stack_top(), but I think it'd still be better to use
>> higher quality bits.
> Btw Kees, does it sounds make sense if we just return the 16 bytes
> uninitialized stack array if the user disable the stack randomize via
> "/proc/sys/kernel/randomize_va_space = 0" or via the related sysctl, or
> even specified norandmaps on boot?

No, I feel that ASLR (randomize_va_space) is distinctly separate from
how glibc uses AT_RANDOM (stack protector and pointer mangling).
AT_RANDOM should remain active even if randomize_va_space is 0.

-Kees

-- 
Kees Cook
Chrome OS Security

Re: + binfmt_elfc-use-get_random_int-to-fix-entropy-depleting.patch added to -mm tree

[Jeff Liu]

On 11/07/2012 12:29 PM, Kees Cook wrote:
> On Tue, Nov 6, 2012 at 8:21 PM, Jeff Liu <jeff.liu@oracle.com> wrote:
>> Hi Andrew and Kees,
>>
>> Great thanks for both your comments!
>>
>> On 11/07/2012 09:11 AM, Kees Cook wrote:
>>> Hrm, I don't like this. get_random_int() specifically says: "Get a
>>> random word for internal kernel use only." The intent of AT_RANDOM is
>>> for userspace pRNG seeding (though glibc currently uses it directly
>>> for stack protector and pointer mangling), which is not "internal
>>> kernel use only". :) Though I suppose this is already being used for
>>> the randomize_stack_top(), but I think it'd still be better to use
>>> higher quality bits.
>> Btw Kees, does it sounds make sense if we just return the 16 bytes
>> uninitialized stack array if the user disable the stack randomize via
>> "/proc/sys/kernel/randomize_va_space = 0" or via the related sysctl, or
>> even specified norandmaps on boot?
> 
> No, I feel that ASLR (randomize_va_space) is distinctly separate from
> how glibc uses AT_RANDOM (stack protector and pointer mangling).
> AT_RANDOM should remain active even if randomize_va_space is 0.
Ok, I was confused about the semantics of ASLR, thanks for your
clarification, will post another patch soon according to your feedback.

-Jeff

Re: + binfmt_elfc-use-get_random_int-to-fix-entropy-depleting.patch added to -mm tree

[Theodore Ts'o]

On Tue, Nov 06, 2012 at 05:11:17PM -0800, Kees Cook wrote:
> Hrm, I don't like this. get_random_int() specifically says: "Get a
> random word for internal kernel use only." The intent of AT_RANDOM is
> for userspace pRNG seeding (though glibc currently uses it directly
> for stack protector and pointer mangling), which is not "internal
> kernel use only". :) Though I suppose this is already being used for
> the randomize_stack_top(), but I think it'd still be better to use
> higher quality bits.

Well, in practice, right now, get_random_int() is only being used for
different cases of ASLR of one variety or another (either by the
kernel in exec or mmap, or in userspace).  So I'm not sure it really
is a major issue.  

If we also change get_random_int() to use a more secure cryptographic
random generator (i.e., maybe AES instead of MD5), would that be
sufficient to address your concerns?  We're not using get_random_int()
for anything that's timing sensitive, so that shouldn't be a problem.

Or maybe we should just add an explicit CRNG set of routines (like the
similar discussions to make an explicitly named PRNG set of routines),
so callers can use whatever random number generator is appropriate for
their performance and security needs.

						- Ted

Re: + binfmt_elfc-use-get_random_int-to-fix-entropy-depleting.patch added to -mm tree

[Kees Cook]

On Wed, Nov 7, 2012 at 1:32 AM, Theodore Ts'o <tytso@mit.edu> wrote:
> On Tue, Nov 06, 2012 at 05:11:17PM -0800, Kees Cook wrote:
>> Hrm, I don't like this. get_random_int() specifically says: "Get a
>> random word for internal kernel use only." The intent of AT_RANDOM is
>> for userspace pRNG seeding (though glibc currently uses it directly
>> for stack protector and pointer mangling), which is not "internal
>> kernel use only". :) Though I suppose this is already being used for
>> the randomize_stack_top(), but I think it'd still be better to use
>> higher quality bits.
>
> Well, in practice, right now, get_random_int() is only being used for
> different cases of ASLR of one variety or another (either by the
> kernel in exec or mmap, or in userspace).  So I'm not sure it really
> is a major issue.

Hrm, yes. I see that the network code uses random32, not
get_random_int(). How are these different? Is one demonstrably better?

> If we also change get_random_int() to use a more secure cryptographic
> random generator (i.e., maybe AES instead of MD5), would that be
> sufficient to address your concerns?  We're not using get_random_int()
> for anything that's timing sensitive, so that shouldn't be a problem.

I wonder if using AES would have a measurable impact on fork speeds?

> Or maybe we should just add an explicit CRNG set of routines (like the
> similar discussions to make an explicitly named PRNG set of routines),
> so callers can use whatever random number generator is appropriate for
> their performance and security needs.

If we do use get_random_int() here, I'd at least like to see its
comment changed to reflect its actual purpose (since it's not
"internal use only") as well as its expected unpredictability. (This
would help document the utility of get_random_bytes() vs
get_random_int() vs random32().)

-Kees

-- 
Kees Cook
Chrome OS Security

Re: + binfmt_elfc-use-get_random_int-to-fix-entropy-depleting.patch added to -mm tree

[Jeff Liu]

On 11/07/2012 11:10 PM, Kees Cook wrote:
> On Wed, Nov 7, 2012 at 1:32 AM, Theodore Ts'o <tytso@mit.edu> wrote:
>> On Tue, Nov 06, 2012 at 05:11:17PM -0800, Kees Cook wrote:
>>> Hrm, I don't like this. get_random_int() specifically says: "Get a
>>> random word for internal kernel use only." The intent of AT_RANDOM is
>>> for userspace pRNG seeding (though glibc currently uses it directly
>>> for stack protector and pointer mangling), which is not "internal
>>> kernel use only". :) Though I suppose this is already being used for
>>> the randomize_stack_top(), but I think it'd still be better to use
>>> higher quality bits.
>>
>> Well, in practice, right now, get_random_int() is only being used for
>> different cases of ASLR of one variety or another (either by the
>> kernel in exec or mmap, or in userspace).  So I'm not sure it really
>> is a major issue.
> 
> Hrm, yes. I see that the network code uses random32, not
> get_random_int(). How are these different? Is one demonstrably better?
I also have the same question in this point.
Both generators are NOT considered safe for cryptographic use, but the
comments of get_random_int() indicates that it could be used for several
uses the cost of depleting entropy is too high, that's why I chose it.
> 
>> If we also change get_random_int() to use a more secure cryptographic
>> random generator (i.e., maybe AES instead of MD5), would that be
>> sufficient to address your concerns?  We're not using get_random_int()
>> for anything that's timing sensitive, so that shouldn't be a problem.
> 
> I wonder if using AES would have a measurable impact on fork speeds?
> 
>> Or maybe we should just add an explicit CRNG set of routines (like the
>> similar discussions to make an explicitly named PRNG set of routines),
>> so callers can use whatever random number generator is appropriate for
>> their performance and security needs.
> 
> If we do use get_random_int() here, I'd at least like to see its
> comment changed to reflect its actual purpose (since it's not
> "internal use only") as well as its expected unpredictability. (This
> would help document the utility of get_random_bytes() vs
> get_random_int() vs random32().)
> 
> -Kees
Thanks,
-Jeff