Re: [PATCH] random: make try_to_generate_entropy() more robust

Re: [PATCH] random: make try_to_generate_entropy() more robust

[Jörn Engel]

On Fri, Oct 18, 2019 at 01:37:04PM -0700, Jörn Engel wrote:
> Sorry for coming late to the discussion.  I generally like the approach
> in try_to_generate_entropy(), but I think we can do a little better
> still.  Would something like this work?

Fixed lkml address.

> From 90078333edb6e720f13f6668376a69c0f9c570f5 Mon Sep 17 00:00:00 2001
> From: Joern Engel <joern@purestorage.com>
> Date: Fri, 18 Oct 2019 13:25:52 -0700
> Subject: [PATCH] random: make try_to_generate_entropy() more robust
> 
> We can generate entropy on almost any CPU, even if it doesn't provide a
> high-resolution timer for random_get_entropy().  As long as the CPU is
> not idle, it changed the register file every few cycles.  As long as the
> ALU isn't fully synchronized with the timer, the drift between the
> register file and the timer is enough to generate entropy from.
> 
> Also print a warning on systems where entropy collection might be a
> problem.  I have good confidence in two unsynchronized timers generating
> entropy.  But I cannot tell whether timer and ALU are synchronized and
> we ought to warn users if all their crypto is likely to be broken.
> 
> Signed-off-by: Joern Engel <joern@purestorage.com>
> ---
>  drivers/char/random.c | 15 ++++++++++++---
>  1 file changed, 12 insertions(+), 3 deletions(-)
> 
> diff --git a/drivers/char/random.c b/drivers/char/random.c
> index de434feb873a..00a04efd0686 100644
> --- a/drivers/char/random.c
> +++ b/drivers/char/random.c
> @@ -1748,6 +1748,16 @@ EXPORT_SYMBOL(get_random_bytes);
>   */
>  static void entropy_timer(struct timer_list *t)
>  {
> +	struct pt_regs *regs = get_irq_regs();
> +
> +	/*
> +	 * Even if we don't have a high-resolution timer in our system,
> +	 * the register file itself is a high-resolution timer.  It
> +	 * isn't monotonic or particularly useful to read the current
> +	 * time.  But it changes with every retired instruction, which
> +	 * is enough to generate entropy from.
> +	 */
> +	mix_pool_bytes(&input_pool, regs, sizeof(*regs));
>  	credit_entropy_bits(&input_pool, 1);
>  }
>  
> @@ -1764,9 +1774,8 @@ static void try_to_generate_entropy(void)
>  
>  	stack.now = random_get_entropy();
>  
> -	/* Slow counter - or none. Don't even bother */
> -	if (stack.now == random_get_entropy())
> -		return;
> +	/* Slow counter - or none.  Warn user */
> +	WARN_ON(stack.now == random_get_entropy());
>  
>  	timer_setup_on_stack(&stack.timer, entropy_timer, 0);
>  	while (!crng_ready()) {
> -- 
> 2.20.1
> 

Jörn

--
...one more straw can't possibly matter...
-- Kirby Bakken

Re: [PATCH] random: make try_to_generate_entropy() more robust

[Linus Torvalds]

On Fri, Oct 18, 2019 at 4:42 PM Jörn Engel <joern@purestorage.com> wrote:
>
> Sorry for coming late to the discussion.  I generally like the approach
> in try_to_generate_entropy(), but I think we can do a little better
> still.  Would something like this work?

Hmm. I'm not convinced that the register set is all that random in
general if you have attackers (or - in the absence of an attack - if
it hits in the idle loop a lot), but I do like it for this particular
use where we have that timeout while doing entropy work.

So I think this is potentially a good way to at least improve on the
situation when there is no TSC. Which would remove one worry about
getrandom() on other platforms than the usual development ones.

I'm on a plane at 38,933 ft right now according to the flight tracker,
and about to lose internet access again, but I like it and will take
another look when I'm on the ground and at a hotel.

              Linus

Re: [PATCH] random: make try_to_generate_entropy() more robust

[Linus Torvalds]

On Fri, Oct 18, 2019 at 4:42 PM Jörn Engel <joern@purestorage.com> wrote:
>
> We can generate entropy on almost any CPU, even if it doesn't provide a
> high-resolution timer for random_get_entropy().  As long as the CPU is
> not idle, it changed the register file every few cycles.  As long as the
> ALU isn't fully synchronized with the timer, the drift between the
> register file and the timer is enough to generate entropy from.

>  static void entropy_timer(struct timer_list *t)
>  {
> +     struct pt_regs *regs = get_irq_regs();
> +
> +     /*
> +      * Even if we don't have a high-resolution timer in our system,
> +      * the register file itself is a high-resolution timer.  It
> +      * isn't monotonic or particularly useful to read the current
> +      * time.  But it changes with every retired instruction, which
> +      * is enough to generate entropy from.
> +      */
> +     mix_pool_bytes(&input_pool, regs, sizeof(*regs));

Ok, so I still like this conceptually, but I'm not entirely sure that
get_irq_regs() works reliably in a timer. It's done from softirq
TIMER_SOFTIRQ context, so not necessarily _in_ an interrupt.

Now, admittedly this code doesn't really need "reliably". The odd
occasional hickup would arguably just add more noise. And I think the
code works fine. get_irq_regs() will return a pointer to the last
interrupt or exception frame on the current CPU, and I guess it's all
fine. But let's bring in Thomas, who was not only active in the
randomness discussion, but might also have stronger opinions on this
get_irq_regs() usage.

Thomas, opinions? Using the register state (while we're doing the
whole entropy load with scheduling etc) looks like a good source of
high-entropy data outside of just the TSC, so it does seem like a very
valid model. But I want to run it past more people first, and Thomas
is the obvious victim^Wchoice.

              Linus

Re: [PATCH] random: make try_to_generate_entropy() more robust

[Ingo Molnar]

* Linus Torvalds <torvalds@linux-foundation.org> wrote:

> On Fri, Oct 18, 2019 at 4:42 PM Jörn Engel <joern@purestorage.com> wrote:
> >
> > We can generate entropy on almost any CPU, even if it doesn't provide a
> > high-resolution timer for random_get_entropy().  As long as the CPU is
> > not idle, it changed the register file every few cycles.  As long as the
> > ALU isn't fully synchronized with the timer, the drift between the
> > register file and the timer is enough to generate entropy from.
> 
> >  static void entropy_timer(struct timer_list *t)
> >  {
> > +     struct pt_regs *regs = get_irq_regs();
> > +
> > +     /*
> > +      * Even if we don't have a high-resolution timer in our system,
> > +      * the register file itself is a high-resolution timer.  It
> > +      * isn't monotonic or particularly useful to read the current
> > +      * time.  But it changes with every retired instruction, which
> > +      * is enough to generate entropy from.
> > +      */
> > +     mix_pool_bytes(&input_pool, regs, sizeof(*regs));
> 
> Ok, so I still like this conceptually, but I'm not entirely sure that
> get_irq_regs() works reliably in a timer. It's done from softirq
> TIMER_SOFTIRQ context, so not necessarily _in_ an interrupt.
> 
> Now, admittedly this code doesn't really need "reliably". The odd
> occasional hickup would arguably just add more noise. And I think the
> code works fine. get_irq_regs() will return a pointer to the last
> interrupt or exception frame on the current CPU, and I guess it's all
> fine. But let's bring in Thomas, who was not only active in the
> randomness discussion, but might also have stronger opinions on this
> get_irq_regs() usage.
> 
> Thomas, opinions? Using the register state (while we're doing the
> whole entropy load with scheduling etc) looks like a good source of
> high-entropy data outside of just the TSC, so it does seem like a very
> valid model. But I want to run it past more people first, and Thomas
> is the obvious victim^Wchoice.

Not Thomas, but one potential problem I can see is that our 
set_irq_regs() use (on x86) is fundamentally nested, we restore whatever 
context we interrupt:

  dagon:~/tip> git grep set_irq_regs arch/x86
  arch/x86/include/asm/irq_regs.h:static inline struct pt_regs *set_irq_regs(struct pt_regs *new_regs)
  arch/x86/kernel/apic/apic.c:    struct pt_regs *old_regs = set_irq_regs(regs);
  arch/x86/kernel/apic/apic.c:    set_irq_regs(old_regs);
  arch/x86/kernel/cpu/acrn.c:     struct pt_regs *old_regs = set_irq_regs(regs);
  arch/x86/kernel/cpu/acrn.c:     set_irq_regs(old_regs);
  arch/x86/kernel/cpu/mshyperv.c: struct pt_regs *old_regs = set_irq_regs(regs);
  arch/x86/kernel/cpu/mshyperv.c: set_irq_regs(old_regs);
  arch/x86/kernel/cpu/mshyperv.c: struct pt_regs *old_regs = set_irq_regs(regs);
  arch/x86/kernel/cpu/mshyperv.c: set_irq_regs(old_regs);
  arch/x86/kernel/irq.c:  struct pt_regs *old_regs = set_irq_regs(regs);
  arch/x86/kernel/irq.c:  set_irq_regs(old_regs);
  arch/x86/kernel/irq.c:  struct pt_regs *old_regs = set_irq_regs(regs);
  arch/x86/kernel/irq.c:  set_irq_regs(old_regs);
  arch/x86/kernel/irq.c:  struct pt_regs *old_regs = set_irq_regs(regs);
  arch/x86/kernel/irq.c:  set_irq_regs(old_regs);
  arch/x86/kernel/irq.c:  struct pt_regs *old_regs = set_irq_regs(regs);
  arch/x86/kernel/irq.c:  set_irq_regs(old_regs);
  arch/x86/kernel/irq.c:  struct pt_regs *old_regs = set_irq_regs(regs);
  arch/x86/kernel/irq.c:  set_irq_regs(old_regs);

But from a softirq or threaded irq context that 'interrupted' regs 
context might potentially be NULL.

NULL isn't a good thing to pass to mix_pool_bytes(), because the first 
use of 'in' (='bytes') in _mix_pool_bytes() is a dereference without a 
NULL check AFAICS:

                w = rol32(*bytes++, input_rotate);

So at minimum I'd only mix this entropy into the pool if 'regs' is 
non-zero. This would automatically do the right thing and not crash the 
kernel on weird irq execution models such as threaded-only or -rt.

If irq-regs _is_ set, then I think we can generally rely on it to either 
be a valid regs pointer or NULL, inside an IRQ handler execution 
instance.

( Furthermore, if we are mixing in regs, then we might as well mix in a 
  few bytes of the interrupted stack as well if it's a kernel stack, 
  which would normally carry quite a bit of variation as well (such as 
  return addresses). Often it has more entropy than just register 
  contents, and it's also cache-hot, so a cheap source of entropy. But 
  that would require a second mix_pool_bytes() call and further 
  examination. Such an approach too would obviously require a non-NULL 
  'regs' pointer. :-) ]

Thanks,

	Ingo

Re: [PATCH] random: make try_to_generate_entropy() more robust

[Thomas Gleixner]

[-- Attachment #1: Type: text/plain, Size: 883 bytes --]

On Sat, 19 Oct 2019, Ingo Molnar wrote:
> * Linus Torvalds <torvalds@linux-foundation.org> wrote:
> > On Fri, Oct 18, 2019 at 4:42 PM Jörn Engel <joern@purestorage.com> wrote:
> 
> But from a softirq or threaded irq context that 'interrupted' regs 
> context might potentially be NULL.
> 
> NULL isn't a good thing to pass to mix_pool_bytes(), because the first 
> use of 'in' (='bytes') in _mix_pool_bytes() is a dereference without a 
> NULL check AFAICS:
> 
>                 w = rol32(*bytes++, input_rotate);
> 
> So at minimum I'd only mix this entropy into the pool if 'regs' is 
> non-zero. This would automatically do the right thing and not crash the 
> kernel on weird irq execution models such as threaded-only or -rt.

You don't even need threaded-only or RT. The timer is fired in the softirq
which very well can happen from thread context in mainline.

Thanks,

	tglx

Re: [PATCH] random: make try_to_generate_entropy() more robust

[Thomas Gleixner]

[-- Attachment #1: Type: text/plain, Size: 3155 bytes --]

On Fri, 18 Oct 2019, Linus Torvalds wrote:
> On Fri, Oct 18, 2019 at 4:42 PM Jörn Engel <joern@purestorage.com> wrote:
> >
> > We can generate entropy on almost any CPU, even if it doesn't provide a
> > high-resolution timer for random_get_entropy().  As long as the CPU is
> > not idle, it changed the register file every few cycles.  As long as the
> > ALU isn't fully synchronized with the timer, the drift between the
> > register file and the timer is enough to generate entropy from.
> 
> >  static void entropy_timer(struct timer_list *t)
> >  {
> > +     struct pt_regs *regs = get_irq_regs();
> > +
> > +     /*
> > +      * Even if we don't have a high-resolution timer in our system,
> > +      * the register file itself is a high-resolution timer.  It
> > +      * isn't monotonic or particularly useful to read the current
> > +      * time.  But it changes with every retired instruction, which
> > +      * is enough to generate entropy from.
> > +      */
> > +     mix_pool_bytes(&input_pool, regs, sizeof(*regs));
> 
> Ok, so I still like this conceptually, but I'm not entirely sure that
> get_irq_regs() works reliably in a timer. It's done from softirq
> TIMER_SOFTIRQ context, so not necessarily _in_ an interrupt.
> 
> Now, admittedly this code doesn't really need "reliably". The odd
> occasional hickup would arguably just add more noise. And I think the
> code works fine. get_irq_regs() will return a pointer to the last
> interrupt or exception frame on the current CPU, and I guess it's all
> fine. But let's bring in Thomas, who was not only active in the
> randomness discussion, but might also have stronger opinions on this
> get_irq_regs() usage.
> 
> Thomas, opinions? Using the register state (while we're doing the
> whole entropy load with scheduling etc) looks like a good source of
> high-entropy data outside of just the TSC, so it does seem like a very
> valid model. But I want to run it past more people first, and Thomas
> is the obvious victim^Wchoice.

The idea is good, but as Ingo pointed out this needs very careful checking
of 'regs'. get_irq_regs() is really only valid from interrupt context up to
the point where the old irq regs (default NULL) are restored, i.e. after
irq_exit() from where softirqs are invoked.

One slightly related thing I was looking into is that the mixing of
interrupt entropy is always done from hard interrupt context. That has a
few issues:

    1) It's pretty visible in profiles for high frequency interrupt
       scenarios.

    2) The regs content can be pretty boring non-deterministic when the
       interrupt hits idle.

       Not an issue in the try_to_generate_entropy() case probably, but
       that still needs some careful investigation.

For #1 I was looking into a trivial storage model with a per cpu ring
buffer, where each entry contains the entropy data of one interrupt and let
some thread or whatever handle the mixing later.

That would allow to filter out 'constant' data (#) but it would also give
Joerns approach a way to get to some 'random' register content independent
of the context in which the timer softirq is running in.

Thanks,

	tglx

Re: [PATCH] random: make try_to_generate_entropy() more robust

[Jörn Engel]

On Sat, Oct 19, 2019 at 12:49:52PM +0200, Thomas Gleixner wrote:
> 
> One slightly related thing I was looking into is that the mixing of
> interrupt entropy is always done from hard interrupt context. That has a
> few issues:
> 
>     1) It's pretty visible in profiles for high frequency interrupt
>        scenarios.
> 
>     2) The regs content can be pretty boring non-deterministic when the
>        interrupt hits idle.
> 
>        Not an issue in the try_to_generate_entropy() case probably, but
>        that still needs some careful investigation.
> 
> For #1 I was looking into a trivial storage model with a per cpu ring
> buffer, where each entry contains the entropy data of one interrupt and let
> some thread or whatever handle the mixing later.

Or you can sum up all regs.

unsigned long regsum(struct pt_regs *regs)
{
	unsigned long *r = (void *)regs;
	unsigned long sum = r[0];
	int i;

	for (i = 1; i < sizeof(*regs) / sizeof(*r); i++) {
		sum += r[i];
	}
	return sum;
}

Takes 1 cycle per register in the current form, half as much if the
compiler can be convinced to unroll the loop.  That's cheaper than
rdtsc() on most/all CPUs.

If interrupt volume is high, the regsum should be good enough.  The
final mixing can be amortized as well.  Once the pool is initialized,
you can mix new entropy once per jiffy or so and otherwise just add to a
percpu counter or something like that.

> That would allow to filter out 'constant' data (#) but it would also give
> Joerns approach a way to get to some 'random' register content independent
> of the context in which the timer softirq is running in.

Jörn

--
Given two functions foo_safe() and foo_fast(), the shorthand foo()
should be an alias for foo_safe(), never foo_fast().
-- me