1. 08 Oct, 2015 2 commits
  2. 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,
      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>
  3. 30 Jul, 2014 1 commit
    • Hannes Frederic Sowa's avatar
      random32: mix in entropy from core to late initcall · 4ada97ab
      Hannes Frederic Sowa authored
      Currently, we have a 3-stage seeding process in prandom():
      Phase 1 is from the early actual initialization of prandom()
      subsystem which happens during core_initcall() and remains
      most likely until the beginning of late_initcall() phase.
      Here, the system might not have enough entropy available
      for seeding with strong randomness from the random driver.
      That means, we currently have a 32bit weak LCG() seeding
      the PRNG status register 1 and mixing that successively
      into the other 3 registers just to get it up and running.
      Phase 2 starts with late_initcall() phase resp. when the
      random driver has initialized its non-blocking pool with
      enough entropy. At that time, we throw away *all* inner
      state from its 4 registers and do a full reseed with strong
      Phase 3 starts right after that and does a periodic reseed
      with random slack of status register 1 by a strong random
      source again.
      A problem in phase 1 is that during bootup data structures
      can be initialized, e.g. on module load time, and thus access
      a weakly seeded prandom and are never changed for the rest
      of their live-time, thus carrying along the results from a
      week seed. Lets make sure that current but also future users
      access a possibly better early seeded prandom.
      This patch therefore improves phase 1 by trying to make it
      more 'unpredictable' through mixing in seed from a possible
      hardware source. Now, the mix-in xors inner state with the
      outcome of either of the two functions arch_get_random_{,seed}_int(),
      preferably arch_get_random_seed_int() as it likely represents
      a non-deterministic random bit generator in hw rather than
      a cryptographically secure PRNG in hw. However, not all might
      have the first one, so we use the PRNG as a fallback if
      available. As we xor the seed into the current state, the
      worst case would be that a hardware source could be unverifiable
      compromised or backdoored. In that case nevertheless it
      would be as good as our original early seeding function
      prandom_seed_very_weak() since we mix through xor which is
      entropy preserving.
      Joint work with Daniel Borkmann.
      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>
  4. 03 Apr, 2014 1 commit
  5. 28 Mar, 2014 1 commit
  6. 14 Nov, 2013 2 commits
  7. 11 Nov, 2013 5 commits
    • Daniel Borkmann's avatar
      random32: add test cases for taus113 implementation · a6a9c0f1
      Daniel Borkmann authored
      We generated a battery of 100 test cases from GSL taus113 implemention
      and compare the results from a particular seed and a particular
      iteration with our implementation in the kernel. We have verified on
      32 and 64 bit machines that our taus113 kernel implementation gives
      same results as GSL taus113 implementation:
        [    0.147370] prandom: seed boundary self test passed
        [    0.148078] prandom: 100 self tests passed
      This is a Kconfig option that is disabled on default, just like the
      crc32 init selftests in order to not unnecessary slow down boot process.
      We also refactored out prandom_seed_very_weak() as it's now used in
      multiple places in order to reduce redundant code.
      GSL code we used for generating test cases:
        int i, j;
        for (i = 0; i < 100; ++i) {
          int iteration = 500 + (rand() % 500);
          gsl_rng_default_seed = rand() + 1;
          gsl_rng *r = gsl_rng_alloc(gsl_rng_taus113);
          printf("\t{ %lu, ", gsl_rng_default_seed);
          for (j = 0; j < iteration - 1; ++j)
          printf("%u, %lu },\n", iteration, gsl_rng_get(r));
      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>
    • 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>
    • 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
      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>
    • Hannes Frederic Sowa's avatar
      random32: add periodic reseeding · 6d319202
      Hannes Frederic Sowa authored
      The current Tausworthe PRNG is never reseeded with truly random data after
      the first attempt in late_initcall. As this PRNG is used for some critical
      random data as e.g. UDP port randomization we should try better and reseed
      the PRNG once in a while with truly random data from get_random_bytes().
      When we reseed with prandom_seed we now make also sure to throw the first
      output away. This suffices the reseeding procedure.
      The delay calculation is based on a proposal from Eric Dumazet.
      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>
      Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
    • 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>
  8. 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>
    • 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>
  9. 07 Mar, 2012 1 commit
  10. 16 Jun, 2010 1 commit
  11. 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>
  12. 30 Jul, 2008 1 commit
  13. 03 Apr, 2008 1 commit
    • Andi Kleen's avatar
      [NET]: srandom32 fixes for networking v2 · 61407f80
      Andi Kleen authored
      - Let it update the state of all CPUs. The network stack goes
      into pains to feed the current IP addresses in, but it is not very
      effective if that is only done for some random CPU instead of all.
      So change it to feed bits into all CPUs.  I decided to do that lockless 
      because well somewhat random results are ok.
      v2: Drop rename so that this patch doesn't depend on x86 maintainers
      Signed-off-by: default avatarAndi Kleen <ak@suse.de>
      Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
  14. 04 Dec, 2006 1 commit
  15. 17 Oct, 2006 1 commit