[RFC PATCH] char: random: stir the output pools differently when the random_write lenght allows splitting the seed

[RFC PATCH] char: random: stir the output pools differently when the random_write lenght allows splitting the seed

[Rafael Aquini]

Since commit "7f397dc random: fix seeding with zero entropy" we are adding
data from zero-entropy random_writes directly to output pools. We can leverage
the fact the seed used for such case is usually long enough to completely stir
all bits from the input pool which is, by default, 4 times longer than the
output pools and break it in two to stir differently the output pools. This
can help on making a stronger security claim on output pool internal state.

This patch introduces changes to the random_write method so it can split the
given seed and completely stir the output pools with different halves of it, 
when seed lenght allows us doing so. 

Signed-off-by: Rafael Aquini <aquini@redhat.com>
---
Suggested by Stephan Mueller <stephan.mueller@atsec.com>

 drivers/char/random.c | 38 ++++++++++++++++++++++++++++++++------
 1 file changed, 32 insertions(+), 6 deletions(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index 429b75b..d623234 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -274,6 +274,7 @@
 #define INPUT_POOL_WORDS	(1 << (INPUT_POOL_SHIFT-5))
 #define OUTPUT_POOL_SHIFT	10
 #define OUTPUT_POOL_WORDS	(1 << (OUTPUT_POOL_SHIFT-5))
+#define OUTPUT_POOL_SIZE	((1 << OUTPUT_POOL_SHIFT) >> 3)
 #define SEC_XFER_SIZE		512
 #define EXTRACT_SIZE		10
 
@@ -1387,19 +1388,44 @@ write_pool(struct entropy_store *r, const char __user *buffer, size_t count)
 	return 0;
 }
 
-static ssize_t random_write(struct file *file, const char __user *buffer,
-			    size_t count, loff_t *ppos)
+static size_t __do_random_write(const char __user *buffer,
+				size_t count, bool split_buffer)
 {
-	size_t ret;
+	size_t ret, offset, count1, count2;
+	struct entropy_store *pool1, *pool2;
+
+	offset = 0;
+	count1 = count2 = count;
+	pool1 = &blocking_pool;
+	pool2 = &nonblocking_pool;
+
+	if (split_buffer) {
+		size_t rnd;
+		count1 = count / 2;
+		count2 = count - count1;
+		offset = count1;
+
+		get_random_bytes(&rnd, 2);
+		if (rnd % 2) {
+			pool1 = &nonblocking_pool;
+			pool2 = &blocking_pool;
+		}
+	}
 
-	ret = write_pool(&blocking_pool, buffer, count);
+	ret = write_pool(pool1, buffer, count1);
 	if (ret)
 		return ret;
-	ret = write_pool(&nonblocking_pool, buffer, count);
+	ret = write_pool(pool2, buffer + offset, count2);
 	if (ret)
 		return ret;
 
-	return (ssize_t)count;
+	return count;
+}
+
+static ssize_t random_write(struct file *file, const char __user *buffer,
+			    size_t count, loff_t *ppos)
+{
+	return __do_random_write(buffer, count, (count >= 2*OUTPUT_POOL_SIZE));
 }
 
 static long random_ioctl(struct file *f, unsigned int cmd, unsigned long arg)
-- 
1.8.3.1

Re: [RFC PATCH] char: random: stir the output pools differently when the random_write lenght allows splitting the seed

[Clemens Ladisch]

Rafael Aquini wrote:
> This patch introduces changes to the random_write method so it can split the
> given seed and completely stir the output pools with different halves of it,
> when seed lenght allows us doing so.
>
> -	ret = write_pool(&blocking_pool, buffer, count);
> +	ret = write_pool(pool1, buffer, count1);
>  	if (ret)
>  		return ret;
> -	ret = write_pool(&nonblocking_pool, buffer, count);
> +	ret = write_pool(pool2, buffer + offset, count2);

Doesn't this assume that both halves of the buffer contain some
(uncredited) entropy?  In other words, wouldn't this result in worse
randomness for pool2 if the second half of the buffer contains just zero
padding?


Regards,
Clemens

Re: [RFC PATCH] char: random: stir the output pools differently when the random_write lenght allows splitting the seed

