[PATCH kvmtool 0/2] Fix virtio/rng handling in low entropy situations

[PATCH kvmtool 0/2] Fix virtio/rng handling in low entropy situations

[Andre Przywara]

At the moment kvmtool uses the /dev/random device to back the randomness
provided by our virtio/rng implementation. We run it in non-blocking
mode, so are not affected by the nasty "can block indefinitely"
behaviour of that file. However:
- If /dev/random WOULD block, it returns EAGAIN, and we reflect that by
  adding 0 bytes of entropy to the virtio queue. However the virtio 1.x
  spec clearly says this is not allowed, and that we should always provide
  at least one random byte.
- If the guest is waiting for the random numbers, we still run into an
  effective blocking situation, because the buffer will only be filled
  very slowly, effectively stalling or blocking the guest. EDK II shows
  that behaviour, when servicing the EFI_RNG_PROTOCOL runtime service
  call, called by the kernel very early on boot.

Those two patches fix those problems, and allow to boot a Linux kernel
MUCH quicker when the host lacks good entropy sources. On a particular
system the kernel took 10 minutes to boot because of /dev/random
effectively blocking, this runs now in full speed.

The block is avoided by using /dev/urandom, there is a proper rabbit
hole in the internet out there why this is safe, even for cryptographic
applications.

I am not sure we now really need patch 2 anymore (originally I had this
one before I switched to /dev/urandom). I *think* even a read from
/dev/urandom can return early (because of a signal, for instance), so
a return with 0 bytes read seems possible.

Please have a look!

Cheers,
Andre


Andre Przywara (2):
  virtio/rng: switch to using /dev/urandom
  virtio/rng: return at least one byte of entropy

 virtio/rng.c | 33 ++++++++++++++++++++++++++++++---
 1 file changed, 30 insertions(+), 3 deletions(-)

-- 
2.25.1

[PATCH kvmtool 1/2] virtio/rng: switch to using /dev/urandom

[Andre Przywara]

At the moment we use /dev/random as the backing device to provide random
numbers to our virtio-rng implementation. The downside of doing so is
that it may block indefinitely - or return EAGAIN repeatedly in our case.
On one headless systbem without ample noise sources (no keyboard, mouse,
or network traffic) I measured 30 seconds to gain one byte of randomness.
At the moment EDK II insists in waiting for all of the requsted random
bytes (for its EFI_RNG_PROTOCOL runtime service) to arrive, that held up
a Linux kernel boot for more than 10 minutes(!).

According to the Internet(TM), on Linux /dev/urandom provides the same
quality random numbers as /dev/random, it just does not block when the
entropy estimation algorithm suggests so. For all practical purposes the
recommendation is to just use /dev/urandom, QEMU did the switch as well
in 2019 [1].

Use /dev/urandom instead of /dev/random when opening the file descriptor
providing the randomness source for the virtio/rng implementation.

[1] https://gitlab.com/qemu-project/qemu/-/commit/a2230bd778d8

Signed-off-by: Andre Przywara <andre.przywara@arm.com>
---
 virtio/rng.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/virtio/rng.c b/virtio/rng.c
index 8f85d5ec1..eab8f3ac0 100644
--- a/virtio/rng.c
+++ b/virtio/rng.c
@@ -166,7 +166,7 @@ int virtio_rng__init(struct kvm *kvm)
 	if (rdev == NULL)
 		return -ENOMEM;
 
