Re: [PATCHv5] random: Make /dev/random wait for input_pool initializedy

[Bernd Edlinger <bernd.edlinger@hotmail.de>]

On 2/22/19 12:18 AM, Theodore Y. Ts'o wrote:
> The whole premise of reading from /dev/random is that it should only
> allow reads up to available estimated entropy.  I'm assuming here that
> sane users of /dev/random will be reading in chunks of at least 128
> bits, reading smaller amounts for, say, a 32-bit SPECK key, is not
> someone who is paranoid enough to want to use /dev/random is likely to
> want to do.  So what I was doing was to simply prevent any reads from
> /dev/random until it had accumulated 128 bits worth of entropy.  If
> the user is reading 128 bits in order to generate a 128-bit session
> key, this won't actually slow down /dev/random any more that it does
> today.
> 
> It will slow down someone who just wants to read a byte from
> /dev/random immediately after boot --- but as far as I'm concerned,
> that's crazy, so I don't really care about optimizing it.  Your
> suggestion of simply not allowing any reads until the CRNG is
> initialized, and then injecting 128-bits into the blocking pool would
> also work, but it wouldn't speed up the use case of "the user is
> trying to read 128 bits from /dev/random".  It only speeds up "read 1
> byte from /dev/random".
> 
> Personally, I would generally be simply tell users, "use getrandom(2)
> and be happy", and I consider /dev/random to be a legacy interface.
> It's just that there are some crazy customers who seem to believe that
> /dev/random is required for FIPS compliance.
> 

Sure.

> So optimizing for users who want to read vast amount of data from
> /dev/random is a non-goal as far as I am concerned.  In particular,
> seeding the CRNG and keeping it properly reseeded is higher priority
> as far as I'm concerned.  If that slows down /dev/random a bit,
> /dev/random is *always* going to be slow.
> 

There are rumors that reading one byte from /dev/random in the rcS
script makes /dev/urandom properly seeded.  That sounds logical,
but does not work as expected due to a bug that I am trying to fix.

>>> -			struct entropy_store *other = &blocking_pool;
>>> -
>>> -			if (other->entropy_count <=
>>> -			    3 * other->poolinfo->poolfracbits / 4) {
>>> -				schedule_work(&other->push_work);
>>> -				r->entropy_total = 0;
>>> -			}
>>> -		}
>>> +		if (!work_pending(&other->push_work) &&
>>> +		    (ENTROPY_BITS(r) > 6 * r->poolinfo->poolbytes) &&
>>> +		    (ENTROPY_BITS(other) <= 6 * other->poolinfo->poolbytes))
>>> +			schedule_work(&other->push_work);
>>
>> push_to_pool will transfer chunks of random_read_wakeup_bits.
>>
>> I think push_to_pool should also match this change.
> 
> I was trying to keep the size of this patch as small as practical,
> since the primary goal was to improve the security of the bits
> returned when reading the a 128 bit of randomness immediately after
> boot.
> 

I definitely share this desire with you.

But there are also issues with the CRNG initialization, it is very important
to me not to make those worse.

