Skip to contentSkip to conversation

hwrng: add randomness to system from rng sources

PATCH RESEND In review Kees Cook 6 participants 16 messages Mar 3, 2014 – Mar 17, 2014

Subsystems (2)
lore
Share & tools
lore

Kees Cook

author
#0 lore raw

PATCH RESEND 1/1 hwrng: add randomness to system from rng sources

When bringing a new RNG source online, it seems like it would make sense to use some of its bytes to make the system entropy pool more random, as done with all sorts of other devices that contain per-device or per-boot differences.

---
 drivers/char/hw_random/core.c |    7 +++++++
 1 file changed, 7 insertions(+)
drivers/char/hw_random/core.c +7 -0
index a0f7724852eb..6e5bb68a708c 100644
@@ -41,6 +41,7 @@
 #include <linux/miscdevice.h>
 #include <linux/delay.h>
 #include <linux/slab.h>
+#include <linux/random.h>
 #include <asm/uaccess.h>
 
 
@@ -305,6 +306,8 @@ int hwrng_register(struct hwrng *rng)
 	int must_register_misc;
 	int err = -EINVAL;
 	struct hwrng *old_rng, *tmp;
+	unsigned char bytes[16];
+	int bytes_read;
 
 	if (rng->name == NULL ||
 	    (rng->data_read == NULL && rng->read == NULL))
@@ -348,6 +351,10 @@ int hwrng_register(struct hwrng *rng)
 	}
 	INIT_LIST_HEAD(&rng->list);
 	list_add_tail(&rng->list, &rng_list);
+
+	bytes_read = rng_get_data(rng, bytes, sizeof(bytes), 1);
+	if (bytes_read > 0)
+		add_device_randomness(bytes, bytes_read);
 out_unlock:
 	mutex_unlock(&rng_mutex);
 out:
Signature · 6 lines
1.7.9.5


-- 
Kees Cook
Chrome OS Security
#1 lore raw

Kees, Ted,

Quoted 4 lines · Kees Cook

When bringing a new RNG source online, it seems like it would make sense to use some of its bytes to make the system entropy pool more random, as done with all sorts of other devices that contain per-device or per-boot differences.

Why is this necessary? init_std_data() already calls arch_get_random_long() while stirring each of the pools.

I'm a little concerned here because this gives potentially untrusted hwrngs more influence over the entropy pools initial state than most users of random.c expect. Many of the drivers in hw_random/ are platform drivers and are initialized before random.c.

I'm comfortable with the design decisions Ted has made wrt random.c and hwrngs. However, I think that this changes that trust relationship in a fundamental way. I'm ok with building support into my kernels for hwrngs as long as random.c's internal use of them is limited to the mixing in extract_buf() and init_std_data().

By adding this patch, even without crediting entropy to the pool, a rogue hwrng now has significantly more influence over the initial state of the entropy pools. Or, am I missing something?

thx,

Jason.

Quoted 48 lines
---
 drivers/char/hw_random/core.c |    7 +++++++
 1 file changed, 7 insertions(+)
drivers/char/hw_random/core.c +7 -0
index a0f7724852eb..6e5bb68a708c 100644
@@ -41,6 +41,7 @@
 #include <linux/miscdevice.h>
 #include <linux/delay.h>
 #include <linux/slab.h>
+#include <linux/random.h>
 #include <asm/uaccess.h>
 
 
@@ -305,6 +306,8 @@ int hwrng_register(struct hwrng *rng)
 	int must_register_misc;
 	int err = -EINVAL;
 	struct hwrng *old_rng, *tmp;
+	unsigned char bytes[16];
+	int bytes_read;
 
 	if (rng->name == NULL ||
 	    (rng->data_read == NULL && rng->read == NULL))
@@ -348,6 +351,10 @@ int hwrng_register(struct hwrng *rng)
 	}
 	INIT_LIST_HEAD(&rng->list);
 	list_add_tail(&rng->list, &rng_list);
+
+	bytes_read = rng_get_data(rng, bytes, sizeof(bytes), 1);
+	if (bytes_read > 0)
+		add_device_randomness(bytes, bytes_read);
 out_unlock:
 	mutex_unlock(&rng_mutex);
 out:
Signature · 10 lines
1.7.9.5


-- 
Kees Cook
Chrome OS Security
--
To unsubscribe from this list: send the line "unsubscribe linux-crypto" in
the body of a message to [email protected]
More majordomo info at  http://vger.kernel.org/majordomo-info.html
author
#2 lore raw
Quoted 10 lines · Jason Cooper

Kees, Ted,

Quoted 4 lines · Kees Cook

When bringing a new RNG source online, it seems like it would make sense to use some of its bytes to make the system entropy pool more random, as done with all sorts of other devices that contain per-device or per-boot differences.

Why is this necessary? init_std_data() already calls arch_get_random_long() while stirring each of the pools.

I may be misunderstanding something here, but hwrng isn't going to get hit by a arch_get_random_long(). That's just for arch-specific RNGs (e.g. RDRAND), where as hwrng is for, effectively, add-on devices (e.g. TPMs).

Quoted 11 lines

I'm a little concerned here because this gives potentially untrusted hwrngs more influence over the entropy pools initial state than most users of random.c expect. Many of the drivers in hw_random/ are platform drivers and are initialized before random.c.

I'm comfortable with the design decisions Ted has made wrt random.c and hwrngs. However, I think that this changes that trust relationship in a fundamental way. I'm ok with building support into my kernels for hwrngs as long as random.c's internal use of them is limited to the mixing in extract_buf() and init_std_data().

Quoted 3 lines

By adding this patch, even without crediting entropy to the pool, a rogue hwrng now has significantly more influence over the initial state of the entropy pools. Or, am I missing something?

