| Message ID | 20220223131231.403386-2-Jason@zx2c4.com (mailing list archive) |
|---|---|
| State | Not Applicable |
| Delegated to: | Herbert Xu |
| Headers | show |
| Series | VM fork detection for RNG | expand |
On Wed, Feb 23, 2022 at 02:12:30PM +0100, Jason A. Donenfeld wrote: > When a VM forks, we must immediately mix in additional information to > the stream of random output so that two forks or a rollback don't > produce the same stream of random numbers, which could have catastrophic > cryptographic consequences. This commit adds a simple API, add_vmfork_ > randomness(), for that. > > Cc: Theodore Ts'o <tytso@mit.edu> > Cc: Jann Horn <jannh@google.com> > Signed-off-by: Jason A. Donenfeld <Jason@zx2c4.com> > --- > drivers/char/random.c | 58 ++++++++++++++++++++++++++++++++++++++++++ > include/linux/random.h | 1 + > 2 files changed, 59 insertions(+) > > diff --git a/drivers/char/random.c b/drivers/char/random.c > index 536237a0f073..29d6ce484d15 100644 > --- a/drivers/char/random.c > +++ b/drivers/char/random.c > @@ -344,6 +344,46 @@ static void crng_reseed(void) > } > } > > +/* > + * This mixes unique_vm_id directly into the base_crng key as soon as > + * possible, similarly to crng_pre_init_inject(), even if the crng is > + * already running, in order to immediately branch streams from prior > + * VM instances. > + */ > +static void crng_vm_fork_inject(const void *unique_vm_id, size_t len) > +{ > + unsigned long flags, next_gen; > + struct blake2s_state hash; > + > + /* > + * Unlike crng_reseed(), we take the lock as early as possible, > + * since we don't want the RNG to be used until it's updated. > + */ > + spin_lock_irqsave(&base_crng.lock, flags); > + > + /* > + * Also update the generation, while locked, as early as > + * possible. This will mean unlocked reads of the generation > + * will cause a reseeding of per-cpu crngs, and those will > + * spin on the base_crng lock waiting for the rest of this > + * operation to complete, which achieves the goal of blocking > + * the production of new output until this is done. > + */ > + next_gen = base_crng.generation + 1; > + if (next_gen == ULONG_MAX) > + ++next_gen; > + WRITE_ONCE(base_crng.generation, next_gen); > + WRITE_ONCE(base_crng.birth, jiffies); > + > + /* This is the same formulation used by crng_pre_init_inject(). */ > + blake2s_init(&hash, sizeof(base_crng.key)); > + blake2s_update(&hash, base_crng.key, sizeof(base_crng.key)); > + blake2s_update(&hash, unique_vm_id, len); > + blake2s_final(&hash, base_crng.key); > + > + spin_unlock_irqrestore(&base_crng.lock, flags); > +} [...] > +/* > + * Handle a new unique VM ID, which is unique, not secret, so we > + * don't credit it, but we do mix it into the entropy pool and > + * inject it into the crng. > + */ > +void add_vmfork_randomness(const void *unique_vm_id, size_t size) > +{ > + add_device_randomness(unique_vm_id, size); > + crng_vm_fork_inject(unique_vm_id, size); > +} > +EXPORT_SYMBOL_GPL(add_vmfork_randomness); I think we should be removing cases where the base_crng key is changed directly besides extraction from the input_pool, not adding new ones. Why not implement this as add_device_randomness() followed by crng_reseed(force=true), where the 'force' argument forces a reseed to occur even if the entropy_count is too low? - Eric
On 2/24/22, Eric Biggers <ebiggers@kernel.org> wrote: > I think we should be removing cases where the base_crng key is changed > directly > besides extraction from the input_pool, not adding new ones. Why not > implement > this as add_device_randomness() followed by crng_reseed(force=true), where > the > 'force' argument forces a reseed to occur even if the entropy_count is too > low? Because that induces a "premature next" condition which can let that entropy, potentially newly acquired by a storm of IRQs at power-on, be bruteforced by unprivileged userspace. I actually had it exactly the way you describe at first, but decided that this here is the lesser of evils and doesn't really complicate things the way an intentional premature next would. The only thing we care about here is branching the crng stream, and so this does explicitly that, without having to interfere with how we collect entropy. Of course we *also* add it as non-credited "device randomness" so that it's part of the next reseeding, whenever that might occur.
On Thu, Feb 24, 2022 at 01:54:54AM +0100, Jason A. Donenfeld wrote: > On 2/24/22, Eric Biggers <ebiggers@kernel.org> wrote: > > I think we should be removing cases where the base_crng key is changed > > directly > > besides extraction from the input_pool, not adding new ones. Why not > > implement > > this as add_device_randomness() followed by crng_reseed(force=true), where > > the > > 'force' argument forces a reseed to occur even if the entropy_count is too > > low? > > Because that induces a "premature next" condition which can let that > entropy, potentially newly acquired by a storm of IRQs at power-on, be > bruteforced by unprivileged userspace. I actually had it exactly the > way you describe at first, but decided that this here is the lesser of > evils and doesn't really complicate things the way an intentional > premature next would. The only thing we care about here is branching > the crng stream, and so this does explicitly that, without having to > interfere with how we collect entropy. Of course we *also* add it as > non-credited "device randomness" so that it's part of the next > reseeding, whenever that might occur. Can you make sure to properly explain this in the code? - Eric
Hey Eric, On Thu, Feb 24, 2022 at 2:27 AM Eric Biggers <ebiggers@kernel.org> wrote: > > On Thu, Feb 24, 2022 at 01:54:54AM +0100, Jason A. Donenfeld wrote: > > On 2/24/22, Eric Biggers <ebiggers@kernel.org> wrote: > > > I think we should be removing cases where the base_crng key is changed > > > directly > > > besides extraction from the input_pool, not adding new ones. Why not > > > implement > > > this as add_device_randomness() followed by crng_reseed(force=true), where > > > the > > > 'force' argument forces a reseed to occur even if the entropy_count is too > > > low? > > > > Because that induces a "premature next" condition which can let that > > entropy, potentially newly acquired by a storm of IRQs at power-on, be > > bruteforced by unprivileged userspace. I actually had it exactly the > > way you describe at first, but decided that this here is the lesser of > > evils and doesn't really complicate things the way an intentional > > premature next would. The only thing we care about here is branching > > the crng stream, and so this does explicitly that, without having to > > interfere with how we collect entropy. Of course we *also* add it as > > non-credited "device randomness" so that it's part of the next > > reseeding, whenever that might occur. > > Can you make sure to properly explain this in the code? The carousel keeps turning, and after I wrote to you last night I kept thinking about the matter. Here's how it breaks down: Injection method: - Assumes existing pool of entropy is still sacred. - Assumes base_crng timestamp is representative of pool age. - Result: Mixes directly into base_crng to avoid premature-next of pool. Input pool method: - Assumes existing pool of entropy is old / out of date / used by a different fork, so not sacred. - Assumes base_crng timestamp is tied to irrelevant entropy pool. - Result: Force-drains input pool, causing intentional premature-next. Which of these assumptions better models the situation? I started in the input pool method camp, then by the time I posted v1, was concerned about power-on IRQs, but now I think relying at all on snapshotted entropy represents the biggest issue. And judging from your email, it appears that you do too. So v3 of this patchset will switch back to the input pool method, per your suggestion. As a plus, it means we go through the RDSEED'd extraction algorithm too, which always helps. Jason
diff --git a/drivers/char/random.c b/drivers/char/random.c index 536237a0f073..29d6ce484d15 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -344,6 +344,46 @@ static void crng_reseed(void) } } +/* + * This mixes unique_vm_id directly into the base_crng key as soon as + * possible, similarly to crng_pre_init_inject(), even if the crng is + * already running, in order to immediately branch streams from prior + * VM instances. + */ +static void crng_vm_fork_inject(const void *unique_vm_id, size_t len) +{ + unsigned long flags, next_gen; + struct blake2s_state hash; + + /* + * Unlike crng_reseed(), we take the lock as early as possible, + * since we don't want the RNG to be used until it's updated. + */ + spin_lock_irqsave(&base_crng.lock, flags); + + /* + * Also update the generation, while locked, as early as + * possible. This will mean unlocked reads of the generation + * will cause a reseeding of per-cpu crngs, and those will + * spin on the base_crng lock waiting for the rest of this + * operation to complete, which achieves the goal of blocking + * the production of new output until this is done. + */ + next_gen = base_crng.generation + 1; + if (next_gen == ULONG_MAX) + ++next_gen; + WRITE_ONCE(base_crng.generation, next_gen); + WRITE_ONCE(base_crng.birth, jiffies); + + /* This is the same formulation used by crng_pre_init_inject(). */ + blake2s_init(&hash, sizeof(base_crng.key)); + blake2s_update(&hash, base_crng.key, sizeof(base_crng.key)); + blake2s_update(&hash, unique_vm_id, len); + blake2s_final(&hash, base_crng.key); + + spin_unlock_irqrestore(&base_crng.lock, flags); +} + /* * This generates a ChaCha block using the provided key, and then * immediately overwites that key with half the block. It returns @@ -935,6 +975,7 @@ static bool drain_entropy(void *buf, size_t nbytes) * void add_hwgenerator_randomness(const void *buffer, size_t count, * size_t entropy); * void add_bootloader_randomness(const void *buf, size_t size); + * void add_vmfork_randomness(const void *unique_vm_id, size_t size); * void add_interrupt_randomness(int irq); * * add_device_randomness() adds data to the input pool that @@ -966,6 +1007,11 @@ static bool drain_entropy(void *buf, size_t nbytes) * add_device_randomness(), depending on whether or not the configuration * option CONFIG_RANDOM_TRUST_BOOTLOADER is set. * + * add_vmfork_randomness() adds a unique (but not neccessarily secret) ID + * representing the current instance of a VM to the pool, without crediting, + * and then immediately mixes that ID into the current base_crng key, so + * that it takes effect prior to a reseeding. + * * add_interrupt_randomness() uses the interrupt timing as random * inputs to the entropy pool. Using the cycle counters and the irq source * as inputs, it feeds the input pool roughly once a second or after 64 @@ -1195,6 +1241,18 @@ void add_bootloader_randomness(const void *buf, size_t size) } EXPORT_SYMBOL_GPL(add_bootloader_randomness); +/* + * Handle a new unique VM ID, which is unique, not secret, so we + * don't credit it, but we do mix it into the entropy pool and + * inject it into the crng. + */ +void add_vmfork_randomness(const void *unique_vm_id, size_t size) +{ + add_device_randomness(unique_vm_id, size); + crng_vm_fork_inject(unique_vm_id, size); +} +EXPORT_SYMBOL_GPL(add_vmfork_randomness); + struct fast_pool { union { u32 pool32[4]; diff --git a/include/linux/random.h b/include/linux/random.h index 6148b8d1ccf3..51b8ed797732 100644 --- a/include/linux/random.h +++ b/include/linux/random.h @@ -34,6 +34,7 @@ extern void add_input_randomness(unsigned int type, unsigned int code, extern void add_interrupt_randomness(int irq) __latent_entropy; extern void add_hwgenerator_randomness(const void *buffer, size_t count, size_t entropy); +extern void add_vmfork_randomness(const void *unique_vm_id, size_t size); extern void get_random_bytes(void *buf, size_t nbytes); extern int wait_for_random_bytes(void);
When a VM forks, we must immediately mix in additional information to the stream of random output so that two forks or a rollback don't produce the same stream of random numbers, which could have catastrophic cryptographic consequences. This commit adds a simple API, add_vmfork_ randomness(), for that. Cc: Theodore Ts'o <tytso@mit.edu> Cc: Jann Horn <jannh@google.com> Signed-off-by: Jason A. Donenfeld <Jason@zx2c4.com> --- drivers/char/random.c | 58 ++++++++++++++++++++++++++++++++++++++++++ include/linux/random.h | 1 + 2 files changed, 59 insertions(+)