[PATCH v3 0/4] enable early printing of hashed pointers

[PATCH v3 0/4] enable early printing of hashed pointers

[Tobin C. Harding]

Currently if an attempt is made to print a pointer before there is
enough entropy then '(____ptrval____)' is printed.  This makes debugging
stack traces during early boot difficult.

It was observed that we can relax the requirement for cryptographically
secure hashing when debugging while still maintaining pointer hashing
behaviour.  This allows kernels to be debugged without developers
relying on different pointer printing behavior.

Using the hw RNG if available solves this problem for those machines
that have a hardware RNG, we would like to solve it for _all_ machines.

Patch 1 - Whitespace fixes.
Patch 2 - Fix get_random_bytes_arch()
Patch 3 - Use hw RNG for pointer hashing if available (by default).
Patch 4 - Use insecure hashing with command line option 'debug_early_boot'.

thanks,
Tobin.


v2 -> v3
 - Add __ro_after_init (suggested by Kees).

v1 -> v2
 - Use min_t() instead of min() (thanks checkpatch).
 - Add __must_check to function declaration (thanks Steve).
 - Use hw RNG by default if available (as originally suggested by Kees).
 - Add command line option to use cryptographically insecure hashing.
   If debug_early_boot is enabled use hash_long() instead of siphash
   (as requested by Steve, and solves original problem for Anna-Maria).

Tobin C. Harding (4):
  random: Fix whitespace pre random-bytes work
  random: Return nbytes filled from hw RNG
  vsprintf: Use hw RNG for ptr_key
  vsprintf: Add command line option debug_early_boot

 Documentation/admin-guide/kernel-parameters.txt |  8 ++++++
 drivers/char/random.c                           | 19 +++++++------
 include/linux/random.h                          |  2 +-
 lib/vsprintf.c                                  | 37 +++++++++++++++++++++++--
 4 files changed, 53 insertions(+), 13 deletions(-)

-- 
2.7.4

[PATCH v3 1/4] random: Fix whitespace pre random-bytes work

[Tobin C. Harding]

There are a couple of whitespace issues around the function
get_random_bytes_arch().  In preparation for patching this function
let's clean them up.

Signed-off-by: Tobin C. Harding <me@tobin.cc>
Acked-by: Theodore Ts'o <tytso@mit.edu>
---
 drivers/char/random.c | 3 +--
 1 file changed, 1 insertion(+), 2 deletions(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index cd888d4ee605..031d18b31e0f 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -1737,7 +1737,7 @@ void get_random_bytes_arch(void *buf, int nbytes)
 
 		if (!arch_get_random_long(&v))
 			break;
-		
+
 		memcpy(p, &v, chunk);
 		p += chunk;
 		nbytes -= chunk;
@@ -1748,7 +1748,6 @@ void get_random_bytes_arch(void *buf, int nbytes)
 }
 EXPORT_SYMBOL(get_random_bytes_arch);
 
-
 /*
  * init_std_data - initialize pool with system data
  *
-- 
2.7.4

[PATCH v3 2/4] random: Return nbytes filled from hw RNG

[Tobin C. Harding]

Currently the function get_random_bytes_arch() has return value 'void'.
If the hw RNG fails we currently fall back to using get_random_bytes().
This defeats the purpose of requesting random material from the hw RNG
in the first place.

There are currently no intree users of get_random_bytes_arch().

Only get random bytes from the hw RNG, make function return the number
of bytes retrieved from the hw RNG.

Signed-off-by: Tobin C. Harding <me@tobin.cc>
Acked-by: Theodore Ts'o <tytso@mit.edu>
Signed-off-by: Tobin C. Harding <me@tobin.cc>
---
 drivers/char/random.c  | 16 +++++++++-------
 include/linux/random.h |  2 +-
 2 files changed, 10 insertions(+), 8 deletions(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index 031d18b31e0f..4b0ec597e783 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -1725,26 +1725,28 @@ EXPORT_SYMBOL(del_random_ready_callback);
  * key known by the NSA).  So it's useful if we need the speed, but
  * only if we're willing to trust the hardware manufacturer not to
  * have put in a back door.
+ *
+ * Return number of bytes filled in.
  */
