[PATCH] gcc-plugins: latent_entropy: use /dev/urandom

[PATCH] gcc-plugins: latent_entropy: use /dev/urandom

[Jason A. Donenfeld]

While the latent entropy plugin mostly doesn't derive entropy from
get_random_const() for measuring the call graph, when __latent_entropy is
applied to a constant, then it's initialized statically to output from
get_random_const(). In that case, this data is derived from a 64-bit
seed, which means a buffer of 512 bits doesn't really have that amount
of compile-time entropy.

This patch fixes that shortcoming by just buffering chunks of
/dev/urandom output and doling it out as requested.

Fixes: 38addce8b600 ("gcc-plugins: Add latent_entropy plugin")
Cc: stable@vger.kernel.org
Signed-off-by: Jason A. Donenfeld <Jason@zx2c4.com>
---
I'm not super familiar with this plugin or its conventions, so pointers
would be most welcome if something here looks amiss. The decision to
buffer 2k at a time is pretty arbitrary too; I haven't measured usage.

 scripts/gcc-plugins/latent_entropy_plugin.c | 34 +++++++++------------
 1 file changed, 15 insertions(+), 19 deletions(-)

diff --git a/scripts/gcc-plugins/latent_entropy_plugin.c b/scripts/gcc-plugins/latent_entropy_plugin.c
index 589454bce930..f238ba6726b8 100644
--- a/scripts/gcc-plugins/latent_entropy_plugin.c
+++ b/scripts/gcc-plugins/latent_entropy_plugin.c
@@ -82,29 +82,27 @@ __visible int plugin_is_GPL_compatible;
 static GTY(()) tree latent_entropy_decl;
 
 static struct plugin_info latent_entropy_plugin_info = {
-	.version	= "201606141920vanilla",
+	.version	= "202203311920vanilla",
 	.help		= "disable\tturn off latent entropy instrumentation\n",
 };
 