[Stephan Mueller]

Am Freitag, 10. Januar 2014, 09:13:57 schrieb Clemens Ladisch:

Hi Clemens,

>Rafael Aquini wrote:
>> This patch introduces changes to the random_write method so it can
>> split the given seed and completely stir the output pools with
>> different halves of it, when seed lenght allows us doing so.
>> 
>> -	ret = write_pool(&blocking_pool, buffer, count);
>> +	ret = write_pool(pool1, buffer, count1);
>> 
>>  	if (ret)
>>  	
>>  		return ret;
>> 
>> -	ret = write_pool(&nonblocking_pool, buffer, count);
>> +	ret = write_pool(pool2, buffer + offset, count2);
>
>Doesn't this assume that both halves of the buffer contain some
>(uncredited) entropy?  In other words, wouldn't this result in worse
>randomness for pool2 if the second half of the buffer contains just
>zero padding?

The concern this patch addresses is the following:

Both pools have dissimilar use cases. Typically, the blocking_pool is 
used for cases where more "secure" random numbers shall be generated 
whereas the nonblocking_pool shall be used for any other case.

The issue now is that both pools intended for different use cases are 
always updated with the same data. That means, we effectively have two 
different RNGs (the blocking and nonblocking pool) which are both 
(re-)seeded with the same data every time when invoking a write on 
/dev/?random.

There is no way that the (re)seed operation mixes both pools with 
different values.

Coming back to your concern: sure, the caller can pad any data injected 
into /dev/?random with zeros. But as writing to the character files is 
allowed to every user, this per definition must not matter (e.g. an 
attacker may simply write zeros or other known data into the character 
file). And the random.c driver handles that case appropriately by not 
increasing the entropy estimator when receiving data. All the patch 
tries to achieve is to ensure that both pools are not always mixed with 
the same values. Hence, the patch does not change the entropy estimator 
operation.

Ciao
Stephan

Re: [RFC PATCH] char: random: stir the output pools differently when the random_write lenght allows splitting the seed

[Clemens Ladisch]

Stephan Mueller wrote:
> Am Freitag, 10. Januar 2014, 09:13:57 schrieb Clemens Ladisch:
>> Rafael Aquini wrote:
>>> This patch introduces changes to the random_write method so it can
>>> split the given seed and completely stir the output pools with
>>> different halves of it, when seed lenght allows us doing so.
>>>
>>> -	ret = write_pool(&blocking_pool, buffer, count);
>>> +	ret = write_pool(pool1, buffer, count1);
>>>  	if (ret)
>>>  		return ret;
>>> -	ret = write_pool(&nonblocking_pool, buffer, count);
>>> +	ret = write_pool(pool2, buffer + offset, count2);
>>
>> Doesn't this assume that both halves of the buffer contain some
>> (uncredited) entropy?  In other words, wouldn't this result in worse
>> randomness for pool2 if the second half of the buffer contains just
>> zero padding?
>
> [...]
> Coming back to your concern: sure, the caller can pad any data injected
> into /dev/?random with zeros.