>> I like it that this path is controllable via random_write_wakeup_bits,
>> that would be lost with this change.
> 
> Very few people actually use these knobs, and in fact I regret making
> them available, since changing these to insane values can impact the
> security properties of /dev/random.  I don't actually see a good
> reason why a user *would* want to adjust the behavior of this code
> path, and it makes it much simpler to reason about how this code path
> works if we don't make it controllable by the user.
> 
>>> @@ -1553,6 +1548,11 @@ static ssize_t extract_entropy_user(struct entropy_store *r, void __user *buf,
>>>  	int large_request = (nbytes > 256);
>>>  
>>>  	trace_extract_entropy_user(r->name, nbytes, ENTROPY_BITS(r), _RET_IP_);
>>> +	if (!r->initialized && r->pull) {
>>> +		xfer_secondary_pool(r, ENTROPY_BITS(r->pull)/8);
>>> +		if (!r->initialized)
>>> +			return 0;
>>
>> Did you want to do that in push_to_pool?
> 
> No, this was deliberate.  The point here is that if the blocking pool
> is not initialized (which is defined as having accumulated 128 bits of
> entropy once), we refuse to return any entropy at all.
> 

Somehow the entropy is not returned, but still transferred from the input_pool
to the blocking_pool, which prevents the initialization of the CRNG.
And finally the blocking_pool is initialized, but not the CRNG.

See my tests below.


>> The second part of the _random_read does not match this change:
>>
>>                 wait_event_interruptible(random_read_wait,
>>                         ENTROPY_BITS(&input_pool) >=
>>                         random_read_wakeup_bits);
>>                 if (signal_pending(current))
>>                         return -ERESTARTSYS;
>>
>>
>> and will go into a busy loop, when
>> ENTROPY_BITS(&input_pool) >= random_read_wakeup_bits, right?
> 
> No, because what's being tested is the entropy estimate in the *input*
> pool.  If there is entropy available, then xfer_secondary_pool() will
> transfer entropy from the input pool to the blocking pool.  This will
> decrease the entropy estimate for the input pool, so we won't busy
> loop.  If the entropy estimate for the blocking pool increases to
> above 128 bits, then the initialized flag will get set, and at that
> point we will start returning random data to the user.
> 
>> The select is basically done here I think this should not indicate read readiness
>> before the pool is initialized that is needs to be changed, right?
> 
> Yes, we should adjust random_pool so it won't report that the fd is
> readable unless the blocking pool is initialized.
> 

Agreed, and the CRNG should never initialize after the blocking pool FWIW.

I use two small test programs to demonstrate what is currently broken.

I hope you are able to reproduce my tests.

I use only interrupt randomness, no dedicated hardware whatsoever,
and no other input events.

$ cat test1.c
#include <stdio.h>
#include <unistd.h>
#include <fcntl.h>
#include <sys/select.h>

int main()
{
  int f = open("/dev/random", O_NDELAY);
  if (f<0) return 1;
  for(;;)
  {
    struct timeval tv = {1, 0};
    fd_set fds;
    int x;
    FD_ZERO(&fds);
    FD_SET(f, &fds);
    x = select(f+1, &fds, NULL, NULL, &tv);
    if (x==1)
    {
      printf("ready\n");
      sleep(1);
    }
    else if (x==0)
    {
      printf("not ready\n");
    }
    else
    {
      printf("error\n");
    }
  }
}

$ cat test2.c
#include <stdio.h>
#include <unistd.h>
#include <fcntl.h>

int main()
{
  int f = open("/dev/random", O_NDELAY);
  if (f<0) return 1;
  for(;;)
  {
    unsigned char buf[16];
    int x = read(f, buf, sizeof(buf));
    if (x>=0)
    {
      int i;
      printf("read %d bytes: ", x);
      for (i=0; i<x; i++) printf("%02x ", buf[i]);
      printf("\n");
    }
  }
}

I build your patch and install.
I boot new, and start test1 and test2 quickly in two terminals,
I start the following command in a bash shell:
while sleep 1; do cat /proc/sys/kernel/random/entropy_avail; done

First the test1 prints not ready, while the entropy avail goes
3 times from 0 to 63
then it goes from 64 to 95, while the test1 (select) prints ready,
but test2 (read) prints nothing.
Then entropy goes to 0 again, and 
read 16 bytes: 38 06 71 17 e6 ac 95 45 57 c4 ab 4a 16 6b 4d 7b
read 3 bytes: 8b d4 50

now always entropy count from 0..63 and
read 6 bytes: e8 08 f7 80 c5 ce

entropy is not reaching 128 bits,
therefore always random: dd: uninitialized urandom read (1 bytes read)
and never random: crng init done


I forgot to mention one other problem in your patch:

> -		if (crng_init < 2 && entropy_bits >= 128) {
> +		if (crng_init < 2) {
> +			if (entropy_bits < 128)
> +				return;
>  			crng_reseed(&primary_crng, r);
>  			entropy_bits = r->entropy_count >> ENTROPY_SHIFT;
>  		}


This will make select more inconsistent than before, because the
test int random_poll (which makes select wait) is now no longer consistent with
the test that follows (which makes select wake up):

this is not waking up, when rng_init < 2 and entropy_bits < 128
                /* should we wake readers? */
                if (entropy_bits >= random_read_wakeup_bits &&
                    wq_has_sleeper(&random_read_wait)) {
                        wake_up_interruptible(&random_read_wait);
                        kill_fasync(&fasync, SIGIO, POLL_IN);
                }

but a select will be immediately satisfied if

        if (ENTROPY_BITS(&input_pool) >= random_read_wakeup_bits)
                mask |= EPOLLIN | EPOLLRDNORM;

those need to match, or the select behaves erratically.

        if (crng_ready() && ENTROPY_BITS(&input_pool) >= random_read_wakeup_bits)
                mask |= EPOLLIN | EPOLLRDNORM;

would behave consistently.


Bernd.