I wasn't viewing this as dealing with rouge hwrngs (though shouldn't that state still be covered due to the existing mixing), but more as a "hey this thing has some randomness associated with it", similar to the mixing done for things like NIC MAC, etc. (Better, actually, since NIC MAC is going to be the same every boot.) It seemed silly to ignore an actual entropy source when seeding.

-Kees

Quoted 53 lines

thx,

Jason.

Quoted 48 lines
---
 drivers/char/hw_random/core.c |    7 +++++++
 1 file changed, 7 insertions(+)
drivers/char/hw_random/core.c +7 -1
index a0f7724852eb..6e5bb68a708c 100644
@@ -41,6 +41,7 @@
 #include <linux/miscdevice.h>
 #include <linux/delay.h>
 #include <linux/slab.h>
+#include <linux/random.h>
 #include <asm/uaccess.h>
 
 
@@ -305,6 +306,8 @@ int hwrng_register(struct hwrng *rng)
      int must_register_misc;
      int err = -EINVAL;
      struct hwrng *old_rng, *tmp;
+     unsigned char bytes[16];
+     int bytes_read;
 
      if (rng->name == NULL ||
          (rng->data_read == NULL && rng->read == NULL))
@@ -348,6 +351,10 @@ int hwrng_register(struct hwrng *rng)
      }
      INIT_LIST_HEAD(&rng->list);
      list_add_tail(&rng->list, &rng_list);
+
+     bytes_read = rng_get_data(rng, bytes, sizeof(bytes), 1);
+     if (bytes_read > 0)
+             add_device_randomness(bytes, bytes_read);
 out_unlock:
      mutex_unlock(&rng_mutex);
 out:
--

1.7.9.5

--
Kees Cook
Chrome OS Security
--
To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

Signature · 2 lines
Kees Cook
Chrome OS Security
#3 lore raw
Quoted 9 lines · Kees Cook
Quoted 8 lines · Jason Cooper

Kees, Ted,

Quoted 4 lines · Kees Cook

When bringing a new RNG source online, it seems like it would make sense to use some of its bytes to make the system entropy pool more random, as done with all sorts of other devices that contain per-device or per-boot differences.

Quoted 5 lines
Quoted 2 lines

Why is this necessary? init_std_data() already calls arch_get_random_long() while stirring each of the pools.

I may be misunderstanding something here, but hwrng isn't going to get hit by a arch_get_random_long().

ahh, you are correct. It appears it's only used on x86 and powerpc. Bad assumption on my part.

Quoted 18 lines

That's just for arch-specific RNGs (e.g. RDRAND), where as hwrng is for, effectively, add-on devices (e.g. TPMs).

Quoted 11 lines

I'm a little concerned here because this gives potentially untrusted hwrngs more influence over the entropy pools initial state than most users of random.c expect. Many of the drivers in hw_random/ are platform drivers and are initialized before random.c.

I'm comfortable with the design decisions Ted has made wrt random.c and hwrngs. However, I think that this changes that trust relationship in a fundamental way. I'm ok with building support into my kernels for hwrngs as long as random.c's internal use of them is limited to the mixing in extract_buf() and init_std_data().

Quoted 3 lines

By adding this patch, even without crediting entropy to the pool, a rogue hwrng now has significantly more influence over the initial state of the entropy pools. Or, am I missing something?

Quoted 6 lines

I wasn't viewing this as dealing with rouge hwrngs (though shouldn't that state still be covered due to the existing mixing), but more as a "hey this thing has some randomness associated with it", similar to the mixing done for things like NIC MAC, etc. (Better, actually, since NIC MAC is going to be the same every boot.) It seemed silly to ignore an actual entropy source when seeding.

Agreed, but I think we need to be careful about how random.c interacts with any hwrng. Ideally, the drivers in hw_random/ could provide arch_get_random_long(). This way, random.c still determines when and how to use the hwrng.

Ultimately, the user (person compiling the kernel) will decide to trust or not trust the hwrng by enabling support for it or not. My concern with this patch is that it changes the magnitude of that trust decision. And only the most diligent user would discover the change.

To date, all discussion wrt random.c and hwrngs are that the output of the hwrng (in particular, RDRAND) is XORd with the output of the mixer. Now, we're saying it can provide input as well.

Please understand, my point-of-view is as someone who installs Linux on equipment *after* purchase (hobbyist, tinkers). If I control the part selection and sourcing of the board components, of course I have more trust in the hwrng.

So my situation is similar to buying an Intel based laptop. I can't do a special order at Bestbuy and ask for a system without the RDRAND instruction. Same with the hobbyist market. We buy the gear, but we have no control over what's inside it.

In that situation, without this patch, I would enable the hwrng for the board. With the patch in it's current form, I would start looking for research papers and discussions regarding using the hwrng for input. If the patch provided arch_get_random_long(), I would feel comfortable enabling the hwrng.

Perhaps I'm being too conservative, but I'd rather have the discussion now and have concerns proven unfounded than have someone say "How the hell did this happen?" three releases down the road.

thx,

Jason.

Quoted 54 lines
Quoted 48 lines
Quoted 48 lines
---
 drivers/char/hw_random/core.c |    7 +++++++
 1 file changed, 7 insertions(+)
drivers/char/hw_random/core.c +7 -1
index a0f7724852eb..6e5bb68a708c 100644
@@ -41,6 +41,7 @@
 #include <linux/miscdevice.h>
 #include <linux/delay.h>
 #include <linux/slab.h>
+#include <linux/random.h>
 #include <asm/uaccess.h>
 
 
@@ -305,6 +306,8 @@ int hwrng_register(struct hwrng *rng)
      int must_register_misc;
      int err = -EINVAL;
      struct hwrng *old_rng, *tmp;
