random: make try_to_generate_entropy() more robust
A message that is not in the archive (sent off-list or not yet received): 20191018203704.GC31027@cork
Quoted 3 lines · Jörn Engel
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.
Quoted 57 lines
From
90078333edb6e720f13f6668376a69c0f9c570f5Mon Sep 17 00:00:00 2001
From: Joern Engel <[email protected]>
Date: Fri, 18 Oct 2019 13:25:52 -0700
Subject: [PATCH] random: maketry_to_generate_entropy()more robustWe 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 <[email protected]>--- drivers/char/random.c | 15 ++++++++++++--- 1 file changed, 12 insertions(+), 3 deletions(-)drivers/char/random.c +12
-3@@ -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 ()) {Signature · 1 line
2.20.1
Jörn
--
...one more straw can't possibly matter...
-- Kirby Bakken
Quoted 4 lines · Jörn Engel
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
Quoted 9 lines · Jörn Engel
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)
{
Review
Quoted 10 lines
(quoted diff) +10
-0+ 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
Quoted 33 lines · Linus Torvalds
Quoted 9 lines · Jörn Engel
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)
{Review
Quoted 10 lines
(quoted diff) +10
-0+ 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 softirqTIMER_SOFTIRQcontext, 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 thisget_irq_regs()usage.
Quoted 5 lines
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
Quoted 10 lines · Ingo Molnar
Quoted 1 line · Linus Torvalds
On Fri, Oct 18, 2019 at 4:42 PM Jörn Engel <[email protected]> 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:
Quoted 5 lines
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
Quoted 33 lines · Linus Torvalds
Quoted 9 lines · Jörn Engel
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)
{Review
Quoted 10 lines
(quoted diff) +10
-0+ 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 softirqTIMER_SOFTIRQcontext, 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 thisget_irq_regs()usage.
Quoted 5 lines
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
Quoted 11 lines · Thomas Gleixner
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.
Quoted 6 lines
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.
Quoted 3 lines
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