Assume that the userspace of an embedded device wants to do the same
kind of initialization that a call to add_device_randomness() does, and
that it has some data like "char serial_number[256]".  The padding
wouldn't be done intentionally, it's just a property of the data (and it
wouldn't have mattered before this patch).

> But as writing to the character files is allowed to every user, this
> per definition must not matter (e.g. an attacker may simply write
> zeros or other known data into the character file). And the random.c
> driver handles that case appropriately by not increasing the entropy
> estimator when receiving data.

The problem is not with the entropy estimate.

> All the patch tries to achieve is to ensure that both pools are not
> always mixed with the same values.

Before this patch, both pools got mixed with the same values.  After
this patch, both pools indeed get mixed with different values, but now
one pool gets mixed with a known value if one half of the buffer happens
to be known.


Regards,
Clemens

Re: [RFC PATCH] char: random: stir the output pools differently when the random_write lenght allows splitting the seed

[Stephan Mueller]

Am Freitag, 10. Januar 2014, 12:37:26 schrieb Clemens Ladisch:

Hi Clemens,

>Stephan Mueller wrote:
>> Am Freitag, 10. Januar 2014, 09:13:57 schrieb Clemens Ladisch:
>>> Rafael Aquini wrote:
>>>> This patch introduces changes to the random_write method so it can
>>>> split the given seed and completely stir the output pools with
>>>> different halves of it, when seed lenght allows us doing so.
>>>> 
>>>> -	ret = write_pool(&blocking_pool, buffer, count);
>>>> +	ret = write_pool(pool1, buffer, count1);
>>>> 
>>>>  	if (ret)
>>>>  	
>>>>  		return ret;
>>>> 
>>>> -	ret = write_pool(&nonblocking_pool, buffer, count);
>>>> +	ret = write_pool(pool2, buffer + offset, count2);
>>> 
>>> Doesn't this assume that both halves of the buffer contain some
>>> (uncredited) entropy?  In other words, wouldn't this result in worse
>>> randomness for pool2 if the second half of the buffer contains just
>>> zero padding?
>> 
>> [...]
>> Coming back to your concern: sure, the caller can pad any data
>> injected into /dev/?random with zeros.
>
>Assume that the userspace of an embedded device wants to do the same
>kind of initialization that a call to add_device_randomness() does, and
>that it has some data like "char serial_number[256]".  The padding
>wouldn't be done intentionally, it's just a property of the data (and
>it wouldn't have mattered before this patch).
>
>> But as writing to the character files is allowed to every user, this
>> per definition must not matter (e.g. an attacker may simply write
>> zeros or other known data into the character file). And the random.c
>> driver handles that case appropriately by not increasing the entropy
>> estimator when receiving data.
>
>The problem is not with the entropy estimate.
>
>> All the patch tries to achieve is to ensure that both pools are not
>> always mixed with the same values.
>
>Before this patch, both pools got mixed with the same values.  After
>this patch, both pools indeed get mixed with different values, but now
>one pool gets mixed with a known value if one half of the buffer
>happens to be known.

Do you imply in your example above that the serial number is unknown? 
Anything that unprivileged user space tries to inject into /dev/?random 
should be considered data with known value.

Ciao
Stephan

Re: [RFC PATCH] char: random: stir the output pools differently when the random_write lenght allows splitting the seed

[Clemens Ladisch]

Stephan Mueller wrote:
> Am Freitag, 10. Januar 2014, 12:37:26 schrieb Clemens Ladisch:
>> Stephan Mueller wrote:
>>> Am Freitag, 10. Januar 2014, 09:13:57 schrieb Clemens Ladisch:
>>>> Rafael Aquini wrote:
>>>>> This patch introduces changes to the random_write method so it can
>>>>> split the given seed and completely stir the output pools with
>>>>> different halves of it, when seed lenght allows us doing so.
>>>>>
>>>>> -	ret = write_pool(&blocking_pool, buffer, count);
>>>>> +	ret = write_pool(pool1, buffer, count1);
>>>>>
>>>>>  	if (ret)
>>>>>  	
>>>>>  		return ret;
>>>>>
>>>>> -	ret = write_pool(&nonblocking_pool, buffer, count);
>>>>> +	ret = write_pool(pool2, buffer + offset, count2);
>>>>
>>>> Doesn't this assume that both halves of the buffer contain some
>>>> (uncredited) entropy?  In other words, wouldn't this result in worse
>>>> randomness for pool2 if the second half of the buffer contains just
>>>> zero padding?
>>>
>>> [...]
>>> Coming back to your concern: sure, the caller can pad any data
>>> injected into /dev/?random with zeros.
>>
>> Assume that the userspace of an embedded device wants to do the same
>> kind of initialization that a call to add_device_randomness() does, and
>> that it has some data like "char serial_number[256]".  The padding
>> wouldn't be done intentionally, it's just a property of the data (and
>> it wouldn't have mattered before this patch).
>>
>>> But as writing to the character files is allowed to every user, this
>>> per definition must not matter (e.g. an attacker may simply write
>>> zeros or other known data into the character file). And the random.c
>>> driver handles that case appropriately by not increasing the entropy
>>> estimator when receiving data.
>>
>> The problem is not with the entropy estimate.
>>
>>> All the patch tries to achieve is to ensure that both pools are not
>>> always mixed with the same values.
>>
>> Before this patch, both pools got mixed with the same values.  After
>> this patch, both pools indeed get mixed with different values, but now
>> one pool gets mixed with a known value if one half of the buffer
>> happens to be known.
>
> Do you imply in your example above that the serial number is unknown?
> Anything that unprivileged user space tries to inject into /dev/?random
> should be considered data with known value.

Like the kernel's add_device_randomness() function, this example assumes
that there is no persistent storage with a saved seed (or that it isn't
yet available), and that mixing a device-specific value at least
prevents multiple device instances from generating identical random
numbers.

This indeed helps only against attackers that do not know that serial
number.

If the data written by unprivileged users to /dev/?random were
considered known to *all* attackers, then it wouldn't make sense to
allow such writes at all.


Regards,
Clemens

Re: [RFC PATCH] char: random: stir the output pools differently when the random_write lenght allows splitting the seed

[Rafael Aquini]

On Fri, Jan 10, 2014 at 12:37:26PM +0100, Clemens Ladisch wrote:
> Stephan Mueller wrote:
> > Am Freitag, 10. Januar 2014, 09:13:57 schrieb Clemens Ladisch:
> >> Rafael Aquini wrote:
> >>> This patch introduces changes to the random_write method so it can
> >>> split the given seed and completely stir the output pools with
> >>> different halves of it, when seed lenght allows us doing so.
> >>>
> >>> -	ret = write_pool(&blocking_pool, buffer, count);
> >>> +	ret = write_pool(pool1, buffer, count1);
> >>>  	if (ret)
> >>>  		return ret;
> >>> -	ret = write_pool(&nonblocking_pool, buffer, count);
> >>> +	ret = write_pool(pool2, buffer + offset, count2);
> >>
> >> Doesn't this assume that both halves of the buffer contain some
> >> (uncredited) entropy?  In other words, wouldn't this result in worse
> >> randomness for pool2 if the second half of the buffer contains just
> >> zero padding?
> >
> > [...]
> > Coming back to your concern: sure, the caller can pad any data injected
> > into /dev/?random with zeros.
> 
> Assume that the userspace of an embedded device wants to do the same
> kind of initialization that a call to add_device_randomness() does, and
> that it has some data like "char serial_number[256]".  The padding
> wouldn't be done intentionally, it's just a property of the data (and it
> wouldn't have mattered before this patch).
> 
> > But as writing to the character files is allowed to every user, this
> > per definition must not matter (e.g. an attacker may simply write
> > zeros or other known data into the character file). And the random.c
> > driver handles that case appropriately by not increasing the entropy
> > estimator when receiving data.
> 
> The problem is not with the entropy estimate.
> 
> > All the patch tries to achieve is to ensure that both pools are not
> > always mixed with the same values.
> 
> Before this patch, both pools got mixed with the same values.  After
> this patch, both pools indeed get mixed with different values, but now
> one pool gets mixed with a known value if one half of the buffer happens
> to be known.
>

Yeah, nice catch. I haven't thought about it. Theoretically speaking there's no
big difference between using the same seed to mix both output pools and split the
seed to use its different halves to mix the pools separately in this case.
Supposing an attacker could successfully compromise the blocking pool
(/dev/random) by injecting a known pattern seed into /dev/urandom, a split seed
would also not be able to do any greater good for us, as the attacker can surely
handcraft an input that shows the same pattern on both halves.


I'm wondering if doing something like initializing an extra structentropy_store, 
fill in its pool with 'OUTPUT_POOL_SIZE' get_random_bytes(), stir this extra pool
with whatever came in as seed from userland and extract two seeds from this pool
to then separately stir the output pools would be something more feasible here, 
or would it just be considered too much for too little... 

if the approach above is sth worth to pursue, I'll come up with something next week.

Thank you all for the comments till here, and have you all a nice weekend!
-- Rafael

Re: [RFC PATCH] char: random: stir the output pools differently when the random_write lenght allows splitting the seed

[Rafael Aquini]

On Fri, Jan 10, 2014 at 01:32:10PM +0100, Clemens Ladisch wrote:
> Stephan Mueller wrote:
> > Am Freitag, 10. Januar 2014, 12:37:26 schrieb Clemens Ladisch:
> >> Stephan Mueller wrote:
> >>> Am Freitag, 10. Januar 2014, 09:13:57 schrieb Clemens Ladisch:
> >>>> Rafael Aquini wrote:
> >>>>> This patch introduces changes to the random_write method so it can
> >>>>> split the given seed and completely stir the output pools with
> >>>>> different halves of it, when seed lenght allows us doing so.
> >>>>>
> >>>>> -	ret = write_pool(&blocking_pool, buffer, count);
> >>>>> +	ret = write_pool(pool1, buffer, count1);
> >>>>>
> >>>>>  	if (ret)
> >>>>>  	
> >>>>>  		return ret;
> >>>>>
> >>>>> -	ret = write_pool(&nonblocking_pool, buffer, count);
> >>>>> +	ret = write_pool(pool2, buffer + offset, count2);
> >>>>
> >>>> Doesn't this assume that both halves of the buffer contain some
> >>>> (uncredited) entropy?  In other words, wouldn't this result in worse
> >>>> randomness for pool2 if the second half of the buffer contains just
> >>>> zero padding?
> >>>
> >>> [...]
> >>> Coming back to your concern: sure, the caller can pad any data
> >>> injected into /dev/?random with zeros.
> >>
> >> Assume that the userspace of an embedded device wants to do the same
> >> kind of initialization that a call to add_device_randomness() does, and
> >> that it has some data like "char serial_number[256]".  The padding
> >> wouldn't be done intentionally, it's just a property of the data (and
> >> it wouldn't have mattered before this patch).
> >>
> >>> But as writing to the character files is allowed to every user, this
> >>> per definition must not matter (e.g. an attacker may simply write
> >>> zeros or other known data into the character file). And the random.c
> >>> driver handles that case appropriately by not increasing the entropy
> >>> estimator when receiving data.
> >>
> >> The problem is not with the entropy estimate.
> >>
> >>> All the patch tries to achieve is to ensure that both pools are not
> >>> always mixed with the same values.
> >>
> >> Before this patch, both pools got mixed with the same values.  After
> >> this patch, both pools indeed get mixed with different values, but now
> >> one pool gets mixed with a known value if one half of the buffer
> >> happens to be known.
> >
> > Do you imply in your example above that the serial number is unknown?
> > Anything that unprivileged user space tries to inject into /dev/?random
> > should be considered data with known value.
> 
> Like the kernel's add_device_randomness() function, this example assumes
> that there is no persistent storage with a saved seed (or that it isn't
> yet available), and that mixing a device-specific value at least
> prevents multiple device instances from generating identical random
> numbers.
> 
> This indeed helps only against attackers that do not know that serial
> number.
> 
> If the data written by unprivileged users to /dev/?random were
> considered known to *all* attackers, then it wouldn't make sense to
> allow such writes at all.
> 

Sorry folks, 

Although I left this one a little behind, I'd like to follow it up and reach
some consensus.


After re-reading the whole discussion, it became clear to me that the source of
Stephan's request on splitting the seed we feed into the LRNG lies around the
fact that any unprivileged user is capable to inject data and stir the entropy
extraction pools arbitrarily.

$ ls -l /dev/{u,}random
crw-rw-rw-. 1 root root 1, 8 Jan 21 23:44 /dev/random
crw-rw-rw-. 1 root root 1, 9 Jan 21 23:44 /dev/urandom

Considering what goes within this thread, wouldn't be simpler to just remove the
privileged of writing to /dev/{u,}random from the wild world? 

Stephan, I'll repeat myself here: theoretically speaking there's no diff between
using the same seed to mix both output pools and splitting it to use its
different halves to stir the pools separately, for the /dev/{u,}random writes,
if an attacker could successfully compromise the pools by feeding them with a
known pattern seed. I understand you raised the split-the-seed point on a
security concern and that concern might eventually become a requirement.
Please, let us (me) know know if:

a) is this request based on an existent pronouncement of standardization?
b) is this (potential) pronouncement based on math proof that one could 
   compromise the LRNG internal state by feeding known seeds into /dev/{u,}random?

If (a) & (b) are true, and there's no code in the actual random.c implementation
that does not address those security claims, and the naive approach of
restricting who can actually write to /dev/{u,}random is not deemed feasible,
then something like the (ugly) hack that goes bellow would be considered
feasible? (perhaps making it conditional to fips_enabled)


Thank you all for the comments till here, and have you all a nice weekend!

Rafael
---
vers/char/random.c | 66 +++++++++++++++++++++++++++++++++++++++++++--------
 1 file changed, 56 insertions(+), 10 deletions(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index 429b75b..63e8852 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -274,6 +274,7 @@
 #define INPUT_POOL_WORDS       (1 << (INPUT_POOL_SHIFT-5))
 #define OUTPUT_POOL_SHIFT      10
 #define OUTPUT_POOL_WORDS      (1 << (OUTPUT_POOL_SHIFT-5))
+#define OUTPUT_POOL_SIZE       ((1 << OUTPUT_POOL_SHIFT) >> 3)
 #define SEC_XFER_SIZE          512
 #define EXTRACT_SIZE           10

@@ -1387,19 +1388,64 @@ write_pool(struct entropy_store *r, const char __user *buffer, size_t count)
        return 0;
 }

-static ssize_t random_write(struct file *file, const char __user *buffer,
-                           size_t count, loff_t *ppos)
+static size_t __do_random_write(const char __user *buffer, size_t count)
 {
-       size_t ret;
-
-       ret = write_pool(&blocking_pool, buffer, count);
-       if (ret)
-               return ret;
-       ret = write_pool(&nonblocking_pool, buffer, count);
+       struct entropy_store *randomwrite_pool, *output_pool1, *output_pool2;
+       __u32 *randomwrite_pool_data, *rnd_seed;
+       size_t dime, ret = -ENOMEM;
+
+       randomwrite_pool_data = kzalloc(OUTPUT_POOL_SIZE, GFP_KERNEL);
+       if (!randomwrite_pool_data)
+               goto out_0;
+
+       randomwrite_pool = kzalloc(sizeof(struct entropy_store), GFP_KERNEL);
+       if (!randomwrite_pool)
+               goto out_1;
+
+       rnd_seed = kzalloc(OUTPUT_POOL_SIZE, GFP_KERNEL);
+       if (!rnd_seed)
+               goto out_2;
+
+       /* init an auxiliary pool and give it a stir with the input bias */
+       get_random_bytes(randomwrite_pool_data, OUTPUT_POOL_SIZE);
+       spin_lock_init(&randomwrite_pool->lock);
+       randomwrite_pool->poolinfo = &poolinfo_table[1];
+       randomwrite_pool->pool = randomwrite_pool_data;
+       randomwrite_pool->name = "randomwrite_pool";
+       ret = write_pool(randomwrite_pool, buffer, count);
        if (ret)
-               return ret;
+               goto out_3;
+
+       /* flip a coin before deciding the output pool seeding order */
+       output_pool1 = &blocking_pool;
+       output_pool2 = &nonblocking_pool;
+       get_random_bytes(&dime, 1);
+       if (dime % 2) {
+               output_pool1 = &nonblocking_pool;
+               output_pool2 = &blocking_pool;
+       }
+
+       extract_entropy(randomwrite_pool, rnd_seed, OUTPUT_POOL_SIZE, 0, 0);
+       mix_pool_bytes(output_pool1, rnd_seed, OUTPUT_POOL_SIZE, NULL);

-       return (ssize_t)count;
+       extract_entropy(randomwrite_pool, rnd_seed, OUTPUT_POOL_SIZE, 0, 0);
+       mix_pool_bytes(output_pool2, rnd_seed, OUTPUT_POOL_SIZE, NULL);
+
+       ret = count;
+out_3:
+       kfree(rnd_seed);
+out_2:
+       kfree(randomwrite_pool);
+out_1:
+       kfree(randomwrite_pool_data);
+out_0:
+       return ret;
+}
+
+static ssize_t random_write(struct file *file, const char __user *buffer,
+                           size_t count, loff_t *ppos)
+{
+       return __do_random_write(buffer, count);
 }

 static long random_ioctl(struct file *f, unsigned int cmd, unsigned long arg)
--