+     unsigned char bytes[16];
+     int bytes_read;
 
      if (rng->name == NULL ||
          (rng->data_read == NULL && rng->read == NULL))
@@ -348,6 +351,10 @@ int hwrng_register(struct hwrng *rng)
      }
      INIT_LIST_HEAD(&rng->list);
      list_add_tail(&rng->list, &rng_list);
+
+     bytes_read = rng_get_data(rng, bytes, sizeof(bytes), 1);
+     if (bytes_read > 0)
+             add_device_randomness(bytes, bytes_read);
 out_unlock:
      mutex_unlock(&rng_mutex);
 out:
--

1.7.9.5

--
Kees Cook
Chrome OS Security
--
To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

Signature · 2 lines
Kees Cook
Chrome OS Security
author
#4 lore raw
Quoted 49 lines · Jason Cooper
Quoted 9 lines · Kees Cook
Quoted 8 lines · Jason Cooper

Kees, Ted,

Quoted 4 lines · Kees Cook

When bringing a new RNG source online, it seems like it would make sense to use some of its bytes to make the system entropy pool more random, as done with all sorts of other devices that contain per-device or per-boot differences.

Quoted 5 lines
Quoted 2 lines

Why is this necessary? init_std_data() already calls arch_get_random_long() while stirring each of the pools.

I may be misunderstanding something here, but hwrng isn't going to get hit by a arch_get_random_long().

ahh, you are correct. It appears it's only used on x86 and powerpc. Bad assumption on my part.

Quoted 18 lines

That's just for arch-specific RNGs (e.g. RDRAND), where as hwrng is for, effectively, add-on devices (e.g. TPMs).

Quoted 11 lines

I'm a little concerned here because this gives potentially untrusted hwrngs more influence over the entropy pools initial state than most users of random.c expect. Many of the drivers in hw_random/ are platform drivers and are initialized before random.c.

I'm comfortable with the design decisions Ted has made wrt random.c and hwrngs. However, I think that this changes that trust relationship in a fundamental way. I'm ok with building support into my kernels for hwrngs as long as random.c's internal use of them is limited to the mixing in extract_buf() and init_std_data().

Quoted 3 lines

By adding this patch, even without crediting entropy to the pool, a rogue hwrng now has significantly more influence over the initial state of the entropy pools. Or, am I missing something?

Quoted 6 lines

I wasn't viewing this as dealing with rouge hwrngs (though shouldn't that state still be covered due to the existing mixing), but more as a "hey this thing has some randomness associated with it", similar to the mixing done for things like NIC MAC, etc. (Better, actually, since NIC MAC is going to be the same every boot.) It seemed silly to ignore an actual entropy source when seeding.

Agreed, but I think we need to be careful about how random.c interacts with any hwrng. Ideally, the drivers in hw_random/ could provide arch_get_random_long(). This way, random.c still determines when and how to use the hwrng.

Quoted 8 lines

Ultimately, the user (person compiling the kernel) will decide to trust or not trust the hwrng by enabling support for it or not. My concern with this patch is that it changes the magnitude of that trust decision. And only the most diligent user would discover the change.

To date, all discussion wrt random.c and hwrngs are that the output of the hwrng (in particular, RDRAND) is XORd with the output of the mixer. Now, we're saying it can provide input as well.

Well, I think there's confusion here over "the" hwrng and "a" hwrng. I have devices with multiple entropy sources, and all my hwrngs are built as modules, so I choose when to load them into my kernel. "The" arch-specific entropy source (e.g. RDRAND) is very different.

Quoted 17 lines

Please understand, my point-of-view is as someone who installs Linux on equipment *after* purchase (hobbyist, tinkers). If I control the part selection and sourcing of the board components, of course I have more trust in the hwrng.

So my situation is similar to buying an Intel based laptop. I can't do a special order at Bestbuy and ask for a system without the RDRAND instruction. Same with the hobbyist market. We buy the gear, but we have no control over what's inside it.

In that situation, without this patch, I would enable the hwrng for the board. With the patch in it's current form, I would start looking for research papers and discussions regarding using the hwrng for input. If the patch provided arch_get_random_long(), I would feel comfortable enabling the hwrng.

Quoted 3 lines

Perhaps I'm being too conservative, but I'd rather have the discussion now and have concerns proven unfounded than have someone say "How the hell did this happen?" three releases down the road.

Sure, and I don't want to be the one weakening the entropy pool. However, I think this patch is no different from the ones that stuff a NIC MAC into the pool -- it's taking something from my system that is unique or random and pushing the entropy seed around. It seems silly that if I've loaded the hwrng-tpm module, my system entropy pool isn't bumped.

-Kees

Quoted 60 lines

thx,

Jason.

Quoted 54 lines
Quoted 41 lines
Quoted 41 lines
---
 drivers/char/hw_random/core.c |    7 +++++++
 1 file changed, 7 insertions(+)
drivers/char/hw_random/core.c +7 -1
index a0f7724852eb..6e5bb68a708c 100644
@@ -41,6 +41,7 @@
 #include <linux/miscdevice.h>
 #include <linux/delay.h>
 #include <linux/slab.h>
+#include <linux/random.h>
 #include <asm/uaccess.h>
 
 
@@ -305,6 +306,8 @@ int hwrng_register(struct hwrng *rng)
      int must_register_misc;
      int err = -EINVAL;
      struct hwrng *old_rng, *tmp;
+     unsigned char bytes[16];
+     int bytes_read;
 
      if (rng->name == NULL ||
          (rng->data_read == NULL && rng->read == NULL))
@@ -348,6 +351,10 @@ int hwrng_register(struct hwrng *rng)
      }
      INIT_LIST_HEAD(&rng->list);
      list_add_tail(&rng->list, &rng_list);
