ELF: implement AT_RANDOM for future glibc use

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

---
 fs/binfmt_elf.c        |   20 ++++++++++++++++++++
 include/linux/auxvec.h |    4 +++-
 security/Kconfig       |    9 +++++++++
 3 files changed, 32 insertions(+), 1 deletions(-)

index 655ed8d..9b2ea62 100644
@@ -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,

index d7afa9d..df4ff65 100644
@@ -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
 

index f6c0429..8d9d49d 100644
@@ -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

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

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

---
 fs/binfmt_elf.c        |   20 ++++++++++++++++++++
 include/linux/auxvec.h |    5 +++--
 security/Kconfig       |    9 +++++++++
 3 files changed, 32 insertions(+), 2 deletions(-)

index 655ed8d..fbaa665 100644
@@ -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,

index d7afa9d..702e506 100644
@@ -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
 

index f6c0429..64f0da9 100644
@@ -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

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.

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

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

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

---
 fs/binfmt_elf.c        |   27 +++++++++++++++++++++++++++
 include/linux/auxvec.h |    7 ++++---
 2 files changed, 31 insertions(+), 3 deletions(-)

index 655ed8d..11931f8 100644
@@ -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,

index d7afa9d..dac7fc2 100644
@@ -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

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

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

---
 fs/binfmt_elf.c        |   25 +++++++++++++++++++++++++
 include/linux/auxvec.h |    6 +++---
 2 files changed, 28 insertions(+), 3 deletions(-)

index 655ed8d..479a7a4 100644
@@ -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,

index d7afa9d..d85b8f7 100644
@@ -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

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

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

---
 fs/binfmt_elf.c        |   12 ++++++++++++
 include/linux/auxvec.h |    6 +++---
 2 files changed, 15 insertions(+), 3 deletions(-)

index 655ed8d..1934ab3 100644
@@ -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,

index d7afa9d..f3b5d4e 100644
@@ -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

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.

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?

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

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.

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

Thanks.

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?

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

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

There are some values defined only on one particular arch.

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

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.

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

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.

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.

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.

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.

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

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).

? 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).

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.

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.

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.

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.

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).

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?

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

[email protected]

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

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

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?

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.

Your current implementation is high cost.

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.

[email protected]

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

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

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

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

-Kees

Kees Cook
Ubuntu Security Team

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.

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.

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

[email protected]

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

Kees Cook
Ubuntu Security Team

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

[email protected]

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

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

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

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

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

Then investigate it.

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

As was suspected, each int is the same.

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

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

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