-void get_random_bytes_arch(void *buf, int nbytes)
+int __must_check get_random_bytes_arch(void *buf, int nbytes)
 {
 	char *p = buf;
+	int left = nbytes;
 
-	trace_get_random_bytes_arch(nbytes, _RET_IP_);
-	while (nbytes) {
+	trace_get_random_bytes_arch(left, _RET_IP_);
+	while (left) {
 		unsigned long v;
-		int chunk = min(nbytes, (int)sizeof(unsigned long));
+		int chunk = min_t(int, left, (int)sizeof(unsigned long));
 
 		if (!arch_get_random_long(&v))
 			break;
 
 		memcpy(p, &v, chunk);
 		p += chunk;
-		nbytes -= chunk;
+		left -= chunk;
 	}
 
-	if (nbytes)
-		get_random_bytes(p, nbytes);
+	return nbytes - left;
 }
 EXPORT_SYMBOL(get_random_bytes_arch);
 
diff --git a/include/linux/random.h b/include/linux/random.h
index 2ddf13b4281e..f1c9bc5cd231 100644
--- a/include/linux/random.h
+++ b/include/linux/random.h
@@ -38,7 +38,7 @@ extern void get_random_bytes(void *buf, int nbytes);
 extern int wait_for_random_bytes(void);
 extern int add_random_ready_callback(struct random_ready_callback *rdy);
 extern void del_random_ready_callback(struct random_ready_callback *rdy);
-extern void get_random_bytes_arch(void *buf, int nbytes);
+extern int __must_check get_random_bytes_arch(void *buf, int nbytes);
 
 #ifndef MODULE
 extern const struct file_operations random_fops, urandom_fops;
-- 
2.7.4

[PATCH v3 3/4] vsprintf: Use hw RNG for ptr_key

[Tobin C. Harding]

Currently we must wait for enough entropy to become available before
hashed pointers can be printed.  We can remove this wait by using the
hw RNG if available.

Use hw RNG to get keying material.

Suggested-by: Kees Cook <keescook@chromium.org>
Signed-off-by: Tobin C. Harding <me@tobin.cc>
---
 lib/vsprintf.c | 19 ++++++++++++++++---
 1 file changed, 16 insertions(+), 3 deletions(-)

diff --git a/lib/vsprintf.c b/lib/vsprintf.c
index b82f0c6c2aec..3697a19c2b25 100644
--- a/lib/vsprintf.c
+++ b/lib/vsprintf.c
@@ -1657,9 +1657,8 @@ char *device_node_string(char *buf, char *end, struct device_node *dn,
 static bool have_filled_random_ptr_key __read_mostly;
 static siphash_key_t ptr_key __read_mostly;
 
-static void fill_random_ptr_key(struct random_ready_callback *unused)
+static void ptr_key_ready(void)
 {
-	get_random_bytes(&ptr_key, sizeof(ptr_key));
 	/*
 	 * have_filled_random_ptr_key==true is dependent on get_random_bytes().
 	 * ptr_to_id() needs to see have_filled_random_ptr_key==true
@@ -1669,14 +1668,28 @@ static void fill_random_ptr_key(struct random_ready_callback *unused)
 	WRITE_ONCE(have_filled_random_ptr_key, true);
 }
 
+static void fill_random_ptr_key(struct random_ready_callback *unused)
+{
+	get_random_bytes(&ptr_key, sizeof(ptr_key));
+	ptr_key_ready();
+}
+
 static struct random_ready_callback random_ready = {
 	.func = fill_random_ptr_key
 };
 
 static int __init initialize_ptr_random(void)
 {
-	int ret = add_random_ready_callback(&random_ready);
+	int ret;
+	int key_size = sizeof(ptr_key);
+
+	/* Use hw RNG if available */
+	if (get_random_bytes_arch(&ptr_key, key_size) == key_size) {
+		ptr_key_ready();
+		return 0;
+	}
 
+	ret = add_random_ready_callback(&random_ready);
 	if (!ret) {
 		return 0;
 	} else if (ret == -EALREADY) {
-- 
2.7.4

[PATCH v3 4/4] vsprintf: Add command line option debug_early_boot

[Tobin C. Harding]

Currently printing [hashed] pointers requires either a hw RNG or enough
entropy to be available.  Early in the boot sequence these conditions
may not be met resulting in a dummy string '(____ptrval____)' being
printed.  This makes debugging the early boot sequence difficult.  We
can relax the requirement to use cryptographically secure hashing during
debugging.  This enables debugging while keeping development/production
kernel behaviour the same.

If new command line option debug_early_boot is enabled use
cryptographically insecure hashing and hash pointer value immediately.

Signed-off-by: Tobin C. Harding <me@tobin.cc>
---
 Documentation/admin-guide/kernel-parameters.txt |  8 ++++++++
 lib/vsprintf.c                                  | 18 ++++++++++++++++++
 2 files changed, 26 insertions(+)

diff --git a/Documentation/admin-guide/kernel-parameters.txt b/Documentation/admin-guide/kernel-parameters.txt
index b8d1379aa039..ab619c4ccbf2 100644
--- a/Documentation/admin-guide/kernel-parameters.txt
+++ b/Documentation/admin-guide/kernel-parameters.txt
@@ -748,6 +748,14 @@
 
 	debug		[KNL] Enable kernel debugging (events log level).
 
+	debug_early_boot
+			[KNL] Enable debugging early in the boot sequence.  If
+			enabled, we use a weak hash instead of siphash to hash
+			pointers.  Use this option if you need to see pointer
+			values during early boot (i.e you are seeing instances
+			of '(___ptrval___)') - cryptographically insecure,
+			please do not use on production kernels.
+
 	debug_locks_verbose=
 			[KNL] verbose self-tests
 			Format=<0|1>
diff --git a/lib/vsprintf.c b/lib/vsprintf.c
index 3697a19c2b25..2c48884f00eb 100644
--- a/lib/vsprintf.c
+++ b/lib/vsprintf.c
@@ -1654,6 +1654,18 @@ char *device_node_string(char *buf, char *end, struct device_node *dn,
 	return widen_string(buf, buf - buf_start, end, spec);
 }
 
+/* Make pointers available for printing early in the boot sequence. */
+static int debug_early_boot __ro_after_init;
+EXPORT_SYMBOL(debug_early_boot);
+
+static int __init debug_early_boot_enable(char *str)
+{
+	debug_early_boot = 1;
+	pr_info("debug_early_boot enabled\n");
+	return 0;
+}
+early_param("debug_early_boot", debug_early_boot_enable);
+
 static bool have_filled_random_ptr_key __read_mostly;
 static siphash_key_t ptr_key __read_mostly;
 
@@ -1707,6 +1719,12 @@ static char *ptr_to_id(char *buf, char *end, void *ptr, struct printf_spec spec)
 	const char *str = sizeof(ptr) == 8 ? "(____ptrval____)" : "(ptrval)";
 	unsigned long hashval;
 
+	/* When debugging early boot use non-cryptographically secure hash */
+	if (unlikely(debug_early_boot)) {
+		hashval = hash_long((unsigned long)ptr, 32);
+		return pointer_string(buf, end, (const void *)hashval, spec);
+	}
+
 	if (unlikely(!have_filled_random_ptr_key)) {
 		spec.field_width = 2 * sizeof(ptr);
 		/* string length must be less than default_width */
-- 
2.7.4

Re: [PATCH v3 4/4] vsprintf: Add command line option debug_early_boot

[Steven Rostedt]

On Fri,  4 May 2018 09:07:41 +1000
"Tobin C. Harding" <me@tobin.cc> wrote:

> Currently printing [hashed] pointers requires either a hw RNG or enough
> entropy to be available.  Early in the boot sequence these conditions
> may not be met resulting in a dummy string '(____ptrval____)' being
> printed.  This makes debugging the early boot sequence difficult.  We
> can relax the requirement to use cryptographically secure hashing during
> debugging.  This enables debugging while keeping development/production
> kernel behaviour the same.
> 
> If new command line option debug_early_boot is enabled use
> cryptographically insecure hashing and hash pointer value immediately.
> 
> Signed-off-by: Tobin C. Harding <me@tobin.cc>
> ---
>  Documentation/admin-guide/kernel-parameters.txt |  8 ++++++++
>  lib/vsprintf.c                                  | 18 ++++++++++++++++++
>  2 files changed, 26 insertions(+)
> 
> diff --git a/Documentation/admin-guide/kernel-parameters.txt b/Documentation/admin-guide/kernel-parameters.txt
> index b8d1379aa039..ab619c4ccbf2 100644
> --- a/Documentation/admin-guide/kernel-parameters.txt
> +++ b/Documentation/admin-guide/kernel-parameters.txt
> @@ -748,6 +748,14 @@
>  
>  	debug		[KNL] Enable kernel debugging (events log level).
>  
> +	debug_early_boot

Honestly, I think this is a bad name for what it does. It doesn't
suggest anything about hashing algorithms. And looks like something to
set if you want to debug early in the boot process but you are not
printing pointers.

Maybe something like "debug_boot_weak_hash"? 

-- Steve


> +			[KNL] Enable debugging early in the boot sequence.  If
> +			enabled, we use a weak hash instead of siphash to hash
> +			pointers.  Use this option if you need to see pointer
> +			values during early boot (i.e you are seeing instances
> +			of '(___ptrval___)') - cryptographically insecure,
> +			please do not use on production kernels.
> +
>  	debug_locks_verbose=
>  			[KNL] verbose self-tests
>  			Format=<0|1>
> diff --git a/lib/vsprintf.c b/lib/vsprintf.c
> index 3697a19c2b25..2c48884f00eb 100644
> --- a/lib/vsprintf.c
> +++ b/lib/vsprintf.c
> @@ -1654,6 +1654,18 @@ char *device_node_string(char *buf, char *end, struct device_node *dn,
>  	return widen_string(buf, buf - buf_start, end, spec);
>  }
>  
> +/* Make pointers available for printing early in the boot sequence. */
> +static int debug_early_boot __ro_after_init;
> +EXPORT_SYMBOL(debug_early_boot);
> +
> +static int __init debug_early_boot_enable(char *str)
> +{
> +	debug_early_boot = 1;
> +	pr_info("debug_early_boot enabled\n");
> +	return 0;
> +}
> +early_param("debug_early_boot", debug_early_boot_enable);
> +
>  static bool have_filled_random_ptr_key __read_mostly;
>  static siphash_key_t ptr_key __read_mostly;
>  
> @@ -1707,6 +1719,12 @@ static char *ptr_to_id(char *buf, char *end, void *ptr, struct printf_spec spec)
>  	const char *str = sizeof(ptr) == 8 ? "(____ptrval____)" : "(ptrval)";
>  	unsigned long hashval;
>  
> +	/* When debugging early boot use non-cryptographically secure hash */
> +	if (unlikely(debug_early_boot)) {
> +		hashval = hash_long((unsigned long)ptr, 32);
> +		return pointer_string(buf, end, (const void *)hashval, spec);
> +	}
> +
>  	if (unlikely(!have_filled_random_ptr_key)) {
>  		spec.field_width = 2 * sizeof(ptr);
>  		/* string length must be less than default_width */

Re: [PATCH v3 0/4] enable early printing of hashed pointers

[Theodore Y. Ts'o]

On Fri, May 04, 2018 at 09:07:37AM +1000, Tobin C. Harding wrote:
> Currently if an attempt is made to print a pointer before there is
> enough entropy then '(____ptrval____)' is printed.  This makes debugging
> stack traces during early boot difficult.
> 
> It was observed that we can relax the requirement for cryptographically
> secure hashing when debugging while still maintaining pointer hashing
> behaviour.  This allows kernels to be debugged without developers
> relying on different pointer printing behavior.
> 
> Using the hw RNG if available solves this problem for those machines
> that have a hardware RNG, we would like to solve it for _all_ machines.
> 
> Patch 1 - Whitespace fixes.
> Patch 2 - Fix get_random_bytes_arch()
> Patch 3 - Use hw RNG for pointer hashing if available (by default).
> Patch 4 - Use insecure hashing with command line option 'debug_early_boot'.

What tree are these patches going in?  It seems to be equally split
between random and core kernel code.  I'm happy taking it in via the
random tree, or if it goes in some other patch (I've already ack'ed
the random changes).  I just want to make sure other folks aren't
assuming I was going take the patches, while I was assuming it would
go to Linus some other way.

				- Ted

Re: [PATCH v3 0/4] enable early printing of hashed pointers

[Tobin C. Harding]

On Thu, May 03, 2018 at 10:23:49PM -0400, Theodore Y. Ts'o wrote:
> On Fri, May 04, 2018 at 09:07:37AM +1000, Tobin C. Harding wrote:
> > Currently if an attempt is made to print a pointer before there is
> > enough entropy then '(____ptrval____)' is printed.  This makes debugging
> > stack traces during early boot difficult.
> > 
> > It was observed that we can relax the requirement for cryptographically
> > secure hashing when debugging while still maintaining pointer hashing
> > behaviour.  This allows kernels to be debugged without developers
> > relying on different pointer printing behavior.
> > 
> > Using the hw RNG if available solves this problem for those machines
> > that have a hardware RNG, we would like to solve it for _all_ machines.
> > 
> > Patch 1 - Whitespace fixes.
> > Patch 2 - Fix get_random_bytes_arch()
> > Patch 3 - Use hw RNG for pointer hashing if available (by default).
> > Patch 4 - Use insecure hashing with command line option 'debug_early_boot'.
> 
> What tree are these patches going in?  It seems to be equally split
> between random and core kernel code.  I'm happy taking it in via the
> random tree, or if it goes in some other patch (I've already ack'ed
> the random changes).  I just want to make sure other folks aren't
> assuming I was going take the patches, while I was assuming it would
> go to Linus some other way.

Thanks for verifying this Ted, I was wondering the same thing.  Perhaps
this set should be split up, patch 4 is not related to the first three.
Assuming no comments come in over the next few days it looks like people
are ok with the first 3 patches, perhaps you could take those through
your tree (I can resend separately if easier for you).  I could then
re-spin the final patch a few more times and perhaps Andrew would take
it through his tree?

Feel free to violently correct me, I'm still learning the ins-and-outs
of the patch pathway to Linus.

thanks,
Tobin.