1. 13 May, 2022 20 commits
    • Jason A. Donenfeld's avatar
      random: vary jitter iterations based on cycle counter speed · 78c768e6
      Jason A. Donenfeld authored
      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 makes 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/20220421233152.58522-1-ebiggers@kernel.org/
          https://lore.kernel.org/lkml/20220421192939.250680-1-ebiggers@kernel.org/
      
      Cc: Eric Biggers <ebiggers@google.com>
      Cc: Theodore Ts'o <tytso@mit.edu>
      Cc: Linus Torvalds <torvalds@linux-foundation.org>
      Signed-off-by: default avatarJason A. Donenfeld <Jason@zx2c4.com>
      78c768e6
    • Jason A. Donenfeld's avatar
      random: insist on random_get_entropy() existing in order to simplify · 4b758eda
      Jason A. Donenfeld authored
      All platforms are now guaranteed to provide some value for
      random_get_entropy(). In case some bug leads to this not being so, we
      print a warning, because that indicates that something is really very
      wrong (and likely other things are impacted too). This should never be
      hit, but it's a good and cheap way of finding out if something ever is
      problematic.
      
      Since we now have viable fallback code for random_get_entropy() on all
      platforms, which is, in the worst case, not worse than jiffies, we can
      count on getting the best possible value out of it. That means there's
      no longer a use for using jiffies as entropy input. It also means we no
      longer have a reason for doing the round-robin register flow in the IRQ
      handler, which was always of fairly dubious value.
      
      Instead we can greatly simplify the IRQ handler inputs and also unify
      the construction between 64-bits and 32-bits. We now collect the cycle
      counter and the return address, since those are the two things that
      matter. Because the return address and the irq number are likely
      related, to the extent we mix in the irq number, we can just xor it into
      the top unchanging bytes of the return address, rather than the bottom
      changing bytes of the cycle counter as before. Then, we can do a fixed 2
      rounds of SipHash/HSipHash. Finally, we use the same construction of
      hashing only half of the [H]SipHash state on 32-bit and 64-bit. We're
      not actually discarding any entropy, since that entropy is carried
      through until the next time. And more importantly, it lets us do the
      same sponge-like construction everywhere.
      
      Cc: Theodore Ts'o <tytso@mit.edu>
      Signed-off-by: default avatarJason A. Donenfeld <Jason@zx2c4.com>
      4b758eda
    • Jason A. Donenfeld's avatar
      xtensa: use fallback for random_get_entropy() instead of zero · e10e2f58
      Jason A. Donenfeld authored
      In the event that random_get_entropy() can't access a cycle counter or
      similar, falling back to returning 0 is really not the best we can do.
      Instead, at least calling random_get_entropy_fallback() would be
      preferable, because that always needs to return _something_, even
      falling back to jiffies eventually. It's not as though
      random_get_entropy_fallback() is super high precision or guaranteed to
      be entropic, but basically anything that's not zero all the time is
      better than returning zero all the time.
      
      This is accomplished by just including the asm-generic code like on
      other architectures, which means we can get rid of the empty stub
      function here.
      
      Cc: Thomas Gleixner <tglx@linutronix.de>
      Cc: Arnd Bergmann <arnd@arndb.de>
      Acked-by: default avatarMax Filippov <jcmvbkbc@gmail.com>
      Signed-off-by: default avatarJason A. Donenfeld <Jason@zx2c4.com>
      e10e2f58
    • Jason A. Donenfeld's avatar
      sparc: use fallback for random_get_entropy() instead of zero · ac9756c7
      Jason A. Donenfeld authored
      In the event that random_get_entropy() can't access a cycle counter or
      similar, falling back to returning 0 is really not the best we can do.
      Instead, at least calling random_get_entropy_fallback() would be
      preferable, because that always needs to return _something_, even
      falling back to jiffies eventually. It's not as though
      random_get_entropy_fallback() is super high precision or guaranteed to
      be entropic, but basically anything that's not zero all the time is
      better than returning zero all the time.
      
      This is accomplished by just including the asm-generic code like on
      other architectures, which means we can get rid of the empty stub
      function here.
      
      Cc: Thomas Gleixner <tglx@linutronix.de>
      Cc: Arnd Bergmann <arnd@arndb.de>
      Cc: David S. Miller <davem@davemloft.net>
      Signed-off-by: default avatarJason A. Donenfeld <Jason@zx2c4.com>
      ac9756c7
    • Jason A. Donenfeld's avatar
      um: use fallback for random_get_entropy() instead of zero · 9f13fb0c
      Jason A. Donenfeld authored
      In the event that random_get_entropy() can't access a cycle counter or
      similar, falling back to returning 0 is really not the best we can do.
      Instead, at least calling random_get_entropy_fallback() would be
      preferable, because that always needs to return _something_, even
      falling back to jiffies eventually. It's not as though
      random_get_entropy_fallback() is super high precision or guaranteed to
      be entropic, but basically anything that's not zero all the time is
      better than returning zero all the time.
      
      This is accomplished by just including the asm-generic code like on
      other architectures, which means we can get rid of the empty stub
      function here.
      
      Cc: Thomas Gleixner <tglx@linutronix.de>
      Cc: Arnd Bergmann <arnd@arndb.de>
      Cc: Richard Weinberger <richard@nod.at>
      Cc: Anton Ivanov <anton.ivanov@cambridgegreys.com>
      Acked-by: default avatarJohannes Berg <johannes@sipsolutions.net>
      Signed-off-by: default avatarJason A. Donenfeld <Jason@zx2c4.com>
      9f13fb0c
    • Jason A. Donenfeld's avatar
      x86/tsc: Use fallback for random_get_entropy() instead of zero · 3bd4abc0
      Jason A. Donenfeld authored
      In the event that random_get_entropy() can't access a cycle counter or
      similar, falling back to returning 0 is suboptimal. Instead, fallback
      to calling random_get_entropy_fallback(), which isn't extremely high
      precision or guaranteed to be entropic, but is certainly better than
      returning zero all the time.
      
      If CONFIG_X86_TSC=n, then it's possible for the kernel to run on systems
      without RDTSC, such as 486 and certain 586, so the fallback code is only
      required for that case.
      
      As well, fix up both the new function and the get_cycles() function from
      which it was derived to use cpu_feature_enabled() rather than
      boot_cpu_has(), and use !IS_ENABLED() instead of #ifndef.
      Signed-off-by: default avatarJason A. Donenfeld <Jason@zx2c4.com>
      Reviewed-by: default avatarThomas Gleixner <tglx@linutronix.de>
      Cc: Thomas Gleixner <tglx@linutronix.de>
      Cc: Arnd Bergmann <arnd@arndb.de>
      Cc: Borislav Petkov <bp@alien8.de>
      Cc: x86@kernel.org
      3bd4abc0
    • Jason A. Donenfeld's avatar
      nios2: use fallback for random_get_entropy() instead of zero · c04e7270
      Jason A. Donenfeld authored
      In the event that random_get_entropy() can't access a cycle counter or
      similar, falling back to returning 0 is really not the best we can do.
      Instead, at least calling random_get_entropy_fallback() would be
      preferable, because that always needs to return _something_, even
      falling back to jiffies eventually. It's not as though
      random_get_entropy_fallback() is super high precision or guaranteed to
      be entropic, but basically anything that's not zero all the time is
      better than returning zero all the time.
      
      Cc: Thomas Gleixner <tglx@linutronix.de>
      Cc: Arnd Bergmann <arnd@arndb.de>
      Acked-by: default avatarDinh Nguyen <dinguyen@kernel.org>
      Signed-off-by: default avatarJason A. Donenfeld <Jason@zx2c4.com>
      c04e7270
    • Jason A. Donenfeld's avatar
      arm: use fallback for random_get_entropy() instead of zero · ff8a8f59
      Jason A. Donenfeld authored
      In the event that random_get_entropy() can't access a cycle counter or
      similar, falling back to returning 0 is really not the best we can do.
      Instead, at least calling random_get_entropy_fallback() would be
      preferable, because that always needs to return _something_, even
      falling back to jiffies eventually. It's not as though
      random_get_entropy_fallback() is super high precision or guaranteed to
      be entropic, but basically anything that's not zero all the time is
      better than returning zero all the time.
      
      Cc: Thomas Gleixner <tglx@linutronix.de>
      Cc: Arnd Bergmann <arnd@arndb.de>
      Reviewed-by: default avatarRussell King (Oracle) <rmk+kernel@armlinux.org.uk>
      Signed-off-by: default avatarJason A. Donenfeld <Jason@zx2c4.com>
      ff8a8f59
    • Jason A. Donenfeld's avatar
      mips: use fallback for random_get_entropy() instead of just c0 random · 1c99c6a7
      Jason A. Donenfeld authored
      For situations in which we don't have a c0 counter register available,
      we've been falling back to reading the c0 "random" register, which is
      usually bounded by the amount of TLB entries and changes every other
      cycle or so. This means it wraps extremely often. We can do better by
      combining this fast-changing counter with a potentially slower-changing
      counter from random_get_entropy_fallback() in the more significant bits.
      This commit combines the two, taking into account that the changing bits
      are in a different bit position depending on the CPU model. In addition,
      we previously were falling back to 0 for ancient CPUs that Linux does
      not support anyway; remove that dead path entirely.
      
      Cc: Thomas Gleixner <tglx@linutronix.de>
      Cc: Arnd Bergmann <arnd@arndb.de>
      Tested-by: default avatarMaciej W. Rozycki <macro@orcam.me.uk>
      Acked-by: default avatarThomas Bogendoerfer <tsbogend@alpha.franken.de>
      Signed-off-by: default avatarJason A. Donenfeld <Jason@zx2c4.com>
      1c99c6a7
    • Jason A. Donenfeld's avatar
      riscv: use fallback for random_get_entropy() instead of zero · 6d012386
      Jason A. Donenfeld authored
      In the event that random_get_entropy() can't access a cycle counter or
      similar, falling back to returning 0 is really not the best we can do.
      Instead, at least calling random_get_entropy_fallback() would be
      preferable, because that always needs to return _something_, even
      falling back to jiffies eventually. It's not as though
      random_get_entropy_fallback() is super high precision or guaranteed to
      be entropic, but basically anything that's not zero all the time is
      better than returning zero all the time.
      
      Cc: Thomas Gleixner <tglx@linutronix.de>
      Cc: Arnd Bergmann <arnd@arndb.de>
      Cc: Paul Walmsley <paul.walmsley@sifive.com>
      Acked-by: default avatarPalmer Dabbelt <palmer@rivosinc.com>
      Reviewed-by: default avatarPalmer Dabbelt <palmer@rivosinc.com>
      Signed-off-by: default avatarJason A. Donenfeld <Jason@zx2c4.com>
      6d012386
    • Jason A. Donenfeld's avatar
      m68k: use fallback for random_get_entropy() instead of zero · 0f392c95
      Jason A. Donenfeld authored
      In the event that random_get_entropy() can't access a cycle counter or
      similar, falling back to returning 0 is really not the best we can do.
      Instead, at least calling random_get_entropy_fallback() would be
      preferable, because that always needs to return _something_, even
      falling back to jiffies eventually. It's not as though
      random_get_entropy_fallback() is super high precision or guaranteed to
      be entropic, but basically anything that's not zero all the time is
      better than returning zero all the time.
      
      Cc: Thomas Gleixner <tglx@linutronix.de>
      Cc: Arnd Bergmann <arnd@arndb.de>
      Acked-by: default avatarGeert Uytterhoeven <geert@linux-m68k.org>
      Signed-off-by: default avatarJason A. Donenfeld <Jason@zx2c4.com>
      0f392c95
    • Jason A. Donenfeld's avatar
      timekeeping: Add raw clock fallback for random_get_entropy() · 1366992e
      Jason A. Donenfeld authored
      The addition of random_get_entropy_fallback() provides access to
      whichever time source has the highest frequency, which is useful for
      gathering entropy on platforms without available cycle counters. It's
      not necessarily as good as being able to quickly access a cycle counter
      that the CPU has, but it's still something, even when it falls back to
      being jiffies-based.
      
      In the event that a given arch does not define get_cycles(), falling
      back to the get_cycles() default implementation that returns 0 is really
      not the best we can do. Instead, at least calling
      random_get_entropy_fallback() would be preferable, because that always
      needs to return _something_, even falling back to jiffies eventually.
      It's not as though random_get_entropy_fallback() is super high precision
      or guaranteed to be entropic, but basically anything that's not zero all
      the time is better than returning zero all the time.
      
      Finally, since random_get_entropy_fallback() is used during extremely
      early boot when randomizing freelists in mm_init(), it can be called
      before timekeeping has been initialized. In that case there really is
      nothing we can do; jiffies hasn't even started ticking yet. So just give
      up and return 0.
      Suggested-by: default avatarThomas Gleixner <tglx@linutronix.de>
      Signed-off-by: default avatarJason A. Donenfeld <Jason@zx2c4.com>
      Reviewed-by: default avatarThomas Gleixner <tglx@linutronix.de>
      Cc: Arnd Bergmann <arnd@arndb.de>
      Cc: Theodore Ts'o <tytso@mit.edu>
      1366992e
    • Jason A. Donenfeld's avatar
      openrisc: start CPU timer early in boot · 516dd4aa
      Jason A. Donenfeld authored
      In order to measure the boot process, the timer should be switched on as
      early in boot as possible. As well, the commit defines the get_cycles
      macro, like the previous patches in this series, so that generic code is
      aware that it's implemented by the platform, as is done on other archs.
      
      Cc: Thomas Gleixner <tglx@linutronix.de>
      Cc: Arnd Bergmann <arnd@arndb.de>
      Cc: Jonas Bonn <jonas@southpole.se>
      Cc: Stefan Kristiansson <stefan.kristiansson@saunalahti.fi>
      Acked-by: default avatarStafford Horne <shorne@gmail.com>
      Reported-by: default avatarGuenter Roeck <linux@roeck-us.net>
      Signed-off-by: default avatarJason A. Donenfeld <Jason@zx2c4.com>
      516dd4aa
    • Jason A. Donenfeld's avatar
      powerpc: define get_cycles macro for arch-override · 40883583
      Jason A. Donenfeld authored
      PowerPC defines a get_cycles() function, but it does not do the usual
      `#define get_cycles get_cycles` dance, making it impossible for generic
      code to see if an arch-specific function was defined. While the
      get_cycles() ifdef is not currently used, the following timekeeping
      patch in this series will depend on the macro existing (or not existing)
      when defining random_get_entropy().
      
      Cc: Thomas Gleixner <tglx@linutronix.de>
      Cc: Arnd Bergmann <arnd@arndb.de>
      Cc: Benjamin Herrenschmidt <benh@ozlabs.org>
      Cc: Paul Mackerras <paulus@samba.org>
      Acked-by: default avatarMichael Ellerman <mpe@ellerman.id.au>
      Signed-off-by: default avatarJason A. Donenfeld <Jason@zx2c4.com>
      40883583
    • Jason A. Donenfeld's avatar
      alpha: define get_cycles macro for arch-override · 1097710b
      Jason A. Donenfeld authored
      Alpha defines a get_cycles() function, but it does not do the usual
      `#define get_cycles get_cycles` dance, making it impossible for generic
      code to see if an arch-specific function was defined. While the
      get_cycles() ifdef is not currently used, the following timekeeping
      patch in this series will depend on the macro existing (or not existing)
      when defining random_get_entropy().
      
      Cc: Thomas Gleixner <tglx@linutronix.de>
      Cc: Arnd Bergmann <arnd@arndb.de>
      Cc: Richard Henderson <rth@twiddle.net>
      Cc: Ivan Kokshaysky <ink@jurassic.park.msu.ru>
      Acked-by: default avatarMatt Turner <mattst88@gmail.com>
      Signed-off-by: default avatarJason A. Donenfeld <Jason@zx2c4.com>
      1097710b
    • Jason A. Donenfeld's avatar
      parisc: define get_cycles macro for arch-override · 8865bbe6
      Jason A. Donenfeld authored
      PA-RISC defines a get_cycles() function, but it does not do the usual
      `#define get_cycles get_cycles` dance, making it impossible for generic
      code to see if an arch-specific function was defined. While the
      get_cycles() ifdef is not currently used, the following timekeeping
      patch in this series will depend on the macro existing (or not existing)
      when defining random_get_entropy().
      
      Cc: Thomas Gleixner <tglx@linutronix.de>
      Cc: Arnd Bergmann <arnd@arndb.de>
      Acked-by: default avatarHelge Deller <deller@gmx.de>
      Signed-off-by: default avatarJason A. Donenfeld <Jason@zx2c4.com>
      8865bbe6
    • Jason A. Donenfeld's avatar
      s390: define get_cycles macro for arch-override · 2e3df523
      Jason A. Donenfeld authored
      S390x defines a get_cycles() function, but it does not do the usual
      `#define get_cycles get_cycles` dance, making it impossible for generic
      code to see if an arch-specific function was defined. While the
      get_cycles() ifdef is not currently used, the following timekeeping
      patch in this series will depend on the macro existing (or not existing)
      when defining random_get_entropy().
      
      Cc: Thomas Gleixner <tglx@linutronix.de>
      Cc: Arnd Bergmann <arnd@arndb.de>
      Cc: Vasily Gorbik <gor@linux.ibm.com>
      Cc: Alexander Gordeev <agordeev@linux.ibm.com>
      Cc: Christian Borntraeger <borntraeger@linux.ibm.com>
      Cc: Sven Schnelle <svens@linux.ibm.com>
      Acked-by: default avatarHeiko Carstens <hca@linux.ibm.com>
      Signed-off-by: default avatarJason A. Donenfeld <Jason@zx2c4.com>
      2e3df523
    • Jason A. Donenfeld's avatar
      ia64: define get_cycles macro for arch-override · 57c0900b
      Jason A. Donenfeld authored
      Itanium defines a get_cycles() function, but it does not do the usual
      `#define get_cycles get_cycles` dance, making it impossible for generic
      code to see if an arch-specific function was defined. While the
      get_cycles() ifdef is not currently used, the following timekeeping
      patch in this series will depend on the macro existing (or not existing)
      when defining random_get_entropy().
      
      Cc: Thomas Gleixner <tglx@linutronix.de>
      Cc: Arnd Bergmann <arnd@arndb.de>
      Signed-off-by: default avatarJason A. Donenfeld <Jason@zx2c4.com>
      57c0900b
    • Jason A. Donenfeld's avatar
      init: call time_init() before rand_initialize() · fe222a6c
      Jason A. Donenfeld authored
      Currently time_init() is called after rand_initialize(), but
      rand_initialize() makes use of the timer on various platforms, and
      sometimes this timer needs to be initialized by time_init() first. In
      order for random_get_entropy() to not return zero during early boot when
      it's potentially used as an entropy source, reverse the order of these
      two calls. The block doing random initialization was right before
      time_init() before, so changing the order shouldn't have any complicated
      effects.
      
      Cc: Andrew Morton <akpm@linux-foundation.org>
      Reviewed-by: default avatarStafford Horne <shorne@gmail.com>
      Signed-off-by: default avatarJason A. Donenfeld <Jason@zx2c4.com>
      fe222a6c
    • Jason A. Donenfeld's avatar
      random: fix sysctl documentation nits · 069c4ea6
      Jason A. Donenfeld authored
      A semicolon was missing, and the almost-alphabetical-but-not ordering
      was confusing, so regroup these by category instead.
      Signed-off-by: default avatarJason A. Donenfeld <Jason@zx2c4.com>
      069c4ea6
  2. 08 May, 2022 20 commits