+
+     bytes_read = rng_get_data(rng, bytes, sizeof(bytes), 1);
+     if (bytes_read > 0)
+             add_device_randomness(bytes, bytes_read);
 out_unlock:
      mutex_unlock(&rng_mutex);
 out:
--

1.7.9.5

Quoted 7 lines
Quoted 7 lines

--
Kees Cook
Chrome OS Security
--
To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

--
Kees Cook
Chrome OS Security

Signature · 2 lines
Kees Cook
Chrome OS Security
#5 lore raw
Quoted 81 lines · Kees Cook
Quoted 49 lines · Jason Cooper
Quoted 9 lines · Kees Cook
Quoted 8 lines · Jason Cooper

Kees, Ted,

Quoted 4 lines · Kees Cook

When bringing a new RNG source online, it seems like it would make sense to use some of its bytes to make the system entropy pool more random, as done with all sorts of other devices that contain per-device or per-boot differences.

Quoted 5 lines
Quoted 2 lines

Why is this necessary? init_std_data() already calls arch_get_random_long() while stirring each of the pools.

I may be misunderstanding something here, but hwrng isn't going to get hit by a arch_get_random_long().

ahh, you are correct. It appears it's only used on x86 and powerpc. Bad assumption on my part.

Quoted 18 lines

That's just for arch-specific RNGs (e.g. RDRAND), where as hwrng is for, effectively, add-on devices (e.g. TPMs).

Quoted 11 lines

I'm a little concerned here because this gives potentially untrusted hwrngs more influence over the entropy pools initial state than most users of random.c expect. Many of the drivers in hw_random/ are platform drivers and are initialized before random.c.

I'm comfortable with the design decisions Ted has made wrt random.c and hwrngs. However, I think that this changes that trust relationship in a fundamental way. I'm ok with building support into my kernels for hwrngs as long as random.c's internal use of them is limited to the mixing in extract_buf() and init_std_data().

Quoted 3 lines

By adding this patch, even without crediting entropy to the pool, a rogue hwrng now has significantly more influence over the initial state of the entropy pools. Or, am I missing something?

Quoted 6 lines

I wasn't viewing this as dealing with rouge hwrngs (though shouldn't that state still be covered due to the existing mixing), but more as a "hey this thing has some randomness associated with it", similar to the mixing done for things like NIC MAC, etc. (Better, actually, since NIC MAC is going to be the same every boot.) It seemed silly to ignore an actual entropy source when seeding.

Agreed, but I think we need to be careful about how random.c interacts with any hwrng. Ideally, the drivers in hw_random/ could provide arch_get_random_long(). This way, random.c still determines when and how to use the hwrng.

Quoted 8 lines

Ultimately, the user (person compiling the kernel) will decide to trust or not trust the hwrng by enabling support for it or not. My concern with this patch is that it changes the magnitude of that trust decision. And only the most diligent user would discover the change.

To date, all discussion wrt random.c and hwrngs are that the output of the hwrng (in particular, RDRAND) is XORd with the output of the mixer. Now, we're saying it can provide input as well.

Well, I think there's confusion here over "the" hwrng and "a" hwrng. I have devices with multiple entropy sources, and all my hwrngs are built as modules, so I choose when to load them into my kernel. "The" arch-specific entropy source (e.g. RDRAND) is very different.

Quoted 17 lines

Please understand, my point-of-view is as someone who installs Linux on equipment *after* purchase (hobbyist, tinkers). If I control the part selection and sourcing of the board components, of course I have more trust in the hwrng.

So my situation is similar to buying an Intel based laptop. I can't do a special order at Bestbuy and ask for a system without the RDRAND instruction. Same with the hobbyist market. We buy the gear, but we have no control over what's inside it.

In that situation, without this patch, I would enable the hwrng for the board. With the patch in it's current form, I would start looking for research papers and discussions regarding using the hwrng for input. If the patch provided arch_get_random_long(), I would feel comfortable enabling the hwrng.

Quoted 5 lines
Quoted 3 lines

Perhaps I'm being too conservative, but I'd rather have the discussion now and have concerns proven unfounded than have someone say "How the hell did this happen?" three releases down the road.

Sure, and I don't want to be the one weakening the entropy pool.

[temporarily coming out of retirement to provide a clue]

The pool mixing function is intentionally _reversible_. This is a crucial security property.

That means, if I have an initial secret pool state X, and hostile attacker controlled data Y, then we can do:

X' = mix(X, Y)

and

