1. 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
    • 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
    • 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>
      6d319202
    • 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
  2. 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
  3. 07 Mar, 2012 1 commit
  4. 16 Jun, 2010 1 commit
  5. 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
  6. 30 Jul, 2008 1 commit
  7. 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>
      61407f80
  8. 04 Dec, 2006 1 commit
  9. 17 Oct, 2006 1 commit