1. 21 Nov, 2017 1 commit
    • Kees Cook's avatar
      treewide: Switch DEFINE_TIMER callbacks to struct timer_list * · 24ed960a
      Kees Cook authored
      This changes all DEFINE_TIMER() callbacks to use a struct timer_list
      pointer instead of unsigned long. Since the data argument has already been
      removed, none of these callbacks are using their argument currently, so
      this renames the argument to "unused".
      
      Done using the following semantic patch:
      
      @match_define_timer@
      declarer name DEFINE_TIMER;
      identifier _timer, _callback;
      @@
      
       DEFINE_TIMER(_timer, _callback);
      
      @change_callback depends on match_define_timer@
      identifier match_define_timer._callback;
      type _origtype;
      identifier _origarg;
      @@
      
       void
      -_callback(_origtype _origarg)
      +_callback(struct timer_list *unused)
       { ... }
      Signed-off-by: default avatarKees Cook <keescook@chromium.org>
      24ed960a
  2. 02 Nov, 2017 1 commit
    • Greg Kroah-Hartman's avatar
      License cleanup: add SPDX GPL-2.0 license identifier to files with no license · b2441318
      Greg Kroah-Hartman authored
      Many source files in the tree are missing licensing information, which
      makes it harder for compliance tools to determine the correct license.
      
      By default all files without license information are under the default
      license of the kernel, which is GPL version 2.
      
      Update the files which contain no license information with the 'GPL-2.0'
      SPDX license identifier.  The SPDX identifier is a legally binding
      shorthand, which can be used instead of the full boiler plate text.
      
      This patch is based on work done by Thomas Gleixner and Kate Stewart and
      Philippe Ombredanne.
      
      How this work was done:
      
      Patches were generated and checked against linux-4.14-rc6 for a subset of
      the use cases:
       - file had no licensing information it it.
       - file was a */uapi/* one with no licensing information in it,
       - file was a */uapi/* one with existing licensing information,
      
      Further patches will be generated in subsequent months to fix up cases
      where non-standard license headers were used, and references to license
      had to be inferred by heuristics based on keywords.
      
      The analysis to determine which SPDX License Identifier to be applied to
      a file was done in a spreadsheet of side by side results from of the
      output of two independent scanners (ScanCode & Windriver) producing SPDX
      tag:value files created by Philippe Ombredanne.  Philippe prepared the
      base worksheet, and did an initial spot review of a few 1000 files.
      
      The 4.13 kernel was the starting point of the analysis with 60,537 files
      assessed.  Kate Stewart did a file by file comparison of the scanner
      results in the spreadsheet to determine which SPDX license identifier(s)
      to be applied to the file. She confirmed any determination that was not
      immediately clear with lawyers working with the Linux Foundation.
      
      Criteria used to select files for SPDX license identifier tagging was:
       - Files considered eligible had to be source code files.
       - Make and config files were included as candidates if they contained >5
         lines of source
       - File already had some variant of a license header in it (even if <5
         lines).
      
      All documentation files were explicitly excluded.
      
      The following heuristics were used to determine which SPDX license
      identifiers to apply.
      
       - when both scanners couldn't find any license traces, file was
         considered to have no license information in it, and the top level
         COPYING file license applied.
      
         For non */uapi/* files that summary was:
      
         SPDX license identifier                            # files
         ---------------------------------------------------|-------
         GPL-2.0                                              11139
      
         and resulted in the first patch in this series.
      
         If that file was a */uapi/* path one, it was "GPL-2.0 WITH
         Linux-syscall-note" otherwise it was "GPL-2.0".  Results of that was:
      
         SPDX license identifier                            # files
         ---------------------------------------------------|-------
         GPL-2.0 WITH Linux-syscall-note                        930
      
         and resulted in the second patch in this series.
      
       - if a file had some form of licensing information in it, and was one
         of the */uapi/* ones, it was denoted with the Linux-syscall-note if
         any GPL family license was found in the file or had no licensing in
         it (per prior point).  Results summary:
      
         SPDX license identifier                            # files
         ---------------------------------------------------|------
         GPL-2.0 WITH Linux-syscall-note                       270
         GPL-2.0+ WITH Linux-syscall-note                      169
         ((GPL-2.0 WITH Linux-syscall-note) OR BSD-2-Clause)    21
         ((GPL-2.0 WITH Linux-syscall-note) OR BSD-3-Clause)    17
         LGPL-2.1+ WITH Linux-syscall-note                      15
         GPL-1.0+ WITH Linux-syscall-note                       14
         ((GPL-2.0+ WITH Linux-syscall-note) OR BSD-3-Clause)    5
         LGPL-2.0+ WITH Linux-syscall-note                       4
         LGPL-2.1 WITH Linux-syscall-note                        3
         ((GPL-2.0 WITH Linux-syscall-note) OR MIT)              3
         ((GPL-2.0 WITH Linux-syscall-note) AND MIT)             1
      
         and that resulted in the third patch in this series.
      
       - when the two scanners agreed on the detected license(s), that became
         the concluded license(s).
      
       - when there was disagreement between the two scanners (one detected a
         license but the other didn't, or they both detected different
         licenses) a manual inspection of the file occurred.
      
       - In most cases a manual inspection of the information in the file
         resulted in a clear resolution of the license that should apply (and
         which scanner probably needed to revisit its heuristics).
      
       - When it was not immediately clear, the license identifier was
         confirmed with lawyers working with the Linux Foundation.
      
       - If there was any question as to the appropriate license identifier,
         the file was flagged for further research and to be revisited later
         in time.
      
      In total, over 70 hours of logged manual review was done on the
      spreadsheet to determine the SPDX license identifiers to apply to the
      source files by Kate, Philippe, Thomas and, in some cases, confirmation
      by lawyers working with the Linux Foundation.
      
      Kate also obtained a third independent scan of the 4.13 code base from
      FOSSology, and compared selected files where the other two scanners
      disagreed against that SPDX file, to see if there was new insights.  The
      Windriver scanner is based on an older version of FOSSology in part, so
      they are related.
      
      Thomas did random spot checks in about 500 files from the spreadsheets
      for the uapi headers and agreed with SPDX license identifier in the
      files he inspected. For the non-uapi files Thomas did random spot checks
      in about 15000 files.
      
      In initial set of patches against 4.14-rc6, 3 files were found to have
      copy/paste license identifier errors, and have been fixed to reflect the
      correct identifier.
      
      Additionally Philippe spent 10 hours this week doing a detailed manual
      inspection and review of the 12,461 patched files from the initial patch
      version early this week with:
       - a full scancode scan run, collecting the matched texts, detected
         license ids and scores
       - reviewing anything where there was a license detected (about 500+
         files) to ensure that the applied SPDX license was correct
       - reviewing anything where there was no detection but the patch license
         was not GPL-2.0 WITH Linux-syscall-note to ensure that the applied
         SPDX license was correct
      
      This produced a worksheet with 20 files needing minor correction.  This
      worksheet was then exported into 3 different .csv files for the
      different types of files to be modified.
      
      These .csv files were then reviewed by Greg.  Thomas wrote a script to
      parse the csv files and add the proper SPDX tag to the file, in the
      format that the file expected.  This script was further refined by Greg
      based on the output to detect more types of files automatically and to
      distinguish between header and source .c files (which need different
      comment types.)  Finally Greg ran the script using the .csv files to
      generate the patches.
      Reviewed-by: default avatarKate Stewart <kstewart@linuxfoundation.org>
      Reviewed-by: default avatarPhilippe Ombredanne <pombredanne@nexb.com>
      Reviewed-by: default avatarThomas Gleixner <tglx@linutronix.de>
      Signed-off-by: default avatarGreg Kroah-Hartman <gregkh@linuxfoundation.org>
      b2441318
  3. 05 Oct, 2017 1 commit
    • Kees Cook's avatar
      timer: Remove expires and data arguments from DEFINE_TIMER · 1d27e3e2
      Kees Cook authored
      Drop the arguments from the macro and adjust all callers with the
      following script:
      
        perl -pi -e 's/DEFINE_TIMER\((.*), 0, 0\);/DEFINE_TIMER($1);/g;' \
          $(git grep DEFINE_TIMER | cut -d: -f1 | sort -u | grep -v timer.h)
      Signed-off-by: default avatarKees Cook <keescook@chromium.org>
      Acked-by: Geert Uytterhoeven <geert@linux-m68k.org> # for m68k parts
      Acked-by: Guenter Roeck <linux@roeck-us.net> # for watchdog parts
      Acked-by: David S. Miller <davem@davemloft.net> # for networking parts
      Acked-by: default avatarGreg Kroah-Hartman <gregkh@linuxfoundation.org>
      Acked-by: Kalle Valo <kvalo@codeaurora.org> # for wireless parts
      Acked-by: default avatarArnd Bergmann <arnd@arndb.de>
      Cc: linux-mips@linux-mips.org
      Cc: Petr Mladek <pmladek@suse.com>
      Cc: Benjamin Herrenschmidt <benh@kernel.crashing.org>
      Cc: Lai Jiangshan <jiangshanlai@gmail.com>
      Cc: Sebastian Reichel <sre@kernel.org>
      Cc: Kalle Valo <kvalo@qca.qualcomm.com>
      Cc: Paul Mackerras <paulus@samba.org>
      Cc: Pavel Machek <pavel@ucw.cz>
      Cc: linux1394-devel@lists.sourceforge.net
      Cc: Chris Metcalf <cmetcalf@mellanox.com>
      Cc: linux-s390@vger.kernel.org
      Cc: linux-wireless@vger.kernel.org
      Cc: "James E.J. Bottomley" <jejb@linux.vnet.ibm.com>
      Cc: Wim Van Sebroeck <wim@iguana.be>
      Cc: Michael Ellerman <mpe@ellerman.id.au>
      Cc: Ursula Braun <ubraun@linux.vnet.ibm.com>
      Cc: Viresh Kumar <viresh.kumar@linaro.org>
      Cc: Harish Patil <harish.patil@cavium.com>
      Cc: Stephen Boyd <sboyd@codeaurora.org>
      Cc: Michael Reed <mdr@sgi.com>
      Cc: Manish Chopra <manish.chopra@cavium.com>
      Cc: Len Brown <len.brown@intel.com>
      Cc: Arnd Bergmann <arnd@arndb.de>
      Cc: linux-pm@vger.kernel.org
      Cc: Heiko Carstens <heiko.carstens@de.ibm.com>
      Cc: Tejun Heo <tj@kernel.org>
      Cc: Julian Wiedmann <jwi@linux.vnet.ibm.com>
      Cc: John Stultz <john.stultz@linaro.org>
      Cc: Mark Gross <mark.gross@intel.com>
      Cc: linux-watchdog@vger.kernel.org
      Cc: linux-scsi@vger.kernel.org
      Cc: "Martin K. Petersen" <martin.petersen@oracle.com>
      Cc: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
      Cc: "Rafael J. Wysocki" <rjw@rjwysocki.net>
      Cc: Oleg Nesterov <oleg@redhat.com>
      Cc: Ralf Baechle <ralf@linux-mips.org>
      Cc: Stefan Richter <stefanr@s5r6.in-berlin.de>
      Cc: Guenter Roeck <linux@roeck-us.net>
      Cc: netdev@vger.kernel.org
      Cc: Martin Schwidefsky <schwidefsky@de.ibm.com>
      Cc: Andrew Morton <akpm@linux-foundation.org>
      Cc: linuxppc-dev@lists.ozlabs.org
      Cc: Sudip Mukherjee <sudipm.mukherjee@gmail.com>
      Link: https://lkml.kernel.org/r/1507159627-127660-11-git-send-email-keescook@chromium.orgSigned-off-by: default avatarThomas Gleixner <tglx@linutronix.de>
      1d27e3e2
  4. 10 Oct, 2016 1 commit
    • 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
  5. 28 Sep, 2016 1 commit
  6. 07 Jul, 2016 1 commit
    • Thomas Gleixner's avatar
      timers: Remove set_timer_slack() leftovers · 53bf837b
      Thomas Gleixner authored
      We now have implicit batching in the timer wheel. The slack API is no longer
      used, so remove it.
      Signed-off-by: default avatarThomas Gleixner <tglx@linutronix.de>
      Cc: Alan Stern <stern@rowland.harvard.edu>
      Cc: Andrew F. Davis <afd@ti.com>
      Cc: Arjan van de Ven <arjan@infradead.org>
      Cc: Chris Mason <clm@fb.com>
      Cc: David S. Miller <davem@davemloft.net>
      Cc: David Woodhouse <dwmw2@infradead.org>
      Cc: Dmitry Eremin-Solenikov <dbaryshkov@gmail.com>
      Cc: Eric Dumazet <edumazet@google.com>
      Cc: Frederic Weisbecker <fweisbec@gmail.com>
      Cc: George Spelvin <linux@sciencehorizons.net>
      Cc: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
      Cc: Jaehoon Chung <jh80.chung@samsung.com>
      Cc: Jens Axboe <axboe@kernel.dk>
      Cc: John Stultz <john.stultz@linaro.org>
      Cc: Josh Triplett <josh@joshtriplett.org>
      Cc: Len Brown <lenb@kernel.org>
      Cc: Linus Torvalds <torvalds@linux-foundation.org>
      Cc: Mathias Nyman <mathias.nyman@intel.com>
      Cc: Pali Rohár <pali.rohar@gmail.com>
      Cc: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
      Cc: Peter Zijlstra <peterz@infradead.org>
      Cc: Rik van Riel <riel@redhat.com>
      Cc: Sebastian Reichel <sre@kernel.org>
      Cc: Ulf Hansson <ulf.hansson@linaro.org>
      Cc: linux-block@vger.kernel.org
      Cc: linux-kernel@vger.kernel.org
      Cc: linux-mmc@vger.kernel.org
      Cc: linux-pm@vger.kernel.org
      Cc: linux-usb@vger.kernel.org
      Cc: netdev@vger.kernel.org
      Cc: rt@linutronix.de
      Link: http://lkml.kernel.org/r/20160704094342.189813118@linutronix.deSigned-off-by: default avatarIngo Molnar <mingo@kernel.org>
      53bf837b
  7. 29 Feb, 2016 1 commit
  8. 08 Oct, 2015 2 commits
  9. 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
  10. 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
      randomness.
      
      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>
      4ada97ab
  11. 03 Apr, 2014 1 commit
  12. 28 Mar, 2014 1 commit
  13. 14 Nov, 2013 2 commits
  14. 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;
        srand(time(NULL));
        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)
            gsl_rng_get(r);
          printf("%u, %lu },\n", iteration, gsl_rng_get(r));
          gsl_rng_free(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>
      a6a9c0f1
    • 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
  15. 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
  16. 07 Mar, 2012 1 commit
  17. 16 Jun, 2010 1 commit
  18. 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
  19. 30 Jul, 2008 1 commit
  20. 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
  21. 04 Dec, 2006 1 commit
  22. 17 Oct, 2006 1 commit