1. 27 Jan, 2017 2 commits
    • Jason A. Donenfeld's avatar
      random: convert get_random_int/long into get_random_u32/u64 · c440408c
      Jason A. Donenfeld authored
      Many times, when a user wants a random number, he wants a random number
      of a guaranteed size. So, thinking of get_random_int and get_random_long
      in terms of get_random_u32 and get_random_u64 makes it much easier to
      achieve this. It also makes the code simpler.
      
      On 32-bit platforms, get_random_int and get_random_long are both aliased
      to get_random_u32. On 64-bit platforms, int->u32 and long->u64.
      Signed-off-by: default avatarJason A. Donenfeld <Jason@zx2c4.com>
      Cc: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
      Cc: Theodore Ts'o <tytso@mit.edu>
      Signed-off-by: default avatarTheodore Ts'o <tytso@mit.edu>
      c440408c
    • Jason A. Donenfeld's avatar
      random: use chacha20 for get_random_int/long · f5b98461
      Jason A. Donenfeld authored
      Now that our crng uses chacha20, we can rely on its speedy
      characteristics for replacing MD5, while simultaneously achieving a
      higher security guarantee. Before the idea was to use these functions if
      you wanted random integers that aren't stupidly insecure but aren't
      necessarily secure either, a vague gray zone, that hopefully was "good
      enough" for its users. With chacha20, we can strengthen this claim,
      since either we're using an rdrand-like instruction, or we're using the
      same crng as /dev/urandom. And it's faster than what was before.
      
      We could have chosen to replace this with a SipHash-derived function,
      which might be slightly faster, but at the cost of having yet another
      RNG construction in the kernel. By moving to chacha20, we have a single
      RNG to analyze and verify, and we also already get good performance
      improvements on all platforms.
      
      Implementation-wise, rather than use a generic buffer for both
      get_random_int/long and memcpy based on the size needs, we use a
      specific buffer for 32-bit reads and for 64-bit reads. This way, we're
      guaranteed to always have aligned accesses on all platforms. While
      slightly more verbose in C, the assembly this generates is a lot
      simpler than otherwise.
      
      Finally, on 32-bit platforms where longs and ints are the same size,
      we simply alias get_random_int to get_random_long.
      Signed-off-by: default avatarJason A. Donenfeld <Jason@zx2c4.com>
      Suggested-by: default avatarTheodore Ts'o <tytso@mit.edu>
      Cc: Theodore Ts'o <tytso@mit.edu>
      Cc: Hannes Frederic Sowa <hannes@stressinduktion.org>
      Cc: Andy Lutomirski <luto@amacapital.net>
      Signed-off-by: default avatarTheodore Ts'o <tytso@mit.edu>
      f5b98461
  2. 11 Oct, 2016 2 commits
    • Jason Cooper's avatar
      random: remove unused randomize_range() · 7425154d
      Jason Cooper authored
      All call sites for randomize_range have been updated to use the much
      simpler and more robust randomize_addr().  Remove the now unnecessary
      code.
      
      Link: http://lkml.kernel.org/r/20160803233913.32511-8-jason@lakedaemon.netSigned-off-by: default avatarJason Cooper <jason@lakedaemon.net>
      Acked-by: default avatarKees Cook <keescook@chromium.org>
      Cc: "Theodore Ts'o" <tytso@mit.edu>
      Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
      7425154d
    • Jason Cooper's avatar
      random: simplify API for random address requests · 99fdafde
      Jason Cooper authored
      To date, all callers of randomize_range() have set the length to 0, and
      check for a zero return value.  For the current callers, the only way to
      get zero returned is if end <= start.  Since they are all adding a
      constant to the start address, this is unnecessary.
      
      We can remove a bunch of needless checks by simplifying the API to do just
      what everyone wants, return an address between [start, start + range).
      
      While we're here, s/get_random_int/get_random_long/.  No current call site
      is adversely affected by get_random_int(), since all current range
      requests are < UINT_MAX.  However, we should match caller expectations to
      avoid coming up short (ha!) in the future.
      
      All current callers to randomize_range() chose to use the start address if
      randomize_range() failed.  Therefore, we simplify things by just returning
      the start address on error.
      
      randomize_range() will be removed once all callers have been converted
      over to randomize_addr().
      
      Link: http://lkml.kernel.org/r/20160803233913.32511-2-jason@lakedaemon.netSigned-off-by: default avatarJason Cooper <jason@lakedaemon.net>
      Acked-by: default avatarKees Cook <keescook@chromium.org>
      Cc: Michael Ellerman <mpe@ellerman.id.au>
      Cc: "Roberts, William C" <william.c.roberts@intel.com>
      Cc: Yann Droneaud <ydroneaud@opteya.com>
      Cc: Russell King <linux@arm.linux.org.uk>
      Cc: "Theodore Ts'o" <tytso@mit.edu>
      Cc: Arnd Bergmann <arnd@arndb.de>
      Cc: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
      Cc: Catalin Marinas <catalin.marinas@arm.com>
      Cc: Will Deacon <will.deacon@arm.com>
      Cc: Ralf Baechle <ralf@linux-mips.org>
      Cc: Benjamin Herrenschmidt <benh@kernel.crashing.org>
      Cc: Paul Mackerras <paulus@samba.org>
      Cc: "David S. Miller" <davem@davemloft.net>
      Cc: Thomas Gleixner <tglx@linutronix.de>
      Cc: Ingo Molnar <mingo@redhat.com>
      Cc: "H . Peter Anvin" <hpa@zytor.com>
      Cc: Nick Kralevich <nnk@google.com>
      Cc: Jeffrey Vander Stoep <jeffv@google.com>
      Cc: Daniel Cashman <dcashman@android.com>
      Cc: Chris Metcalf <cmetcalf@mellanox.com>
      Cc: Guan Xuetao <gxt@mprc.pku.edu.cn>
      Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
      99fdafde
  3. 10 Oct, 2016 2 commits
    • Emese Revfy's avatar
      latent_entropy: Mark functions with __latent_entropy · 0766f788
      Emese Revfy authored
      The __latent_entropy gcc attribute can be used only on functions and
      variables.  If it is on a function then the plugin will instrument it for
      gathering control-flow entropy. If the attribute is on a variable then
      the plugin will initialize it with random contents.  The variable must
      be an integer, an integer array type or a structure with integer fields.
      
      These specific functions have been selected because they are init
      functions (to help gather boot-time entropy), are called at unpredictable
      times, or they have variable loops, each of which provide some level of
      latent entropy.
      Signed-off-by: default avatarEmese Revfy <re.emese@gmail.com>
      [kees: expanded commit message]
      Signed-off-by: default avatarKees Cook <keescook@chromium.org>
      0766f788
    • Emese Revfy's avatar
      gcc-plugins: Add latent_entropy plugin · 38addce8
      Emese Revfy authored
      This adds a new gcc plugin named "latent_entropy". It is designed to
      extract as much possible uncertainty from a running system at boot time as
      possible, hoping to capitalize on any possible variation in CPU operation
      (due to runtime data differences, hardware differences, SMP ordering,
      thermal timing variation, cache behavior, etc).
      
      At the very least, this plugin is a much more comprehensive example for
      how to manipulate kernel code using the gcc plugin internals.
      
      The need for very-early boot entropy tends to be very architecture or
      system design specific, so this plugin is more suited for those sorts
      of special cases. The existing kernel RNG already attempts to extract
      entropy from reliable runtime variation, but this plugin takes the idea to
      a logical extreme by permuting a global variable based on any variation
      in code execution (e.g. a different value (and permutation function)
      is used to permute the global based on loop count, case statement,
      if/then/else branching, etc).
      
      To do this, the plugin starts by inserting a local variable in every
      marked function. The plugin then adds logic so that the value of this
      variable is modified by randomly chosen operations (add, xor and rol) and
      random values (gcc generates separate static values for each location at
      compile time and also injects the stack pointer at runtime). The resulting
      value depends on the control flow path (e.g., loops and branches taken).
      
      Before the function returns, the plugin mixes this local variable into
      the latent_entropy global variable. The value of this global variable
      is added to the kernel entropy pool in do_one_initcall() and _do_fork(),
      though it does not credit any bytes of entropy to the pool; the contents
      of the global are just used to mix the pool.
      
      Additionally, the plugin can pre-initialize arrays with build-time
      random contents, so that two different kernel builds running on identical
      hardware will not have the same starting values.
      Signed-off-by: default avatarEmese Revfy <re.emese@gmail.com>
      [kees: expanded commit message and code comments]
      Signed-off-by: default avatarKees Cook <keescook@chromium.org>
      38addce8
  4. 08 Jun, 2016 1 commit
  5. 21 May, 2016 1 commit
  6. 27 Feb, 2016 1 commit
    • Daniel Cashman's avatar
      drivers: char: random: add get_random_long() · ec9ee4ac
      Daniel Cashman authored
      Commit d07e2259 ("mm: mmap: add new /proc tunable for mmap_base
      ASLR") added the ability to choose from a range of values to use for
      entropy count in generating the random offset to the mmap_base address.
      
      The maximum value on this range was set to 32 bits for 64-bit x86
      systems, but this value could be increased further, requiring more than
      the 32 bits of randomness provided by get_random_int(), as is already
      possible for arm64.  Add a new function: get_random_long() which more
      naturally fits with the mmap usage of get_random_int() but operates
      exactly the same as get_random_int().
      
      Also, fix the shifting constant in mmap_rnd() to be an unsigned long so
      that values greater than 31 bits generate an appropriate mask without
      overflow.  This is especially important on x86, as its shift instruction
      uses a 5-bit mask for the shift operand, which meant that any value for
      mmap_rnd_bits over 31 acts as a no-op and effectively disables mmap_base
      randomization.
      
      Finally, replace calls to get_random_int() with get_random_long() where
      appropriate.
      
      This patch (of 2):
      
      Add get_random_long().
      Signed-off-by: default avatarDaniel Cashman <dcashman@android.com>
      Acked-by: default avatarKees Cook <keescook@chromium.org>
      Cc: "Theodore Ts'o" <tytso@mit.edu>
      Cc: Arnd Bergmann <arnd@arndb.de>
      Cc: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
      Cc: Catalin Marinas <catalin.marinas@arm.com>
      Cc: Will Deacon <will.deacon@arm.com>
      Cc: Ralf Baechle <ralf@linux-mips.org>
      Cc: Benjamin Herrenschmidt <benh@kernel.crashing.org>
      Cc: Paul Mackerras <paulus@samba.org>
      Cc: Michael Ellerman <mpe@ellerman.id.au>
      Cc: David S. Miller <davem@davemloft.net>
      Cc: Thomas Gleixner <tglx@linutronix.de>
      Cc: Ingo Molnar <mingo@redhat.com>
      Cc: H. Peter Anvin <hpa@zytor.com>
      Cc: Al Viro <viro@zeniv.linux.org.uk>
      Cc: Nick Kralevich <nnk@google.com>
      Cc: Jeff Vander Stoep <jeffv@google.com>
      Cc: Mark Salyzyn <salyzyn@android.com>
      Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
      ec9ee4ac
  7. 08 Oct, 2015 1 commit
  8. 10 Jun, 2015 2 commits
    • Herbert Xu's avatar
      random: Remove kernel blocking API · c2719503
      Herbert Xu authored
      This patch removes the kernel blocking API as it has been completely
      replaced by the callback API.
      Signed-off-by: default avatarHerbert Xu <herbert@gondor.apana.org.au>
      c2719503
    • Herbert Xu's avatar
      random: Add callback API for random pool readiness · 205a525c
      Herbert Xu authored
      The get_blocking_random_bytes API is broken because the wait can
      be arbitrarily long (potentially forever) so there is no safe way
      of calling it from within the kernel.
      
      This patch replaces it with a callback API instead.  The callback
      is invoked potentially from interrupt context so the user needs
      to schedule their own work thread if necessary.
      
      In addition to adding callbacks, they can also be removed as
      otherwise this opens up a way for user-space to allocate kernel
      memory with no bound (by opening algif_rng descriptors and then
      closing them).
      Signed-off-by: default avatarHerbert Xu <herbert@gondor.apana.org.au>
      205a525c
  9. 27 May, 2015 1 commit
  10. 25 Aug, 2014 1 commit
    • Daniel Borkmann's avatar
      random32: improvements to prandom_bytes · a98406e2
      Daniel Borkmann authored
      This patch addresses a couple of minor items, mostly addesssing
      prandom_bytes(): 1) prandom_bytes{,_state}() should use size_t
      for length arguments, 2) We can use put_unaligned() when filling
      the array instead of open coding it [ perhaps some archs will
      further benefit from their own arch specific implementation when
      GCC cannot make up for it ], 3) Fix a typo, 4) Better use unsigned
      int as type for getting the arch seed, 5) Make use of
      prandom_u32_max() for timer slack.
      
      Regarding the change to put_unaligned(), callers of prandom_bytes()
      which internally invoke prandom_bytes_state(), don't bother as
      they expect the array to be filled randomly and don't have any
      control of the internal state what-so-ever (that's also why we
      have periodic reseeding there, etc), so they really don't care.
      
      Now for the direct callers of prandom_bytes_state(), which
      are solely located in test cases for MTD devices, that is,
      drivers/mtd/tests/{oobtest.c,pagetest.c,subpagetest.c}:
      
      These tests basically fill a test write-vector through
      prandom_bytes_state() with an a-priori defined seed each time
      and write that to a MTD device. Later on, they set up a read-vector
      and read back that blocks from the device. So in the verification
      phase, the write-vector is being re-setup [ so same seed and
      prandom_bytes_state() called ], and then memcmp()'ed against the
      read-vector to check if the data is the same.
      
      Akinobu, Lothar and I also tested this patch and it runs through
      the 3 relevant MTD test cases w/o any errors on the nandsim device
      (simulator for MTD devs) for x86_64, ppc64, ARM (i.MX28, i.MX53
      and i.MX6):
      
        # modprobe nandsim first_id_byte=0x20 second_id_byte=0xac \
                           third_id_byte=0x00 fourth_id_byte=0x15
        # modprobe mtd_oobtest dev=0
        # modprobe mtd_pagetest dev=0
        # modprobe mtd_subpagetest dev=0
      
      We also don't have any users depending directly on a particular
      result of the PRNG (except the PRNG self-test itself), and that's
      just fine as it e.g. allowed us easily to do things like upgrading
      from taus88 to taus113.
      Signed-off-by: default avatarDaniel Borkmann <dborkman@redhat.com>
      Tested-by: default avatarAkinobu Mita <akinobu.mita@gmail.com>
      Tested-by: default avatarLothar Waßmann <LW@KARO-electronics.de>
      Cc: Hannes Frederic Sowa <hannes@stressinduktion.org>
      Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
      a98406e2
  11. 20 Mar, 2014 2 commits
    • H. Peter Anvin's avatar
      random: Add arch_has_random[_seed]() · 7b878d4b
      H. Peter Anvin authored
      Add predicate functions for having arch_get_random[_seed]*().  The
      only current use is to avoid the loop in arch_random_refill() when
      arch_get_random_seed_long() is unavailable.
      Signed-off-by: default avatarH. Peter Anvin <hpa@linux.intel.com>
      Cc: Benjamin Herrenschmidt <benh@kernel.crashing.org>
      Cc: Paul Mackerras <paulus@samba.org>
      Cc: Michael Ellerman <michael@ellerman.id.au>
      Signed-off-by: default avatarTheodore Ts'o <tytso@mit.edu>
      7b878d4b
    • H. Peter Anvin's avatar
      x86, random: Enable the RDSEED instruction · d20f78d2
      H. Peter Anvin authored
      Upcoming Intel silicon adds a new RDSEED instruction, which is similar
      to RDRAND but provides a stronger guarantee: unlike RDRAND, RDSEED
      will always reseed the PRNG from the true random number source between
      each read.  Thus, the output of RDSEED is guaranteed to be 100%
      entropic, unlike RDRAND which is only architecturally guaranteed to be
      1/512 entropic (although in practice is much more.)
      
      The RDSEED instruction takes the same time to execute as RDRAND, but
      RDSEED unlike RDRAND can legitimately return failure (CF=0) due to
      entropy exhaustion if too many threads on too many cores are hammering
      the RDSEED instruction at the same time.  Therefore, we have to be
      more conservative and only use it in places where we can tolerate
      failures.
      
      This patch introduces the primitives arch_get_random_seed_{int,long}()
      but does not use it yet.
      Signed-off-by: default avatarH. Peter Anvin <hpa@linux.intel.com>
      Reviewed-by: default avatarIngo Molnar <mingo@kernel.org>
      Cc: Benjamin Herrenschmidt <benh@kernel.crashing.org>
      Cc: Paul Mackerras <paulus@samba.org>
      Cc: Michael Ellerman <michael@ellerman.id.au>
      Signed-off-by: default avatarTheodore Ts'o <tytso@mit.edu>
      d20f78d2
  12. 22 Jan, 2014 1 commit
    • Daniel Borkmann's avatar
      random32: add prandom_u32_max and convert open coded users · f337db64
      Daniel Borkmann authored
      Many functions have open coded a function that returns a random
      number in range [0,N-1]. Under the assumption that we have a PRNG
      such as taus113 with being well distributed in [0, ~0U] space,
      we can implement such a function as uword t = (n*m')>>32, where
      m' is a random number obtained from PRNG, n the right open interval
      border and t our resulting random number, with n,m',t in u32 universe.
      
      Lets go with Joe and simply call it prandom_u32_max(), although
      technically we have an right open interval endpoint, but that we
      have documented. Other users can further be migrated to the new
      prandom_u32_max() function later on; for now, we need to make sure
      to migrate reciprocal_divide() users for the reciprocal_divide()
      follow-up fixup since their function signatures are going to change.
      
      Joint work with Hannes Frederic Sowa.
      
      Cc: Jakub Zawadzki <darkjames-ws@darkjames.pl>
      Cc: Eric Dumazet <eric.dumazet@gmail.com>
      Cc: linux-kernel@vger.kernel.org
      Signed-off-by: default avatarHannes Frederic Sowa <hannes@stressinduktion.org>
      Signed-off-by: default avatarDaniel Borkmann <dborkman@redhat.com>
      Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
      f337db64
  13. 11 Nov, 2013 4 commits
    • Daniel Borkmann's avatar
      random32: upgrade taus88 generator to taus113 from errata paper · a98814ce
      Daniel Borkmann authored
      Since we use prandom*() functions quite often in networking code
      i.e. in UDP port selection, netfilter code, etc, upgrade the PRNG
      from Pierre L'Ecuyer's original paper "Maximally Equidistributed
      Combined Tausworthe Generators", Mathematics of Computation, 65,
      213 (1996), 203--213 to the version published in his errata paper [1].
      
      The Tausworthe generator is a maximally-equidistributed generator,
      that is fast and has good statistical properties [1].
      
      The version presented there upgrades the 3 state LFSR to a 4 state
      LFSR with increased periodicity from about 2^88 to 2^113. The
      algorithm is presented in [1] by the very same author who also
      designed the original algorithm in [2].
      
      Also, by increasing the state, we make it a bit harder for attackers
      to "guess" the PRNGs internal state. See also discussion in [3].
      
      Now, as we use this sort of weak initialization discussed in [3]
      only between core_initcall() until late_initcall() time [*] for
      prandom32*() users, namely in prandom_init(), it is less relevant
      from late_initcall() onwards as we overwrite seeds through
      prandom_reseed() anyways with a seed source of higher entropy, that
      is, get_random_bytes(). In other words, a exhaustive keysearch of
      96 bit would be needed. Now, with the help of this patch, this
      state-search increases further to 128 bit. Initialization needs
      to make sure that s1 > 1, s2 > 7, s3 > 15, s4 > 127.
      
      taus88 and taus113 algorithm is also part of GSL. I added a test
      case in the next patch to verify internal behaviour of this patch
      with GSL and ran tests with the dieharder 3.31.1 RNG test suite:
      
      $ dieharder -g 052 -a -m 10 -s 1 -S 4137730333 #taus88
      $ dieharder -g 054 -a -m 10 -s 1 -S 4137730333 #taus113
      
      With this seed configuration, in order to compare both, we get
      the following differences:
      
      algorithm                 taus88           taus113
      rands/second [**]         1.61e+08         1.37e+08
      sts_serial(4, 1st run)    WEAK             PASSED
      sts_serial(9, 2nd run)    WEAK             PASSED
      rgb_lagged_sum(31)        WEAK             PASSED
      
      We took out diehard_sums test as according to the authors it is
      considered broken and unusable [4]. Despite that and the slight
      decrease in performance (which is acceptable), taus113 here passes
      all 113 tests (only rgb_minimum_distance_5 in WEAK, the rest PASSED).
      In general, taus/taus113 is considered "very good" by the authors
      of dieharder [5].
      
      The papers [1][2] states a single warm-up step is sufficient by
      running quicktaus once on each state to ensure proper initialization
      of ~s_{0}:
      
      Our selection of (s) according to Table 1 of [1] row 1 holds the
      condition L - k <= r - s, that is,
      
        (32 32 32 32) - (31 29 28 25) <= (25 27 15 22) - (18 2 7 13)
      
      with r = k - q and q = (6 2 13 3) as also stated by the paper.
      So according to [2] we are safe with one round of quicktaus for
      initialization. However we decided to include the warm-up phase
      of the PRNG as done in GSL in every case as a safety net. We also
      use the warm up phase to make the output of the RNG easier to
      verify by the GSL output.
      
      In prandom_init(), we also mix random_get_entropy() into it, just
      like drivers/char/random.c does it, jiffies ^ random_get_entropy().
      random-get_entropy() is get_cycles(). xor is entropy preserving so
      it is fine if it is not implemented by some architectures.
      
      Note, this PRNG is *not* used for cryptography in the kernel, but
      rather as a fast PRNG for various randomizations i.e. in the
      networking code, or elsewhere for debugging purposes, for example.
      
      [*]: In order to generate some "sort of pseduo-randomness", since
      get_random_bytes() is not yet available for us, we use jiffies and
      initialize states s1 - s3 with a simple linear congruential generator
      (LCG), that is x <- x * 69069; and derive s2, s3, from the 32bit
      initialization from s1. So the above quote from [3] accounts only
      for the time from core to late initcall, not afterwards.
      [**] Single threaded run on MacBook Air w/ Intel Core i5-3317U
      
       [1] http://www.iro.umontreal.ca/~lecuyer/myftp/papers/tausme2.ps
       [2] http://www.iro.umontreal.ca/~lecuyer/myftp/papers/tausme.ps
       [3] http://thread.gmane.org/gmane.comp.encryption.general/12103/
       [4] http://code.google.com/p/dieharder/source/browse/trunk/libdieharder/diehard_sums.c?spec=svn490&r=490#20
       [5] http://www.phy.duke.edu/~rgb/General/dieharder.php
      
      Joint work with Hannes Frederic Sowa.
      
      Cc: Florian Weimer <fweimer@redhat.com>
      Cc: Theodore Ts'o <tytso@mit.edu>
      Signed-off-by: default avatarDaniel Borkmann <dborkman@redhat.com>
      Signed-off-by: default avatarHannes Frederic Sowa <hannes@stressinduktion.org>
      Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
      a98814ce
    • Daniel Borkmann's avatar
      random32: move rnd_state to linux/random.h · 38e9efcd
      Daniel Borkmann authored
      struct rnd_state got mistakenly pulled into uapi header. It is not
      used anywhere and does also not belong there!
      
      Commit 5960164f ("lib/random32: export pseudo-random number
      generator for modules"), the last commit on rnd_state before it
      got moved to uapi, says:
      
        This patch moves the definition of struct rnd_state and the inline
        __seed() function to linux/random.h.  It renames the static __random32()
        function to prandom32() and exports it for use in modules.
      
      Hence, the structure was moved from lib/random32.c to linux/random.h
      so that it can be used within modules (FCoE-related code in this
      case), but not from user space. However, it seems to have been
      mistakenly moved to uapi header through the uapi script. Since no-one
      should make use of it from the linux headers, move the structure back
      to the kernel for internal use, so that it can be modified on demand.
      
      Joint work with Hannes Frederic Sowa.
      
      Cc: Joe Eykholt <jeykholt@cisco.com>
      Signed-off-by: default avatarDaniel Borkmann <dborkman@redhat.com>
      Signed-off-by: default avatarHannes Frederic Sowa <hannes@stressinduktion.org>
      Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
      38e9efcd
    • Hannes Frederic Sowa's avatar
      random32: add prandom_reseed_late() and call when nonblocking pool becomes initialized · 4af712e8
      Hannes Frederic Sowa authored
      The Tausworthe PRNG is initialized at late_initcall time. At that time the
      entropy pool serving get_random_bytes is not filled sufficiently. This
      patch adds an additional reseeding step as soon as the nonblocking pool
      gets marked as initialized.
      
      On some machines it might be possible that late_initcall gets called after
      the pool has been initialized. In this situation we won't reseed again.
      
      (A call to prandom_seed_late blocks later invocations of early reseed
      attempts.)
      
      Joint work with Daniel Borkmann.
      
      Cc: Eric Dumazet <eric.dumazet@gmail.com>
      Cc: Theodore Ts'o <tytso@mit.edu>
      Signed-off-by: default avatarHannes Frederic Sowa <hannes@stressinduktion.org>
      Signed-off-by: default avatarDaniel Borkmann <dborkman@redhat.com>
      Acked-by: default avatar"Theodore Ts'o" <tytso@mit.edu>
      Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
      4af712e8
    • Daniel Borkmann's avatar
      random32: fix off-by-one in seeding requirement · 51c37a70
      Daniel Borkmann authored
      For properly initialising the Tausworthe generator [1], we have
      a strict seeding requirement, that is, s1 > 1, s2 > 7, s3 > 15.
      
      Commit 697f8d03 ("random32: seeding improvement") introduced
      a __seed() function that imposes boundary checks proposed by the
      errata paper [2] to properly ensure above conditions.
      
      However, we're off by one, as the function is implemented as:
      "return (x < m) ? x + m : x;", and called with __seed(X, 1),
      __seed(X, 7), __seed(X, 15). Thus, an unwanted seed of 1, 7, 15
      would be possible, whereas the lower boundary should actually
      be of at least 2, 8, 16, just as GSL does. Fix this, as otherwise
      an initialization with an unwanted seed could have the effect
      that Tausworthe's PRNG properties cannot not be ensured.
      
      Note that this PRNG is *not* used for cryptography in the kernel.
      
       [1] http://www.iro.umontreal.ca/~lecuyer/myftp/papers/tausme.ps
       [2] http://www.iro.umontreal.ca/~lecuyer/myftp/papers/tausme2.ps
      
      Joint work with Hannes Frederic Sowa.
      
      Fixes: 697f8d03 ("random32: seeding improvement")
      Cc: Stephen Hemminger <stephen@networkplumber.org>
      Cc: Florian Weimer <fweimer@redhat.com>
      Cc: Theodore Ts'o <tytso@mit.edu>
      Signed-off-by: default avatarDaniel Borkmann <dborkman@redhat.com>
      Signed-off-by: default avatarHannes Frederic Sowa <hannes@stressinduktion.org>
      Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
      51c37a70
  14. 23 Sep, 2013 1 commit
  15. 08 May, 2013 1 commit
  16. 23 Jan, 2013 1 commit
  17. 18 Dec, 2012 2 commits
    • Akinobu Mita's avatar
      prandom: introduce prandom_bytes() and prandom_bytes_state() · 6582c665
      Akinobu Mita authored
      Add functions to get the requested number of pseudo-random bytes.
      
      The difference from get_random_bytes() is that it generates pseudo-random
      numbers by prandom_u32().  It doesn't consume the entropy pool, and the
      sequence is reproducible if the same rnd_state is used.  So it is suitable
      for generating random bytes for testing.
      Signed-off-by: default avatarAkinobu Mita <akinobu.mita@gmail.com>
      Cc: "Theodore Ts'o" <tytso@mit.edu>
      Cc: Artem Bityutskiy <dedekind1@gmail.com>
      Cc: Adrian Hunter <adrian.hunter@intel.com>
      Cc: David Woodhouse <dwmw2@infradead.org>
      Cc: Eilon Greenstein <eilong@broadcom.com>
      Cc: David Laight <david.laight@aculab.com>
      Cc: Michel Lespinasse <walken@google.com>
      Cc: Robert Love <robert.w.love@intel.com>
      Cc: Valdis Kletnieks <valdis.kletnieks@vt.edu>
      Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
      6582c665
    • Akinobu Mita's avatar
      random32: rename random32 to prandom · 496f2f93
      Akinobu Mita authored
      This renames all random32 functions to have 'prandom_' prefix as follows:
      
        void prandom_seed(u32 seed);	/* rename from srandom32() */
        u32 prandom_u32(void);		/* rename from random32() */
        void prandom_seed_state(struct rnd_state *state, u64 seed);
        				/* rename from prandom32_seed() */
        u32 prandom_u32_state(struct rnd_state *state);
        				/* rename from prandom32() */
      
      The purpose of this renaming is to prevent some kernel developers from
      assuming that prandom32() and random32() might imply that only
      prandom32() was the one using a pseudo-random number generator by
      prandom32's "p", and the result may be a very embarassing security
      exposure.  This concern was expressed by Theodore Ts'o.
      
      And furthermore, I'm going to introduce new functions for getting the
      requested number of pseudo-random bytes.  If I continue to use both
      prandom32 and random32 prefixes for these functions, the confusion
      is getting worse.
      
      As a result of this renaming, "prandom_" is the common prefix for
      pseudo-random number library.
      
      Currently, srandom32() and random32() are preserved because it is
      difficult to rename too many users at once.
      Signed-off-by: default avatarAkinobu Mita <akinobu.mita@gmail.com>
      Cc: "Theodore Ts'o" <tytso@mit.edu>
      Cc: Robert Love <robert.w.love@intel.com>
      Cc: Michel Lespinasse <walken@google.com>
      Cc: Valdis Kletnieks <valdis.kletnieks@vt.edu>
      Cc: David Laight <david.laight@aculab.com>
      Cc: Adrian Hunter <adrian.hunter@intel.com>
      Cc: Artem Bityutskiy <dedekind1@gmail.com>
      Cc: David Woodhouse <dwmw2@infradead.org>
      Cc: Eilon Greenstein <eilong@broadcom.com>
      Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
      496f2f93
  18. 13 Oct, 2012 1 commit
  19. 19 Jul, 2012 1 commit
  20. 15 Jul, 2012 3 commits
    • Theodore Ts'o's avatar
      random: add new get_random_bytes_arch() function · c2557a30
      Theodore Ts'o authored
      Create a new function, get_random_bytes_arch() which will use the
      architecture-specific hardware random number generator if it is
      present.  Change get_random_bytes() to not use the HW RNG, even if it
      is avaiable.
      
      The reason for this is that the hw random number generator is fast (if
      it is present), but it requires that we trust the hardware
      manufacturer to have not put in a back door.  (For example, an
      increasing counter encrypted by an AES key known to the NSA.)
      
      It's unlikely that Intel (for example) was paid off by the US
      Government to do this, but it's impossible for them to prove otherwise
      --- especially since Bull Mountain is documented to use AES as a
      whitener.  Hence, the output of an evil, trojan-horse version of
      RDRAND is statistically indistinguishable from an RDRAND implemented
      to the specifications claimed by Intel.  Short of using a tunnelling
      electronic microscope to reverse engineer an Ivy Bridge chip and
      disassembling and analyzing the CPU microcode, there's no way for us
      to tell for sure.
      
      Since users of get_random_bytes() in the Linux kernel need to be able
      to support hardware systems where the HW RNG is not present, most
      time-sensitive users of this interface have already created their own
      cryptographic RNG interface which uses get_random_bytes() as a seed.
      So it's much better to use the HW RNG to improve the existing random
      number generator, by mixing in any entropy returned by the HW RNG into
      /dev/random's entropy pool, but to always _use_ /dev/random's entropy
      pool.
      
      This way we get almost of the benefits of the HW RNG without any
      potential liabilities.  The only benefits we forgo is the
      speed/performance enhancements --- and generic kernel code can't
      depend on depend on get_random_bytes() having the speed of a HW RNG
      anyway.
      
      For those places that really want access to the arch-specific HW RNG,
      if it is available, we provide get_random_bytes_arch().
      Signed-off-by: default avatar"Theodore Ts'o" <tytso@mit.edu>
      Cc: stable@vger.kernel.org
      c2557a30
    • Linus Torvalds's avatar
      random: create add_device_randomness() interface · a2080a67
      Linus Torvalds authored
      Add a new interface, add_device_randomness() for adding data to the
      random pool that is likely to differ between two devices (or possibly
      even per boot).  This would be things like MAC addresses or serial
      numbers, or the read-out of the RTC. This does *not* add any actual
      entropy to the pool, but it initializes the pool to different values
      for devices that might otherwise be identical and have very little
      entropy available to them (particularly common in the embedded world).
      
      [ Modified by tytso to mix in a timestamp, since there may be some
        variability caused by the time needed to detect/configure the hardware
        in question. ]
      Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
      Signed-off-by: default avatar"Theodore Ts'o" <tytso@mit.edu>
      Cc: stable@vger.kernel.org
      a2080a67
    • Theodore Ts'o's avatar
      random: make 'add_interrupt_randomness()' do something sane · 775f4b29
      Theodore Ts'o authored
      We've been moving away from add_interrupt_randomness() for various
      reasons: it's too expensive to do on every interrupt, and flooding the
      CPU with interrupts could theoretically cause bogus floods of entropy
      from a somewhat externally controllable source.
      
      This solves both problems by limiting the actual randomness addition
      to just once a second or after 64 interrupts, whicever comes first.
      During that time, the interrupt cycle data is buffered up in a per-cpu
      pool.  Also, we make sure the the nonblocking pool used by urandom is
      initialized before we start feeding the normal input pool.  This
      assures that /dev/urandom is returning unpredictable data as soon as
      possible.
      
      (Based on an original patch by Linus, but significantly modified by
      tytso.)
      Tested-by: default avatarEric Wustrow <ewust@umich.edu>
      Reported-by: default avatarEric Wustrow <ewust@umich.edu>
      Reported-by: default avatarNadia Heninger <nadiah@cs.ucsd.edu>
      Reported-by: default avatarZakir Durumeric <zakir@umich.edu>
      Reported-by: J. Alex Halderman <jhalderm@umich.edu>.
      Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
      Signed-off-by: default avatar"Theodore Ts'o" <tytso@mit.edu>
      Cc: stable@vger.kernel.org
      775f4b29
  21. 07 Aug, 2011 1 commit
    • David S. Miller's avatar
      net: Compute protocol sequence numbers and fragment IDs using MD5. · 6e5714ea
      David S. Miller authored
      Computers have become a lot faster since we compromised on the
      partial MD4 hash which we use currently for performance reasons.
      
      MD5 is a much safer choice, and is inline with both RFC1948 and
      other ISS generators (OpenBSD, Solaris, etc.)
      
      Furthermore, only having 24-bits of the sequence number be truly
      unpredictable is a very serious limitation.  So the periodic
      regeneration and 8-bit counter have been removed.  We compute and
      use a full 32-bit sequence number.
      
      For ipv6, DCCP was found to use a 32-bit truncated initial sequence
      number (it needs 43-bits) and that is fixed here as well.
      Reported-by: default avatarDan Kaminsky <dan@doxpara.com>
      Tested-by: default avatarWilly Tarreau <w@1wt.eu>
      Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
      6e5714ea
  22. 31 Jul, 2011 1 commit
    • H. Peter Anvin's avatar
      random: Add support for architectural random hooks · 63d77173
      H. Peter Anvin authored
      Add support for architecture-specific hooks into the kernel-directed
      random number generator interfaces.  This patchset does not use the
      architecture random number generator interfaces for the
      userspace-directed interfaces (/dev/random and /dev/urandom), thus
      eliminating the need to distinguish between them based on a pool
      pointer.
      
      Changes in version 3:
      - Moved the hooks from extract_entropy() to get_random_bytes().
      - Changes the hooks to inlines.
      Signed-off-by: default avatarH. Peter Anvin <hpa@linux.intel.com>
      Cc: Fenghua Yu <fenghua.yu@intel.com>
      Cc: Matt Mackall <mpm@selenic.com>
      Cc: Herbert Xu <herbert@gondor.apana.org.au>
      Cc: "Theodore Ts'o" <tytso@mit.edu>
      63d77173
  23. 22 Jul, 2011 1 commit
  24. 27 May, 2010 1 commit
    • Joe Eykholt's avatar
      lib/random32: export pseudo-random number generator for modules · 5960164f
      Joe Eykholt authored
      This patch moves the definition of struct rnd_state and the inline
      __seed() function to linux/random.h.  It renames the static __random32()
      function to prandom32() and exports it for use in modules.
      
      prandom32() is useful as a privately-seeded pseudo random number generator
      that can give the same result every time it is initialized.
      
      For FCoE FC-BB-6 VN2VN mode self-selected unique FC address generation, we
      need an pseudo-random number generator seeded with the 64-bit world-wide
      port name.  A truly random generator or one seeded with randomness won't
      do because the same sequence of numbers should be generated each time we
      boot or the link comes up.
      
      A prandom32_seed() inline function is added to the header file.  It is
      inlined not for speed, but so the function won't be expanded in the base
      kernel, but only in the module that uses it.
      Signed-off-by: default avatarJoe Eykholt <jeykholt@cisco.com>
      Acked-by: default avatarMatt Mackall <mpm@selenic.com>
      Cc: Theodore Ts'o <tytso@mit.edu>
      Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
      5960164f
  25. 30 Jan, 2009 1 commit
  26. 03 Jan, 2009 1 commit
  27. 12 Dec, 2008 1 commit
    • Ingo Molnar's avatar
      sparse irqs: handle !GENIRQ platforms · 0ebb26e7
      Ingo Molnar authored
      Impact: build fix
      
      fix:
      
       In file included from /home/mingo/tip/arch/m68k/amiga/amiints.c:39:
       /home/mingo/tip/include/linux/interrupt.h:21: error: expected identifier or '('
       /home/mingo/tip/arch/m68k/amiga/amiints.c: In function 'amiga_init_IRQ':
      Signed-off-by: default avatarIngo Molnar <mingo@elte.hu>
      0ebb26e7
  28. 08 Dec, 2008 1 commit
    • Yinghai Lu's avatar
      sparse irq_desc[] array: core kernel and x86 changes · 0b8f1efa
      Yinghai Lu authored
      Impact: new feature
      
      Problem on distro kernels: irq_desc[NR_IRQS] takes megabytes of RAM with
      NR_CPUS set to large values. The goal is to be able to scale up to much
      larger NR_IRQS value without impacting the (important) common case.
      
      To solve this, we generalize irq_desc[NR_IRQS] to an (optional) array of
      irq_desc pointers.
      
      When CONFIG_SPARSE_IRQ=y is used, we use kzalloc_node to get irq_desc,
      this also makes the IRQ descriptors NUMA-local (to the site that calls
      request_irq()).
      
      This gets rid of the irq_cfg[] static array on x86 as well: irq_cfg now
      uses desc->chip_data for x86 to store irq_cfg.
      Signed-off-by: default avatarYinghai Lu <yinghai@kernel.org>
      Signed-off-by: default avatarIngo Molnar <mingo@elte.hu>
      0b8f1efa
  29. 12 Feb, 2007 1 commit