X = unmix(X', Y)

We can see from this that the combination of (X' and Y) still contain the information that was originally in X. Since it's clearly not in Y.. it must all remain in X'.

In other words, if there are 4096 bits of "unknownness" in X to start with, and I can get those same 4096 bits of "unknownness" back by unmixing X' and Y, then there must still be 4096 bits of "unknownness" in X'. If X' is 4096 bits long, then we've just proven that reversibility means the attacker can know nothing about the contents of X' by his choice of Y.

Consider the case of a single bit: the quarter in my pocket. I let you tell me how many times to flip it, but this reversible function gives you no way to force it to be heads when I reveal it.

So as long as the mixing function remains reversible, it is perfectly safe to mix in arbitrary amounts of potentially attacker-controlled data. In fact:

$ ls -l /dev/random
crw-rw-rw- 1 root root 1, 8 Feb 15 16:24 /dev/random

..that's exactly what the 'w' bits here lets you do.

On the other hand, you should continue to be vigilant against anything that bypasses the pool mixing.

Signature · 1 line
Mathematics is the supreme nostalgia of our time.
#6 lore raw

Matt, Kees,

Quoted 5 lines · Matt Mackall
Quoted 4 lines · Kees Cook
Quoted 3 lines · Jason Cooper
Quoted 2 lines · Kees Cook
Quoted 1 line · Jason Cooper

On Mon, Mar 03, 2014 at 03:51:48PM -0800, Kees Cook wrote:

...

Quoted 4 lines
Quoted 4 lines

Well, I think there's confusion here over "the" hwrng and "a" hwrng. I have devices with multiple entropy sources, and all my hwrngs are built as modules, so I choose when to load them into my kernel. "The" arch-specific entropy source (e.g. RDRAND) is very different.

Dynamically loading modules _after_ boot is fine. Especially with Matt's clear explanation. I'm not concerned about that scenario.

Quoted 16 lines
Quoted 16 lines
Quoted 16 lines

Please understand, my point-of-view is as someone who installs Linux on equipment *after* purchase (hobbyist, tinkers). If I control the part selection and sourcing of the board components, of course I have more trust in the hwrng.

So my situation is similar to buying an Intel based laptop. I can't do a special order at Bestbuy and ask for a system without the RDRAND instruction. Same with the hobbyist market. We buy the gear, but we have no control over what's inside it.

In that situation, without this patch, I would enable the hwrng for the board. With the patch in it's current form, I would start looking for research papers and discussions regarding using the hwrng for input. If the patch provided arch_get_random_long(), I would feel comfortable enabling the hwrng.

Quoted 7 lines
Quoted 5 lines
Quoted 3 lines

Perhaps I'm being too conservative, but I'd rather have the discussion now and have concerns proven unfounded than have someone say "How the hell did this happen?" three releases down the road.

Sure, and I don't want to be the one weakening the entropy pool.

[temporarily coming out of retirement to provide a clue]

Thanks, Matt!

Quoted 16 lines

The pool mixing function is intentionally _reversible_. This is a crucial security property.

That means, if I have an initial secret pool state X, and hostile attacker controlled data Y, then we can do:

X' = mix(X, Y)

and

X = unmix(X', Y)

We can see from this that the combination of (X' and Y) still contain the information that was originally in X. Since it's clearly not in Y.. it must all remain in X'.

Quoted 6 lines

In other words, if there are 4096 bits of "unknownness" in X to start with, and I can get those same 4096 bits of "unknownness" back by unmixing X' and Y, then there must still be 4096 bits of "unknownness" in X'. If X' is 4096 bits long, then we've just proven that reversibility means the attacker can know nothing about the contents of X' by his choice of Y.

Well, this reinforces my comfortability with loadable modules. The pool is already initialized by the point at which the driver is loaded.

Unfortunately, any of the drivers in hw_random can be built in. When built in, hwrng_register is going to be called during the kernel initialization process. In that case, the unknownness in X is not 4096 bits, but far less. Also, the items that may have seeded X (MAC addr, time, etc) are discoverable by a potential attacker. This is also well before random-seed has been fed in.

That's the crux of my concern with this patch. Basically, the user can choose 'y' over 'm', say when building a dedicated system w/o loadable modules, and not realize how much more trust he has placed in the hwrng.

How does this patch look? I'm not claiming my change is acceptable for mainline, just seeking feedback on the concept. IS_MODULE() really doesn't have many users afaict.

This builds without warning on ARCH=arm with multi_v7_defconfig when HW_RANDOM={y,m,n}

thx,

Jason.

-------->8--------------------------
commit 0fcc0669ee4bbeae355c0f61f79a6b319a32ba12

Author: Kees Cook <[email protected]>
Date:   Mon Mar 3 15:51:48 2014 -0800

hwrng: add randomness to system from rng sources

When bringing a new RNG source online, it seems like it would make sense to use some of its bytes to make the system entropy pool more random, as done with all sorts of other devices that contain per-device or per-boot differences.

[jac] prevent the code from being called at boot up, before the entropy pool has had time to build and be well initialized. We do this by making the code conditional on being built as a module.

drivers/char/hw_random/core.c +18 -0
index a0f7724852eb..5c3314cbf671 100644
@@ -41,6 +41,8 @@
 #include <linux/miscdevice.h>
 #include <linux/delay.h>
 #include <linux/slab.h>
+#include <linux/random.h>
+#include <linux/kconfig.h>
 #include <asm/uaccess.h>
 
 
@@ -305,6 +307,10 @@ int hwrng_register(struct hwrng *rng)
 	int must_register_misc;
 	int err = -EINVAL;
 	struct hwrng *old_rng, *tmp;
+#if IS_MODULE(CONFIG_HW_RANDOM)
+	unsigned char bytes[16];
+	int bytes_read;
+#endif
 
 	if (rng->name == NULL ||
 	    (rng->data_read == NULL && rng->read == NULL))
@@ -348,6 +354,18 @@ int hwrng_register(struct hwrng *rng)
 	}
 	INIT_LIST_HEAD(&rng->list);
 	list_add_tail(&rng->list, &rng_list);
+
+	/*
+	 * Out of an abundance of caution, we should avoid seeding the entropy
+	 * pool when it is first initialized (ie at kernel boot time).
+	 * Therefore, we take advantage of the hwrng when it is built as a
+	 * module, but not when built in.
+	 */
+#if IS_MODULE(CONFIG_HW_RANDOM)
+	bytes_read = rng_get_data(rng, bytes, sizeof(bytes), 1);
+	if (bytes_read > 0)
+		add_device_randomness(bytes, bytes_read);
+#endif
 out_unlock:
 	mutex_unlock(&rng_mutex);
 out:
author
#7 lore raw
Quoted 69 lines · Jason Cooper

Matt, Kees,

Quoted 5 lines · Matt Mackall
Quoted 4 lines · Kees Cook
Quoted 3 lines · Jason Cooper
Quoted 2 lines · Kees Cook
Quoted 1 line · Jason Cooper

On Mon, Mar 03, 2014 at 03:51:48PM -0800, Kees Cook wrote:

...

Quoted 4 lines
Quoted 4 lines

Well, I think there's confusion here over "the" hwrng and "a" hwrng. I have devices with multiple entropy sources, and all my hwrngs are built as modules, so I choose when to load them into my kernel. "The" arch-specific entropy source (e.g. RDRAND) is very different.

Dynamically loading modules _after_ boot is fine. Especially with Matt's clear explanation. I'm not concerned about that scenario.

Quoted 16 lines
Quoted 16 lines
Quoted 16 lines

Please understand, my point-of-view is as someone who installs Linux on equipment *after* purchase (hobbyist, tinkers). If I control the part selection and sourcing of the board components, of course I have more trust in the hwrng.

So my situation is similar to buying an Intel based laptop. I can't do a special order at Bestbuy and ask for a system without the RDRAND instruction. Same with the hobbyist market. We buy the gear, but we have no control over what's inside it.

In that situation, without this patch, I would enable the hwrng for the board. With the patch in it's current form, I would start looking for research papers and discussions regarding using the hwrng for input. If the patch provided arch_get_random_long(), I would feel comfortable enabling the hwrng.

Quoted 7 lines
Quoted 5 lines
Quoted 3 lines

Perhaps I'm being too conservative, but I'd rather have the discussion now and have concerns proven unfounded than have someone say "How the hell did this happen?" three releases down the road.

Sure, and I don't want to be the one weakening the entropy pool.

[temporarily coming out of retirement to provide a clue]

Thanks, Matt!

Quoted 16 lines

The pool mixing function is intentionally _reversible_. This is a crucial security property.

That means, if I have an initial secret pool state X, and hostile attacker controlled data Y, then we can do:

X' = mix(X, Y)

and

X = unmix(X', Y)

We can see from this that the combination of (X' and Y) still contain the information that was originally in X. Since it's clearly not in Y.. it must all remain in X'.

Quoted 6 lines

In other words, if there are 4096 bits of "unknownness" in X to start with, and I can get those same 4096 bits of "unknownness" back by unmixing X' and Y, then there must still be 4096 bits of "unknownness" in X'. If X' is 4096 bits long, then we've just proven that reversibility means the attacker can know nothing about the contents of X' by his choice of Y.

Well, this reinforces my comfortability with loadable modules. The pool is already initialized by the point at which the driver is loaded.

Quoted 6 lines

Unfortunately, any of the drivers in hw_random can be built in. When built in, hwrng_register is going to be called during the kernel initialization process. In that case, the unknownness in X is not 4096 bits, but far less. Also, the items that may have seeded X (MAC addr, time, etc) are discoverable by a potential attacker. This is also well before random-seed has been fed in.

Would reducing the size of the buffer used for this help your concerns? Ironically, a non-malicious hwng using this code would actually improve defense against other early-boot rng badness since unlike time and MAC, this is much less discoverable by an attacker.

Quoted 8 lines

That's the crux of my concern with this patch. Basically, the user can choose 'y' over 'm', say when building a dedicated system w/o loadable modules, and not realize how much more trust he has placed in the hwrng.

How does this patch look? I'm not claiming my change is acceptable for mainline, just seeking feedback on the concept. IS_MODULE() really doesn't have many users afaict.

Regardless, making this change to the patch would be fine with me, yeah. I think the module case is much more common.

-Kees

Quoted 70 lines

This builds without warning on ARCH=arm with multi_v7_defconfig when HW_RANDOM={y,m,n}

thx,

Jason.

-------->8--------------------------
commit 0fcc0669ee4bbeae355c0f61f79a6b319a32ba12

Author: Kees Cook <[email protected]>
Date:   Mon Mar 3 15:51:48 2014 -0800

hwrng: add randomness to system from rng sources

When bringing a new RNG source online, it seems like it would make sense to use some of its bytes to make the system entropy pool more random, as done with all sorts of other devices that contain per-device or per-boot differences.

[jac] prevent the code from being called at boot up, before the entropy pool has had time to build and be well initialized. We do this by making the code conditional on being built as a module.

drivers/char/hw_random/core.c +18 -0
index a0f7724852eb..5c3314cbf671 100644
@@ -41,6 +41,8 @@
 #include <linux/miscdevice.h>
 #include <linux/delay.h>
 #include <linux/slab.h>
+#include <linux/random.h>
+#include <linux/kconfig.h>
 #include <asm/uaccess.h>
 
 
@@ -305,6 +307,10 @@ int hwrng_register(struct hwrng *rng)
        int must_register_misc;
        int err = -EINVAL;
        struct hwrng *old_rng, *tmp;
+#if IS_MODULE(CONFIG_HW_RANDOM)
+       unsigned char bytes[16];
+       int bytes_read;
+#endif
 
        if (rng->name == NULL ||
            (rng->data_read == NULL && rng->read == NULL))
@@ -348,6 +354,18 @@ int hwrng_register(struct hwrng *rng)
        }
        INIT_LIST_HEAD(&rng->list);
        list_add_tail(&rng->list, &rng_list);
+
+       /*
+        * Out of an abundance of caution, we should avoid seeding the entropy
+        * pool when it is first initialized (ie at kernel boot time).
+        * Therefore, we take advantage of the hwrng when it is built as a
+        * module, but not when built in.
+        */
+#if IS_MODULE(CONFIG_HW_RANDOM)
+       bytes_read = rng_get_data(rng, bytes, sizeof(bytes), 1);
+       if (bytes_read > 0)
+               add_device_randomness(bytes, bytes_read);
+#endif
 out_unlock:
        mutex_unlock(&rng_mutex);
 out:
Signature · 2 lines
Kees Cook
Chrome OS Security
#8 lore raw
In reply to Jason Cooper
Quoted 10 lines · Jason Cooper
Quoted 6 lines

In other words, if there are 4096 bits of "unknownness" in X to start with, and I can get those same 4096 bits of "unknownness" back by unmixing X' and Y, then there must still be 4096 bits of "unknownness" in X'. If X' is 4096 bits long, then we've just proven that reversibility means the attacker can know nothing about the contents of X' by his choice of Y.

Well, this reinforces my comfortability with loadable modules. The pool is already initialized by the point at which the driver is loaded.

Quoted 6 lines

Unfortunately, any of the drivers in hw_random can be built in. When built in, hwrng_register is going to be called during the kernel initialization process. In that case, the unknownness in X is not 4096 bits, but far less. Also, the items that may have seeded X (MAC addr, time, etc) are discoverable by a potential attacker. This is also well before random-seed has been fed in.

To which I would respond.. so?

If the pool is in an attacker-knowable state at early boot, adding attacker-controlled data does not make the situation any worse. In fact, if the attacker has less-than-perfect control of the inputs, mixing more things in will make things exponentially harder for the attacker.

Put another way: mixing can't ever removes unknownness from the pool, it can only add more. So the only reason you should ever choose not to mix something into the pool is performance.

Signature · 1 line
Mathematics is the supreme nostalgia of our time.
author
#9 lore raw
Quoted 20 lines · Matt Mackall
Quoted 10 lines · Jason Cooper
Quoted 6 lines

In other words, if there are 4096 bits of "unknownness" in X to start with, and I can get those same 4096 bits of "unknownness" back by unmixing X' and Y, then there must still be 4096 bits of "unknownness" in X'. If X' is 4096 bits long, then we've just proven that reversibility means the attacker can know nothing about the contents of X' by his choice of Y.

Well, this reinforces my comfortability with loadable modules. The pool is already initialized by the point at which the driver is loaded.

Quoted 6 lines

Unfortunately, any of the drivers in hw_random can be built in. When built in, hwrng_register is going to be called during the kernel initialization process. In that case, the unknownness in X is not 4096 bits, but far less. Also, the items that may have seeded X (MAC addr, time, etc) are discoverable by a potential attacker. This is also well before random-seed has been fed in.

To which I would respond.. so?

Quoted 8 lines

If the pool is in an attacker-knowable state at early boot, adding attacker-controlled data does not make the situation any worse. In fact, if the attacker has less-than-perfect control of the inputs, mixing more things in will make things exponentially harder for the attacker.

Put another way: mixing can't ever removes unknownness from the pool, it can only add more. So the only reason you should ever choose not to mix something into the pool is performance.

Excellent. So it sounds like you're okay with my original patch as-is?

-Kees

Signature · 2 lines
Kees Cook
Chrome OS Security
#10 lore raw
In reply to Matt Mackall
Quoted 11 lines · Matt Mackall
Quoted 10 lines · Jason Cooper
Quoted 6 lines

In other words, if there are 4096 bits of "unknownness" in X to start with, and I can get those same 4096 bits of "unknownness" back by unmixing X' and Y, then there must still be 4096 bits of "unknownness" in X'. If X' is 4096 bits long, then we've just proven that reversibility means the attacker can know nothing about the contents of X' by his choice of Y.

Well, this reinforces my comfortability with loadable modules. The pool is already initialized by the point at which the driver is loaded.

Quoted 8 lines
Quoted 6 lines

Unfortunately, any of the drivers in hw_random can be built in. When built in, hwrng_register is going to be called during the kernel initialization process. In that case, the unknownness in X is not 4096 bits, but far less. Also, the items that may have seeded X (MAC addr, time, etc) are discoverable by a potential attacker. This is also well before random-seed has been fed in.

To which I would respond.. so?

I only saw this line of context pop on my phone last night, and that led me to a train of thought. In short, I agree with you, and I actually now prefer Kees patch in it's original form.

Quoted 4 lines

If the pool is in an attacker-knowable state at early boot, adding attacker-controlled data does not make the situation any worse. In fact, if the attacker has less-than-perfect control of the inputs, mixing more things in will make things exponentially harder for the attacker.

Just to clarify my understanding: Say we have inputs A, B, C, W, X, Y, Z. A, B are known to the attacker (MAC address, etc), C is the attacker known hwrng data. W-Z are small chunks added in from unpredictable events.

In order to predict a potential set of states at boot, the attacker not only has to brute force W-Z, but also the order of A-C,W-Z.

Without C, the order of the events becomes more deterministic. Thus making the job easier for the attacker.

Quoted 3 lines

Put another way: mixing can't ever removes unknownness from the pool, it can only add more. So the only reason you should ever choose not to mix something into the pool is performance.

I also need to clarify an assumption I made in this thread. I focused too heavily on Attacker1, who has secret knowledge of the internal workings of the hwrng. As we've established above, his job isn't made easier by adding hwrng data during system boot.

In addition, Attacker2 through AttackerN who _don't_ have the secret knowledge of the hwrng, but do know the MAC address and other initial inputs are defeated by adding the hwrng during system boot.

Matt, thanks for taking the time to come out of retirement to help us with this. Kees, thanks for your patience :)

thx,

Jason.

#11 lore raw
In reply to Matt Mackall
Quoted 11 lines · Matt Mackall

[temporarily coming out of retirement to provide a clue]

The pool mixing function is intentionally _reversible_. This is a crucial security property.

That means, if I have an initial secret pool state X, and hostile attacker controlled data Y, then we can do:

X' = mix(X, Y)

Quoted 8 lines

and

X = unmix(X', Y)

We can see from this that the combination of (X' and Y) still contain the information that was originally in X. Since it's clearly not in Y.. it must all remain in X'.

This of course assumes that the attacker doesn't know the state of the pool X.

The other thing to note is that reversible doesn't necessarily mean linear (the current mixing function is linear.) AES, for example, is reversible (if and only if you possess the key) but is highly nonlinear.

I'm not saying we should use AES to mix the pool -- it is almost guaranteed to be too expensive.

-hpa

Reviewed-by on v1 1/1
#12 lore raw
In reply to Kees Cook
Quoted 9 lines · Kees Cook

When bringing a new RNG source online, it seems like it would make sense to use some of its bytes to make the system entropy pool more random, as done with all sorts of other devices that contain per-device or per-boot differences.

---
 drivers/char/hw_random/core.c |    7 +++++++
 1 file changed, 7 insertions(+)

fwiw,

thx,

Jason.

Quoted 43 lines
drivers/char/hw_random/core.c +7 -0
index a0f7724852eb..6e5bb68a708c 100644
@@ -41,6 +41,7 @@
 #include <linux/miscdevice.h>
 #include <linux/delay.h>
 #include <linux/slab.h>
+#include <linux/random.h>
 #include <asm/uaccess.h>
 
 
@@ -305,6 +306,8 @@ int hwrng_register(struct hwrng *rng)
 	int must_register_misc;
 	int err = -EINVAL;
 	struct hwrng *old_rng, *tmp;
+	unsigned char bytes[16];
+	int bytes_read;
 
 	if (rng->name == NULL ||
 	    (rng->data_read == NULL && rng->read == NULL))
@@ -348,6 +351,10 @@ int hwrng_register(struct hwrng *rng)
 	}
 	INIT_LIST_HEAD(&rng->list);
 	list_add_tail(&rng->list, &rng_list);
+
+	bytes_read = rng_get_data(rng, bytes, sizeof(bytes), 1);
+	if (bytes_read > 0)
+		add_device_randomness(bytes, bytes_read);
 out_unlock:
 	mutex_unlock(&rng_mutex);
 out:
Signature · 10 lines
1.7.9.5


-- 
Kees Cook
Chrome OS Security
--
To unsubscribe from this list: send the line "unsubscribe linux-crypto" in
the body of a message to [email protected]
More majordomo info at  http://vger.kernel.org/majordomo-info.html
maintainer
#13 lore raw
Quoted 6 lines · Jason Cooper
Quoted 5 lines · Kees Cook

When bringing a new RNG source online, it seems like it would make sense to use some of its bytes to make the system entropy pool more random, as done with all sorts of other devices that contain per-device or per-boot differences.

Quoted 8 lines
Quoted 4 lines
---
 drivers/char/hw_random/core.c |    7 +++++++
 1 file changed, 7 insertions(+)

fwiw,

Patch applied. Thanks everyone!

Signature · 3 lines
Email: Herbert Xu <[email protected]>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt
#14 lore raw
In reply to Kees Cook
Quoted 6 lines · Kees Cook

When bringing a new RNG source online, it seems like it would make sense to use some of its bytes to make the system entropy pool more random, as done with all sorts of other devices that contain per-device or per-boot differences.

I would like to raise again the concept of at least optionally using a kernel thread, rather than a user-space daemon, to feed hwrng output to the kernel pools. The main service rngd provides is FIPS tests, but those FIPS tests were withdrawn as a standard over 10 years ago and are known to be extremely weak, at the very best a minimal sanity check. Furthermore, they are completely useless against the output of any RNG which contains a cryptographic whitener, which is the vast majority of commercial sources -- this is especially so since rngd doesn't expect to have to do any data reduction for output coming from hwrng.

Furthermore, if more than one hwrng device is available, rngd will only be able to read one of them because of the way /dev/hwrng is implemented in the kernel.

For contrast, the kernel could do data reduction just fine by only crediting the entropy coming out of each hwrng driver with a fractional amount.

That does *not* mean that there aren't random number generators which require significant computation better done in user space. For example, an audio noise daemon or a lava lamp camera which requires video processing.

-hpa

#15 lore raw
Quoted 26 lines · H. Peter Anvin
Quoted 6 lines · Kees Cook

When bringing a new RNG source online, it seems like it would make sense to use some of its bytes to make the system entropy pool more random, as done with all sorts of other devices that contain per-device or per-boot differences.

I would like to raise again the concept of at least optionally using a kernel thread, rather than a user-space daemon, to feed hwrng output to the kernel pools. The main service rngd provides is FIPS tests, but those FIPS tests were withdrawn as a standard over 10 years ago and are known to be extremely weak, at the very best a minimal sanity check. Furthermore, they are completely useless against the output of any RNG which contains a cryptographic whitener, which is the vast majority of commercial sources -- this is especially so since rngd doesn't expect to have to do any data reduction for output coming from hwrng.

Furthermore, if more than one hwrng device is available, rngd will only be able to read one of them because of the way /dev/hwrng is implemented in the kernel.

For contrast, the kernel could do data reduction just fine by only crediting the entropy coming out of each hwrng driver with a fractional amount.

Quoted 5 lines

That does *not* mean that there aren't random number generators which require significant computation better done in user space. For example, an audio noise daemon or a lava lamp camera which requires video processing.

-hpa

I definitely second this proposal, not only does it get rid of the overhead of the FIPS tests (which can be quite significant on embedded systems), it also removes a significant percentage of the context switches that rngd needs to make. This should provide some way of disabling this behavior, probably either making it a module, or providing a command-line/sysfs option to disable it. In fact, it should probably default to being disabled (at least at first) and require the user to explicitly opt-in to using it (I know people who run simulations who use the output from /dev/hwrng directly for the simulation software exclusively, and /dev/[u]random for everything else).