-static unsigned HOST_WIDE_INT seed;
-/*
- * get_random_seed() (this is a GCC function) generates the seed.
- * This is a simple random generator without any cryptographic security because
- * the entropy doesn't come from here.
- */
+static unsigned HOST_WIDE_INT rnd_buf[256];
+static size_t rnd_idx = ARRAY_SIZE(rnd_buf);
+static int urandom_fd = -1;
+
 static unsigned HOST_WIDE_INT get_random_const(void)
 {
-	unsigned int i;
-	unsigned HOST_WIDE_INT ret = 0;
-
-	for (i = 0; i < 8 * sizeof(ret); i++) {
-		ret = (ret << 1) | (seed & 1);
-		seed >>= 1;
-		if (ret & 1)
-			seed ^= 0xD800000000000000ULL;
+	if (urandom_fd < 0) {
+		urandom_fd = open("/dev/urandom", O_RDONLY);
+		if (urandom_fd < 0)
+			abort();
 	}
-
-	return ret;
+	if (rnd_idx >= ARRAY_SIZE(rnd_buf)) {
+		if (read(urandom_fd, rnd_buf, sizeof(rnd_buf)) != sizeof(rnd_buf))
+			abort();
+		rnd_idx = 0;
+	}
+	return rnd_buf[rnd_idx++];
 }
 
 static tree tree_get_random_const(tree type)
@@ -537,8 +535,6 @@ static void latent_entropy_start_unit(void *gcc_data __unused,
 	tree type, id;
 	int quals;
 
-	seed = get_random_seed(false);
-
 	if (in_lto_p)
 		return;
 
-- 
2.35.1

Re: [PATCH v2] gcc-plugins: latent_entropy: use /dev/urandom

[Jason A. Donenfeld]

Hi Kees,

On Mon, Apr 4, 2022 at 8:49 PM Kees Cook <keescook@chromium.org> wrote:
> This mixes two changes: the pRNG change and the "use urandom if
> non-deterministic" change. I think these should be split, so the pRNG
> change can be explicitly justified.

Alright, I'll split those. Or, more probably, just drop the xorshift
thing. There's not actually a strong reason for preferring xorshift. I
did it because it produces more uniformity and is faster to compute and
all that. But none of that stuff actually matters here. It was just a
sort of "well I'm at it..." thing.

> >  static struct plugin_info latent_entropy_plugin_info = {
> > -     .version        = "201606141920vanilla",
> > +     .version        = "202203311920vanilla",
>
> This doesn't really need to be versioned. We can change this to just
> "vanilla", IMO.

Okay. I suppose you want it to be in a different patch too, right? In
which case I'll leave it out and maybe get to it later. (I suppose one
probably needs to double check whether it's used for anything
interesting like dwarf debug info or whatever, where maybe it's
helpful?)

> > +     if (deterministic_seed) {
> > +             unsigned HOST_WIDE_INT w = deterministic_seed;
> > +             w ^= w << 13;
> > +             w ^= w >> 7;
> > +             w ^= w << 17;
> > +             deterministic_seed = w;
> > +             return deterministic_seed;
>
> While seemingly impossible, perhaps don't reset "deterministic_seed",
> and just continue to use "seed", so that it can never become "0" again.

Not sure I follow. It's an LFSR. The "L" is important. It'll never become
zero. It's not "seemingly". We can prove it trivially in Magma:

    > w := 64;
    > K := GF(2);
    > I := IdentityMatrix(K, w);
    > SHL := HorizontalJoin(RemoveColumn(I, 1), ZeroMatrix(K, w, 1));
    > SHR := HorizontalJoin(ZeroMatrix(K, w, 1), RemoveColumn(I, w));
    > M :=  (I + SHL^17) * (I + SHR^7) * (I + SHL^13);
    > Order(M) eq 2^64 - 1;
    true
    > P<x> := MinimalPolynomial(M);
    > IsPrimitive(P);
    true
    > IsInvertible(M);
    true 
    > Rank(M);
    64

And more obviously, splitting this into "seed" and "deterministic_seed",
as you suggested, wouldn't actually do much in the case when seed=0,
since 0<<N==0 and 0^0==0.

Jason

[PATCH] gcc-plugins: latent_entropy: use /dev/urandom

[Jason A. Donenfeld]

While the latent entropy plugin mostly doesn't derive entropy from
get_random_const() for measuring the call graph, when __latent_entropy is
applied to a constant, then it's initialized statically to output from
get_random_const(). In that case, this data is derived from a 64-bit
seed, which means a buffer of 512 bits doesn't really have that amount
of compile-time entropy.

This patch fixes that shortcoming by just buffering chunks of
/dev/urandom output and doling it out as requested.

At the same time, it's important that we don't break the use of
-frandom-seed, for people who want the runtime benefits of the latent
entropy plugin, while still having compile-time determinism. In that
case, we detect whether a seed is in use via the local_ticks variable,
which the documentation explains is, "-1u, if the user has specified a
particular random seed."

Fixes: 38addce8b600 ("gcc-plugins: Add latent_entropy plugin")
Cc: stable@vger.kernel.org
Cc: PaX Team <pageexec@freemail.hu>
Signed-off-by: Jason A. Donenfeld <Jason@zx2c4.com>
---
 scripts/gcc-plugins/latent_entropy_plugin.c | 44 ++++++++++++++-------
 1 file changed, 30 insertions(+), 14 deletions(-)

diff --git a/scripts/gcc-plugins/latent_entropy_plugin.c b/scripts/gcc-plugins/latent_entropy_plugin.c
index 589454bce930..435b956ac1bd 100644
--- a/scripts/gcc-plugins/latent_entropy_plugin.c
+++ b/scripts/gcc-plugins/latent_entropy_plugin.c
@@ -87,24 +87,40 @@ static struct plugin_info latent_entropy_plugin_info = {
 };
 
 static unsigned HOST_WIDE_INT seed;
-/*
- * get_random_seed() (this is a GCC function) generates the seed.
- * This is a simple random generator without any cryptographic security because
- * the entropy doesn't come from here.
- */
+static unsigned HOST_WIDE_INT rnd_buf[256];
+static size_t rnd_idx = ARRAY_SIZE(rnd_buf);
+static int urandom_fd = -1;
+
 static unsigned HOST_WIDE_INT get_random_const(void)
 {
-	unsigned int i;
-	unsigned HOST_WIDE_INT ret = 0;
-
-	for (i = 0; i < 8 * sizeof(ret); i++) {
-		ret = (ret << 1) | (seed & 1);
-		seed >>= 1;
-		if (ret & 1)
-			seed ^= 0xD800000000000000ULL;
+	/*
+	 * When local_tick==-1, the user has specified a seed using
+	 * -frandom-seed, which means we should do something deterministic.
+	 */
+	if (local_tick == -1U) {
+		unsigned HOST_WIDE_INT ret = 0;
+		size_t i;
+
+		for (i = 0; i < 8 * sizeof(ret); i++) {
+			ret = (ret << 1) | (seed & 1);
+			seed >>= 1;
+			if (ret & 1)
+				seed ^= 0xD800000000000000ULL;
+		}
+		return ret;
 	}
 
-	return ret;
+	if (urandom_fd < 0) {
+		urandom_fd = open("/dev/urandom", O_RDONLY);
+		if (urandom_fd < 0)
+			abort();
+	}
+	if (rnd_idx >= ARRAY_SIZE(rnd_buf)) {
+		if (read(urandom_fd, rnd_buf, sizeof(rnd_buf)) != sizeof(rnd_buf))
+			abort();
+		rnd_idx = 0;
+	}
+	return rnd_buf[rnd_idx++];
 }
 
 static tree tree_get_random_const(tree type)
-- 
2.35.1