-	rdev->fd = open("/dev/random", O_RDONLY | O_NONBLOCK);
+	rdev->fd = open("/dev/urandom", O_RDONLY | O_NONBLOCK);
 	if (rdev->fd < 0) {
 		r = rdev->fd;
 		goto cleanup;
-- 
2.25.1

Re: [PATCH kvmtool 1/2] virtio/rng: switch to using /dev/urandom

[Jean-Philippe Brucker]

On Thu, Apr 13, 2023 at 05:57:56PM +0100, Andre Przywara wrote:
> At the moment we use /dev/random as the backing device to provide random
> numbers to our virtio-rng implementation. The downside of doing so is
> that it may block indefinitely - or return EAGAIN repeatedly in our case.
> On one headless systbem without ample noise sources (no keyboard, mouse,

system

> or network traffic) I measured 30 seconds to gain one byte of randomness.
> At the moment EDK II insists in waiting for all of the requsted random
> bytes (for its EFI_RNG_PROTOCOL runtime service) to arrive, that held up
> a Linux kernel boot for more than 10 minutes(!).
> 
> According to the Internet(TM), on Linux /dev/urandom provides the same
> quality random numbers as /dev/random, it just does not block when the
> entropy estimation algorithm suggests so. For all practical purposes the
> recommendation is to just use /dev/urandom, QEMU did the switch as well
> in 2019 [1].
> 
> Use /dev/urandom instead of /dev/random when opening the file descriptor
> providing the randomness source for the virtio/rng implementation.
> 
> [1] https://gitlab.com/qemu-project/qemu/-/commit/a2230bd778d8
> 
> Signed-off-by: Andre Przywara <andre.przywara@arm.com>

Reviewed-by: Jean-Philippe Brucker <jean-philippe@linaro.org>

> ---
>  virtio/rng.c | 2 +-
>  1 file changed, 1 insertion(+), 1 deletion(-)
> 
> diff --git a/virtio/rng.c b/virtio/rng.c
> index 8f85d5ec1..eab8f3ac0 100644
> --- a/virtio/rng.c
> +++ b/virtio/rng.c
> @@ -166,7 +166,7 @@ int virtio_rng__init(struct kvm *kvm)
>  	if (rdev == NULL)
>  		return -ENOMEM;
>  
> -	rdev->fd = open("/dev/random", O_RDONLY | O_NONBLOCK);
> +	rdev->fd = open("/dev/urandom", O_RDONLY | O_NONBLOCK);
>  	if (rdev->fd < 0) {
>  		r = rdev->fd;
>  		goto cleanup;
> -- 
> 2.25.1
> 

[RFC PATCH kvmtool 2/2] virtio/rng: return at least one byte of entropy

[Andre Przywara]

In contrast to the original v0.9 virtio spec (which was rather vague),
the virtio 1.0+ spec demands that a RNG request returns at least one
byte:
"The device MUST place one or more random bytes into the buffer, but it
MAY use less than the entire buffer length."

Our current implementation does not prevent returning zero bytes, which
upsets an assert in EDK II. Since we open the fd with O_NONBLOCK, a
return with not the whole buffer filled seems possible.

Take care of that special case, by switching the /dev/urandom file
descriptor into blocking mode when a 0-return happens, than wait for one
byte to arrive. We then switch back to non-blocking mode, and try to
read even more (in case multiple bytes became available at once).
This makes sure we return at least one byte of entropy and become spec
compliant.

Signed-off-by: Andre Przywara <andre.przywara@arm.com>
Reported-by: Sami Mujawar <sami.mujawar@arm.com>
---
 virtio/rng.c | 31 +++++++++++++++++++++++++++++--
 1 file changed, 29 insertions(+), 2 deletions(-)

diff --git a/virtio/rng.c b/virtio/rng.c
index eab8f3ac0..0a0b31a16 100644
--- a/virtio/rng.c
+++ b/virtio/rng.c
@@ -66,8 +66,35 @@ static bool virtio_rng_do_io_request(struct kvm *kvm, struct rng_dev *rdev, stru
 
 	head	= virt_queue__get_iov(queue, iov, &out, &in, kvm);
 	len	= readv(rdev->fd, iov, in);
-	if (len < 0 && errno == EAGAIN)
-		len = 0;
+	if (len < 0 && errno == EAGAIN) {
+		/*
+		 * The virtio 1.0 spec demands at least one byte of entropy.
+		 * Switch the /dev/urandom file descriptor to blocking mode,
+		 * then wait for one byte to arrive. Switch it back to
+		 * non-blocking mode, and try to read even more, if available.
+		 */
+		int flags = fcntl(rdev->fd, F_GETFL);
+
+		if (flags < 0)
+			return false;
+
+		fcntl(rdev->fd, F_SETFL, flags & ~O_NONBLOCK);
+		len = read(rdev->fd, iov[0].iov_base, 1);
+		if (len < 1)
+			return false;
+		fcntl(rdev->fd, F_SETFL, flags);
+		iov[0].iov_base++;
+		iov[0].iov_len--;
+		len = readv(rdev->fd, iov, in);
+		if (len < 0) {
+			if (errno == EAGAIN)	/* no more bytes yet */
+				len = 1;
+			else
+				return false;	/* some error */
+		} else {
+			len++;			/* the one byte already read */
+		}
+	}
 
 	virt_queue__set_used_elem(queue, head, len);
 
-- 
2.25.1

Re: [PATCH kvmtool 0/2] Fix virtio/rng handling in low entropy situations

[Jean-Philippe Brucker]

On Thu, Apr 13, 2023 at 05:57:55PM +0100, Andre Przywara wrote:
> I am not sure we now really need patch 2 anymore (originally I had this
> one before I switched to /dev/urandom). I *think* even a read from
> /dev/urandom can return early (because of a signal, for instance), so
> a return with 0 bytes read seems possible.

Given that this should be very rare, maybe a simple loop would be better
than switching the blocking mode?  It's certainly a good idea to apply the
"MUST" requirements from virtio.

Thanks,
Jean

Re: [PATCH kvmtool 0/2] Fix virtio/rng handling in low entropy situations

[Jean-Philippe Brucker]

On Wed, Apr 19, 2023 at 02:58:32PM +0100, Jean-Philippe Brucker wrote:
> On Thu, Apr 13, 2023 at 05:57:55PM +0100, Andre Przywara wrote:
> > I am not sure we now really need patch 2 anymore (originally I had this
> > one before I switched to /dev/urandom). I *think* even a read from
> > /dev/urandom can return early (because of a signal, for instance), so
> > a return with 0 bytes read seems possible.
> 
> Given that this should be very rare, maybe a simple loop would be better
> than switching the blocking mode?  It's certainly a good idea to apply the
> "MUST" requirements from virtio.

Digging a bit more, the manpage [1] is helpful:

	The O_NONBLOCK flag has no effect when opening /dev/urandom.
	When calling read(2) for the device /dev/urandom, reads of up to
	256 bytes will return as many bytes as are requested and will not
	be interrupted by a signal handler. Reads with a buffer over
	this limit may return less than the requested number of bytes or
	fail with the error EINTR, if interrupted by a signal handler.

So I guess you can also drop the O_NONBLOCK flag in patch 1. And for the
second one, maybe we could fallback to a 256 bytes read if the first one
fails

Thanks,
Jean

[1] https://man7.org/linux/man-pages/man4/urandom.4.html

Re: [PATCH kvmtool 0/2] Fix virtio/rng handling in low entropy situations

[Andre Przywara]

On Wed, 19 Apr 2023 16:10:13 +0100
Jean-Philippe Brucker <jean-philippe@linaro.org> wrote:

Hi Jean-Philippe,

thanks for having a look!

> On Wed, Apr 19, 2023 at 02:58:32PM +0100, Jean-Philippe Brucker wrote:
> > On Thu, Apr 13, 2023 at 05:57:55PM +0100, Andre Przywara wrote:  
> > > I am not sure we now really need patch 2 anymore (originally I had this
> > > one before I switched to /dev/urandom). I *think* even a read from
> > > /dev/urandom can return early (because of a signal, for instance), so
> > > a return with 0 bytes read seems possible.  
> > 
> > Given that this should be very rare, maybe a simple loop would be better
> > than switching the blocking mode?  It's certainly a good idea to apply the
> > "MUST" requirements from virtio.  

So originally I had this patch 2/2 on its own, still using /dev/random.
And there a read() on the O_NONBLOCKed fd would return -EAGAIN immediately
for the next 30 seconds straight, so doing this in a loop sounds very
wrong. After all blocking fd's are there to solve exactly that problem.

But indeed with /dev/urandom being much nicer to us already, and with the
below mentioned special behaviour, just a simple second try (no loop) is
sufficient.

> Digging a bit more, the manpage [1] is helpful:
> 
> 	The O_NONBLOCK flag has no effect when opening /dev/urandom.
> 	When calling read(2) for the device /dev/urandom, reads of up to
> 	256 bytes will return as many bytes as are requested and will not
> 	be interrupted by a signal handler. Reads with a buffer over
> 	this limit may return less than the requested number of bytes or
> 	fail with the error EINTR, if interrupted by a signal handler.

Right, I saw references to that behaviour on the Internet(TM), but missed
the manpage stanza. It still feels a bit awkward since this seems to rely
on some Linux implementation detail, but that's certainly fine for kvmtool
(being Linux only anyway).

> So I guess you can also drop the O_NONBLOCK flag in patch 1. And for the
> second one, maybe we could fallback to a 256 bytes read if the first one
> fails

Yes, that's certainly better and simplifies that patch.

Thanks for digging this out!

Cheers,
Andre

> 
> [1] https://man7.org/linux/man-pages/man4/urandom.4.html
>