04 Apr, 2014
1 commit
-
These are just some very minor and misc cleanups in the PRNG. In
prandom_u32() we store the result in an unsigned long which is
unnecessary as it should be u32 instead that we get from
prandom_u32_state(). prandom_bytes_state()'s comment is in kdoc format,
so change it into such as it's done everywhere else. Also, use the
normal comment style for the header comment. Last but not least for
readability, add some newlines.Signed-off-by: Daniel Borkmann
Cc: Joe Perches
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds
29 Mar, 2014
1 commit
-
Commit 4af712e8df ("random32: add prandom_reseed_late() and call when
nonblocking pool becomes initialized") has added a late reseed stage
that happens as soon as the nonblocking pool is marked as initialized.This fails in the case that the nonblocking pool gets initialized
during __prandom_reseed()'s call to get_random_bytes(). In that case
we'd double back into __prandom_reseed() in an attempt to do a late
reseed - deadlocking on 'lock' early on in the boot process.Instead, just avoid even waiting to do a reseed if a reseed is already
occuring.Fixes: 4af712e8df99 ("random32: add prandom_reseed_late() and call when nonblocking pool becomes initialized")
Signed-off-by: Sasha Levin
Acked-by: Hannes Frederic Sowa
Signed-off-by: Daniel Borkmann
Signed-off-by: David S. Miller
15 Nov, 2013
2 commits
-
Use msecs_to_jiffies, for these calculations as different HZ
considerations are taken into account for conversion of the timer
shot, and also it makes the code more readable.Signed-off-by: Daniel Borkmann
Signed-off-by: Hannes Frederic Sowa
Signed-off-by: David S. Miller -
We only call that in functions annotated with __init, so add __init
prefix in prandom_start_seed_timer() as well, so that the kernel can
make use of this hint and we can possibly free up resources after it's
usage. And since it's an internal function rename it to
__prandom_start_seed_timer().Signed-off-by: Daniel Borkmann
Signed-off-by: Hannes Frederic Sowa
Signed-off-by: David S. Miller
12 Nov, 2013
5 commits
-
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 passedThis 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
Cc: Theodore Ts'o
Signed-off-by: Daniel Borkmann
Signed-off-by: Hannes Frederic Sowa
Signed-off-by: David S. Miller -
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 #taus113With 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 PASSEDWe 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
Cc: Theodore Ts'o
Signed-off-by: Daniel Borkmann
Signed-off-by: Hannes Frederic Sowa
Signed-off-by: David S. Miller -
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
Cc: Theodore Ts'o
Signed-off-by: Hannes Frederic Sowa
Signed-off-by: Daniel Borkmann
Acked-by: "Theodore Ts'o"
Signed-off-by: David S. Miller -
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
Cc: Theodore Ts'o
Signed-off-by: Hannes Frederic Sowa
Signed-off-by: Daniel Borkmann
Signed-off-by: David S. Miller -
For properly initialising the Tausworthe generator [1], we have
a strict seeding requirement, that is, s1 > 1, s2 > 7, s3 > 15.Commit 697f8d0348 ("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.psJoint work with Hannes Frederic Sowa.
Fixes: 697f8d0348a6 ("random32: seeding improvement")
Cc: Stephen Hemminger
Cc: Florian Weimer
Cc: Theodore Ts'o
Signed-off-by: Daniel Borkmann
Signed-off-by: Hannes Frederic Sowa
Signed-off-by: David S. Miller
18 Dec, 2012
2 commits
-
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: Akinobu Mita
Cc: "Theodore Ts'o"
Cc: Artem Bityutskiy
Cc: Adrian Hunter
Cc: David Woodhouse
Cc: Eilon Greenstein
Cc: David Laight
Cc: Michel Lespinasse
Cc: Robert Love
Cc: Valdis Kletnieks
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds -
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: Akinobu Mita
Cc: "Theodore Ts'o"
Cc: Robert Love
Cc: Michel Lespinasse
Cc: Valdis Kletnieks
Cc: David Laight
Cc: Adrian Hunter
Cc: Artem Bityutskiy
Cc: David Woodhouse
Cc: Eilon Greenstein
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds
08 Mar, 2012
1 commit
-
For files only using THIS_MODULE and/or EXPORT_SYMBOL, map
them onto including export.h -- or if the file isn't even
using those, then just delete the include. Fix up any implicit
include dependencies that were being masked by module.h along
the way.Signed-off-by: Paul Gortmaker
17 Jun, 2010
2 commits
-
Signed-off-by: Uwe Kleine-König
Signed-off-by: Jiri Kosina
28 May, 2010
1 commit
-
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: Joe Eykholt
Acked-by: Matt Mackall
Cc: Theodore Ts'o
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds
31 Jul, 2008
1 commit
-
The rationale is:
* use u32 consistently
* no need to do LCG on values from (better) get_random_bytes
* use more data from get_random_bytes for secondary seeding
* don't reduce state space on srandom32()
* enforce state variable initialization restrictionsNote: the second paper has a version of random32() with even longer period
and a version of random64() if needed.Signed-off-by: Stephen Hemminger
Signed-off-by: Andrew Morton
04 Apr, 2008
1 commit
-
- 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: Andi Kleen
Signed-off-by: David S. Miller
04 Dec, 2006
1 commit
-
Signed-off-by: Al Viro
17 Oct, 2006
1 commit
-
Make net_random() more widely available by calling it random32
akpm: hopefully this will permit the removal of carta_random32. That needs
confirmation from Stephane - this code looks somewhat more computationally
expensive, and has a different (ie: callee-stateful) interface.[akpm@osdl.org: lots of build fixes, cleanups]
Signed-off-by: Stephen Hemminger
Signed-off-by: David S. Miller
Cc: Stephane Eranian
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds