1. 21 Feb, 2022 22 commits
    • Jason A. Donenfeld's avatar
      random: remove ifdef'd out interrupt bench · 95e6060c
      Jason A. Donenfeld authored
      With tools like kbench9000 giving more finegrained responses, and this
      basically never having been used ever since it was initially added,
      let's just get rid of this. There *is* still work to be done on the
      interrupt handler, but this really isn't the way it's being developed.
      
      Cc: Theodore Ts'o <tytso@mit.edu>
      Reviewed-by: default avatarEric Biggers <ebiggers@google.com>
      Reviewed-by: default avatarDominik Brodowski <linux@dominikbrodowski.net>
      Signed-off-by: default avatarJason A. Donenfeld <Jason@zx2c4.com>
      95e6060c
    • Jason A. Donenfeld's avatar
      random: tie batched entropy generation to base_crng generation · 0791e8b6
      Jason A. Donenfeld authored
      Now that we have an explicit base_crng generation counter, we don't need
      a separate one for batched entropy. Rather, we can just move the
      generation forward every time we change crng_init state or update the
      base_crng key.
      
      Cc: Theodore Ts'o <tytso@mit.edu>
      Reviewed-by: default avatarEric Biggers <ebiggers@google.com>
      Reviewed-by: default avatarDominik Brodowski <linux@dominikbrodowski.net>
      Signed-off-by: default avatarJason A. Donenfeld <Jason@zx2c4.com>
      0791e8b6
    • Dominik Brodowski's avatar
      random: fix locking for crng_init in crng_reseed() · 7191c628
      Dominik Brodowski authored
      crng_init is protected by primary_crng->lock. Therefore, we need
      to hold this lock when increasing crng_init to 2. As we shouldn't
      hold this lock for too long, only hold it for those parts which
      require protection.
      Signed-off-by: default avatarDominik Brodowski <linux@dominikbrodowski.net>
      Reviewed-by: default avatarEric Biggers <ebiggers@google.com>
      Signed-off-by: default avatarJason A. Donenfeld <Jason@zx2c4.com>
      7191c628
    • Jason A. Donenfeld's avatar
      random: zero buffer after reading entropy from userspace · 7b5164fb
      Jason A. Donenfeld authored
      This buffer may contain entropic data that shouldn't stick around longer
      than needed, so zero out the temporary buffer at the end of write_pool().
      Reviewed-by: default avatarDominik Brodowski <linux@dominikbrodowski.net>
      Reviewed-by: default avatarJann Horn <jannh@google.com>
      Reviewed-by: default avatarEric Biggers <ebiggers@google.com>
      Signed-off-by: default avatarJason A. Donenfeld <Jason@zx2c4.com>
      7b5164fb
    • Jason A. Donenfeld's avatar
      random: remove outdated INT_MAX >> 6 check in urandom_read() · 434537ae
      Jason A. Donenfeld authored
      In 79a84687 ("random: check for increase of entropy_count because of
      signed conversion"), a number of checks were added around what values
      were passed to account(), because account() was doing fancy fixed point
      fractional arithmetic, and a user had some ability to pass large values
      directly into it. One of things in that commit was limiting those values
      to INT_MAX >> 6. The first >> 3 was for bytes to bits, and the next >> 3
      was for bits to 1/8 fractional bits.
      
      However, for several years now, urandom reads no longer touch entropy
      accounting, and so this check serves no purpose. The current flow is:
      
      urandom_read_nowarn()-->get_random_bytes_user()-->chacha20_block()
      
      Of course, we don't want that size_t to be truncated when adding it into
      the ssize_t. But we arrive at urandom_read_nowarn() in the first place
      either via ordinary fops, which limits reads to MAX_RW_COUNT, or via
      getrandom() which limits reads to INT_MAX.
      
      Cc: Theodore Ts'o <tytso@mit.edu>
      Reviewed-by: default avatarDominik Brodowski <linux@dominikbrodowski.net>
      Reviewed-by: default avatarJann Horn <jannh@google.com>
      Reviewed-by: default avatarEric Biggers <ebiggers@google.com>
      Signed-off-by: default avatarJason A. Donenfeld <Jason@zx2c4.com>
      434537ae
    • Jason A. Donenfeld's avatar
      random: make more consistent use of integer types · 04ec96b7
      Jason A. Donenfeld authored
      We've been using a flurry of int, unsigned int, size_t, and ssize_t.
      Let's unify all of this into size_t where it makes sense, as it does in
      most places, and leave ssize_t for return values with possible errors.
      
      In addition, keeping with the convention of other functions in this
      file, functions that are dealing with raw bytes now take void *
      consistently instead of a mix of that and u8 *, because much of the time
      we're actually passing some other structure that is then interpreted as
      bytes by the function.
      
      We also take the opportunity to fix the outdated and incorrect comment
      in get_random_bytes_arch().
      
      Cc: Theodore Ts'o <tytso@mit.edu>
      Reviewed-by: default avatarDominik Brodowski <linux@dominikbrodowski.net>
      Reviewed-by: default avatarJann Horn <jannh@google.com>
      Reviewed-by: default avatarEric Biggers <ebiggers@google.com>
      Signed-off-by: default avatarJason A. Donenfeld <Jason@zx2c4.com>
      04ec96b7
    • Jason A. Donenfeld's avatar
      random: use hash function for crng_slow_load() · 66e4c2b9
      Jason A. Donenfeld authored
      Since we have a hash function that's really fast, and the goal of
      crng_slow_load() is reportedly to "touch all of the crng's state", we
      can just hash the old state together with the new state and call it a
      day. This way we dont need to reason about another LFSR or worry about
      various attacks there. This code is only ever used at early boot and
      then never again.
      
      Cc: Theodore Ts'o <tytso@mit.edu>
      Reviewed-by: default avatarDominik Brodowski <linux@dominikbrodowski.net>
      Reviewed-by: default avatarEric Biggers <ebiggers@google.com>
      Signed-off-by: default avatarJason A. Donenfeld <Jason@zx2c4.com>
      66e4c2b9
    • Jason A. Donenfeld's avatar
      random: use simpler fast key erasure flow on per-cpu keys · 186873c5
      Jason A. Donenfeld authored
      Rather than the clunky NUMA full ChaCha state system we had prior, this
      commit is closer to the original "fast key erasure RNG" proposal from
      <https://blog.cr.yp.to/20170723-random.html>, by simply treating ChaCha
      keys on a per-cpu basis.
      
      All entropy is extracted to a base crng key of 32 bytes. This base crng
      has a birthdate and a generation counter. When we go to take bytes from
      the crng, we first check if the birthdate is too old; if it is, we
      reseed per usual. Then we start working on a per-cpu crng.
      
      This per-cpu crng makes sure that it has the same generation counter as
      the base crng. If it doesn't, it does fast key erasure with the base
      crng key and uses the output as its new per-cpu key, and then updates
      its local generation counter. Then, using this per-cpu state, we do
      ordinary fast key erasure. Half of this first block is used to overwrite
      the per-cpu crng key for the next call -- this is the fast key erasure
      RNG idea -- and the other half, along with the ChaCha state, is returned
      to the caller. If the caller desires more than this remaining half, it
      can generate more ChaCha blocks, unlocked, using the now detached ChaCha
      state that was just returned. Crypto-wise, this is more or less what we
      were doing before, but this simply makes it more explicit and ensures
      that we always have backtrack protection by not playing games with a
      shared block counter.
      
      The flow looks like this:
      
      ──extract()──► base_crng.key ◄──memcpy()───┐
                         │                       │
                         └──chacha()──────┬─► new_base_key
                                          └─► crngs[n].key ◄──memcpy()───┐
                                                    │                    │
                                                    └──chacha()───┬─► new_key
                                                                  └─► random_bytes
                                                                            │
                                                                            └────►
      
      There are a few hairy details around early init. Just as was done
      before, prior to having gathered enough entropy, crng_fast_load() and
      crng_slow_load() dump bytes directly into the base crng, and when we go
      to take bytes from the crng, in that case, we're doing fast key erasure
      with the base crng rather than the fast unlocked per-cpu crngs. This is
      fine as that's only the state of affairs during very early boot; once
      the crng initializes we never use these paths again.
      
      In the process of all this, the APIs into the crng become a bit simpler:
      we have get_random_bytes(buf, len) and get_random_bytes_user(buf, len),
      which both do what you'd expect. All of the details of fast key erasure
      and per-cpu selection happen only in a very short critical section of
      crng_make_state(), which selects the right per-cpu key, does the fast
      key erasure, and returns a local state to the caller's stack. So, we no
      longer have a need for a separate backtrack function, as this happens
      all at once here. The API then allows us to extend backtrack protection
      to batched entropy without really having to do much at all.
      
      The result is a bit simpler than before and has fewer foot guns. The
      init time state machine also gets a lot simpler as we don't need to wait
      for workqueues to come online and do deferred work. And the multi-core
      performance should be increased significantly, by virtue of having hardly
      any locking on the fast path.
      
      Cc: Theodore Ts'o <tytso@mit.edu>
      Cc: Dominik Brodowski <linux@dominikbrodowski.net>
      Cc: Sebastian Andrzej Siewior <bigeasy@linutronix.de>
      Reviewed-by: default avatarJann Horn <jannh@google.com>
      Reviewed-by: default avatarEric Biggers <ebiggers@google.com>
      Signed-off-by: default avatarJason A. Donenfeld <Jason@zx2c4.com>
      186873c5
    • Jason A. Donenfeld's avatar
      random: absorb fast pool into input pool after fast load · c30c575d
      Jason A. Donenfeld authored
      During crng_init == 0, we never credit entropy in add_interrupt_
      randomness(), but instead dump it directly into the primary_crng. That's
      fine, except for the fact that we then wind up throwing away that
      entropy later when we switch to extracting from the input pool and
      xoring into (and later in this series overwriting) the primary_crng key.
      The two other early init sites -- add_hwgenerator_randomness()'s use
      crng_fast_load() and add_device_ randomness()'s use of crng_slow_load()
      -- always additionally give their inputs to the input pool. But not
      add_interrupt_randomness().
      
      This commit fixes that shortcoming by calling mix_pool_bytes() after
      crng_fast_load() in add_interrupt_randomness(). That's partially
      verboten on PREEMPT_RT, where it implies taking spinlock_t from an IRQ
      handler. But this also only happens during early boot and then never
      again after that. Plus it's a trylock so it has the same considerations
      as calling crng_fast_load(), which we're already using.
      
      Cc: Theodore Ts'o <tytso@mit.edu>
      Reviewed-by: default avatarDominik Brodowski <linux@dominikbrodowski.net>
      Reviewed-by: default avatarEric Biggers <ebiggers@google.com>
      Suggested-by: default avatarEric Biggers <ebiggers@google.com>
      Signed-off-by: default avatarJason A. Donenfeld <Jason@zx2c4.com>
      c30c575d
    • Jason A. Donenfeld's avatar
      random: do not xor RDRAND when writing into /dev/random · 91c2afca
      Jason A. Donenfeld authored
      Continuing the reasoning of "random: ensure early RDSEED goes through
      mixer on init", we don't want RDRAND interacting with anything without
      going through the mixer function, as a backdoored CPU could presumably
      cancel out data during an xor, which it'd have a harder time doing when
      being forced through a cryptographic hash function. There's actually no
      need at all to be calling RDRAND in write_pool(), because before we
      extract from the pool, we always do so with 32 bytes of RDSEED hashed in
      at that stage. Xoring at this stage is needless and introduces a minor
      liability.
      
      Cc: Theodore Ts'o <tytso@mit.edu>
      Reviewed-by: default avatarDominik Brodowski <linux@dominikbrodowski.net>
      Reviewed-by: default avatarEric Biggers <ebiggers@google.com>
      Signed-off-by: default avatarJason A. Donenfeld <Jason@zx2c4.com>
      91c2afca
    • Jason A. Donenfeld's avatar
      random: ensure early RDSEED goes through mixer on init · a02cf3d0
      Jason A. Donenfeld authored
      Continuing the reasoning of "random: use RDSEED instead of RDRAND in
      entropy extraction" from this series, at init time we also don't want to
      be xoring RDSEED directly into the crng. Instead it's safer to put it
      into our entropy collector and then re-extract it, so that it goes
      through a hash function with preimage resistance. As a matter of hygiene,
      we also order these now so that the RDSEED byte are hashed in first,
      followed by the bytes that are likely more predictable (e.g. utsname()).
      
      Cc: Theodore Ts'o <tytso@mit.edu>
      Reviewed-by: default avatarDominik Brodowski <linux@dominikbrodowski.net>
      Reviewed-by: default avatarEric Biggers <ebiggers@google.com>
      Signed-off-by: default avatarJason A. Donenfeld <Jason@zx2c4.com>
      a02cf3d0
    • Jason A. Donenfeld's avatar
      random: inline leaves of rand_initialize() · 85664172
      Jason A. Donenfeld authored
      This is a preparatory commit for the following one. We simply inline the
      various functions that rand_initialize() calls that have no other
      callers. The compiler was doing this anyway before. Doing this will
      allow us to reorganize this after. We can then move the trust_cpu and
      parse_trust_cpu definitions a bit closer to where they're actually used,
      which makes the code easier to read.
      
      Cc: Theodore Ts'o <tytso@mit.edu>
      Reviewed-by: default avatarDominik Brodowski <linux@dominikbrodowski.net>
      Reviewed-by: default avatarEric Biggers <ebiggers@google.com>
      Signed-off-by: default avatarJason A. Donenfeld <Jason@zx2c4.com>
      85664172
    • Jason A. Donenfeld's avatar
      random: get rid of secondary crngs · a9412d51
      Jason A. Donenfeld authored
      As the comment said, this is indeed a "hack". Since it was introduced,
      it's been a constant state machine nightmare, with lots of subtle early
      boot issues and a wildly complex set of machinery to keep everything in
      sync. Rather than continuing to play whack-a-mole with this approach,
      this commit simply removes it entirely. This commit is preparation for
      "random: use simpler fast key erasure flow on per-cpu keys" in this
      series, which introduces a simpler (and faster) mechanism to accomplish
      the same thing.
      
      Cc: Theodore Ts'o <tytso@mit.edu>
      Reviewed-by: default avatarEric Biggers <ebiggers@google.com>
      Reviewed-by: default avatarDominik Brodowski <linux@dominikbrodowski.net>
      Signed-off-by: default avatarJason A. Donenfeld <Jason@zx2c4.com>
      a9412d51
    • Jason A. Donenfeld's avatar
      random: use RDSEED instead of RDRAND in entropy extraction · 28f425e5
      Jason A. Donenfeld authored
      When /dev/random was directly connected with entropy extraction, without
      any expansion stage, extract_buf() was called for every 10 bytes of data
      read from /dev/random. For that reason, RDRAND was used rather than
      RDSEED. At the same time, crng_reseed() was still only called every 5
      minutes, so there RDSEED made sense.
      
      Those olden days were also a time when the entropy collector did not use
      a cryptographic hash function, which meant most bets were off in terms
      of real preimage resistance. For that reason too it didn't matter
      _that_ much whether RDSEED was mixed in before or after entropy
      extraction; both choices were sort of bad.
      
      But now we have a cryptographic hash function at work, and with that we
      get real preimage resistance. We also now only call extract_entropy()
      every 5 minutes, rather than every 10 bytes. This allows us to do two
      important things.
      
      First, we can switch to using RDSEED in extract_entropy(), as Dominik
      suggested. Second, we can ensure that RDSEED input always goes into the
      cryptographic hash function with other things before being used
      directly. This eliminates a category of attacks in which the CPU knows
      the current state of the crng and knows that we're going to xor RDSEED
      into it, and so it computes a malicious RDSEED. By going through our
      hash function, it would require the CPU to compute a preimage on the
      fly, which isn't going to happen.
      
      Cc: Theodore Ts'o <tytso@mit.edu>
      Reviewed-by: default avatarEric Biggers <ebiggers@google.com>
      Reviewed-by: default avatarDominik Brodowski <linux@dominikbrodowski.net>
      Suggested-by: default avatarDominik Brodowski <linux@dominikbrodowski.net>
      Signed-off-by: default avatarJason A. Donenfeld <Jason@zx2c4.com>
      28f425e5
    • Dominik Brodowski's avatar
      random: fix locking in crng_fast_load() · 7c2fe2b3
      Dominik Brodowski authored
      crng_init is protected by primary_crng->lock, so keep holding that lock
      when incrementing crng_init from 0 to 1 in crng_fast_load(). The call to
      pr_notice() can wait until the lock is released; this code path cannot
      be reached twice, as crng_fast_load() aborts early if crng_init > 0.
      Signed-off-by: default avatarDominik Brodowski <linux@dominikbrodowski.net>
      Reviewed-by: default avatarEric Biggers <ebiggers@google.com>
      Signed-off-by: default avatarJason A. Donenfeld <Jason@zx2c4.com>
      7c2fe2b3
    • Jason A. Donenfeld's avatar
      random: remove batched entropy locking · 77760fd7
      Jason A. Donenfeld authored
      Rather than use spinlocks to protect batched entropy, we can instead
      disable interrupts locally, since we're dealing with per-cpu data, and
      manage resets with a basic generation counter. At the same time, we
      can't quite do this on PREEMPT_RT, where we still want spinlocks-as-
      mutexes semantics. So we use a local_lock_t, which provides the right
      behavior for each. Because this is a per-cpu lock, that generation
      counter is still doing the necessary CPU-to-CPU communication.
      
      This should improve performance a bit. It will also fix the linked splat
      that Jonathan received with a PROVE_RAW_LOCK_NESTING=y.
      Reviewed-by: default avatarSebastian Andrzej Siewior <bigeasy@linutronix.de>
      Reviewed-by: default avatarDominik Brodowski <linux@dominikbrodowski.net>
      Reviewed-by: default avatarEric Biggers <ebiggers@google.com>
      Suggested-by: default avatarAndy Lutomirski <luto@kernel.org>
      Reported-by: default avatarJonathan Neuschäfer <j.neuschaefer@gmx.net>
      Tested-by: default avatarJonathan Neuschäfer <j.neuschaefer@gmx.net>
      Link: https://lore.kernel.org/lkml/YfMa0QgsjCVdRAvJ@latitude/Signed-off-by: default avatarJason A. Donenfeld <Jason@zx2c4.com>
      77760fd7
    • Eric Biggers's avatar
      random: remove use_input_pool parameter from crng_reseed() · 5d58ea3a
      Eric Biggers authored
      The primary_crng is always reseeded from the input_pool, while the NUMA
      crngs are always reseeded from the primary_crng.  Remove the redundant
      'use_input_pool' parameter from crng_reseed() and just directly check
      whether the crng is the primary_crng.
      Signed-off-by: default avatarEric Biggers <ebiggers@google.com>
      Signed-off-by: default avatarJason A. Donenfeld <Jason@zx2c4.com>
      5d58ea3a
    • Jason A. Donenfeld's avatar
      random: make credit_entropy_bits() always safe · a49c010e
      Jason A. Donenfeld authored
      This is called from various hwgenerator drivers, so rather than having
      one "safe" version for userspace and one "unsafe" version for the
      kernel, just make everything safe; the checks are cheap and sensible to
      have anyway.
      Reported-by: default avatarSultan Alsawaf <sultan@kerneltoast.com>
      Reviewed-by: default avatarEric Biggers <ebiggers@google.com>
      Reviewed-by: default avatarDominik Brodowski <linux@dominikbrodowski.net>
      Signed-off-by: default avatarJason A. Donenfeld <Jason@zx2c4.com>
      a49c010e
    • Jason A. Donenfeld's avatar
      random: always wake up entropy writers after extraction · 489c7fc4
      Jason A. Donenfeld authored
      Now that POOL_BITS == POOL_MIN_BITS, we must unconditionally wake up
      entropy writers after every extraction. Therefore there's no point of
      write_wakeup_threshold, so we can move it to the dustbin of unused
      compatibility sysctls. While we're at it, we can fix a small comparison
      where we were waking up after <= min rather than < min.
      
      Cc: Theodore Ts'o <tytso@mit.edu>
      Suggested-by: default avatarEric Biggers <ebiggers@kernel.org>
      Reviewed-by: default avatarEric Biggers <ebiggers@google.com>
      Reviewed-by: default avatarDominik Brodowski <linux@dominikbrodowski.net>
      Signed-off-by: default avatarJason A. Donenfeld <Jason@zx2c4.com>
      489c7fc4
    • Jason A. Donenfeld's avatar
      random: use linear min-entropy accumulation crediting · c5704490
      Jason A. Donenfeld authored
      30e37ec5 ("random: account for entropy loss due to overwrites")
      assumed that adding new entropy to the LFSR pool probabilistically
      cancelled out old entropy there, so entropy was credited asymptotically,
      approximating Shannon entropy of independent sources (rather than a
      stronger min-entropy notion) using 1/8th fractional bits and replacing
      a constant 2-2/√𝑒 term (~0.786938) with 3/4 (0.75) to slightly
      underestimate it. This wasn't superb, but it was perhaps better than
      nothing, so that's what was done. Which entropy specifically was being
      cancelled out and how much precisely each time is hard to tell, though
      as I showed with the attack code in my previous commit, a motivated
      adversary with sufficient information can actually cancel out
      everything.
      
      Since we're no longer using an LFSR for entropy accumulation, this
      probabilistic cancellation is no longer relevant. Rather, we're now
      using a computational hash function as the accumulator and we've
      switched to working in the random oracle model, from which we can now
      revisit the question of min-entropy accumulation, which is done in
      detail in <https://eprint.iacr.org/2019/198>.
      
      Consider a long input bit string that is built by concatenating various
      smaller independent input bit strings. Each one of these inputs has a
      designated min-entropy, which is what we're passing to
      credit_entropy_bits(h). When we pass the concatenation of these to a
      random oracle, it means that an adversary trying to receive back the
      same reply as us would need to become certain about each part of the
      concatenated bit string we passed in, which means becoming certain about
      all of those h values. That means we can estimate the accumulation by
      simply adding up the h values in calls to credit_entropy_bits(h);
      there's no probabilistic cancellation at play like there was said to be
      for the LFSR. Incidentally, this is also what other entropy accumulators
      based on computational hash functions do as well.
      
      So this commit replaces credit_entropy_bits(h) with essentially `total =
      min(POOL_BITS, total + h)`, done with a cmpxchg loop as before.
      
      What if we're wrong and the above is nonsense? It's not, but let's
      assume we don't want the actual _behavior_ of the code to change much.
      Currently that behavior is not extracting from the input pool until it
      has 128 bits of entropy in it. With the old algorithm, we'd hit that
      magic 128 number after roughly 256 calls to credit_entropy_bits(1). So,
      we can retain more or less the old behavior by waiting to extract from
      the input pool until it hits 256 bits of entropy using the new code. For
      people concerned about this change, it means that there's not that much
      practical behavioral change. And for folks actually trying to model
      the behavior rigorously, it means that we have an even higher margin
      against attacks.
      
      Cc: Theodore Ts'o <tytso@mit.edu>
      Cc: Dominik Brodowski <linux@dominikbrodowski.net>
      Cc: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
      Reviewed-by: default avatarEric Biggers <ebiggers@google.com>
      Reviewed-by: default avatarJean-Philippe Aumasson <jeanphilippe.aumasson@gmail.com>
      Signed-off-by: default avatarJason A. Donenfeld <Jason@zx2c4.com>
      c5704490
    • Jason A. Donenfeld's avatar
      random: simplify entropy debiting · 9c07f578
      Jason A. Donenfeld authored
      Our pool is 256 bits, and we only ever use all of it or don't use it at
      all, which is decided by whether or not it has at least 128 bits in it.
      So we can drastically simplify the accounting and cmpxchg loop to do
      exactly this.  While we're at it, we move the minimum bit size into a
      constant so it can be shared between the two places where it matters.
      
      The reason we want any of this is for the case in which an attacker has
      compromised the current state, and then bruteforces small amounts of
      entropy added to it. By demanding a particular minimum amount of entropy
      be present before reseeding, we make that bruteforcing difficult.
      
      Note that this rationale no longer includes anything about /dev/random
      blocking at the right moment, since /dev/random no longer blocks (except
      for at ~boot), but rather uses the crng. In a former life, /dev/random
      was different and therefore required a more nuanced account(), but this
      is no longer.
      
      Behaviorally, nothing changes here. This is just a simplification of
      the code.
      
      Cc: Theodore Ts'o <tytso@mit.edu>
      Cc: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
      Reviewed-by: default avatarEric Biggers <ebiggers@google.com>
      Reviewed-by: default avatarDominik Brodowski <linux@dominikbrodowski.net>
      Signed-off-by: default avatarJason A. Donenfeld <Jason@zx2c4.com>
      9c07f578
    • Jason A. Donenfeld's avatar
      random: use computational hash for entropy extraction · 6e8ec255
      Jason A. Donenfeld authored
      The current 4096-bit LFSR used for entropy collection had a few
      desirable attributes for the context in which it was created. For
      example, the state was huge, which meant that /dev/random would be able
      to output quite a bit of accumulated entropy before blocking. It was
      also, in its time, quite fast at accumulating entropy byte-by-byte,
      which matters given the varying contexts in which mix_pool_bytes() is
      called. And its diffusion was relatively high, which meant that changes
      would ripple across several words of state rather quickly.
      
      However, it also suffers from a few security vulnerabilities. In
      particular, inputs learned by an attacker can be undone, but moreover,
      if the state of the pool leaks, its contents can be controlled and
      entirely zeroed out. I've demonstrated this attack with this SMT2
      script, <https://xn--4db.cc/5o9xO8pb>, which Boolector/CaDiCal solves in
      a matter of seconds on a single core of my laptop, resulting in little
      proof of concept C demonstrators such as <https://xn--4db.cc/jCkvvIaH/c>.
      
      For basically all recent formal models of RNGs, these attacks represent
      a significant cryptographic flaw. But how does this manifest
      practically? If an attacker has access to the system to such a degree
      that he can learn the internal state of the RNG, arguably there are
      other lower hanging vulnerabilities -- side-channel, infoleak, or
      otherwise -- that might have higher priority. On the other hand, seed
      files are frequently used on systems that have a hard time generating
      much entropy on their own, and these seed files, being files, often leak
      or are duplicated and distributed accidentally, or are even seeded over
      the Internet intentionally, where their contents might be recorded or
      tampered with. Seen this way, an otherwise quasi-implausible
      vulnerability is a bit more practical than initially thought.
      
      Another aspect of the current mix_pool_bytes() function is that, while
      its performance was arguably competitive for the time in which it was
      created, it's no longer considered so. This patch improves performance
      significantly: on a high-end CPU, an i7-11850H, it improves performance
      of mix_pool_bytes() by 225%, and on a low-end CPU, a Cortex-A7, it
      improves performance by 103%.
      
      This commit replaces the LFSR of mix_pool_bytes() with a straight-
      forward cryptographic hash function, BLAKE2s, which is already in use
      for pool extraction. Universal hashing with a secret seed was considered
      too, something along the lines of <https://eprint.iacr.org/2013/338>,
      but the requirement for a secret seed makes for a chicken & egg problem.
      Instead we go with a formally proven scheme using a computational hash
      function, described in sections 5.1, 6.4, and B.1.8 of
      <https://eprint.iacr.org/2019/198>.
      
      BLAKE2s outputs 256 bits, which should give us an appropriate amount of
      min-entropy accumulation, and a wide enough margin of collision
      resistance against active attacks. mix_pool_bytes() becomes a simple
      call to blake2s_update(), for accumulation, while the extraction step
      becomes a blake2s_final() to generate a seed, with which we can then do
      a HKDF-like or BLAKE2X-like expansion, the first part of which we fold
      back as an init key for subsequent blake2s_update()s, and the rest we
      produce to the caller. This then is provided to our CRNG like usual. In
      that expansion step, we make opportunistic use of 32 bytes of RDRAND
      output, just as before. We also always reseed the crng with 32 bytes,
      unconditionally, or not at all, rather than sometimes with 16 as before,
      as we don't win anything by limiting beyond the 16 byte threshold.
      
      Going for a hash function as an entropy collector is a conservative,
      proven approach. The result of all this is a much simpler and much less
      bespoke construction than what's there now, which not only plugs a
      vulnerability but also improves performance considerably.
      
      Cc: Theodore Ts'o <tytso@mit.edu>
      Cc: Dominik Brodowski <linux@dominikbrodowski.net>
      Reviewed-by: default avatarEric Biggers <ebiggers@google.com>
      Reviewed-by: default avatarGreg Kroah-Hartman <gregkh@linuxfoundation.org>
      Reviewed-by: default avatarJean-Philippe Aumasson <jeanphilippe.aumasson@gmail.com>
      Signed-off-by: default avatarJason A. Donenfeld <Jason@zx2c4.com>
      6e8ec255
  2. 20 Feb, 2022 13 commits
  3. 19 Feb, 2022 5 commits