Currently, we do the jitter dance if two consecutive reads to the cycle
counter return different values. If they do, then we consider the cycle
counter to be fast enough that one trip through the scheduler will yield
one "bit" of credited entropy. If those two reads return the same value,
then we assume the cycle counter is too slow to show meaningful
differences.
This methodology is flawed for a variety of reasons, one of which Eric
posted a patch to fix in [1]. The issue that patch solves is that on a
system with a slow counter, you might be [un]lucky and read the counter
_just_ before it changes, so that the second cycle counter you read
differs from the first, even though there's usually quite a large period
of time in between the two. For example:
| real time | cycle counter |
| --------- | ------------- |
| 3 | 5 |
| 4 | 5 |
| 5 | 5 |
| 6 | 5 |
| 7 | 5 | <--- a
| 8 | 6 | <--- b
| 9 | 6 | <--- c
If we read the counter at (a) and compare it to (b), we might be fooled
into thinking that it's a fast counter, when in reality it is not. The
solution in [1] is to also compare counter (b) to counter (c), on the
theory that if the counter is _actually_ slow, and (a)!=(b), then
certainly (b)==(c).
This helps solve this particular issue, in one sense, but in another
sense, it mostly functions to disallow jitter entropy on these systems,
rather than simply taking more samples in that case.
Instead, this patch takes a different approach. Right now we assume that
a difference in one set of consecutive samples means one "bit" of
credited entropy per scheduler trip. We can extend this so that a
difference in two sets of consecutive samples means one "bit" of
credited entropy per /two/ scheduler trips, and three for three, and
four for four. In other words, we can increase the amount of jitter
"work" we require for each "bit", depending on how slow the cycle
counter is.
So this patch takes whole bunch of samples, sees how many of them are
different, and divides to find the amount of work required per "bit",
and also requires that at least some minimum of them are different in
order to attempt any jitter entropy.
Note that this approach is still far from perfect. It's not a real
statistical estimate on how much these samples vary; it's not a
real-time analysis of the relevant input data. That remains a project
for another time. However, it does the same (partly flawed) assumptions
as the code that's there now, so it's probably not worse than the status
quo, and it handles the issue Eric mentioned in [1]. But, again, it's
probably a far cry from whatever a really robust version of this would
be.
[1] https://lore.kernel.org/lkml/[email protected]/
https://lore.kernel.org/lkml/[email protected]/
Cc: Eric Biggers <[email protected]>
Cc: Theodore Ts'o <[email protected]>
Cc: Linus Torvalds <[email protected]>
Signed-off-by: Jason A. Donenfeld <[email protected]>
---
This is an argument very much centered around the somewhat low bar of
being "not worse than before". If you can think of ways that it doesn't
even manage to clear that, please do pipe up.
drivers/char/random.c | 36 ++++++++++++++++++++++++++----------
1 file changed, 26 insertions(+), 10 deletions(-)
diff --git a/drivers/char/random.c b/drivers/char/random.c
index bf89c6f27a19..94a2ddb53662 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -1354,6 +1354,12 @@ void add_interrupt_randomness(int irq)
}
EXPORT_SYMBOL_GPL(add_interrupt_randomness);
+struct entropy_timer_state {
+ unsigned long entropy;
+ struct timer_list timer;
+ unsigned int samples, samples_per_bit;
+};
+
/*
* Each time the timer fires, we expect that we got an unpredictable
* jump in the cycle counter. Even if the timer is running on another
@@ -1367,9 +1373,14 @@ EXPORT_SYMBOL_GPL(add_interrupt_randomness);
*
* So the re-arming always happens in the entropy loop itself.
*/
-static void entropy_timer(struct timer_list *t)
+static void entropy_timer(struct timer_list *timer)
{
- credit_entropy_bits(1);
+ struct entropy_timer_state *state = container_of(timer, struct entropy_timer_state, timer);
+
+ if (++state->samples == state->samples_per_bit) {
+ credit_entropy_bits(1);
+ state->samples = 0;
+ }
}
/*
@@ -1378,17 +1389,22 @@ static void entropy_timer(struct timer_list *t)
*/
static void try_to_generate_entropy(void)
{
- struct {
- unsigned long entropy;
- struct timer_list timer;
- } stack;
-
- stack.entropy = random_get_entropy();
+ enum { NUM_TRIAL_SAMPLES = 8192, MAX_SAMPLES_PER_BIT = 256 };
+ struct entropy_timer_state stack;
+ unsigned int i, num_different = 0;
+ unsigned long last = random_get_entropy();
- /* Slow counter - or none. Don't even bother */
- if (stack.entropy == random_get_entropy())
+ for (i = 0; i < NUM_TRIAL_SAMPLES - 1; ++i) {
+ stack.entropy = random_get_entropy();
+ if (stack.entropy != last)
+ ++num_different;
+ last = stack.entropy;
+ }
+ stack.samples_per_bit = DIV_ROUND_UP(NUM_TRIAL_SAMPLES, num_different + 1);
+ if (stack.samples_per_bit > MAX_SAMPLES_PER_BIT)
return;
+ stack.samples = 0;
timer_setup_on_stack(&stack.timer, entropy_timer, 0);
while (!crng_ready() && !signal_pending(current)) {
if (!timer_pending(&stack.timer))
--
2.35.1
Hi Vladimir,
On Wed, Jul 13, 2022 at 03:31:05PM +0100, Vladimir Murzin wrote:
> I've just seen on the platform with slow(ish) timer that it is now considered
> as a source of entropy with samples_per_bit set to 27 (5.19-rc6 has MAX_SAMPLES_PER_BIT
> set to 32). Because of that I see significant delays and I'm trying to understand what
> could be wrong with my setup.
>
> I observe one credit_init_bits(1) call (via entropy_timer()) per ~970 schedule() calls.
> Is that somewhat expected? Does it make sense at all?
How slow are we talking? Seconds? Minutes? Is it too slow? It's possible
that MAX_SAMPLES_PER_BIT=32 is a bit high as a threshold and I should
reduce that a bit.
Also, out of curiosity, why is your timer so slow?
Jason
Hi All,
On 4/22/22 14:20, Jason A. Donenfeld wrote:
> Currently, we do the jitter dance if two consecutive reads to the cycle
> counter return different values. If they do, then we consider the cycle
> counter to be fast enough that one trip through the scheduler will yield
> one "bit" of credited entropy. If those two reads return the same value,
> then we assume the cycle counter is too slow to show meaningful
> differences.
>
> This methodology is flawed for a variety of reasons, one of which Eric
> posted a patch to fix in [1]. The issue that patch solves is that on a
> system with a slow counter, you might be [un]lucky and read the counter
> _just_ before it changes, so that the second cycle counter you read
> differs from the first, even though there's usually quite a large period
> of time in between the two. For example:
>
> | real time | cycle counter |
> | --------- | ------------- |
> | 3 | 5 |
> | 4 | 5 |
> | 5 | 5 |
> | 6 | 5 |
> | 7 | 5 | <--- a
> | 8 | 6 | <--- b
> | 9 | 6 | <--- c
>
> If we read the counter at (a) and compare it to (b), we might be fooled
> into thinking that it's a fast counter, when in reality it is not. The
> solution in [1] is to also compare counter (b) to counter (c), on the
> theory that if the counter is _actually_ slow, and (a)!=(b), then
> certainly (b)==(c).
>
> This helps solve this particular issue, in one sense, but in another
> sense, it mostly functions to disallow jitter entropy on these systems,
> rather than simply taking more samples in that case.
>
> Instead, this patch takes a different approach. Right now we assume that
> a difference in one set of consecutive samples means one "bit" of
> credited entropy per scheduler trip. We can extend this so that a
> difference in two sets of consecutive samples means one "bit" of
> credited entropy per /two/ scheduler trips, and three for three, and
> four for four. In other words, we can increase the amount of jitter
> "work" we require for each "bit", depending on how slow the cycle
> counter is.
>
> So this patch takes whole bunch of samples, sees how many of them are
> different, and divides to find the amount of work required per "bit",
> and also requires that at least some minimum of them are different in
> order to attempt any jitter entropy.
>
> Note that this approach is still far from perfect. It's not a real
> statistical estimate on how much these samples vary; it's not a
> real-time analysis of the relevant input data. That remains a project
> for another time. However, it does the same (partly flawed) assumptions
> as the code that's there now, so it's probably not worse than the status
> quo, and it handles the issue Eric mentioned in [1]. But, again, it's
> probably a far cry from whatever a really robust version of this would
> be.
>
> [1] https://lore.kernel.org/lkml/[email protected]/
> https://lore.kernel.org/lkml/[email protected]/
>
> Cc: Eric Biggers <[email protected]>
> Cc: Theodore Ts'o <[email protected]>
> Cc: Linus Torvalds <[email protected]>
> Signed-off-by: Jason A. Donenfeld <[email protected]>
> ---
> This is an argument very much centered around the somewhat low bar of
> being "not worse than before". If you can think of ways that it doesn't
> even manage to clear that, please do pipe up.
>
>
> drivers/char/random.c | 36 ++++++++++++++++++++++++++----------
> 1 file changed, 26 insertions(+), 10 deletions(-)
>
> diff --git a/drivers/char/random.c b/drivers/char/random.c
> index bf89c6f27a19..94a2ddb53662 100644
> --- a/drivers/char/random.c
> +++ b/drivers/char/random.c
> @@ -1354,6 +1354,12 @@ void add_interrupt_randomness(int irq)
> }
> EXPORT_SYMBOL_GPL(add_interrupt_randomness);
>
> +struct entropy_timer_state {
> + unsigned long entropy;
> + struct timer_list timer;
> + unsigned int samples, samples_per_bit;
> +};
> +
> /*
> * Each time the timer fires, we expect that we got an unpredictable
> * jump in the cycle counter. Even if the timer is running on another
> @@ -1367,9 +1373,14 @@ EXPORT_SYMBOL_GPL(add_interrupt_randomness);
> *
> * So the re-arming always happens in the entropy loop itself.
> */
> -static void entropy_timer(struct timer_list *t)
> +static void entropy_timer(struct timer_list *timer)
> {
> - credit_entropy_bits(1);
> + struct entropy_timer_state *state = container_of(timer, struct entropy_timer_state, timer);
> +
> + if (++state->samples == state->samples_per_bit) {
> + credit_entropy_bits(1);
> + state->samples = 0;
> + }
> }
>
> /*
> @@ -1378,17 +1389,22 @@ static void entropy_timer(struct timer_list *t)
> */
> static void try_to_generate_entropy(void)
> {
> - struct {
> - unsigned long entropy;
> - struct timer_list timer;
> - } stack;
> -
> - stack.entropy = random_get_entropy();
> + enum { NUM_TRIAL_SAMPLES = 8192, MAX_SAMPLES_PER_BIT = 256 };
> + struct entropy_timer_state stack;
> + unsigned int i, num_different = 0;
> + unsigned long last = random_get_entropy();
>
> - /* Slow counter - or none. Don't even bother */
> - if (stack.entropy == random_get_entropy())
> + for (i = 0; i < NUM_TRIAL_SAMPLES - 1; ++i) {
> + stack.entropy = random_get_entropy();
> + if (stack.entropy != last)
> + ++num_different;
> + last = stack.entropy;
> + }
> + stack.samples_per_bit = DIV_ROUND_UP(NUM_TRIAL_SAMPLES, num_different + 1);
> + if (stack.samples_per_bit > MAX_SAMPLES_PER_BIT)
> return;
>
> + stack.samples = 0;
> timer_setup_on_stack(&stack.timer, entropy_timer, 0);
> while (!crng_ready() && !signal_pending(current)) {
> if (!timer_pending(&stack.timer))
I've just seen on the platform with slow(ish) timer that it is now considered
as a source of entropy with samples_per_bit set to 27 (5.19-rc6 has MAX_SAMPLES_PER_BIT
set to 32). Because of that I see significant delays and I'm trying to understand what
could be wrong with my setup.
I observe one credit_init_bits(1) call (via entropy_timer()) per ~970 schedule() calls.
Is that somewhat expected? Does it make sense at all?
Cheers
Vladimir
Hi Jason,
On 7/13/22 15:40, Jason A. Donenfeld wrote:
> Hi Vladimir,
>
> On Wed, Jul 13, 2022 at 03:31:05PM +0100, Vladimir Murzin wrote:
>> I've just seen on the platform with slow(ish) timer that it is now considered
>> as a source of entropy with samples_per_bit set to 27 (5.19-rc6 has MAX_SAMPLES_PER_BIT
>> set to 32). Because of that I see significant delays and I'm trying to understand what
>> could be wrong with my setup.
>>
>> I observe one credit_init_bits(1) call (via entropy_timer()) per ~970 schedule() calls.
>> Is that somewhat expected? Does it make sense at all?
>
> How slow are we talking? Seconds? Minutes? Is it too slow? It's possible
> that MAX_SAMPLES_PER_BIT=32 is a bit high as a threshold and I should
> reduce that a bit.
>
TBH, I run out of patience and never seen it completes, more then seconds. I just was
curious how much it is should take to get crng_ready() return true.
> Also, out of curiosity, why is your timer so slow?
It is part of slow(ish) FPGA.
Cheers
Vladimir
>
> Jason
Hi Vladimir,
On Wed, Jul 13, 2022 at 4:52 PM Vladimir Murzin <[email protected]> wrote:
>
> Hi Jason,
>
> On 7/13/22 15:40, Jason A. Donenfeld wrote:
> > Hi Vladimir,
> >
> > On Wed, Jul 13, 2022 at 03:31:05PM +0100, Vladimir Murzin wrote:
> >> I've just seen on the platform with slow(ish) timer that it is now considered
> >> as a source of entropy with samples_per_bit set to 27 (5.19-rc6 has MAX_SAMPLES_PER_BIT
> >> set to 32). Because of that I see significant delays and I'm trying to understand what
> >> could be wrong with my setup.
> >>
> >> I observe one credit_init_bits(1) call (via entropy_timer()) per ~970 schedule() calls.
> >> Is that somewhat expected? Does it make sense at all?
> >
> > How slow are we talking? Seconds? Minutes? Is it too slow? It's possible
> > that MAX_SAMPLES_PER_BIT=32 is a bit high as a threshold and I should
> > reduce that a bit.
> >
>
> TBH, I run out of patience and never seen it completes, more then seconds. I just was
> curious how much it is should take to get crng_ready() return true.
Ooof. Yea, running this in a VM with various settings I can see that
the current maximum is problematic. I'll fix that up and send a patch.
Jason
Currently the jitter mechanism will require two timer ticks per
iteration, and it requires N iterations per bit. This N is determined
with a small measurement, and if it's too big, it won't waste time with
jitter entropy because it'd take too long or not have sufficient entropy
anyway.
With the current max N of 32, there are large timeouts on systems with a
small CONFIG_HZ. Rather than set that maximum to 32, instead choose a
factor of CONFIG_HZ. In this case, 1/30 seems to yield sane values for
different configurations of CONFIG_HZ.
Reported-by: Vladimir Murzin <[email protected]>
Fixes: 78c768e619fb ("random: vary jitter iterations based on cycle counter speed")
Signed-off-by: Jason A. Donenfeld <[email protected]>
---
Vladimir - Can you let me know if this appears to fix the issue you're
seeing? -Jason
drivers/char/random.c | 2 +-
1 file changed, 1 insertion(+), 1 deletion(-)
diff --git a/drivers/char/random.c b/drivers/char/random.c
index e3dd1dd3dd22..a1af90bacc9f 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -1174,7 +1174,7 @@ static void __cold entropy_timer(struct timer_list *timer)
*/
static void __cold try_to_generate_entropy(void)
{
- enum { NUM_TRIAL_SAMPLES = 8192, MAX_SAMPLES_PER_BIT = 32 };
+ enum { NUM_TRIAL_SAMPLES = 8192, MAX_SAMPLES_PER_BIT = HZ / 30 };
struct entropy_timer_state stack;
unsigned int i, num_different = 0;
unsigned long last = random_get_entropy();
--
2.35.1
On 7/13/22 16:11, Jason A. Donenfeld wrote:
> Currently the jitter mechanism will require two timer ticks per
> iteration, and it requires N iterations per bit. This N is determined
> with a small measurement, and if it's too big, it won't waste time with
> jitter entropy because it'd take too long or not have sufficient entropy
> anyway.
>
> With the current max N of 32, there are large timeouts on systems with a
> small CONFIG_HZ. Rather than set that maximum to 32, instead choose a
> factor of CONFIG_HZ. In this case, 1/30 seems to yield sane values for
> different configurations of CONFIG_HZ.
>
> Reported-by: Vladimir Murzin <[email protected]>
> Fixes: 78c768e619fb ("random: vary jitter iterations based on cycle counter speed")
> Signed-off-by: Jason A. Donenfeld <[email protected]>
> ---
> Vladimir - Can you let me know if this appears to fix the issue you're
> seeing? -Jason
Works for me, thanks! :)
>
> drivers/char/random.c | 2 +-
> 1 file changed, 1 insertion(+), 1 deletion(-)
>
> diff --git a/drivers/char/random.c b/drivers/char/random.c
> index e3dd1dd3dd22..a1af90bacc9f 100644
> --- a/drivers/char/random.c
> +++ b/drivers/char/random.c
> @@ -1174,7 +1174,7 @@ static void __cold entropy_timer(struct timer_list *timer)
> */
> static void __cold try_to_generate_entropy(void)
> {
> - enum { NUM_TRIAL_SAMPLES = 8192, MAX_SAMPLES_PER_BIT = 32 };
> + enum { NUM_TRIAL_SAMPLES = 8192, MAX_SAMPLES_PER_BIT = HZ / 30 };
> struct entropy_timer_state stack;
> unsigned int i, num_different = 0;
> unsigned long last = random_get_entropy();
FWIW
Tested-by: Vladimir Murzin <[email protected]>
Cheers
Vladimir
Hi Vladmir,
On Wed, Jul 13, 2022 at 04:52:20PM +0100, Vladimir Murzin wrote:
> On 7/13/22 16:11, Jason A. Donenfeld wrote:
> > Vladimir - Can you let me know if this appears to fix the issue you're
> > seeing? -Jason
>
> Works for me, thanks! :)
> Tested-by: Vladimir Murzin <[email protected]>
Thanks for testing. I'll push this out to Linus probably tomorrow.
(Though I noticed that Linus is in the CC for this thread already, and
he's been on a patch picking spree as of late, so in case he happens to
be following along, fell free to pick away. Otherwise I'll send a pull
not before long.)
Jason
Hey Linus,
On Sat, Jul 16, 2022 at 10:45:24AM -0700, Linus Torvalds wrote:
> On Wed, Jul 13, 2022 at 9:22 AM Jason A. Donenfeld <[email protected]> wrote:
> >
> > Thanks for testing. I'll push this out to Linus probably tomorrow.
> >
> > (Though I noticed that Linus is in the CC for this thread already, and
> > he's been on a patch picking spree as of late, so in case he happens to
> > be following along, fell free to pick away. Otherwise I'll send a pull
> > not before long.)
>
> Well, the "probably tomorrow" didn't happen, so yes, I've just picked
> it up directly.
Oh, okay. Something came up on Thursday, and I just sat down (on the
train back home) to do this now. So I didn't forget! But thanks for
taking it nonetheless.
Jason