[RFC PATCH 0/2] Propagating reseed notifications to user space

[RFC PATCH 0/2] Propagating reseed notifications to user space

[Babis Chalios]

User space often implements PRNGs that use /dev/random as entropy
source. We can not expect that this randomness sources stay completely
unknown forever. For various reasons, the originating PRNG seed may
become known at which point the PRNG becomes insecure for further random
number generation. Events that can lead to that are for example fast
computers reversing the PRNG function using a number of inputs or
Virtual Machine clones which carry seed values into their clones.

During LPC 2022 Jason, Alex, Michael and me brainstormed on how to
atomically expose a notification to user space that it should reseed.
Atomicity is key for the VM clone case. This patchset implements a
potential path to do so.

This patchset introduces an epoch value as the means of communicating to
the guest the need to reseed. The epoch is a 32bit value with the
following form:

              RNG epoch
*-------------*---------------------*
| notifier id | epoch counter value |
*-------------*---------------------*
     8 bits           24 bits

Changes in this value signal moments in time that PRNGs need to be
re-seeded. As a result, the intended use of the epoch from user space
PRNGs is to cache the epoch value every time they reseed using kernel
entropy, then control that its value hasn't changed before giving out
random numbers. If the value has changed the PRNG needs to reseed before
producing any more random bits.

The API for getting hold of this value is offered through
/dev/(u)random. We introduce a new ioctl for these devices, which
creates an anonymous file descriptor. User processes can call the
ioctl() to get the anon fd and then mmap it to a single page. That page
contains the value of the epoch at offset 0.

Naturally, random.c is the component that maintains the RNG epoch.
During initialization it allocates a single global page which holds the
epoch value. Moreover, it exposes an API to kernel subsystems
(notifiers) which can report events that require PRNG reseeding.
Notifiers register with random.c and receive an 8-bit notifier id (up to
256 subscribers should be enough) and a pointer to the epoch. Notifying,
then, is equivalent to writing in the epoch address a new epoch value.

Notifiers write epoch values that include the notifier ID on the higher
8 bits and increasing counter values on the 24 remaining bits. This
guarantees that two notifiers cannot ever write the same epoch value,
since notificator IDs are unique.

The first patch of this series implements the epoch mechanism. It adds
the logic in the random.c to maintain the epoch page and expose the
user space facing API. It also adds the internal API that allows kernel
systems to register as notifiers.

Based on this API, we can implement notifiers. As example notifier, this
patch set only contains a virtio-rng backend. If we agree on this path
forward, the natural next notifier would be an in-kernel timer with a
user settable frequency that allows the kernel to notify all its user
space applications to reseed regularly.

Michael sent out a proposal for an extension to virtio-rng [1] which we
can use to turn virtio-rng devices to RNG epoch notifiers. Briefly, the
proposal defines the concept of "entropy leaks", i.e. events in time
that cause entropy to decrease, such as VM snapshots. A virtio-rng
driver can program the device to perform a number of operations on guest
memory when entropy leaks happen. The proposal defines two possible
operations:

* "fill-on-leak": Fill a buffer with random bytes
* "copy-on-leak": Copy a source buffer in a destination buffer

The second patch implements the entropy leak reporting feature of
virtio-rng and registers virtio-rng devices as epoch notifiers with
random.c. It ensures that one copy-on-leak operation is always in-flight
to increase the epoch value when a VM snapshot occurs. The intention is
that the VMM will perform these operations before resuming vCPUs, so
that user space processes will observe the changes in the epoch value
atomically. Additionally, it always keeps a fill-on-leak command in the
queue, so that we can get some fresh entropy when VM snapshots occur.

This is an RFC, so that we can discuss whether the proposed ABI works.
Also, I'd like to hear people's opinion on the internal registration
API, 8/24 split etc. If we decide that this approach works, I 'm happy
to add documentation for it, with examples on how user space can make
use of it. 

[1] https://lore.kernel.org/virtio-dev/20221121162756.350032-1-mst@redhat.com/

Babis Chalios (2):
  random: emit reseed notifications for PRNGs
  virtio-rng: implement entropy leak feature

 drivers/char/hw_random/virtio-rng.c | 189 +++++++++++++++++++++++++++-
 drivers/char/random.c               | 147 ++++++++++++++++++++++
 include/linux/random.h              |  28 +++++
 include/uapi/linux/random.h         |  11 ++
 include/uapi/linux/virtio_rng.h     |   3 +
 5 files changed, 373 insertions(+), 5 deletions(-)

-- 
2.40.1

[RFC PATCH 1/2] random: emit reseed notifications for PRNGs

[Babis Chalios]

Sometimes, PRNGs need to reseed. For example, on a regular timer
interval, to ensure nothing consumes a random value for longer than e.g.
5 minutes, or when VMs get cloned, to ensure seeds don't leak in to
clones.

The notification happens through a 32bit epoch value that changes every
time cached entropy is no longer valid, hence PRNGs need to reseed. User
space applications can get hold of a pointer to this value through
/dev/(u)random. We introduce a new ioctl() that returns an anonymous
file descriptor. From this file descriptor we can mmap() a single page
which includes the epoch at offset 0.

random.c maintains the epoch value in a global shared page. It exposes
a registration API for kernel subsystems that are able to notify when
reseeding is needed. Notifiers register with random.c and receive a
unique 8bit ID and a pointer to the epoch. When they need to report a
reseeding event they write a new epoch value which includes the
notifier ID in the first 8 bits and an increasing counter value in the
remaining 24 bits:

              RNG epoch
*-------------*---------------------*
| notifier id | epoch counter value |
*-------------*---------------------*
     8 bits           24 bits

Like this, different notifiers always write different values in the
epoch.

Signed-off-by: Babis Chalios <bchalios@amazon.es>
---
 drivers/char/random.c       | 147 ++++++++++++++++++++++++++++++++++++
 include/linux/random.h      |  28 +++++++
 include/uapi/linux/random.h |  11 +++
 3 files changed, 186 insertions(+)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index 3cb37760dfec..72b524099b60 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -54,6 +54,8 @@
 #include <linux/suspend.h>
 #include <linux/siphash.h>
 #include <linux/sched/isolation.h>
+#include "linux/anon_inodes.h"
+#include "linux/bitmap.h"
 #include <crypto/chacha.h>
 #include <crypto/blake2s.h>
 #include <asm/archrandom.h>
