[PATCH] ELF: implement AT_RANDOM for future glibc use

[PATCH] ELF: implement AT_RANDOM for future glibc use

[Kees Cook]

While discussing[1] the need for glibc to have access to random bytes
during program load, it seems that an earlier attempt to implement
AT_RANDOM got stalled.  This implements a configurable number of random
bytes available to every ELF program via a new auxv AT_RANDOM vector.

[1] http://sourceware.org/ml/libc-alpha/2008-10/msg00006.html

Signed-off-by: Kees Cook <kees.cook@canonical.com>
---
 fs/binfmt_elf.c        |   20 ++++++++++++++++++++
 include/linux/auxvec.h |    4 +++-
 security/Kconfig       |    9 +++++++++
 3 files changed, 32 insertions(+), 1 deletions(-)

diff --git a/fs/binfmt_elf.c b/fs/binfmt_elf.c
index 655ed8d..9b2ea62 100644
--- a/fs/binfmt_elf.c
+++ b/fs/binfmt_elf.c
@@ -152,6 +152,8 @@ create_elf_tables(struct linux_binprm *bprm, struct elfhdr *exec,
 	elf_addr_t __user *sp;
 	elf_addr_t __user *u_platform;
 	elf_addr_t __user *u_base_platform;
+	elf_addr_t __user *u_rand_bytes;
+	unsigned int rand_size;
 	const char *k_platform = ELF_PLATFORM;
 	const char *k_base_platform = ELF_BASE_PLATFORM;
 	int items;
@@ -196,6 +198,18 @@ create_elf_tables(struct linux_binprm *bprm, struct elfhdr *exec,
 			return -EFAULT;
 	}
 
+	rand_size = CONFIG_SECURITY_AUXV_RANDOM_SIZE * sizeof(unsigned long);
+	u_rand_bytes = NULL;
+	if (rand_size) {
+		unsigned char k_rand_bytes[CONFIG_SECURITY_AUXV_RANDOM_SIZE *
+					   sizeof(unsigned long)];
+		get_random_bytes(k_rand_bytes, rand_size);
+
+		u_rand_bytes = (elf_addr_t __user *)STACK_ALLOC(p, rand_size);
+		if (__copy_to_user(u_rand_bytes, k_rand_bytes, rand_size))
+			return -EFAULT;
+	}
+
 	/* Create the ELF interpreter info */
 	elf_info = (elf_addr_t *)current->mm->saved_auxv;
 	/* update AT_VECTOR_SIZE_BASE if the number of NEW_AUX_ENT() changes */
@@ -228,6 +242,12 @@ create_elf_tables(struct linux_binprm *bprm, struct elfhdr *exec,
 	NEW_AUX_ENT(AT_GID, tsk->gid);
 	NEW_AUX_ENT(AT_EGID, tsk->egid);
  	NEW_AUX_ENT(AT_SECURE, security_bprm_secureexec(bprm));
+	if (rand_size) {
+		NEW_AUX_ENT(AT_RANDOM_SIZE,
+			    (elf_addr_t)(unsigned long)rand_size);
+		NEW_AUX_ENT(AT_RANDOM,
+			    (elf_addr_t)(unsigned long)u_rand_bytes);
+	}
 	NEW_AUX_ENT(AT_EXECFN, bprm->exec);
 	if (k_platform) {
 		NEW_AUX_ENT(AT_PLATFORM,
diff --git a/include/linux/auxvec.h b/include/linux/auxvec.h
index d7afa9d..df4ff65 100644
--- a/include/linux/auxvec.h
+++ b/include/linux/auxvec.h
@@ -23,6 +23,8 @@
 #define AT_PLATFORM 15  /* string identifying CPU for optimizations */
 #define AT_HWCAP  16    /* arch dependent hints at CPU capabilities */
 #define AT_CLKTCK 17	/* frequency at which times() increments */
+#define AT_RANDOM 18    /* address of random bytes */
+#define AT_RANDOM_SIZE 19   /* number of random bytes at AT_RANDOM */
 
 #define AT_SECURE 23   /* secure mode boolean */
 
@@ -32,7 +34,7 @@
 #define AT_EXECFN  31	/* filename of program */
 
 #ifdef __KERNEL__
-#define AT_VECTOR_SIZE_BASE 18 /* NEW_AUX_ENT entries in auxiliary table */
+#define AT_VECTOR_SIZE_BASE 20 /* NEW_AUX_ENT entries in auxiliary table */
   /* number of "#define AT_.*" above, minus {AT_NULL, AT_IGNORE, AT_NOTELF} */
 #endif
 
diff --git a/security/Kconfig b/security/Kconfig
index f6c0429..8d9d49d 100644
--- a/security/Kconfig
+++ b/security/Kconfig
@@ -114,6 +114,15 @@ config SECURITY_DEFAULT_MMAP_MIN_ADDR
 	  This value can be changed after boot using the
 	  /proc/sys/vm/mmap_min_addr tunable.
 
+config SECURITY_AUXV_RANDOM_SIZE
+	int "Number of random longs to store in AT_RANDOM on every exec"
+	default 4
+	help
+	  This value determines the size of the random longs provided
+	  to programs via the auxv AT_RANDOM vector.  It can be used
+	  to initialize random values needed during program load.
+
+	  If you are unsure how many longs to use, answer 4.
 
 source security/selinux/Kconfig
 source security/smack/Kconfig
-- 
1.5.6.3

-- 
Kees Cook
Ubuntu Security Team

Re: [PATCH] ELF: implement AT_RANDOM for future glibc use

[Jakub Jelinek]

On Thu, Oct 02, 2008 at 05:16:16PM -0700, Kees Cook wrote:
> @@ -196,6 +198,18 @@ create_elf_tables(struct linux_binprm *bprm, struct elfhdr *exec,
>  			return -EFAULT;
>  	}
>  
> +	rand_size = CONFIG_SECURITY_AUXV_RANDOM_SIZE * sizeof(unsigned long);

I believe you want sizeof (elf_addr_t) here instead.

> +	u_rand_bytes = NULL;
> +	if (rand_size) {
> +		unsigned char k_rand_bytes[CONFIG_SECURITY_AUXV_RANDOM_SIZE *
> +					   sizeof(unsigned long)];

And here too, because having a 64-bit kernel supply twice as much random
data to 32-bit programs as a 32-bit kernel would supply would be certainly
unexpected.

	Jakub

Re: [PATCH] ELF: implement AT_RANDOM for future glibc use

[Kees Cook]

On Fri, Oct 03, 2008 at 02:43:40AM +0200, Jakub Jelinek wrote:
> On Thu, Oct 02, 2008 at 05:16:16PM -0700, Kees Cook wrote:
> > @@ -196,6 +198,18 @@ create_elf_tables(struct linux_binprm *bprm, struct elfhdr *exec,
> >  			return -EFAULT;
> >  	}
> >  
> > +	rand_size = CONFIG_SECURITY_AUXV_RANDOM_SIZE * sizeof(unsigned long);
> 
> I believe you want sizeof (elf_addr_t) here instead.
> 
> > +	u_rand_bytes = NULL;
> > +	if (rand_size) {
> > +		unsigned char k_rand_bytes[CONFIG_SECURITY_AUXV_RANDOM_SIZE *
> > +					   sizeof(unsigned long)];
> 
> And here too, because having a 64-bit kernel supply twice as much random
> data to 32-bit programs as a 32-bit kernel would supply would be certainly
> unexpected.

Ah-ha!  I see the 32-vs-64 elf_addr_t magic in fs/compat_binfmt_elf.c now.
Excellent, I will send an updated patch.

Thanks!

-Kees

-- 
Kees Cook
Ubuntu Security Team

[PATCH] ELF: implement AT_RANDOM for future glibc use

[Kees Cook]

While discussing[1] the need for glibc to have access to random bytes
during program load, it seems that an earlier attempt to implement
AT_RANDOM got stalled.  This implements a configurable number of random
bytes, as a multiple of userspace pointer size, available to every ELF
program via a new auxv AT_RANDOM vector.

[1] http://sourceware.org/ml/libc-alpha/2008-10/msg00006.html

Signed-off-by: Kees Cook <kees.cook@canonical.com>
---
 fs/binfmt_elf.c        |   20 ++++++++++++++++++++
 include/linux/auxvec.h |    5 +++--
 security/Kconfig       |    9 +++++++++
 3 files changed, 32 insertions(+), 2 deletions(-)

diff --git a/fs/binfmt_elf.c b/fs/binfmt_elf.c
index 655ed8d..fbaa665 100644
--- a/fs/binfmt_elf.c
+++ b/fs/binfmt_elf.c
@@ -152,6 +152,8 @@ create_elf_tables(struct linux_binprm *bprm, struct elfhdr *exec,
 	elf_addr_t __user *sp;
 	elf_addr_t __user *u_platform;
 	elf_addr_t __user *u_base_platform;
+	elf_addr_t __user *u_rand_bytes;
+	unsigned int rand_size;
 	const char *k_platform = ELF_PLATFORM;
 	const char *k_base_platform = ELF_BASE_PLATFORM;
 	int items;
@@ -196,6 +198,18 @@ create_elf_tables(struct linux_binprm *bprm, struct elfhdr *exec,
 			return -EFAULT;
 	}
 
+	rand_size = CONFIG_SECURITY_AUXV_RANDOM_SIZE * sizeof(elf_addr_t);
+	u_rand_bytes = NULL;
+	if (rand_size) {
+		unsigned char k_rand_bytes[CONFIG_SECURITY_AUXV_RANDOM_SIZE *
+					   sizeof(elf_addr_t)];
+		get_random_bytes(k_rand_bytes, rand_size);
+
+		u_rand_bytes = (elf_addr_t __user *)STACK_ALLOC(p, rand_size);
+		if (__copy_to_user(u_rand_bytes, k_rand_bytes, rand_size))
+			return -EFAULT;
+	}
+
 	/* Create the ELF interpreter info */
 	elf_info = (elf_addr_t *)current->mm->saved_auxv;
 	/* update AT_VECTOR_SIZE_BASE if the number of NEW_AUX_ENT() changes */
@@ -228,6 +242,12 @@ create_elf_tables(struct linux_binprm *bprm, struct elfhdr *exec,
 	NEW_AUX_ENT(AT_GID, tsk->gid);
 	NEW_AUX_ENT(AT_EGID, tsk->egid);
  	NEW_AUX_ENT(AT_SECURE, security_bprm_secureexec(bprm));
+	if (rand_size) {
+		NEW_AUX_ENT(AT_RANDOM_SIZE,
+			    (elf_addr_t)(unsigned long)rand_size);
+		NEW_AUX_ENT(AT_RANDOM,
+			    (elf_addr_t)(unsigned long)u_rand_bytes);
+	}
 	NEW_AUX_ENT(AT_EXECFN, bprm->exec);
 	if (k_platform) {
 		NEW_AUX_ENT(AT_PLATFORM,
diff --git a/include/linux/auxvec.h b/include/linux/auxvec.h
index d7afa9d..702e506 100644
--- a/include/linux/auxvec.h
+++ b/include/linux/auxvec.h
@@ -25,14 +25,15 @@
 #define AT_CLKTCK 17	/* frequency at which times() increments */
 
 #define AT_SECURE 23   /* secure mode boolean */
-
 #define AT_BASE_PLATFORM 24	/* string identifying real platform, may
 				 * differ from AT_PLATFORM. */
+#define AT_RANDOM_SIZE   25	/* number of random bytes at AT_RANDOM */
+#define AT_RANDOM 26	/* address of random bytes */
 
 #define AT_EXECFN  31	/* filename of program */
 
 #ifdef __KERNEL__
-#define AT_VECTOR_SIZE_BASE 18 /* NEW_AUX_ENT entries in auxiliary table */
+#define AT_VECTOR_SIZE_BASE 20 /* NEW_AUX_ENT entries in auxiliary table */
   /* number of "#define AT_.*" above, minus {AT_NULL, AT_IGNORE, AT_NOTELF} */
 #endif
 
diff --git a/security/Kconfig b/security/Kconfig
index f6c0429..64f0da9 100644
--- a/security/Kconfig
+++ b/security/Kconfig
@@ -114,6 +114,15 @@ config SECURITY_DEFAULT_MMAP_MIN_ADDR
 	  This value can be changed after boot using the
 	  /proc/sys/vm/mmap_min_addr tunable.
 
+config SECURITY_AUXV_RANDOM_SIZE
+	int "Number of pointer-sized random byte strings in AT_RANDOM"
+	default 4
+	help
+	  This value determines how many pointer-sized random byte strings
+	  are provided to programs via the auxv AT_RANDOM vector.  It can
+	  be used to initialize random values needed during program load.
+
+	  If you are unsure how many to use, answer 4.
 
 source security/selinux/Kconfig
 source security/smack/Kconfig
-- 
1.5.6.3

-- 
Kees Cook
Ubuntu Security Team

Re: [PATCH] ELF: implement AT_RANDOM for future glibc use

[Arjan van de Ven]

On Thu, 2 Oct 2008 22:29:38 -0700
Kees Cook <kees.cook@canonical.com> wrote:

> While discussing[1] the need for glibc to have access to random bytes
> during program load, it seems that an earlier attempt to implement
> AT_RANDOM got stalled.  This implements a configurable number of
> random bytes, as a multiple of userspace pointer size, available to
> every ELF program via a new auxv AT_RANDOM vector.


while I really like the idea of passing random bytes to glibc...
... why make it complex and configurable, rather than just always
passing, say 8 or 16 bytes.
16 bytes (say 4 vectors) is easier than "variable number of" both on the
kernel and on the glibc side, and nobody other than maybe Ulrich
and Jakub wouldn't know what to answer to the KConfig question anyway.

Or lets put it differently: why would I answer anything other than the
default? Your KConfig help text sure doesn't explain my what I give up
by answering 0 or 256....  If nobody can answer anything sensible other
than the default, it shouldn't be a config option imo.

Re: [PATCH] ELF: implement AT_RANDOM for future glibc use

[Ulrich Drepper]

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

Arjan van de Ven wrote:
> 16 bytes (say 4 vectors) is easier than "variable number of" both on the
> kernel and on the glibc side, and nobody other than maybe Ulrich
> and Jakub wouldn't know what to answer to the KConfig question anyway.

As Roland already wrote, I consider 16 bytes sufficient.  Everything
else will then be served via a PRNG which is seeded through the 16 bytes.

- --
➧ Ulrich Drepper ➧ Red Hat, Inc. ➧ 444 Castro St ➧ Mountain View, CA ❖
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (GNU/Linux)
Comment: Using GnuPG with Fedora - http://enigmail.mozdev.org

iEYEARECAAYFAkjlusYACgkQ2ijCOnn/RHTOqwCghULjVoA+bZVlqv8eFhSHRPOt
jUYAoMNM+IXtS3HkVTZdFsH3kooSWFk2
=Z6f0
-----END PGP SIGNATURE-----

[PATCH] ELF: implement AT_RANDOM for glibc PRNG seeding

[Kees Cook]

While discussing[1] the need for glibc to have access to random bytes
during program load, it seems that an earlier attempt to implement
AT_RANDOM got stalled.  This implements a random 16 byte string, available
to every ELF program via a new auxv AT_RANDOM vector.

[1] http://sourceware.org/ml/libc-alpha/2008-10/msg00006.html

Signed-off-by: Kees Cook <kees.cook@canonical.com>
---
 fs/binfmt_elf.c        |   27 +++++++++++++++++++++++++++
 include/linux/auxvec.h |    7 ++++---
 2 files changed, 31 insertions(+), 3 deletions(-)

diff --git a/fs/binfmt_elf.c b/fs/binfmt_elf.c
index 655ed8d..11931f8 100644
--- a/fs/binfmt_elf.c
+++ b/fs/binfmt_elf.c
@@ -140,6 +140,14 @@ static int padzero(unsigned long elf_bss)
 #define ELF_BASE_PLATFORM NULL
 #endif
 
+#ifndef ELF_AUXV_RANDOM_SIZE
+/*
+ * AT_RANDOM provides a random byte stream which can be used to seed
+ * userspace PRNGs at program load time.
+ */
+#define ELF_AUXV_RANDOM_SIZE 16
+#endif
+
 static int
 create_elf_tables(struct linux_binprm *bprm, struct elfhdr *exec,
 		unsigned long load_addr, unsigned long interp_load_addr)
@@ -152,6 +160,8 @@ create_elf_tables(struct linux_binprm *bprm, struct elfhdr *exec,
 	elf_addr_t __user *sp;
 	elf_addr_t __user *u_platform;
 	elf_addr_t __user *u_base_platform;
+	elf_addr_t __user *u_rand_bytes;
+	unsigned int rand_size;
 	const char *k_platform = ELF_PLATFORM;
 	const char *k_base_platform = ELF_BASE_PLATFORM;
 	int items;
@@ -196,6 +206,17 @@ create_elf_tables(struct linux_binprm *bprm, struct elfhdr *exec,
 			return -EFAULT;
 	}
 
+	rand_size = ELF_AUXV_RANDOM_SIZE;
+	u_rand_bytes = NULL;
+	if (rand_size) {
+		unsigned char k_rand_bytes[ELF_AUXV_RANDOM_SIZE];
+		get_random_bytes(k_rand_bytes, rand_size);
+
+		u_rand_bytes = (elf_addr_t __user *)STACK_ALLOC(p, rand_size);
+		if (__copy_to_user(u_rand_bytes, k_rand_bytes, rand_size))
+			return -EFAULT;
+	}
+
 	/* Create the ELF interpreter info */
 	elf_info = (elf_addr_t *)current->mm->saved_auxv;
 	/* update AT_VECTOR_SIZE_BASE if the number of NEW_AUX_ENT() changes */
@@ -228,6 +249,12 @@ create_elf_tables(struct linux_binprm *bprm, struct elfhdr *exec,
 	NEW_AUX_ENT(AT_GID, tsk->gid);
 	NEW_AUX_ENT(AT_EGID, tsk->egid);
  	NEW_AUX_ENT(AT_SECURE, security_bprm_secureexec(bprm));
+	if (rand_size) {
+		NEW_AUX_ENT(AT_RANDOM_SIZE,
+			    (elf_addr_t)(unsigned long)rand_size);
+		NEW_AUX_ENT(AT_RANDOM,
+			    (elf_addr_t)(unsigned long)u_rand_bytes);
+	}
 	NEW_AUX_ENT(AT_EXECFN, bprm->exec);
 	if (k_platform) {
 		NEW_AUX_ENT(AT_PLATFORM,
diff --git a/include/linux/auxvec.h b/include/linux/auxvec.h
index d7afa9d..dac7fc2 100644
--- a/include/linux/auxvec.h
+++ b/include/linux/auxvec.h
@@ -23,16 +23,17 @@
 #define AT_PLATFORM 15  /* string identifying CPU for optimizations */
 #define AT_HWCAP  16    /* arch dependent hints at CPU capabilities */
 #define AT_CLKTCK 17	/* frequency at which times() increments */
-
+/* AT_* values 18 through 22 are reserved */
 #define AT_SECURE 23   /* secure mode boolean */
-
 #define AT_BASE_PLATFORM 24	/* string identifying real platform, may
 				 * differ from AT_PLATFORM. */
+#define AT_RANDOM_SIZE   25	/* number of random bytes at AT_RANDOM */
+#define AT_RANDOM 26	/* address of random bytes */
 
 #define AT_EXECFN  31	/* filename of program */
 
 #ifdef __KERNEL__
-#define AT_VECTOR_SIZE_BASE 18 /* NEW_AUX_ENT entries in auxiliary table */
+#define AT_VECTOR_SIZE_BASE 20 /* NEW_AUX_ENT entries in auxiliary table */
   /* number of "#define AT_.*" above, minus {AT_NULL, AT_IGNORE, AT_NOTELF} */
 #endif
 
-- 
1.5.6.3

-- 
Kees Cook
Ubuntu Security Team

Re: [PATCH] ELF: implement AT_RANDOM for glibc PRNG seeding

[Ulrich Drepper]

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

There is no need for a AT_RANDOM_SIZE entry.  It's unlikely that ever a
different value is used.  The kernel's entropy pool cannot be strssed
that much.  If more data is needed userlevel will use the bits to seed a
PRNG.

- --
➧ Ulrich Drepper ➧ Red Hat, Inc. ➧ 444 Castro St ➧ Mountain View, CA ❖
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (GNU/Linux)

iEYEARECAAYFAkjmMrkACgkQ2ijCOnn/RHS9QQCgvCKS9jKMmCI+ow3BmboHgjfb
5CAAni8Qohrs3qZ1RPa9fqCKMsUE355o
=9bI+
-----END PGP SIGNATURE-----

Re: [PATCH] ELF: implement AT_RANDOM for glibc PRNG seeding

[Jakub Jelinek]

On Fri, Oct 03, 2008 at 07:50:54AM -0700, Kees Cook wrote:
> @@ -152,6 +160,8 @@ create_elf_tables(struct linux_binprm *bprm, struct elfhdr *exec,
>  	elf_addr_t __user *sp;
>  	elf_addr_t __user *u_platform;
>  	elf_addr_t __user *u_base_platform;
> +	elf_addr_t __user *u_rand_bytes;
> +	unsigned int rand_size;
>  	const char *k_platform = ELF_PLATFORM;
>  	const char *k_base_platform = ELF_BASE_PLATFORM;
>  	int items;

Why are you introducing the rand_size variable at all?  The only thing it
can cause is confuse somebody to change it, which might do bad things as
k_rand_bytes var uses ELF_AUXV_RANDOM_SIZE directly.  Just use
ELF_AUXV_RANDOM_SIZE in all places you use rand_size ATM (except the
assignment and declaration of course).

	Jakub

[PATCH] ELF: implement AT_RANDOM for glibc PRNG seeding

[Kees Cook]

While discussing[1] the need for glibc to have access to random bytes
during program load, it seems that an earlier attempt to implement
AT_RANDOM got stalled.  This implements a random 16 byte string, available
to every ELF program via a new auxv AT_RANDOM vector.

[1] http://sourceware.org/ml/libc-alpha/2008-10/msg00006.html

Signed-off-by: Kees Cook <kees.cook@canonical.com>
---
 fs/binfmt_elf.c        |   25 +++++++++++++++++++++++++
 include/linux/auxvec.h |    6 +++---
 2 files changed, 28 insertions(+), 3 deletions(-)

diff --git a/fs/binfmt_elf.c b/fs/binfmt_elf.c
index 655ed8d..479a7a4 100644
--- a/fs/binfmt_elf.c
+++ b/fs/binfmt_elf.c
@@ -140,6 +140,14 @@ static int padzero(unsigned long elf_bss)
 #define ELF_BASE_PLATFORM NULL
 #endif
 
+#ifndef ELF_AUXV_RANDOM_SIZE
+/*
+ * AT_RANDOM provides 16 random bytes which can be used to seed
+ * userspace PRNGs at program load time.
+ */
+#define ELF_AUXV_RANDOM_SIZE 16
+#endif
+
 static int
 create_elf_tables(struct linux_binprm *bprm, struct elfhdr *exec,
 		unsigned long load_addr, unsigned long interp_load_addr)
@@ -152,6 +160,7 @@ create_elf_tables(struct linux_binprm *bprm, struct elfhdr *exec,
 	elf_addr_t __user *sp;
 	elf_addr_t __user *u_platform;
 	elf_addr_t __user *u_base_platform;
+	elf_addr_t __user *u_rand_bytes;
 	const char *k_platform = ELF_PLATFORM;
 	const char *k_base_platform = ELF_BASE_PLATFORM;
 	int items;
@@ -196,6 +205,18 @@ create_elf_tables(struct linux_binprm *bprm, struct elfhdr *exec,
 			return -EFAULT;
 	}
 
+	u_rand_bytes = NULL;
+	if (ELF_AUXV_RANDOM_SIZE) {
+		unsigned char k_rand_bytes[ELF_AUXV_RANDOM_SIZE];
+		get_random_bytes(k_rand_bytes, ELF_AUXV_RANDOM_SIZE);
+
+		u_rand_bytes = (elf_addr_t __user *)
+			       STACK_ALLOC(p, ELF_AUXV_RANDOM_SIZE);
+		if (__copy_to_user(u_rand_bytes, k_rand_bytes,
+				   ELF_AUXV_RANDOM_SIZE))
+			return -EFAULT;
+	}
+
 	/* Create the ELF interpreter info */
 	elf_info = (elf_addr_t *)current->mm->saved_auxv;
 	/* update AT_VECTOR_SIZE_BASE if the number of NEW_AUX_ENT() changes */
@@ -228,6 +249,10 @@ create_elf_tables(struct linux_binprm *bprm, struct elfhdr *exec,
 	NEW_AUX_ENT(AT_GID, tsk->gid);
 	NEW_AUX_ENT(AT_EGID, tsk->egid);
  	NEW_AUX_ENT(AT_SECURE, security_bprm_secureexec(bprm));
+	if (ELF_AUXV_RANDOM_SIZE) {
+		NEW_AUX_ENT(AT_RANDOM,
+			    (elf_addr_t)(unsigned long)u_rand_bytes);
+	}
 	NEW_AUX_ENT(AT_EXECFN, bprm->exec);
 	if (k_platform) {
 		NEW_AUX_ENT(AT_PLATFORM,
diff --git a/include/linux/auxvec.h b/include/linux/auxvec.h
index d7afa9d..d85b8f7 100644
--- a/include/linux/auxvec.h
+++ b/include/linux/auxvec.h
@@ -23,16 +23,16 @@
 #define AT_PLATFORM 15  /* string identifying CPU for optimizations */
 #define AT_HWCAP  16    /* arch dependent hints at CPU capabilities */
 #define AT_CLKTCK 17	/* frequency at which times() increments */
-
+/* AT_* values 18 through 22 are reserved */
 #define AT_SECURE 23   /* secure mode boolean */
-
 #define AT_BASE_PLATFORM 24	/* string identifying real platform, may
 				 * differ from AT_PLATFORM. */
+#define AT_RANDOM 25	/* address of 16 random bytes */
 
 #define AT_EXECFN  31	/* filename of program */
 
 #ifdef __KERNEL__
-#define AT_VECTOR_SIZE_BASE 18 /* NEW_AUX_ENT entries in auxiliary table */
+#define AT_VECTOR_SIZE_BASE 20 /* NEW_AUX_ENT entries in auxiliary table */
   /* number of "#define AT_.*" above, minus {AT_NULL, AT_IGNORE, AT_NOTELF} */
 #endif
 
-- 
1.5.6.3

-- 
Kees Cook
Ubuntu Security Team

Re: [PATCH] ELF: implement AT_RANDOM for glibc PRNG seeding

[Ulrich Drepper]

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

Kees Cook wrote:
> +#ifndef ELF_AUXV_RANDOM_SIZE
> +/*
> + * AT_RANDOM provides 16 random bytes which can be used to seed
> + * userspace PRNGs at program load time.
> + */
> +#define ELF_AUXV_RANDOM_SIZE 16
> +#endif

No, this cannot be changeable because there is no way for userland to
find out the size.  And no, don't reintroduce the the extra aux vector
entry.  Just define it to 16 and that's it.

- --
➧ Ulrich Drepper ➧ Red Hat, Inc. ➧ 444 Castro St ➧ Mountain View, CA ❖
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (GNU/Linux)
Comment: Using GnuPG with Fedora - http://enigmail.mozdev.org

iEYEARECAAYFAkjmWWQACgkQ2ijCOnn/RHTbUACfU7i4DImOYXiFNxPa7m7HWiMX
4iQAoLk+7r0bVPGSrjAUcwW701oeDKlJ
=y+Ci
-----END PGP SIGNATURE-----

[PATCH v5] ELF: implement AT_RANDOM for glibc PRNG seeding

[Kees Cook]

While discussing[1] the need for glibc to have access to random bytes
during program load, it seems that an earlier attempt to implement
AT_RANDOM got stalled.  This implements a random 16 byte string, available
to every ELF program via a new auxv AT_RANDOM vector.

[1] http://sourceware.org/ml/libc-alpha/2008-10/msg00006.html

Signed-off-by: Kees Cook <kees.cook@canonical.com>
---
 fs/binfmt_elf.c        |   12 ++++++++++++
 include/linux/auxvec.h |    6 +++---
 2 files changed, 15 insertions(+), 3 deletions(-)

diff --git a/fs/binfmt_elf.c b/fs/binfmt_elf.c
index 655ed8d..1934ab3 100644
--- a/fs/binfmt_elf.c
+++ b/fs/binfmt_elf.c
@@ -152,8 +152,10 @@ create_elf_tables(struct linux_binprm *bprm, struct elfhdr *exec,
 	elf_addr_t __user *sp;
 	elf_addr_t __user *u_platform;
 	elf_addr_t __user *u_base_platform;
+	elf_addr_t __user *u_rand_bytes;
 	const char *k_platform = ELF_PLATFORM;
 	const char *k_base_platform = ELF_BASE_PLATFORM;
+	unsigned char k_rand_bytes[16];
 	int items;
 	elf_addr_t *elf_info;
 	int ei_index = 0;
@@ -196,6 +198,15 @@ create_elf_tables(struct linux_binprm *bprm, struct elfhdr *exec,
 			return -EFAULT;
 	}
 
+	/*
+	 * Generate 16 random bytes for userspace PRNG seeding.
+	 */
+	get_random_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)))
+		return -EFAULT;
+
 	/* Create the ELF interpreter info */
 	elf_info = (elf_addr_t *)current->mm->saved_auxv;
 	/* update AT_VECTOR_SIZE_BASE if the number of NEW_AUX_ENT() changes */
@@ -228,6 +239,7 @@ create_elf_tables(struct linux_binprm *bprm, struct elfhdr *exec,
 	NEW_AUX_ENT(AT_GID, tsk->gid);
 	NEW_AUX_ENT(AT_EGID, tsk->egid);
  	NEW_AUX_ENT(AT_SECURE, security_bprm_secureexec(bprm));
+	NEW_AUX_ENT(AT_RANDOM, (elf_addr_t)(unsigned long)u_rand_bytes);
 	NEW_AUX_ENT(AT_EXECFN, bprm->exec);
 	if (k_platform) {
 		NEW_AUX_ENT(AT_PLATFORM,
diff --git a/include/linux/auxvec.h b/include/linux/auxvec.h
index d7afa9d..f3b5d4e 100644
--- a/include/linux/auxvec.h
+++ b/include/linux/auxvec.h
@@ -23,16 +23,16 @@
 #define AT_PLATFORM 15  /* string identifying CPU for optimizations */
 #define AT_HWCAP  16    /* arch dependent hints at CPU capabilities */
 #define AT_CLKTCK 17	/* frequency at which times() increments */
-
+/* AT_* values 18 through 22 are reserved */
 #define AT_SECURE 23   /* secure mode boolean */
-
 #define AT_BASE_PLATFORM 24	/* string identifying real platform, may
 				 * differ from AT_PLATFORM. */
+#define AT_RANDOM 25	/* address of 16 random bytes */
 
 #define AT_EXECFN  31	/* filename of program */
 
 #ifdef __KERNEL__
-#define AT_VECTOR_SIZE_BASE 18 /* NEW_AUX_ENT entries in auxiliary table */
+#define AT_VECTOR_SIZE_BASE 19 /* NEW_AUX_ENT entries in auxiliary table */
   /* number of "#define AT_.*" above, minus {AT_NULL, AT_IGNORE, AT_NOTELF} */
 #endif
 
-- 
1.5.6.3

-- 
Kees Cook
Ubuntu Security Team

Re: [PATCH v5] ELF: implement AT_RANDOM for glibc PRNG seeding

[Ulrich Drepper]

On Fri, Oct 3, 2008 at 10:59 AM, Kees Cook <kees.cook@canonical.com> wrote:
> While discussing[1] the need for glibc to have access to random bytes
> during program load, it seems that an earlier attempt to implement
> AT_RANDOM got stalled.  This implements a random 16 byte string, available
> to every ELF program via a new auxv AT_RANDOM vector.
>
> [1] http://sourceware.org/ml/libc-alpha/2008-10/msg00006.html
>
> Signed-off-by: Kees Cook <kees.cook@canonical.com>
> ---
>  fs/binfmt_elf.c        |   12 ++++++++++++
>  include/linux/auxvec.h |    6 +++---
>  2 files changed, 15 insertions(+), 3 deletions(-)

This version is OK with me as long as the get_random_bytes call is
producing 16 reasonably random bytes.  If the random data generation
is changed at some point I'd want to have very strong PRNG for
binaries which have AT_SECURE set.

Acked-by: Ulrich Drepper <drepper@redhat.com>

Re: [PATCH v5] ELF: implement AT_RANDOM for glibc PRNG seeding

[Andrew Morton]

On Fri, 3 Oct 2008 10:59:17 -0700
Kees Cook <kees.cook@canonical.com> wrote:

> While discussing[1] the need for glibc to have access to random bytes
> during program load, it seems that an earlier attempt to implement
> AT_RANDOM got stalled.  This implements a random 16 byte string, available
> to every ELF program via a new auxv AT_RANDOM vector.
> 
> [1] http://sourceware.org/ml/libc-alpha/2008-10/msg00006.html

I read the above changeloglet and read the above-linked page and it's
still 87% unclear to me what this feature does.  Something to do with
stack randomisation, apparently.  I suppose I could go do further
hunting, but from the quality-of-changelog POV I don't think I should
need to do so.

IOW: better changelog, please.

It's unclear to me that the random-number issue got sorted out?

Re: [PATCH v5] ELF: implement AT_RANDOM for glibc PRNG seeding

[Ulrich Drepper]

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

Andrew Morton wrote:
> I read the above changeloglet and read the above-linked page and it's
> still 87% unclear to me what this feature does.  Something to do with
> stack randomisation, apparently.  I suppose I could go do further
> hunting, but from the quality-of-changelog POV I don't think I should
> need to do so.

Not stack randomization.  glibc needs right after startup a bit of
random data for internal protections (stack canary etc).  What is now in
upstream glibc is that we always unconditionally open /dev/urandom, read
some data, and use it.  For every process startup.  That's slow.

In addition Andi mentioned that this use of /dev/urandom might be
problematic.  I let him explain this.

The solution is to provide a limited amount of random data to the
starting process in the aux vector.  I suggested 16 bytes and this is
what the patch implements.  If we need only 16 bytes or less we use the
data directly.  If we need more we'll use the 16 bytes to see a PRNG.
This avoids the costly /dev/urandom use and it allows the kernel to use
the most adequate source of random data for this purpose.  It might not
be the same pool as that for /dev/urandom.


> It's unclear to me that the random-number issue got sorted out?

I think the last patch used the normal function to get 16 random bytes,
equivalent to the data used for stack randomization etc.

If Andi has concrete proposals for a revamp of the use of entropy in the
kernel this can be easily done as an add-on.  This patch doesn't make
the situation worse, it doesn't deplete entropy more than it happens now.

- --
➧ Ulrich Drepper ➧ Red Hat, Inc. ➧ 444 Castro St ➧ Mountain View, CA ❖
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (GNU/Linux)

iEYEARECAAYFAkj+OfoACgkQ2ijCOnn/RHST+gCfTriVvBAdfYNXSPuklog3V47u
/2kAnipBxYx7IFZe/M2zc6MOnDZkalSb
=JpXN
-----END PGP SIGNATURE-----

Re: [PATCH v5] ELF: implement AT_RANDOM for glibc PRNG seeding

[Andrew Morton]

On Tue, 21 Oct 2008 13:22:18 -0700 Ulrich Drepper <drepper@redhat.com> wrote:

> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
> 
> Andrew Morton wrote:
> > I read the above changeloglet and read the above-linked page and it's
> > still 87% unclear to me what this feature does.  Something to do with
> > stack randomisation, apparently.  I suppose I could go do further
> > hunting, but from the quality-of-changelog POV I don't think I should
> > need to do so.
> 
> Not stack randomization.  glibc needs right after startup a bit of
> random data for internal protections (stack canary etc).  What is now in
> upstream glibc is that we always unconditionally open /dev/urandom, read
> some data, and use it.  For every process startup.  That's slow.
> 
> In addition Andi mentioned that this use of /dev/urandom might be
> problematic.  I let him explain this.
> 
> The solution is to provide a limited amount of random data to the
> starting process in the aux vector.  I suggested 16 bytes and this is
> what the patch implements.  If we need only 16 bytes or less we use the
> data directly.  If we need more we'll use the 16 bytes to see a PRNG.
> This avoids the costly /dev/urandom use and it allows the kernel to use
> the most adequate source of random data for this purpose.  It might not
> be the same pool as that for /dev/urandom.
> 

Thanks.

> > It's unclear to me that the random-number issue got sorted out?
> 
> I think the last patch used the normal function to get 16 random bytes,
> equivalent to the data used for stack randomization etc.
> 
> If Andi has concrete proposals for a revamp of the use of entropy in the
> kernel this can be easily done as an add-on.  This patch doesn't make
> the situation worse, it doesn't deplete entropy more than it happens now.
> 

True.

As long as glibc doesn't do the /dev/urandom read when the kenrel has
already done that.  I assume that it will do so, until AT_RANDOM-aware
glibc has propagated out?

Re: [PATCH] ELF: implement AT_RANDOM for future glibc use

[Roland McGrath]

I think the safe available AT_* values to use are 25, 26.

I would configure the size in bytes.  Ulrich suggested it be 16 bytes on
both 32-bit and 64-bit machines.


Thanks,
Roland

Re: [PATCH] ELF: implement AT_RANDOM for future glibc use

[Kees Cook]

On Thu, Oct 02, 2008 at 05:52:58PM -0700, Roland McGrath wrote:
> I think the safe available AT_* values to use are 25, 26.

Out of curiosity, why are there gaps?  I figure I can include some
comments in that header to explain the gaps for future AT_* creations.

> I would configure the size in bytes.  Ulrich suggested it be 16 bytes on
> both 32-bit and 64-bit machines.

I was trying to make the size compile-time static so I could avoid
kmalloc'ing a buffer for get_random_bytes().  But maybe avoid that isn't
sensible?

As for 16 bytes on both 32bit and 64bit, I was aiming to have 4
pointer-sized random values.  16 works for 32bit, but I was hoping to
have 32 on 64bit.  Perhaps I am over-estimating?

-Kees

-- 
Kees Cook
Ubuntu Security Team

Re: [PATCH] ELF: implement AT_RANDOM for future glibc use

[Roland McGrath]

> Out of curiosity, why are there gaps?  I figure I can include some
> comments in that header to explain the gaps for future AT_* creations.

There are some values defined only on one particular arch.

Re: [PATCH] ELF: implement AT_RANDOM for future glibc use

[Andi Kleen]

Kees Cook <kees.cook@canonical.com> writes:

> While discussing[1] the need for glibc to have access to random bytes
> during program load, it seems that an earlier attempt to implement
> AT_RANDOM got stalled.  This implements a configurable number of random
> bytes available to every ELF program via a new auxv AT_RANDOM vector.

While the basic idea is good using get_random_bytes() is not. 

That eats precious cryptography strength entropy from the entropy
pool, which on many systems is not adequately fed. In those cases you
really only want to use it for real keys, not for lower grade
applications. The applications glibc wants to use this for do not
really require crypto strength entropy, just relatively unpredictable
randomness.

What you should instead do is to initialize some other cryptographic RNG 
regularly and use the output of that.

-Andi

Re: [PATCH] ELF: implement AT_RANDOM for future glibc use

[Kees Cook]

On Mon, Oct 06, 2008 at 08:00:21AM +0200, Andi Kleen wrote:
> Kees Cook <kees.cook@canonical.com> writes:
> 
> > While discussing[1] the need for glibc to have access to random bytes
> > during program load, it seems that an earlier attempt to implement
> > AT_RANDOM got stalled.  This implements a configurable number of random
> > bytes available to every ELF program via a new auxv AT_RANDOM vector.
> 
> While the basic idea is good using get_random_bytes() is not.
> 
> That eats precious cryptography strength entropy from the entropy
> pool, which on many systems is not adequately fed. In those cases you
> really only want to use it for real keys, not for lower grade
> applications. The applications glibc wants to use this for do not
> really require crypto strength entropy, just relatively unpredictable
> randomness.

We're already using get_random* for stack, heap, and brk.  Also,
get_random* uses the nonblocking pool, so this is the same as if userspace
had tried to pull bytes out of /dev/urandom, which (as I understand it)
is the very thing we're trying to duplicate without the VFS overhead.

> What you should instead do is to initialize some other cryptographic RNG
> regularly and use the output of that.

Can you give me some examples of this?  I thought the nonblocking
entropy pool was specifically for this purpose?

-Kees

-- 
Kees Cook
Ubuntu Security Team

Re: [PATCH] ELF: implement AT_RANDOM for future glibc use

[David Wagner]

Kees Cook  wrote:
>On Mon, Oct 06, 2008 at 08:00:21AM +0200, Andi Kleen wrote:
>> While the basic idea is good using get_random_bytes() is not.
>> 
>> That eats precious cryptography strength entropy from the entropy
>> pool, which on many systems is not adequately fed. In those cases you
>> really only want to use it for real keys, not for lower grade
>> applications. The applications glibc wants to use this for do not
>> really require crypto strength entropy, just relatively unpredictable
>> randomness.
>
>We're already using get_random* for stack, heap, and brk.  Also,
>get_random* uses the nonblocking pool, so this is the same as if userspace
>had tried to pull bytes out of /dev/urandom, which (as I understand it)
>is the very thing we're trying to duplicate without the VFS overhead.

Using /dev/urandom does seem like exactly the right thing to do.
(Andi Kleen's criticisms would be relevant if get_random_bytes() acted
like reading from /dev/random.)

I don't think it would be wise to use less than crypto strength
pseudorandom numbers for glibc -- at least, not without very thorough
analysis.  glibc is using this for security, so it has to be right.
When people say "oh, we don't need crypto-strength randomness", in
my experience it's too common to end up with something insecure.

Re: [PATCH] ELF: implement AT_RANDOM for future glibc use

[Andi Kleen]

daw@cs.berkeley.edu (David Wagner) writes:

> Kees Cook  wrote:
>>On Mon, Oct 06, 2008 at 08:00:21AM +0200, Andi Kleen wrote:
>>> While the basic idea is good using get_random_bytes() is not.
>>> 
>>> That eats precious cryptography strength entropy from the entropy
>>> pool, which on many systems is not adequately fed. In those cases you
>>> really only want to use it for real keys, not for lower grade
>>> applications. The applications glibc wants to use this for do not
>>> really require crypto strength entropy, just relatively unpredictable
>>> randomness.
>>
>>We're already using get_random* for stack, heap, and brk.  Also,
>>get_random* uses the nonblocking pool, so this is the same as if userspace
>>had tried to pull bytes out of /dev/urandom, which (as I understand it)
>>is the very thing we're trying to duplicate without the VFS overhead.
>
> Using /dev/urandom does seem like exactly the right thing to do.

Nobody really is using blocking /dev/random anymore, unless you like seeing
"Please bang the keyboard randomly until the pool is full" messages.
Good luck doing that on a rackmounted system in some data center.

Unfortunately most systems have very little real entropy
input, so every application what doesn't want itself constantly
dos'ed has to use /dev/unradom.

> (Andi Kleen's criticisms would be relevant if get_random_bytes() acted
> like reading from /dev/random.)

It does. It processes your real entropy from the pool and then
afterwards it's not unique anymore because it has been reused. Yes it
runs through a few hashes and what not, so it's not trivially
predictable, and it won't block on depletion, but it still
affects the entropy pool and degenerates it into a psuedo
random RNG.

The only chance to have some for the applications
that really need it is to conserve the little entropy
that is there anyways as best as possible. And giving out 
16 bytes of it (or rather dilluting it by giving out
parts of it) for each programs isn't the way to do.

> I don't think it would be wise to use less than crypto strength
> pseudorandom numbers for glibc 

It depends on how you define crypto strength pseudorandom:
if you refer to a true environmental entropy pool then you're clearly wrong.
If you refer to some crytographic pseudo RNG: that is what
urandom does, except that it still uses up previous real
entropy so that the next user who needs real entropy for their
session keys won't get as much (or rather it will get low quality entropy
instead which is dangerous)
The better way would be to use a crypto strength RNG that is only
seeded very seldom from the true pool, as to not affect the precious
real entropy pool for applications that really need it much.

> -- at least, not without very thorough
> analysis.  glibc is using this for security, so it has to be right.
> When people say "oh, we don't need crypto-strength randomness", in
> my experience it's too common to end up with something insecure.

The problem in your reasoning is that you assume the entropy
pool is a infinite resource that there is enough for everybody.
While that's a nice theory it does not match real systems unfortunately.

So in your quest for "same strength for everyone" you end up
with "poor strength for everyone". Bad tradeoff. 

-Andi

Re: [PATCH] ELF: implement AT_RANDOM for future glibc use

[David Wagner]

Andi Kleen  wrote:
>Nobody really is using blocking /dev/random anymore,

Good.  /dev/random was a poor choice for most applications.
I've always lamented the naming scheme (which for a long time
caused many applications to use /dev/random when /dev/urandom would
have been more appropriate).

>> (Andi Kleen's criticisms would be relevant if get_random_bytes() acted
>> like reading from /dev/random.)
>
>It does. It processes your real entropy from the pool and then
>afterwards it's not unique anymore because it has been reused. Yes it
>runs through a few hashes and what not, so it's not trivially
>predictable, and it won't block on depletion, but it still
>affects the entropy pool and degenerates it into a psuedo
>random RNG.

?  You say get_random_bytes() acts like reading from /dev/random,
but then your subsequent sentences are consistent with it acting like
reading from /dev/urandom, so I'm lost.

/dev/urandom also runs its inputs through cryptographic hash functions
to ensure that it acts as a cryptographic-quality pseudorandom number
generator.  /dev/urandom also won't block on depletion.  /dev/urandom
also affects the entropy pool.  /dev/urandom is a pseudorandom number
generator.

"not trivially predictable" seems overly dismissive.  /dev/urandom is
a lot better than "not trivially predictable"; it is intended as a
cryptographic-quality PRNG.  It's not just "run through a few hashes
and what not": it uses cryptographic hash functions in an appropriately
chosen way to ensure that its output will be cryptographically strong
(assuming it has been properly seeded, and assuming that the
cryptographic hash functions have no relevant security holes).

>The only chance to have some for the applications
>that really need it is to conserve the little entropy
>that is there anyways as best as possible. And giving out 
>16 bytes of it (or rather dilluting it by giving out
>parts of it) for each programs isn't the way to do.

I'm not sure what you mean by "conserving entropy".  Are you
referring to the impact on other applications that use /dev/random?
If the impact of get_random_bytes() on /dev/random-users is the
same as the impact of /dev/urandom on /dev/random-users, then I
don't understand the objection.

>It depends on how you define crypto strength pseudorandom:

This term has a standard well-defined meaning in the cryptographic
literature.  That's how I define it.

"pseudorandom" implies that it is not true, information-theoretic
randomness; rather, it refers to bits that are computationally
indistinguishable from true randomness.

>If you refer to some crytographic pseudo RNG: that is what
>urandom does, except that it still uses up previous real
>entropy so that the next user who needs real entropy for their
>session keys won't get as much (or rather it will get low quality entropy
>instead which is dangerous)

This statement looks confused to me.  You really have to separate users
of /dev/random from users of /dev/urandom if you want to make these kinds
of statements, and you need to separate information-theoretic security
("entropy") from computational security (where, confusingly, sometimes
people also use the word "entropy" to refer to computational
indistinguishability from true entropy; let's try to avoid that here,
since there seems to be some confusion about information-theoretic
vs computational security).

Once /dev/urandom is properly seeded, it doesn't matter how much output
you grab from /dev/urandom; all subsequent users of /dev/urandom will
continue to get cryptographic-quality pseudorandom bits (bits that cannot
be distinguished from true randomness by any computationally feasible
computation, so far as we know).

Perhaps you are referring to the effect that reading from /dev/urandom
has on user of /dev/random.  I'm not sure I fully understand the issue.
Are you saying that if /dev/random is relatively starved for entropy,
and if Alice reads lots of bits from /dev/urandom, and then Bob reads
from /dev/random, then Bob might block waiting for /dev/random's pool
to be replenished?

If that's the issue, then the solution seems to be to fix /dev/urandom
and /dev/random, as this is a general issue for all users of /dev/random,
not specific to get_random_bytes() or to this particular use of random
bits for glibc.  (Keep in mind your earlier claim that no one uses
/dev/random.)

Note that /dev/random will block if it thinks there is not sufficient
entropy availbale; it doesn't return low quality entropy.  I'm not clear
on the scenario under which you expect some user to get low quality
entropy.

>The better way would be to use a crypto strength RNG that is only
>seeded very seldom from the true pool, as to not affect the precious
>real entropy pool for applications that really need it much.

Seems to me cleaner fix /dev/urandom to work that way, if this is
the concern, rather than narrowing in on glibc's use of /dev/urandom.

>The problem in your reasoning is that you assume the entropy
>pool is a infinite resource that there is enough for everybody.

I never made that assumption.  Once /dev/urandom is seeded with
128 bits of high-quality entropy, all of its subsequent outputs
will be fantastic (computationally indistinguishable from true
randomness).

Re: [PATCH] ELF: implement AT_RANDOM for future glibc use

[Andi Kleen]

> We're already using get_random* for stack, heap, and brk.  Also,
> get_random* uses the nonblocking pool, so this is the same as if userspace
> had tried to pull bytes out of /dev/urandom, which (as I understand it)

Yes exactly that's the problem. Think about it: do you really 
need the same cryptographic strength for your mmap placement
as you need for your SSL session keys?

And if you need true entropy for your session keys do you
still get it when it was all used for low security 
purposes first?

> > What you should instead do is to initialize some other cryptographic RNG
> > regularly and use the output of that.
> 
> Can you give me some examples of this?  I thought the nonblocking
> entropy pool was specifically for this purpose?

It's definitely not a "general purpose random number generator"
or even a "general purpose secure random number generator"

Since so many systems have poor entropy input /dev/urandom has generally 
replaced /dev/random for near all cryptographic software, so it's
just the new black.

-Andi

-- 
ak@linux.intel.com

Re: [PATCH] ELF: implement AT_RANDOM for future glibc use

[Kees Cook]

On Mon, Oct 06, 2008 at 09:26:41PM +0200, Andi Kleen wrote:
> > We're already using get_random* for stack, heap, and brk.  Also,
> > get_random* uses the nonblocking pool, so this is the same as if userspace
> > had tried to pull bytes out of /dev/urandom, which (as I understand it)
> 
> Yes exactly that's the problem. Think about it: do you really 
> need the same cryptographic strength for your mmap placement
> as you need for your SSL session keys?

Well, my ultimate intention was to put this into the stack protector
guard value, so I did want something as strong as the ASLR.

> Since so many systems have poor entropy input /dev/urandom has generally 
> replaced /dev/random for near all cryptographic software, so it's
> just the new black.

If I understand, you're suggesting that ASLR doesn't need to be strong,
and that there should be something besides get_random* used to produce
these values?  If that's true, that has nothing to do with the patch
I've suggested (i.e. we have an immediate need and I'm solving it using
the current available solutions.)  (Additionally, I think ASLR should be
as strong as possible.)

If instead, you're saying that the use of urandom has generally caused
a drain on entropy, and ASLR is suffering, then does it matter that a
few more bytes are used for the stack guard?  I'm just not clear what
direction you're trying to aim my patch.  :)

I'd really love to see this solved.  My goal is to get a mainline glibc
patch for a low-cost randomized stack guard value.  Ulrich has a set of
requirements, and it sounds like there's a growing new set of requirements
from the kernel folks.  What's needed to sort this out?

-Kees

-- 
Kees Cook
Ubuntu Security Team

Re: [PATCH] ELF: implement AT_RANDOM for future glibc use

[Andi Kleen]

On Mon, Oct 06, 2008 at 03:01:01PM -0700, Kees Cook wrote:
> > Since so many systems have poor entropy input /dev/urandom has generally 
> > replaced /dev/random for near all cryptographic software, so it's
> > just the new black.
> 
> If I understand, you're suggesting that ASLR doesn't need to be strong,
> and that there should be something besides get_random* used to produce
> these values?  If that's true, that has nothing to do with the patch
> I've suggested (i.e. we have an immediate need and I'm solving it using
> the current available solutions.)  (Additionally, I think ASLR should be
> as strong as possible.)

Sure in a perfect world we had endless money and endless entropy 
and no world hunger and could make all such RNGs truly random.

But in practice the world is not like that. And entropy on a standard
Linux system is a very precious commodity.

And you won't deny that session keys are more important than mmap
placement, will you?

> 
> If instead, you're saying that the use of urandom has generally caused
> a drain on entropy, and ASLR is suffering, then does it matter that a
> few more bytes are used for the stack guard?  I'm just not clear what

It's eating entropy on every process start, so it's a incredible
drain on the entropy pool. Just calculate how much entropy
a standard "configure" run or kernel build will need.

> direction you're trying to aim my patch.  :)
> 
> I'd really love to see this solved.  My goal is to get a mainline glibc
> patch for a low-cost randomized stack guard value.

Your current implementation is high cost.

> Ulrich has a set of
> requirements, and it sounds like there's a growing new set of requirements
> from the kernel folks.  What's needed to sort this out?

IMHO it needs a new class of random numbers in the kernel that use
some cryptographically strong RNG (there are a couple of candidates
like yarrow) which is very rarely seeded
from the entropy pool[1] and use that for these applications.
A couple of other users in the kernel would benefit that too,
most users of get_random_bytes() probably should be reviewed
for their true requirements.
Ideally expose it to userland too so that dumb users like
tmpfile can use it too. 

An alternative would be also to use existing entropy sources
like the TPMs which are in many boxes now better and automatically,
but that doesn't help on systems without TPM.

-Andi

[1] getting that right is tricky, note that the entropy pool
is useless early at boot because  there's no random input.

-- 
ak@linux.intel.com

Re: [PATCH] ELF: implement AT_RANDOM for future glibc use

[Kees Cook]

On Tue, Oct 07, 2008 at 01:19:42AM +0200, Andi Kleen wrote:
> And you won't deny that session keys are more important than mmap
> placement, will you?

Right, I would tend to agree that session key strength is more important
than ASLR strength.

> > I'd really love to see this solved.  My goal is to get a mainline glibc
> > patch for a low-cost randomized stack guard value.
> 
> Your current implementation is high cost.
>...
> random32() is not a cryptographically strong RNG. I suspect it would
> be pretty easy to reverse engineer its seed given some state. It hasn't
> been designed to be protected against that.

It's being used for randomness in the networking code, so it's at least
mildly random "enough".

> IMHO it needs a new class of random numbers in the kernel that use
> some cryptographically strong RNG (there are a couple of candidates
> like yarrow) which is very rarely seeded
> from the entropy pool[1] and use that for these applications.
> A couple of other users in the kernel would benefit that too,
> most users of get_random_bytes() probably should be reviewed
> for their true requirements.

Sure, but this is a larger (and pre-existing) problem.

> Ideally expose it to userland too so that dumb users like
> tmpfile can use it too. 

Would you propose that it get hooked to /dev/urandom?

-Kees

-- 
Kees Cook
Ubuntu Security Team

Re: [PATCH] ELF: implement AT_RANDOM for future glibc use

[Andi Kleen]

On Mon, Oct 06, 2008 at 04:29:36PM -0700, Kees Cook wrote:
> > > I'd really love to see this solved.  My goal is to get a mainline glibc
> > > patch for a low-cost randomized stack guard value.
> > 
> > Your current implementation is high cost.
> >...
> > random32() is not a cryptographically strong RNG. I suspect it would
> > be pretty easy to reverse engineer its seed given some state. It hasn't
> > been designed to be protected against that.
> 
> It's being used for randomness in the networking code, so it's at least
> mildly random "enough".

Only for applications there which are not considered security sensitive.
I think. A general review of all the rngs in the kernel would be 
probably a good idea. 

Note that there are also several degrees of random
requirements in the networking code.
e.g. IPsec clearly needs stronger randomness than pktgen.

A lot of users are somewhere inbetween. e.g. I suspect the regular
routing cache rehashing would also be a excellent client of a 
a new medium quality rng facility.

> 
> > IMHO it needs a new class of random numbers in the kernel that use
> > some cryptographically strong RNG (there are a couple of candidates
> > like yarrow) which is very rarely seeded
> > from the entropy pool[1] and use that for these applications.
> > A couple of other users in the kernel would benefit that too,
> > most users of get_random_bytes() probably should be reviewed
> > for their true requirements.
> 
> Sure, but this is a larger (and pre-existing) problem.

Yes it is, but since you propose to extend the problematic 
usage much further (and also eating incredible amounts of entropy
on many workloads) you end up with the task of solving 
this problem first, sorry.

> 
> > Ideally expose it to userland too so that dumb users like
> > tmpfile can use it too. 
> 
> Would you propose that it get hooked to /dev/urandom?

It would need to be a new device.

The problem is that since noone in their right mind really still
uses /dev/random (except perhaps for gpg secret keygen) a lot
of real cryptographic applications also use /dev/urandom. And silently
changing the semantics under those wouldn't be nice.

The abusers like tmpfile etc. would just need to be fixed to 
use a different interface.

-Andi

-- 
ak@linux.intel.com

Re: [PATCH] ELF: implement AT_RANDOM for future glibc use

[Kees Cook]

On Mon, Oct 06, 2008 at 09:26:41PM +0200, Andi Kleen wrote:
> > We're already using get_random* for stack, heap, and brk.  Also,
> > get_random* uses the nonblocking pool, so this is the same as if userspace
> > had tried to pull bytes out of /dev/urandom, which (as I understand it)
> 
> Yes exactly that's the problem. Think about it: do you really 
> need the same cryptographic strength for your mmap placement
> as you need for your SSL session keys?
> 
> And if you need true entropy for your session keys do you
> still get it when it was all used for low security 
> purposes first?

Off-list I was just shown random32().  If AT_RANDOM used that instead,
would that be acceptable?

-- 
Kees Cook
Ubuntu Security Team

Re: [PATCH] ELF: implement AT_RANDOM for future glibc use

[Andi Kleen]

On Mon, Oct 06, 2008 at 03:07:59PM -0700, Kees Cook wrote:
> On Mon, Oct 06, 2008 at 09:26:41PM +0200, Andi Kleen wrote:
> > > We're already using get_random* for stack, heap, and brk.  Also,
> > > get_random* uses the nonblocking pool, so this is the same as if userspace
> > > had tried to pull bytes out of /dev/urandom, which (as I understand it)
> > 
> > Yes exactly that's the problem. Think about it: do you really 
> > need the same cryptographic strength for your mmap placement
> > as you need for your SSL session keys?
> > 
> > And if you need true entropy for your session keys do you
> > still get it when it was all used for low security 
> > purposes first?
> 
> Off-list I was just shown random32().  If AT_RANDOM used that instead,
> would that be acceptable?

random32() is not a cryptographically strong RNG. I suspect it would
be pretty easy to reverse engineer its seed given some state. It hasn't
been designed to be protected against that.

While I suspect this wouldn't be a serious threat to the security
model for mmap (to break the mmap placement you would still need quite a lot of
addresses before you can predict some and I presume most apps do not leak
addresses) it would seem unnecessarily 
weak to me because using a better algorithm is not very costly.
Also it might be a problem for some of the other potential users.

cryptographically strong RNGs are especially designed to make this
reverse engineering of the state hard. 

Simple ones can be just a cryptographic hash + counter + secret or
the same with a encryption algorithm like AES, but there are 
also algorithms who are especially designed for this like yarrow/fortuna

See
http://en.wikipedia.org/wiki/Cryptographically_secure_pseudo-random_number_generator

-Andi

-- 
ak@linux.intel.com

Re: [PATCH] ELF: implement AT_RANDOM for future glibc use

[Roland McGrath]

What mmap randomization and stack randomization actually use is
get_random_int(), not get_random_bytes().  This is one of those weaker
flavors seeded occasionally from the real entropy pool.  (As is, it's not a
good choice for getting 16 bytes of random at once, since it usually
returns the same 4 bytes each time when called 4 times in quick succession.)

What glibc wants is some bits with a strength of randomness chosen by the
kernel, and not to worry about the details.  I think the strength applied
to mmap and stack randomization is good enough for AT_RANDOM.


Thanks,
Roland

Re: [PATCH] ELF: implement AT_RANDOM for future glibc use

[Ulrich Drepper]

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

Roland McGrath wrote:
> What glibc wants is some bits with a strength of randomness chosen by the
> kernel, and not to worry about the details.  I think the strength applied
> to mmap and stack randomization is good enough for AT_RANDOM.

I think the decision about the pool should be hidden behind some
interface.  I agree, the AT_RANDOM data and ASLR can live with the same
type of data.

But perhaps we can make the interface a bid more complex for SUID and
uid==0 binaries.

Also, for platforms with cheap random data sources (VIA Padlock,
hopefully more in future).

- --
➧ Ulrich Drepper ➧ Red Hat, Inc. ➧ 444 Castro St ➧ Mountain View, CA ❖
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (GNU/Linux)

iEYEARECAAYFAkjqqHsACgkQ2ijCOnn/RHRRVgCeIQDpaol6HXgTdzpGcQKn40lp
ZX4An1HBITlkN/hRHe1Cqy8/QUuZ7ZyX
=nQuu
-----END PGP SIGNATURE-----

Re: [PATCH] ELF: implement AT_RANDOM for future glibc use

[Kees Cook]

On Mon, Oct 06, 2008 at 04:58:27PM -0700, Roland McGrath wrote:
> What mmap randomization and stack randomization actually use is
> get_random_int(), not get_random_bytes().  This is one of those weaker
> flavors seeded occasionally from the real entropy pool.  (As is, it's not a
> good choice for getting 16 bytes of random at once, since it usually
> returns the same 4 bytes each time when called 4 times in quick succession.)
> 
> What glibc wants is some bits with a strength of randomness chosen by the
> kernel, and not to worry about the details.  I think the strength applied
> to mmap and stack randomization is good enough for AT_RANDOM.

Is this email a vote for or against doing:

+       k_rand_bytes[0] = get_random_int();
+       k_rand_bytes[1] = get_random_int();
+       k_rand_bytes[2] = get_random_int();
+       k_rand_bytes[3] = get_random_int();

It sounds like it's not very safe, but on the other hand, glibc doesn't
really care?

-- 
Kees Cook
Ubuntu Security Team

Re: [PATCH] ELF: implement AT_RANDOM for future glibc use

[Ulrich Drepper]

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

Kees Cook wrote:
> It sounds like it's not very safe,

Then investigate it.


> but on the other hand, glibc doesn't really care?

Of course we care.  Especially for SUID and uid==0 binaries.

- --
➧ Ulrich Drepper ➧ Red Hat, Inc. ➧ 444 Castro St ➧ Mountain View, CA ❖
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (GNU/Linux)
Comment: Using GnuPG with Fedora - http://enigmail.mozdev.org

iEYEARECAAYFAkjqtAwACgkQ2ijCOnn/RHT0KwCgx2arTZmBrChTeTdO8AJIhDyB
yS0AnjXbx375xONSQeK0Jcmq+TMzQwS/
=NXtk
-----END PGP SIGNATURE-----

Re: [PATCH] ELF: implement AT_RANDOM for future glibc use

[Kees Cook]

On Mon, Oct 06, 2008 at 05:57:48PM -0700, Ulrich Drepper wrote:
> Kees Cook wrote:
> > It sounds like it's not very safe,
> 
> Then investigate it.

As was suspected, each int is the same.

> > but on the other hand, glibc doesn't really care?
> 
> Of course we care.  Especially for SUID and uid==0 binaries.

I meant based on what was said about "if it's as strong as the ASLR
randomness, it's good enough for this".  While the ultimate solution
would be to bolt a better PRNG into the kernel, is the following good
enough for now for glibc:

$ ./rands
0x2b 0x06 0xb7 0x53 0x2b 0x06 0xb7 0x53 0x2b 0x06 0xb7 0x53 0x2b 0x06 0xb7 0x53
$ ./rands
0xc2 0xb5 0x42 0xdc 0xc2 0xb5 0x42 0xdc 0xc2 0xb5 0x42 0xdc 0xc2 0xb5 0x42 0xdc
$ ./rands
0x5f 0x39 0xc6 0xc0 0x5f 0x39 0xc6 0xc0 0x5f 0x39 0xc6 0xc0 0x5f 0x39 0xc6 0xc0
$ ./rands
0xfb 0x4a 0x82 0xbd 0xfb 0x4a 0x82 0xbd 0xfb 0x4a 0x82 0xbd 0xfb 0x4a 0x82 0xbd

-Kees

-- 
Kees Cook
Ubuntu Security Team

Re: [PATCH] ELF: implement AT_RANDOM for future glibc use

[Ulrich Drepper]

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

Kees Cook wrote:
> is the following good enough for now for glibc:

No, definitely not.

- --
➧ Ulrich Drepper ➧ Red Hat, Inc. ➧ 444 Castro St ➧ Mountain View, CA ❖
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (GNU/Linux)
Comment: Using GnuPG with Fedora - http://enigmail.mozdev.org

iEYEARECAAYFAkjqwJAACgkQ2ijCOnn/RHTyPgCeNxmD/YZviECSPkUfLVwOvzWR
baEAnj+DAloWyH8LK5Hb4d5E/rQfVgGJ
=zJ5z
-----END PGP SIGNATURE-----