src/patches/linux/linux-random_try_to_actively_add_entropy.patch

   1 From 50ee7529ec4500c88f8664560770a7a1b65db72b Mon Sep 17 00:00:00 2001
   2 From: Linus Torvalds <torvalds@linux-foundation.org>
   3 Date: Sat, 28 Sep 2019 16:53:52 -0700
   4 Subject: random: try to actively add entropy rather than passively wait for it
   5
   6 For 5.3 we had to revert a nice ext4 IO pattern improvement, because it
   7 caused a bootup regression due to lack of entropy at bootup together
   8 with arguably broken user space that was asking for secure random
   9 numbers when it really didn't need to.
  10
  11 See commit 72dbcf721566 (Revert "ext4: make __ext4_get_inode_loc plug").
  12
  13 This aims to solve the issue by actively generating entropy noise using
  14 the CPU cycle counter when waiting for the random number generator to
  15 initialize.  This only works when you have a high-frequency time stamp
  16 counter available, but that's the case on all modern x86 CPU's, and on
  17 most other modern CPU's too.
  18
  19 What we do is to generate jitter entropy from the CPU cycle counter
  20 under a somewhat complex load: calling the scheduler while also
  21 guaranteeing a certain amount of timing noise by also triggering a
  22 timer.
  23
  24 I'm sure we can tweak this, and that people will want to look at other
  25 alternatives, but there's been a number of papers written on jitter
  26 entropy, and this should really be fairly conservative by crediting one
  27 bit of entropy for every timer-induced jump in the cycle counter.  Not
  28 because the timer itself would be all that unpredictable, but because
  29 the interaction between the timer and the loop is going to be.
  30
  31 Even if (and perhaps particularly if) the timer actually happens on
  32 another CPU, the cacheline interaction between the loop that reads the
  33 cycle counter and the timer itself firing is going to add perturbations
  34 to the cycle counter values that get mixed into the entropy pool.
  35
  36 As Thomas pointed out, with a modern out-of-order CPU, even quite simple
  37 loops show a fair amount of hard-to-predict timing variability even in
  38 the absense of external interrupts.  But this tries to take that further
  39 by actually having a fairly complex interaction.
  40
  41 This is not going to solve the entropy issue for architectures that have
  42 no CPU cycle counter, but it's not clear how (and if) that is solvable,
  43 and the hardware in question is largely starting to be irrelevant.  And
  44 by doing this we can at least avoid some of the even more contentious
  45 approaches (like making the entropy waiting time out in order to avoid
  46 the possibly unbounded waiting).
  47
  48 Cc: Ahmed Darwish <darwish.07@gmail.com>
  49 Cc: Thomas Gleixner <tglx@linutronix.de>
  50 Cc: Theodore Ts'o <tytso@mit.edu>
  51 Cc: Nicholas Mc Guire <hofrat@opentech.at>
  52 Cc: Andy Lutomirski <luto@kernel.org>
  53 Cc: Kees Cook <keescook@chromium.org>
  54 Cc: Willy Tarreau <w@1wt.eu>
  55 Cc: Alexander E. Patrakov <patrakov@gmail.com>
  56 Cc: Lennart Poettering <mzxreary@0pointer.de>
  57 Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
  58 ---
  59  drivers/char/random.c | 62 ++++++++++++++++++++++++++++++++++++++++++++++++++-
  60  1 file changed, 61 insertions(+), 1 deletion(-)
  61
  62 (limited to 'drivers/char/random.c')
  63
  64 diff --git a/drivers/char/random.c b/drivers/char/random.c
  65 index 5d5ea4ce1442..2fda6166c1dd 100644
  66 --- a/drivers/char/random.c
  67 +++ b/drivers/char/random.c
  68 @@ -1731,6 +1731,56 @@ void get_random_bytes(void *buf, int nbytes)
  69  }
  70  EXPORT_SYMBOL(get_random_bytes);
  71
  72 +
  73 +/*
  74 + * Each time the timer fires, we expect that we got an unpredictable
  75 + * jump in the cycle counter. Even if the timer is running on another
  76 + * CPU, the timer activity will be touching the stack of the CPU that is
  77 + * generating entropy..
  78 + *
  79 + * Note that we don't re-arm the timer in the timer itself - we are
  80 + * happy to be scheduled away, since that just makes the load more
  81 + * complex, but we do not want the timer to keep ticking unless the
  82 + * entropy loop is running.
  83 + *
  84 + * So the re-arming always happens in the entropy loop itself.
  85 + */
  86 +static void entropy_timer(struct timer_list *t)
  87 +{
  88 +       credit_entropy_bits(&input_pool, 1);
  89 +}
  90 +
  91 +/*
  92 + * If we have an actual cycle counter, see if we can
  93 + * generate enough entropy with timing noise
  94 + */
  95 +static void try_to_generate_entropy(void)
  96 +{
  97 +       struct {
  98 +               unsigned long now;
  99 +               struct timer_list timer;
 100 +       } stack;
 101 +
 102 +       stack.now = random_get_entropy();
 103 +
 104 +       /* Slow counter - or none. Don't even bother */
 105 +       if (stack.now == random_get_entropy())
 106 +               return;
 107 +
 108 +       timer_setup_on_stack(&stack.timer, entropy_timer, 0);
 109 +       while (!crng_ready()) {
 110 +               if (!timer_pending(&stack.timer))
 111 +                       mod_timer(&stack.timer, jiffies+1);
 112 +               mix_pool_bytes(&input_pool, &stack.now, sizeof(stack.now));
 113 +               schedule();
 114 +               stack.now = random_get_entropy();
 115 +       }
 116 +
 117 +       del_timer_sync(&stack.timer);
 118 +       destroy_timer_on_stack(&stack.timer);
 119 +       mix_pool_bytes(&input_pool, &stack.now, sizeof(stack.now));
 120 +}
 121 +
 122  /*
 123   * Wait for the urandom pool to be seeded and thus guaranteed to supply
 124   * cryptographically secure random numbers. This applies to: the /dev/urandom
 125 @@ -1745,7 +1795,17 @@ int wait_for_random_bytes(void)
 126  {
 127         if (likely(crng_ready()))
 128                 return 0;
 129 -       return wait_event_interruptible(crng_init_wait, crng_ready());
 130 +
 131 +       do {
 132 +               int ret;
 133 +               ret = wait_event_interruptible_timeout(crng_init_wait, crng_ready(), HZ);
 134 +               if (ret)
 135 +                       return ret > 0 ? 0 : ret;
 136 +
 137 +               try_to_generate_entropy();
 138 +       } while (!crng_ready());
 139 +
 140 +       return 0;
 141  }
 142  EXPORT_SYMBOL(wait_for_random_bytes);
 143
 144 --
 145 cgit 1.2-0.3.lf.el7
 146