@@ -206,6 +208,7 @@ enum {
 static struct {
 	u8 key[CHACHA_KEY_SIZE] __aligned(__alignof__(long));
 	unsigned long generation;
+	u32 cached_epoch;
 	spinlock_t lock;
 } base_crng = {
 	.lock = __SPIN_LOCK_UNLOCKED(base_crng.lock)
@@ -242,6 +245,138 @@ static unsigned int crng_reseed_interval(void)
 	return CRNG_RESEED_INTERVAL;
 }
 
+/*
+ * Tracking moments in time that PRNGs (ours and user-space) need to reseed
+ * due to an "entropy leak".
+ *
+ * We call the time period between two "entropy leak" events an "epoch".
+ * Epoch is a 32-bit unsigned value that lives in a dedicated global page.
+ * Systems that want to report entropy leaks will get an 1-byte notifier id
+ * (up to 256 notifiers) and the address of the epoch.
+ *
+ * Each notifier will write epochs in the form:
+ *
+ *      1 byte                  3 bytes
+ * +---------------+-------------------------------+
+ * |  notifier id  |    next epoch counter value   |
+ * +---------------+-------------------------------+
+ *
+ * This way, epochs are namespaced per notifier, so no two different
+ * notifiers will ever write the same epoch value.
+ */
+
+static struct {
+	struct rand_epoch_data *epoch;
+	DECLARE_BITMAP(notifiers, RNG_EPOCH_NOTIFIER_NR_BITS);
+	spinlock_t lock;
+} epoch_data = {
+	.lock = __SPIN_LOCK_UNLOCKED(epoch_data.lock),
+};
+
+static int epoch_mmap(struct file *filep, struct vm_area_struct *vma)
+{
+	if (vma->vm_pgoff || vma_pages(vma) > 1)
+		return -EINVAL;
+
+	if (vma->vm_flags & VM_WRITE)
+		return -EPERM;
+
+	/* Don't allow growing the region with mremap(). */
+	vm_flags_set(vma, VM_DONTEXPAND);
+	/* Don't allow mprotect() to make this writeable in the future */
+	vm_flags_clear(vma, VM_MAYWRITE);
+
+	return vm_insert_page(vma, vma->vm_start, virt_to_page(epoch_data.epoch));
+}
+
+static const struct file_operations rng_epoch_fops = {
+	.mmap = epoch_mmap,
+	.llseek = noop_llseek,
+};
+
+static int create_epoch_fd(void)
+{
+	unsigned long flags;
+	int ret = -ENOTTY;
+
+	spin_lock_irqsave(&epoch_data.lock, flags);
+	if (bitmap_empty(epoch_data.notifiers, RNG_EPOCH_NOTIFIER_NR_BITS))
+		goto out;
+	spin_unlock_irqrestore(&epoch_data.lock, flags);
+
+	return anon_inode_getfd("rand:epoch", &rng_epoch_fops, &epoch_data, O_RDONLY | O_CLOEXEC);
+out:
+	spin_unlock_irqrestore(&epoch_data.lock, flags);
+	return ret;
+}
+
+/*
+ * Get the current epoch. If nobody has subscribed, this will always return 0.
+ */
+static unsigned long get_epoch(void)
+{
+	u32 epoch = 0;
+
+	if (likely(epoch_data.epoch))
+		epoch = epoch_data.epoch->data;
+
+	return epoch;
+}
+
+/*
+ * Register an epoch notifier
+ *
+ * Allocate a notifier ID and provide the address to the epoch. If the address
+ * has not being allocated yet (this is the first call to register a notifier)
+ * this will allocate the page holding the epoch. If we have reached the limit
+ * of notifiers it will fail.
+ */
+int rng_register_epoch_notifier(struct rng_epoch_notifier *notifier)
+{
+	unsigned long flags;
+	u8 new_id;
+
+	if (!notifier)
+		return -EINVAL;
+
+	spin_lock_irqsave(&epoch_data.lock, flags);
+	new_id = bitmap_find_free_region(epoch_data.notifiers, RNG_EPOCH_NOTIFIER_NR_BITS, 0);
+	if (new_id < 0)
+		goto err_no_id;
+	spin_unlock_irqrestore(&epoch_data.lock, flags);
+
+	notifier->id = new_id;
+	notifier->epoch = epoch_data.epoch;
+	return 0;
+
+err_no_id:
+	spin_unlock_irqrestore(&epoch_data.lock, flags);
+	return -ENOMEM;
+}
+EXPORT_SYMBOL_GPL(rng_register_epoch_notifier);
+
+/*
+ * Unregister an epoch notifier
+ *
+ * This will release the notifier ID previously allocated through
+ * `rng_register_epoch_notifier`.
+ */
+int rng_unregister_epoch_notifier(struct rng_epoch_notifier *notifier)
+{
+	unsigned long flags;
+
+	if (!notifier)
+		return -EINVAL;
+
+	spin_lock_irqsave(&epoch_data.lock, flags);
+	bitmap_clear(epoch_data.notifiers, notifier->id, 1);
+	spin_unlock_irqrestore(&epoch_data.lock, flags);
+
+	notifier->epoch = NULL;
+	return 0;
+}
+EXPORT_SYMBOL_GPL(rng_unregister_epoch_notifier);
+
 /* Used by crng_reseed() and crng_make_state() to extract a new seed from the input pool. */
 static void extract_entropy(void *buf, size_t len);
 
@@ -344,6 +479,14 @@ static void crng_make_state(u32 chacha_state[CHACHA_STATE_WORDS],
 			return;
 	}
 
+	/*
+	 * If the epoch has changed we reseed.
+	 */
+	if (unlikely(READ_ONCE(base_crng.cached_epoch) != get_epoch())) {
+		WRITE_ONCE(base_crng.cached_epoch, get_epoch());
+		crng_reseed(NULL);
+	}
+
 	local_lock_irqsave(&crngs.lock, flags);
 	crng = raw_cpu_ptr(&crngs);
 
@@ -888,6 +1031,8 @@ void __init random_init(void)
 	_mix_pool_bytes(&entropy, sizeof(entropy));
 	add_latent_entropy();
 
+	epoch_data.epoch = (struct rand_epoch_data *)get_zeroed_page(GFP_KERNEL);
+
 	/*
 	 * If we were initialized by the cpu or bootloader before jump labels
 	 * are initialized, then we should enable the static branch here, where
@@ -1528,6 +1673,8 @@ static long random_ioctl(struct file *f, unsigned int cmd, unsigned long arg)
 			return -ENODATA;
 		crng_reseed(NULL);
 		return 0;
+	case RNDEPOCH:
+		return create_epoch_fd();
 	default:
 		return -EINVAL;
 	}
diff --git a/include/linux/random.h b/include/linux/random.h
index b0a940af4fff..0fdacf4ee8aa 100644
--- a/include/linux/random.h
+++ b/include/linux/random.h
@@ -161,4 +161,32 @@ int random_online_cpu(unsigned int cpu);
 extern const struct file_operations random_fops, urandom_fops;
 #endif
 
+
+/*
+ * Constants that define the format of the epoch value.
+ *
+ * Currently we use a 8/24 split for epoch values. The lower 24 bits are used
+ * for the epoch counter and the 8 remaining are used for the notifier ID.
+ */
+#define RNG_EPOCH_NOTIFIER_NR_BITS 8
+#define RNG_EPOCH_COUNTER_SHIFT 0
+#define RNG_EPOCH_COUNTER_MASK GENMASK(23, 0)
+#define RNG_EPOCH_ID_SHIFT 24
+#define RNG_EPOCH_ID_MASK GENMASK(31, 24)
+
+/*
+ * An epoch notifier is a system that can report entropy leak events.
+ * Notifiers receive a unique identifier and the address where they will write
+ * a new epoch when an entropy leak happens.
+ */
+struct rng_epoch_notifier {
+	/* unique ID of the notifier */
+	u8 id;
+	/* pointer to epoch data */
+	struct rand_epoch_data *epoch;
+};
+
+int rng_register_epoch_notifier(struct rng_epoch_notifier *notifier);
+int rng_unregister_epoch_notifier(struct rng_epoch_notifier *notifier);
+
 #endif /* _LINUX_RANDOM_H */
diff --git a/include/uapi/linux/random.h b/include/uapi/linux/random.h
index e744c23582eb..f79d93820bdd 100644
--- a/include/uapi/linux/random.h
+++ b/include/uapi/linux/random.h
@@ -38,6 +38,9 @@
 /* Reseed CRNG.  (Superuser only.) */
 #define RNDRESEEDCRNG	_IO( 'R', 0x07 )
 
+/* Get a file descriptor for the RNG generation page. */
+#define RNDEPOCH	_IO('R', 0x08)
+
 struct rand_pool_info {
 	int	entropy_count;
 	int	buf_size;
@@ -55,4 +58,12 @@ struct rand_pool_info {
 #define GRND_RANDOM	0x0002
 #define GRND_INSECURE	0x0004
 
+/*
+ * The epoch type exposed through /dev/(u)random to notify user-space
+ * PRNGs that need to re-seed
+ */
+struct rand_epoch_data {
+	__u32 data;
+};
+
 #endif /* _UAPI_LINUX_RANDOM_H */
-- 
2.40.1

Re: [RFC PATCH 1/2] random: emit reseed notifications for PRNGs

[Greg KH]

On Wed, Aug 23, 2023 at 11:01:05AM +0200, Babis Chalios wrote:
> Sometimes, PRNGs need to reseed. For example, on a regular timer
> interval, to ensure nothing consumes a random value for longer than e.g.
> 5 minutes, or when VMs get cloned, to ensure seeds don't leak in to
> clones.
> 
> The notification happens through a 32bit epoch value that changes every
> time cached entropy is no longer valid, hence PRNGs need to reseed. User
> space applications can get hold of a pointer to this value through
> /dev/(u)random. We introduce a new ioctl() that returns an anonymous
> file descriptor. From this file descriptor we can mmap() a single page
> which includes the epoch at offset 0.
> 
> random.c maintains the epoch value in a global shared page. It exposes
> a registration API for kernel subsystems that are able to notify when
> reseeding is needed. Notifiers register with random.c and receive a
> unique 8bit ID and a pointer to the epoch. When they need to report a
> reseeding event they write a new epoch value which includes the
> notifier ID in the first 8 bits and an increasing counter value in the
> remaining 24 bits:
> 
>               RNG epoch
> *-------------*---------------------*
> | notifier id | epoch counter value |
> *-------------*---------------------*
>      8 bits           24 bits

Why not just use 32/32 for a full 64bit value, or better yet, 2
different variables?  Why is 32bits and packing things together here
somehow simpler?

thanks,

greg k-h

Re: [RFC PATCH 1/2] random: emit reseed notifications for PRNGs

[Babis Chalios]

Hi Greg,

On 23/8/23 11:08, Greg KH wrote:
> CAUTION: This email originated from outside of the organization. Do not click links or open attachments unless you can confirm the sender and know the content is safe.
>
>
>
> On Wed, Aug 23, 2023 at 11:01:05AM +0200, Babis Chalios wrote:
>> Sometimes, PRNGs need to reseed. For example, on a regular timer
>> interval, to ensure nothing consumes a random value for longer than e.g.
>> 5 minutes, or when VMs get cloned, to ensure seeds don't leak in to
>> clones.
>>
>> The notification happens through a 32bit epoch value that changes every
>> time cached entropy is no longer valid, hence PRNGs need to reseed. User
>> space applications can get hold of a pointer to this value through
>> /dev/(u)random. We introduce a new ioctl() that returns an anonymous
>> file descriptor. From this file descriptor we can mmap() a single page
>> which includes the epoch at offset 0.
>>
>> random.c maintains the epoch value in a global shared page. It exposes
>> a registration API for kernel subsystems that are able to notify when
>> reseeding is needed. Notifiers register with random.c and receive a
>> unique 8bit ID and a pointer to the epoch. When they need to report a
>> reseeding event they write a new epoch value which includes the
>> notifier ID in the first 8 bits and an increasing counter value in the
>> remaining 24 bits:
>>
>>                RNG epoch
>> *-------------*---------------------*
>> | notifier id | epoch counter value |
>> *-------------*---------------------*
>>       8 bits           24 bits
> Why not just use 32/32 for a full 64bit value, or better yet, 2
> different variables?  Why is 32bits and packing things together here
> somehow simpler?

We made it 32 bits so that we can read/write it atomically in all 32bit 
architectures.
Do you think that's not a problem?

Cheers,
Babis

Re: [RFC PATCH 1/2] random: emit reseed notifications for PRNGs

[Greg KH]

On Wed, Aug 23, 2023 at 11:27:11AM +0200, Babis Chalios wrote:
> Hi Greg,
> 
> On 23/8/23 11:08, Greg KH wrote:
> > CAUTION: This email originated from outside of the organization. Do not click links or open attachments unless you can confirm the sender and know the content is safe.
> > 
> > 
> > 
> > On Wed, Aug 23, 2023 at 11:01:05AM +0200, Babis Chalios wrote:
> > > Sometimes, PRNGs need to reseed. For example, on a regular timer
> > > interval, to ensure nothing consumes a random value for longer than e.g.
> > > 5 minutes, or when VMs get cloned, to ensure seeds don't leak in to
> > > clones.
> > > 
> > > The notification happens through a 32bit epoch value that changes every
> > > time cached entropy is no longer valid, hence PRNGs need to reseed. User
> > > space applications can get hold of a pointer to this value through
> > > /dev/(u)random. We introduce a new ioctl() that returns an anonymous
> > > file descriptor. From this file descriptor we can mmap() a single page
> > > which includes the epoch at offset 0.
> > > 
> > > random.c maintains the epoch value in a global shared page. It exposes
> > > a registration API for kernel subsystems that are able to notify when
> > > reseeding is needed. Notifiers register with random.c and receive a
> > > unique 8bit ID and a pointer to the epoch. When they need to report a
> > > reseeding event they write a new epoch value which includes the
> > > notifier ID in the first 8 bits and an increasing counter value in the
> > > remaining 24 bits:
> > > 
> > >                RNG epoch
> > > *-------------*---------------------*
> > > | notifier id | epoch counter value |
> > > *-------------*---------------------*
> > >       8 bits           24 bits
> > Why not just use 32/32 for a full 64bit value, or better yet, 2
> > different variables?  Why is 32bits and packing things together here
> > somehow simpler?
> 
> We made it 32 bits so that we can read/write it atomically in all 32bit
> architectures.
> Do you think that's not a problem?

What 32bit platforms care about this type of interface at all?

thanks,

greg k-h

Re: [RFC PATCH 1/2] random: emit reseed notifications for PRNGs

[Alexander Graf]

Hey Greg,

On 23.08.23 12:08, Babis Chalios wrote:
>
>
> On 23/8/23 12:06, Greg KH wrote:
>>
>> On Wed, Aug 23, 2023 at 11:27:11AM +0200, Babis Chalios wrote:
>>> Hi Greg,
>>>
>>> On 23/8/23 11:08, Greg KH wrote:
>>>>
>>>> On Wed, Aug 23, 2023 at 11:01:05AM +0200, Babis Chalios wrote:
>>>>> Sometimes, PRNGs need to reseed. For example, on a regular timer
>>>>> interval, to ensure nothing consumes a random value for longer than e.g.
>>>>> 5 minutes, or when VMs get cloned, to ensure seeds don't leak in to
>>>>> clones.
>>>>>
>>>>> The notification happens through a 32bit epoch value that changes every
>>>>> time cached entropy is no longer valid, hence PRNGs need to reseed. User
>>>>> space applications can get hold of a pointer to this value through
>>>>> /dev/(u)random. We introduce a new ioctl() that returns an anonymous
>>>>> file descriptor. From this file descriptor we can mmap() a single page
>>>>> which includes the epoch at offset 0.
>>>>>
>>>>> random.c maintains the epoch value in a global shared page. It exposes
>>>>> a registration API for kernel subsystems that are able to notify when
>>>>> reseeding is needed. Notifiers register with random.c and receive a
>>>>> unique 8bit ID and a pointer to the epoch. When they need to report a
>>>>> reseeding event they write a new epoch value which includes the
>>>>> notifier ID in the first 8 bits and an increasing counter value in the
>>>>> remaining 24 bits:
>>>>>
>>>>>                 RNG epoch
>>>>> *-------------*---------------------*
>>>>> | notifier id | epoch counter value |
>>>>> *-------------*---------------------*
>>>>>        8 bits           24 bits
>>>> Why not just use 32/32 for a full 64bit value, or better yet, 2
>>>> different variables?  Why is 32bits and packing things together here
>>>> somehow simpler?
>>> We made it 32 bits so that we can read/write it atomically in all 32bit
>>> architectures.
>>> Do you think that's not a problem?
>> What 32bit platforms care about this type of interface at all?
>
> I think, any 32bit platform that gets random bytes from the kernel.


We're building an ABI here that generically propagates an atomic way for 
user space to learn about an "rng epoch". Since there are 32bit user 
space applications out there whose executing VMs can be cloned or that 
want to learn about regular epoch changes (i386, arm32, 32bit riscv, 
etc), we need to make sure we have a viable way for them to consume the 
ABI as well. This applies to 32bit user space - the kernel may as well 
run 64bit like a typical aarch64 setup today.

We could of course build this ABI with a "long" notion in mind. But then 
you would get an ioctl to a kernel data structure that is 64bit, even 
with CONFIG_COMPAT. So now we'd have to build wrappers and maintain 2 
structures for 32bit and 64bit user space and everything would become 
super complicated.

These events won't happen very often. 24bits is very likely easily 
sufficient to not ever race between someone setting a new epoch and 
someone reading the epoch value. So by keeping it 32bit, we make it 
guaranteed atomic on all targets and completely remove any CONFIG_COMPAT 
woes.


Alex





Amazon Development Center Germany GmbH
Krausenstr. 38
10117 Berlin
Geschaeftsfuehrung: Christian Schlaeger, Jonathan Weiss
Eingetragen am Amtsgericht Charlottenburg unter HRB 149173 B
Sitz: Berlin
Ust-ID: DE 289 237 879

Re: [RFC PATCH 1/2] random: emit reseed notifications for PRNGs

[Greg KH]

On Wed, Aug 23, 2023 at 12:08:35PM +0200, Babis Chalios wrote:
> 
> 
> On 23/8/23 12:06, Greg KH wrote:
> > CAUTION: This email originated from outside of the organization. Do not click links or open attachments unless you can confirm the sender and know the content is safe.
> > 
> > 
> > 
> > On Wed, Aug 23, 2023 at 11:27:11AM +0200, Babis Chalios wrote:
> > > Hi Greg,
> > > 
> > > On 23/8/23 11:08, Greg KH wrote:
> > > > CAUTION: This email originated from outside of the organization. Do not click links or open attachments unless you can confirm the sender and know the content is safe.
> > > > 
> > > > 
> > > > 
> > > > On Wed, Aug 23, 2023 at 11:01:05AM +0200, Babis Chalios wrote:
> > > > > Sometimes, PRNGs need to reseed. For example, on a regular timer
> > > > > interval, to ensure nothing consumes a random value for longer than e.g.
> > > > > 5 minutes, or when VMs get cloned, to ensure seeds don't leak in to
> > > > > clones.
> > > > > 
> > > > > The notification happens through a 32bit epoch value that changes every
> > > > > time cached entropy is no longer valid, hence PRNGs need to reseed. User
> > > > > space applications can get hold of a pointer to this value through
> > > > > /dev/(u)random. We introduce a new ioctl() that returns an anonymous
> > > > > file descriptor. From this file descriptor we can mmap() a single page
> > > > > which includes the epoch at offset 0.
> > > > > 
> > > > > random.c maintains the epoch value in a global shared page. It exposes
> > > > > a registration API for kernel subsystems that are able to notify when
> > > > > reseeding is needed. Notifiers register with random.c and receive a
> > > > > unique 8bit ID and a pointer to the epoch. When they need to report a
> > > > > reseeding event they write a new epoch value which includes the
> > > > > notifier ID in the first 8 bits and an increasing counter value in the
> > > > > remaining 24 bits:
> > > > > 
> > > > >                 RNG epoch
> > > > > *-------------*---------------------*
> > > > > | notifier id | epoch counter value |
> > > > > *-------------*---------------------*
> > > > >        8 bits           24 bits
> > > > Why not just use 32/32 for a full 64bit value, or better yet, 2
> > > > different variables?  Why is 32bits and packing things together here
> > > > somehow simpler?
> > > We made it 32 bits so that we can read/write it atomically in all 32bit
> > > architectures.
> > > Do you think that's not a problem?
> > What 32bit platforms care about this type of interface at all?
> 
> I think, any 32bit platform that gets random bytes from the kernel.

You are making a new api, for some new functionality, for what I thought
was virtual machines (hence the virtio driver), none of which work in a
32bit system.

I thought this was an ioctl for userspace, which can handle 64bits at
once (or 2 32bit numbers).

For internal kernel stuff, a lock should be fine, or better yet, a 64bit
atomic value read (horrible on 32bit platforms, I know...)

Just asking, it feels odd to pack bits in these days for when 90% of the
cpus really don't need it.

greg k-h

Re: [RFC PATCH 1/2] random: emit reseed notifications for PRNGs

[Alexander Graf]

On 23.08.23 12:25, Greg KH wrote:
> On Wed, Aug 23, 2023 at 12:08:35PM +0200, Babis Chalios wrote:
>>
>> On 23/8/23 12:06, Greg KH wrote:
>>> CAUTION: This email originated from outside of the organization. Do not click links or open attachments unless you can confirm the sender and know the content is safe.
>>>
>>>
>>>
>>> On Wed, Aug 23, 2023 at 11:27:11AM +0200, Babis Chalios wrote:
>>>> Hi Greg,
>>>>
>>>> On 23/8/23 11:08, Greg KH wrote:
>>>>> CAUTION: This email originated from outside of the organization. Do not click links or open attachments unless you can confirm the sender and know the content is safe.
>>>>>
>>>>>
>>>>>
>>>>> On Wed, Aug 23, 2023 at 11:01:05AM +0200, Babis Chalios wrote:
>>>>>> Sometimes, PRNGs need to reseed. For example, on a regular timer
>>>>>> interval, to ensure nothing consumes a random value for longer than e.g.
>>>>>> 5 minutes, or when VMs get cloned, to ensure seeds don't leak in to
>>>>>> clones.
>>>>>>
>>>>>> The notification happens through a 32bit epoch value that changes every
>>>>>> time cached entropy is no longer valid, hence PRNGs need to reseed. User
>>>>>> space applications can get hold of a pointer to this value through
>>>>>> /dev/(u)random. We introduce a new ioctl() that returns an anonymous
>>>>>> file descriptor. From this file descriptor we can mmap() a single page
>>>>>> which includes the epoch at offset 0.
>>>>>>
>>>>>> random.c maintains the epoch value in a global shared page. It exposes
>>>>>> a registration API for kernel subsystems that are able to notify when
>>>>>> reseeding is needed. Notifiers register with random.c and receive a
>>>>>> unique 8bit ID and a pointer to the epoch. When they need to report a
>>>>>> reseeding event they write a new epoch value which includes the
>>>>>> notifier ID in the first 8 bits and an increasing counter value in the
>>>>>> remaining 24 bits:
>>>>>>
>>>>>>                  RNG epoch
>>>>>> *-------------*---------------------*
>>>>>> | notifier id | epoch counter value |
>>>>>> *-------------*---------------------*
>>>>>>         8 bits           24 bits
>>>>> Why not just use 32/32 for a full 64bit value, or better yet, 2
>>>>> different variables?  Why is 32bits and packing things together here
>>>>> somehow simpler?
>>>> We made it 32 bits so that we can read/write it atomically in all 32bit
>>>> architectures.
>>>> Do you think that's not a problem?
>>> What 32bit platforms care about this type of interface at all?
>> I think, any 32bit platform that gets random bytes from the kernel.
> You are making a new api, for some new functionality, for what I thought
> was virtual machines (hence the virtio driver), none of which work in a
> 32bit system.


There should be 2 use cases of this that I'm aware of:

   * Virtual machine clones. Most 64bit VMs can execute 32bit user space.
   * Bare metal rng time-to-live. An easy mechanism to tell every PRNG 
in the system to reseed every 5 minutes. This applies to all 
architectures Linux supports.


> I thought this was an ioctl for userspace, which can handle 64bits at
> once (or 2 32bit numbers).


The ioctl is only to create a file descriptor that you can use to mmap() 
a shared page between kernel and user space which you can then 
atomically access to understand if you're in the old epoch (keep using 
previous RNG values) or in the new epoch (discard any old cached RNG 
values).


> For internal kernel stuff, a lock should be fine, or better yet, a 64bit
> atomic value read (horrible on 32bit platforms, I know...)
>
> Just asking, it feels odd to pack bits in these days for when 90% of the
> cpus really don't need it.


I agree, but we're really not really bit constrained for this value and 
by making it 32bit always, we can guarantee that there will never be 
muckery for 32-on-64 compatibility.


Alex





Amazon Development Center Germany GmbH
Krausenstr. 38
10117 Berlin
Geschaeftsfuehrung: Christian Schlaeger, Jonathan Weiss
Eingetragen am Amtsgericht Charlottenburg unter HRB 149173 B
Sitz: Berlin
Ust-ID: DE 289 237 879

[RFC PATCH 2/2] virtio-rng: implement entropy leak feature

[Babis Chalios]

Implement the virtio-rng entropy leak feature that allows the guest
driver to request from the device to perform certain operations in the
event of an "entropy leak", such as when taking a VM snapshot. The guest
can request one of two operations: (i) fill a buffer with random bytes,
or (ii) perform a memory copy between two buffers.

The feature is similar to Microsoft's Virtual Machine Generation ID and
it can be used to (1) avoid the race-condition that exists in our
current VMGENID implementation, between the time vcpus are resumed and
the ACPI notification is being handled and (2) propagate these events to
user space through the random.c epoch mechanism.

This commit implements the protocol between guest and device.
Moreover, it makes sure that there is always a request from random bytes
in flight. It uses these bytes as fresh entropy upon a snapshot.
Finally, it programs the device to bump the random.c epoch when a
snapshot occurs.

Signed-off-by: Babis Chalios <bchalios@amazon.es>
---
 drivers/char/hw_random/virtio-rng.c | 189 +++++++++++++++++++++++++++-
 include/uapi/linux/virtio_rng.h     |   3 +
 2 files changed, 187 insertions(+), 5 deletions(-)

diff --git a/drivers/char/hw_random/virtio-rng.c b/drivers/char/hw_random/virtio-rng.c
index e41a84e6b4b5..469e0c522dbf 100644
--- a/drivers/char/hw_random/virtio-rng.c
+++ b/drivers/char/hw_random/virtio-rng.c
@@ -13,12 +13,29 @@
 #include <linux/virtio_rng.h>
 #include <linux/module.h>
 #include <linux/slab.h>
+#include <linux/random.h>
 
 static DEFINE_IDA(rng_index_ida);
 
+struct virtrng_leak_queue {
+	/* The underlying virtqueue of this leak queue */
+	struct virtqueue *vq;
+	/* The next epoch value the device should write through this leak queue */
+	struct rand_epoch_data next_epoch;
+};
+
+struct virtrng_leak_queue;
+
 struct virtrng_info {
 	struct hwrng hwrng;
 	struct virtqueue *vq;
+
+	/* Leak queues */
+	bool has_leakqs;
+	struct virtrng_leak_queue leakq[2];
+	int active_leakq;
+	struct rng_epoch_notifier epoch_notifier;
+
 	char name[25];
 	int index;
 	bool hwrng_register_done;
@@ -30,11 +47,118 @@ struct virtrng_info {
 	/* minimal size returned by rng_buffer_size() */
 #if SMP_CACHE_BYTES < 32
 	u8 data[32];
+	u8 leak_data[32];
 #else
 	u8 data[SMP_CACHE_BYTES];
+	u8 leak_data[SMP_CACHE_BYTES];
 #endif
 };
 
+static struct virtrng_leak_queue *vq_to_leakq(struct virtrng_info *vi,
+		struct virtqueue *vq)
+{
+	return &vi->leakq[vq->index - 1];
+}
+
+/*
+ * Swaps the queues and returns the new active leak queue.
+ * It assumes that the leak queues' lock is being held
+ */
+static void swap_leakqs(struct virtrng_info *vi)
+{
+	vi->active_leakq = 1 - vi->active_leakq;
+}
+
+static struct virtrng_leak_queue *get_active_leakq(struct virtrng_info *vi)
+{
+	return &vi->leakq[vi->active_leakq];
+}
+
+/*
+ * Create the next epoch value that we will write through the leak queue.
+ *
+ * Subsequent epoch values will be written through alternate leak queues,
+ * so the next epoch value for each queue will be:
+ *
+ * *-------------*----------------------------------------------*
+ * | notifier_id | (current_epoch + 2) & RNG_EPOCH_COUNTER_MASK |
+ * *-------------*----------------------------------------------*
+ */
+static void prepare_next_epoch(struct virtrng_info *vi, struct virtrng_leak_queue *leakq)
+{
+	leakq->next_epoch.data = ((leakq->next_epoch.data + 2) & RNG_EPOCH_COUNTER_MASK) |
+		 (vi->epoch_notifier.id << RNG_EPOCH_ID_SHIFT);
+}
+
+static int do_fill_on_leak_request(struct virtrng_info *vi, struct virtqueue *vq, void *data,
+				    size_t len)
+{
+	struct scatterlist sg;
+
+	sg_init_one(&sg, data, len);
+	return virtqueue_add_inbuf(vq, &sg, 1, data, GFP_KERNEL);
+}
+
+static int do_copy_on_leak_request(struct virtrng_info *vi, struct virtqueue *vq,
+				   void *to, void *from, size_t len)
+{
+	struct scatterlist out, in, *sgs[2];
+
+	sg_init_one(&out, from, len);
+	sgs[0] = &out;
+	sg_init_one(&in, to, len);
+	sgs[1] = &in;
+
+	return virtqueue_add_sgs(vq, sgs, 1, 1, to, GFP_KERNEL);
+}
+
+static int add_entropy_leak_requests(struct virtrng_info *vi, struct virtrng_leak_queue *leakq)
+{
+	do_fill_on_leak_request(vi, leakq->vq, &vi->leak_data, sizeof(vi->leak_data));
+	/* Make sure the device writes the next valid epoch value */
+	do_copy_on_leak_request(vi, leakq->vq, vi->epoch_notifier.epoch, &leakq->next_epoch,
+			sizeof(u32));
+
+	return 0;
+}
+
+static void entropy_leak_detected(struct virtqueue *vq)
+{
+	struct virtrng_info *vi = vq->vdev->priv;
+	struct virtrng_leak_queue *activeq = get_active_leakq(vi);
+	struct virtrng_leak_queue *leakq = vq_to_leakq(vi, vq);
+	unsigned int len;
+	void *buffer;
+
+	/*
+	 * The first time we see a used buffer in the active leak queue we swap queues
+	 * so that new commands are added in the new active leak queue.
+	 */
+	if (vq == activeq->vq) {
+		pr_info("%s: entropy leak detected!", vi->name);
+		swap_leakqs(vi);
+	}
+
+	/* Drain all the used buffers from the queue */
+	while ((buffer = virtqueue_get_buf(vq, &len)) != NULL) {
+		if (buffer == vi->leak_data) {
+			add_device_randomness(vi->leak_data, sizeof(vi->leak_data));
+
+			/*
+			 * Ensure we always have a pending request for random bytes on entropy
+			 * leak. Do it here, after we have swapped leak queues, so it gets handled
+			 * with the next entropy leak event.
+			 */
+			do_fill_on_leak_request(vi, vq, &vi->leak_data, sizeof(vi->leak_data));
+		} else if (buffer == &vi->epoch_notifier.epoch->data) {
+			/* Also, ensure we always have a pending request for bumping the epoch */
+			prepare_next_epoch(vi, leakq);
+			do_copy_on_leak_request(vi, vq, &vi->epoch_notifier.epoch->data,
+					&leakq->next_epoch, sizeof(leakq->next_epoch));
+		}
+	}
+}
+
 static void random_recv_done(struct virtqueue *vq)
 {
 	struct virtrng_info *vi = vq->vdev->priv;
@@ -126,6 +250,51 @@ static void virtio_cleanup(struct hwrng *rng)
 	complete(&vi->have_data);
 }
 
+static int init_virtqueues(struct virtrng_info *vi, struct virtio_device *vdev)
+{
+	int ret, vqs_nr = 1;
+	struct virtqueue *vqs[3];
+	const char *names[3];
+	vq_callback_t *callbacks[3];
+
+	callbacks[0] = random_recv_done;
+	names[0] = "input";
+
+	if (vi->has_leakqs) {
+		vqs_nr = 3;
+		vi->active_leakq = 0;
+
+		/* Register with random.c to get epoch info */
+		ret = rng_register_epoch_notifier(&vi->epoch_notifier);
+		if (ret)
+			goto err_register_epoch;
+
+		callbacks[1] = entropy_leak_detected;
+		names[1] = "leakq.1";
+		callbacks[2] = entropy_leak_detected;
+		names[2] = "leakq.2";
+	}
+
+	ret = virtio_find_vqs(vdev, vqs_nr, vqs, callbacks, names, NULL);
+	if (ret)
+		goto err_find_vqs;
+
+	vi->vq = vqs[0];
+	if (vi->has_leakqs) {
+		vi->leakq[0].vq = vqs[1];
+		vi->leakq[0].next_epoch.data = 1;
+		vi->leakq[1].vq = vqs[2];
+		vi->leakq[1].next_epoch.data = 2;
+	}
+
+	return 0;
+
+err_find_vqs:
+	rng_unregister_epoch_notifier(&vi->epoch_notifier);
+err_register_epoch:
+	return ret;
+}
+
 static int probe_common(struct virtio_device *vdev)
 {
 	int err, index;
@@ -151,18 +320,22 @@ static int probe_common(struct virtio_device *vdev)
 	};
 	vdev->priv = vi;
 
-	/* We expect a single virtqueue. */
-	vi->vq = virtio_find_single_vq(vdev, random_recv_done, "input");
-	if (IS_ERR(vi->vq)) {
-		err = PTR_ERR(vi->vq);
+	vi->has_leakqs = virtio_has_feature(vdev, VIRTIO_RNG_F_LEAK);
+	err = init_virtqueues(vi, vdev);
+	if (err)
 		goto err_find;
-	}
 
 	virtio_device_ready(vdev);
 
 	/* we always have a pending entropy request */
 	request_entropy(vi);
 
+	if (vi->has_leakqs) {
+		/* we always have entropy-leak requests pending */
+		add_entropy_leak_requests(vi, &vi->leakq[0]);
+		add_entropy_leak_requests(vi, &vi->leakq[1]);
+	}
+
 	return 0;
 
 err_find:
@@ -245,7 +418,13 @@ static const struct virtio_device_id id_table[] = {
 	{ 0 },
 };
 
+static unsigned int features[] = {
+	VIRTIO_RNG_F_LEAK,
+};
+
 static struct virtio_driver virtio_rng_driver = {
+	.feature_table = features,
+	.feature_table_size = ARRAY_SIZE(features),
 	.driver.name =	KBUILD_MODNAME,
 	.driver.owner =	THIS_MODULE,
 	.id_table =	id_table,
diff --git a/include/uapi/linux/virtio_rng.h b/include/uapi/linux/virtio_rng.h
index c4d5de896f0c..d9774951547e 100644
--- a/include/uapi/linux/virtio_rng.h
+++ b/include/uapi/linux/virtio_rng.h
@@ -5,4 +5,7 @@
 #include <linux/virtio_ids.h>
 #include <linux/virtio_config.h>
 
+/* The feature bitmap for virtio entropy device */
+#define VIRTIO_RNG_F_LEAK 0
+
 #endif /* _LINUX_VIRTIO_RNG_H */
-- 
2.40.1

Re: [RFC PATCH 0/2] Propagating reseed notifications to user space

[Babis Chalios]

Hello all,

On 23/8/23 11:01, Babis Chalios wrote:
> This is an RFC, so that we can discuss whether the proposed ABI works.
> Also, I'd like to hear people's opinion on the internal registration
> API, 8/24 split etc. If we decide that this approach works, I 'm happy
> to add documentation for it, with examples on how user space can make
> use of it.

Some time has passed since I sent this and I haven't received any 
comments, so I assume people
are happy with the proposed API. I will work on adding documentation and 
examples on how
user space can use this and send a v1.

Cheers,
Babis

Re: [RFC PATCH 0/2] Propagating reseed notifications to user space

[Jason A. Donenfeld]

On Mon, Sep 04, 2023 at 03:44:48PM +0200, Babis Chalios wrote:
> Hello all,
> 
> On 23/8/23 11:01, Babis Chalios wrote:
> > This is an RFC, so that we can discuss whether the proposed ABI works.
> > Also, I'd like to hear people's opinion on the internal registration
> > API, 8/24 split etc. If we decide that this approach works, I 'm happy
> > to add documentation for it, with examples on how user space can make
> > use of it.
> 
> Some time has passed since I sent this and I haven't received any 
> comments, so I assume people

Nope. This still stands:
https://lore.kernel.org/all/CAHmME9pxc-nO_xa=4+1CnvbnuefbRTJHxM7n817c_TPeoxzu_g@mail.gmail.com/

And honestly the constant pushing from you has in part been
demotivating.

Re: [RFC PATCH 0/2] Propagating reseed notifications to user space

[Babis Chalios]

Hi Jason,

On 4/9/23 16:42, Jason A. Donenfeld wrote:
> CAUTION: This email originated from outside of the organization. Do not click links or open attachments unless you can confirm the sender and know the content is safe.
>
>
>
> On Mon, Sep 04, 2023 at 03:44:48PM +0200, Babis Chalios wrote:
>> Hello all,
>>
>> On 23/8/23 11:01, Babis Chalios wrote:
>>> This is an RFC, so that we can discuss whether the proposed ABI works.
>>> Also, I'd like to hear people's opinion on the internal registration
>>> API, 8/24 split etc. If we decide that this approach works, I 'm happy
>>> to add documentation for it, with examples on how user space can make
>>> use of it.
>> Some time has passed since I sent this and I haven't received any
>> comments, so I assume people
> Nope. This still stands:
> https://lore.kernel.org/all/CAHmME9pxc-nO_xa=4+1CnvbnuefbRTJHxM7n817c_TPeoxzu_g@mail.gmail.com/
Could you elaborate on why the proposed RFC is not inline with your 
plan? We need to let user space
know that it needs to reseed its PRNGs. It is not very clear to me, how 
does that interplay with having a
getrandom vDSO.

IOW, say we did have a vDSO getrandom, don't you think we should have 
such an API to notify when it
needs to discard stale state, or do you think this is not the right API?

> And honestly the constant pushing from you has in part been
> demotivating.


Cheers,
Babis

Re: [RFC PATCH 0/2] Propagating reseed notifications to user space

[Alexander Graf]

[Resending in plain text only. Let's hope it reaches everyone this time :)]

Hey Jason!

On 04.09.23 16:42, Jason A. Donenfeld wrote:
> On Mon, Sep 04, 2023 at 03:44:48PM +0200, Babis Chalios wrote:
>> Hello all,
>>
>> On 23/8/23 11:01, Babis Chalios wrote:
>>> This is an RFC, so that we can discuss whether the proposed ABI works.
>>> Also, I'd like to hear people's opinion on the internal registration
>>> API, 8/24 split etc. If we decide that this approach works, I 'm happy
>>> to add documentation for it, with examples on how user space can make
>>> use of it.
>> Some time has passed since I sent this and I haven't received any
>> comments, so I assume people
> Nope. This still stands:
> https://lore.kernel.org/all/CAHmME9pxc-nO_xa=4+1CnvbnuefbRTJHxM7n817c_TPeoxzu_g@mail.gmail.com/


To recap, that email said:

> Just so you guys know, roughly the order of operations here are going to be:
>
> - vdso vgetrandom v+1
> - virtio fork driver
> - exposing fork events to userspace
>
> I'll keep you posted on those.

I don't quite understand both the relationship of vgetrandom to this nor 
how we could help. I understand how a VDSO vgetrandom could use 
primitives that are very similar (or maybe even identical) to this patch 
set.

What I'm missing is why there is a dependency between them. I don't 
expect user space PRNGs to disappear over night, especially given all 
the heavy lifting and architecture specific code that vDSOs require. So 
if we want to build a solution that allows user space to generically 
solve VM snapshots, we should strive to have a mechanism that works in 
today's environment in addition to making the vgetrandom call safe when 
it emerges.

The last revision of vgetrandom that I found was v14 from January. Is it 
still in active development? And if so, what is the status? The last 
fundamental comment I found in archives was this comment from Linus:


> This should all be in libc. Not in the kernel with special magic vdso
> support and special buffer allocations. The kernel should give good
> enough support that libc can do a good job, but the kernel should
> simply *not* take the approach of "libc will get this wrong, so let's
> just do all the work for it".

to which you replied

> That buffering cannot be done safely currently -- VM forks, reseeding
> semantics, and so forth. Again, discussed in the cover letter of the
> patch if you'd like to engage with those ideas.

My understanding is that this patch set solves exactly that problem in a 
way that is fully compatible with existing user space PRNGs and easy to 
consume as well as add support for in "Enterprise" systems for anyone 
who wishes to do so.

So, where is v15 without VM changes standing? And why exactly should we 
couple vgetrandom with atomic user space reseed notifications? :)


Thanks,

Alex




Amazon Development Center Germany GmbH
Krausenstr. 38
10117 Berlin
Geschaeftsfuehrung: Christian Schlaeger, Jonathan Weiss
Eingetragen am Amtsgericht Charlottenburg unter HRB 149173 B
Sitz: Berlin
Ust-ID: DE 289 237 879

Re: [RFC PATCH 0/2] Propagating reseed notifications to user space

[Yann Droneaud]

Hi,

Le 23/08/2023 à 11:01, Babis Chalios a écrit :
> User space often implements PRNGs that use /dev/random as entropy
> source. We can not expect that this randomness sources stay completely
> unknown forever. For various reasons, the originating PRNG seed may
> become known at which point the PRNG becomes insecure for further random
> number generation. Events that can lead to that are for example fast
> computers reversing the PRNG function using a number of inputs or
> Virtual Machine clones which carry seed values into their clones.
>
> During LPC 2022 Jason, Alex, Michael and me brainstormed on how to
> atomically expose a notification to user space that it should reseed.
> Atomicity is key for the VM clone case. This patchset implements a
> potential path to do so.
>
> This patchset introduces an epoch value as the means of communicating to
> the guest the need to reseed. The epoch is a 32bit value with the
> following form:
>
>                RNG epoch
> *-------------*---------------------*
> | notifier id | epoch counter value |
> *-------------*---------------------*
>       8 bits           24 bits
>
> Changes in this value signal moments in time that PRNGs need to be
> re-seeded. As a result, the intended use of the epoch from user space
> PRNGs is to cache the epoch value every time they reseed using kernel
> entropy, then control that its value hasn't changed before giving out
> random numbers. If the value has changed the PRNG needs to reseed before
> producing any more random bits.
>
> The API for getting hold of this value is offered through
> /dev/(u)random. We introduce a new ioctl for these devices, which
> creates an anonymous file descriptor. User processes can call the
> ioctl() to get the anon fd and then mmap it to a single page. That page
> contains the value of the epoch at offset 0.
>
> Naturally, random.c is the component that maintains the RNG epoch.
> During initialization it allocates a single global page which holds the
> epoch value. Moreover, it exposes an API to kernel subsystems
> (notifiers) which can report events that require PRNG reseeding.
> Notifiers register with random.c and receive an 8-bit notifier id (up to
> 256 subscribers should be enough) and a pointer to the epoch. Notifying,
> then, is equivalent to writing in the epoch address a new epoch value.
>
> Notifiers write epoch values that include the notifier ID on the higher
> 8 bits and increasing counter values on the 24 remaining bits. This
> guarantees that two notifiers cannot ever write the same epoch value,
> since notificator IDs are unique.
>
> The first patch of this series implements the epoch mechanism. It adds
> the logic in the random.c to maintain the epoch page and expose the
> user space facing API. It also adds the internal API that allows kernel
> systems to register as notifiers.

 From userspace point of view, having to open /dev/random, ioctl, and mmap()
is a no-go for a (CS)PRNG embedded in libc for arc4random().

I'm biased, as I proposed to expose such seed epoch value to userspace through
getrandom() directly, relying on vDSO for reasonable performances, because
current's glibc arc4random() is somewhat to slow to be a general replacement
rand().

See
https://lore.kernel.org/all/cover.1673539719.git.ydroneaud@opteya.com/
https://lore.kernel.org/all/ae35afa5b824dc76c5ded98efcabc117e6dd3d70@opteya.com/

Reards.

-- 
Yann Droneaud

Re: [RFC PATCH 0/2] Propagating reseed notifications to user space

[Alexander Graf]

Hey Yann!

On 17.09.23 15:34, Yann Droneaud wrote:
>
> Hi,
>
> Le 23/08/2023 à 11:01, Babis Chalios a écrit :
>> User space often implements PRNGs that use /dev/random as entropy
>> source. We can not expect that this randomness sources stay completely
>> unknown forever. For various reasons, the originating PRNG seed may
>> become known at which point the PRNG becomes insecure for further random
>> number generation. Events that can lead to that are for example fast
>> computers reversing the PRNG function using a number of inputs or
>> Virtual Machine clones which carry seed values into their clones.
>>
>> During LPC 2022 Jason, Alex, Michael and me brainstormed on how to
>> atomically expose a notification to user space that it should reseed.
>> Atomicity is key for the VM clone case. This patchset implements a
>> potential path to do so.
>>
>> This patchset introduces an epoch value as the means of communicating to
>> the guest the need to reseed. The epoch is a 32bit value with the
>> following form:
>>
>>                RNG epoch
>> *-------------*---------------------*
>> | notifier id | epoch counter value |
>> *-------------*---------------------*
>>       8 bits           24 bits
>>
>> Changes in this value signal moments in time that PRNGs need to be
>> re-seeded. As a result, the intended use of the epoch from user space
>> PRNGs is to cache the epoch value every time they reseed using kernel
>> entropy, then control that its value hasn't changed before giving out
>> random numbers. If the value has changed the PRNG needs to reseed before
>> producing any more random bits.
>>
>> The API for getting hold of this value is offered through
>> /dev/(u)random. We introduce a new ioctl for these devices, which
>> creates an anonymous file descriptor. User processes can call the
>> ioctl() to get the anon fd and then mmap it to a single page. That page
>> contains the value of the epoch at offset 0.
>>
>> Naturally, random.c is the component that maintains the RNG epoch.
>> During initialization it allocates a single global page which holds the
>> epoch value. Moreover, it exposes an API to kernel subsystems
>> (notifiers) which can report events that require PRNG reseeding.
>> Notifiers register with random.c and receive an 8-bit notifier id (up to
>> 256 subscribers should be enough) and a pointer to the epoch. Notifying,
>> then, is equivalent to writing in the epoch address a new epoch value.
>>
>> Notifiers write epoch values that include the notifier ID on the higher
>> 8 bits and increasing counter values on the 24 remaining bits. This
>> guarantees that two notifiers cannot ever write the same epoch value,
>> since notificator IDs are unique.
>>
>> The first patch of this series implements the epoch mechanism. It adds
>> the logic in the random.c to maintain the epoch page and expose the
>> user space facing API. It also adds the internal API that allows kernel
>> systems to register as notifiers.
>
> From userspace point of view, having to open /dev/random, ioctl, and 
> mmap()
> is a no-go for a (CS)PRNG embedded in libc for arc4random().


Could you please elaborate on why it's a no-go? With any approach we 
take, someone somewhere needs to map and expose data to user space that 
we are in a new "epoch". With this patch set, you do that explicitly 
from user space through an fd that you keep open plus an mmap that you 
keep active. With vgetrandom, the kernel does it implicitly for you.

So with this patch set's approach, the first call to arc4random() would 
need to establish the epoch mmap and leave it open. After that epoch 
handling is (almost) free - it's just a 32bit value compare.

Are you saying that there is a problem with keeping track of that 
additional state? As mentioned above, we need to keep track of some 
state somewhere: Either in the vdso plus kernel page map logic or in the 
library that consumes epochs.

If this is the problem, maybe the fundamental issue is that arc4random() 
assumes you always have everything in place to receive randomness 
without a handle that could go through an open/close (init/destroy) 
cycle? I suppose you could change that?

> I'm biased, as I proposed to expose such seed epoch value to userspace 
> through
> getrandom() directly, relying on vDSO for reasonable performances, 
> because
> current's glibc arc4random() is somewhat to slow to be a general 
> replacement
> rand().
>
> See
> https://lore.kernel.org/all/cover.1673539719.git.ydroneaud@opteya.com/
> https://lore.kernel.org/all/ae35afa5b824dc76c5ded98efcabc117e6dd3d70@opteya.com/ 
>


There are more problems with coupling epochs to the vgetrandom approach: 
Not everyone will want to or can use Linux's rng as the sole source of 
entropy for various reasons (NIST, FIPS, TLS recommendations to not rely 
on a single source, real time requirements, etc) but still require 
knowledge of epoch changes.

That means we need an alternative path for these applications 
regardless. May as well start with that :). If we then still conclude 
that vgetrandom is the best path forward to accelerate access to 
/dev/urandom in user space, we can just always map this patch set's 
epoch page into the vDSO range and then make vgetrandom consume it, 
similar to how a user space library would.

I genuinely don't understand how vgetrandom and this patch set 
contradict each other.


Alex




Amazon Development Center Germany GmbH
Krausenstr. 38
10117 Berlin
Geschaeftsfuehrung: Christian Schlaeger, Jonathan Weiss
Eingetragen am Amtsgericht Charlottenburg unter HRB 149173 B
Sitz: Berlin
Ust-ID: DE 289 237 879