aboutsummaryrefslogtreecommitdiff
path: root/shell
diff options
context:
space:
mode:
authorDenys Vlasenko <vda.linux@googlemail.com>2014-03-13 12:52:43 +0100
committerDenys Vlasenko <vda.linux@googlemail.com>2014-03-13 12:52:43 +0100
commitfb183076a3a6580a4aba435c53ce033ef89e7fe6 (patch)
tree72e36e623d7b8841825a8d82aabe5ac7b7654cab /shell
parent69f9567de28976cfbc7b216c46aa391ce82bd3b7 (diff)
downloadbusybox-w32-fb183076a3a6580a4aba435c53ce033ef89e7fe6.tar.gz
busybox-w32-fb183076a3a6580a4aba435c53ce033ef89e7fe6.tar.bz2
busybox-w32-fb183076a3a6580a4aba435c53ce033ef89e7fe6.zip
ash,hush: improve randomness of $RANDOM, add easy-ish way to test it
function old new delta next_random 68 113 +45 change_random 103 121 +18 Signed-off-by: Denys Vlasenko <vda.linux@googlemail.com>
Diffstat (limited to 'shell')
-rw-r--r--shell/random.c136
-rw-r--r--shell/random.h16
2 files changed, 135 insertions, 17 deletions
diff --git a/shell/random.c b/shell/random.c
index 853ab085a..9a64f54b0 100644
--- a/shell/random.c
+++ b/shell/random.c
@@ -6,17 +6,51 @@
6 * 6 *
7 * Licensed under GPLv2, see file LICENSE in this source tree. 7 * Licensed under GPLv2, see file LICENSE in this source tree.
8 */ 8 */
9#include "libbb.h" 9
10#include "random.h" 10/* For testing against dieharder, you need only random.{c,h}
11 * Howto:
12 * gcc -O2 -Wall -DRANDTEST random.c -o random
13 * ./random | dieharder -g 200 -a
14 */
15
16#if !defined RANDTEST
17
18# include "libbb.h"
19# include "random.h"
20# define RAND_BASH_MASK 0x7fff
21
22#else
23# include <stdint.h>
24# include <unistd.h>
25# include <stdio.h>
26# include <time.h>
27# define RAND_BASH_MASK 0xffffffff /* off */
28# define FAST_FUNC /* nothing */
29# define PUSH_AND_SET_FUNCTION_VISIBILITY_TO_HIDDEN /* nothing */
30# define POP_SAVED_FUNCTION_VISIBILITY /* nothing */
31# define monotonic_us() time(NULL)
32# include "random.h"
33#endif
11 34
12uint32_t FAST_FUNC 35uint32_t FAST_FUNC
13next_random(random_t *rnd) 36next_random(random_t *rnd)
14{ 37{
15 /* Galois LFSR parameter */ 38 /* Galois LFSR parameter:
16 /* Taps at 32 31 29 1: */ 39 * Taps at 32 31 29 1:
40 */
17 enum { MASK = 0x8000000b }; 41 enum { MASK = 0x8000000b };
18 /* Another example - taps at 32 31 30 10: */ 42 /* Another example - taps at 32 31 30 10: */
19 /* MASK = 0x00400007 */ 43 /* enum { MASK = 0x00400007 }; */
44
45 /* Xorshift parameters:
46 * Choices for a,b,c: 10,13,10; 8,9,22; 2,7,3; 23,3,24
47 * (given by algorithm author)
48 */
49 enum {
50 a = 2,
51 b = 7,
52 c = 3,
53 };
20 54
21 uint32_t t; 55 uint32_t t;
22 56
@@ -27,18 +61,94 @@ next_random(random_t *rnd)
27 INIT_RANDOM_T(rnd, getpid(), monotonic_us()); 61 INIT_RANDOM_T(rnd, getpid(), monotonic_us());
28 } 62 }
29 63
30 /* LCG has period of 2^32 and alternating lowest bit */ 64 /* LCG: period of 2^32, but quite weak:
65 * bit 0 alternates beetween 0 and 1 (pattern of length 2)
66 * bit 1 has a repeating pattern of length 4
67 * bit 2 has a repeating pattern of length 8
68 * etc...
69 */
31 rnd->LCG = 1664525 * rnd->LCG + 1013904223; 70 rnd->LCG = 1664525 * rnd->LCG + 1013904223;
32 /* Galois LFSR has period of 2^32-1 = 3 * 5 * 17 * 257 * 65537 */ 71
72 /* Galois LFSR:
73 * period of 2^32-1 = 3 * 5 * 17 * 257 * 65537.
74 * Successive values are right-shifted one bit
75 * and possibly xored with a sparse constant.
76 */
33 t = (rnd->galois_LFSR << 1); 77 t = (rnd->galois_LFSR << 1);
34 if (rnd->galois_LFSR < 0) /* if we just shifted 1 out of msb... */ 78 if (rnd->galois_LFSR < 0) /* if we just shifted 1 out of msb... */
35 t ^= MASK; 79 t ^= MASK;
36 rnd->galois_LFSR = t; 80 rnd->galois_LFSR = t;
37 /* Both are weak, combining them gives better randomness
38 * and ~2^64 period. & 0x7fff is probably bash compat
39 * for $RANDOM range. Combining with subtraction is
40 * just for fun. + and ^ would work equally well. */
41 t = (t - rnd->LCG) & 0x7fff;
42 81
43 return t; 82 /* http://en.wikipedia.org/wiki/Xorshift
83 * Period 2^64-1 = 3 * 715827883 * 2147483647
84 * Moderately good statistical properties:
85 * fails the following "dieharder -g 200 -a" tests:
86 * diehard_operm5| 0
87 * diehard_oqso| 0
88 * diehard_count_1s_byt| 0
89 * diehard_3dsphere| 3
90 * diehard_squeeze| 0
91 * diehard_runs| 0
92 * diehard_runs| 0
93 * diehard_craps| 0
94 * diehard_craps| 0
95 * rgb_minimum_distance| 3
96 * rgb_minimum_distance| 4
97 * rgb_minimum_distance| 5
98 * rgb_permutations| 3
99 * rgb_permutations| 4
100 * rgb_permutations| 5
101 * dab_filltree| 32
102 * dab_filltree| 32
103 * dab_monobit2| 12
104 */
105 t = rnd->xs64_x ^ (rnd->xs64_x << a);
106 rnd->xs64_x = rnd->xs64_y;
107 rnd->xs64_y = rnd->xs64_y ^ (rnd->xs64_y >> c) ^ t ^ (t >> b);
108
109 /* Combined LCG + Galois LFSR have 2^32 * 2^32-1 period.
110 * Strength:
111 * individually, both are extremely weak cryptographycally;
112 * when combined, they fail the following "dieharder -g 200 -a" tests:
113 * diehard_rank_6x8| 0
114 * diehard_oqso| 0
115 * diehard_dna| 0
116 * diehard_count_1s_byt| 0
117 * rgb_bitdist| 2
118 * dab_monobit2| 12
119 *
120 * Combining them with xorshift-64 increases period to
121 * 2^32 * 2^32-1 * 2^64-1 / 3
122 * (2^32-1 and 2^64-1 have one common divisor 3, hence "/ 3" part),
123 * which is about 2^128 / 3, or in base 10 ~1.13*10^38.
124 * Strength of the combination:
125 * passes all "dieharder -g 200 -a" tests.
126 *
127 * Combining with subtraction and addition is just for fun.
128 * It does not add meaningful strength, could use xor operation instead.
129 */
130 t = rnd->galois_LFSR - rnd->LCG + rnd->xs64_y;
131
132 /* bash compat $RANDOM range: */
133 return t & RAND_BASH_MASK;
44} 134}
135
136#ifdef RANDTEST
137static random_t rnd;
138
139int main(int argc, char **argv)
140{
141 int i;
142 int buf[4096];
143
144 for (;;) {
145 for (i = 0; i < sizeof(buf) / sizeof(buf[0]); i++) {
146 buf[i] = next_random(&rnd);
147 }
148 write(1, buf, sizeof(buf));
149 }
150
151 return 0;
152}
153
154#endif
diff --git a/shell/random.h b/shell/random.h
index 180c48abb..c4eb44c13 100644
--- a/shell/random.h
+++ b/shell/random.h
@@ -12,16 +12,24 @@
12PUSH_AND_SET_FUNCTION_VISIBILITY_TO_HIDDEN 12PUSH_AND_SET_FUNCTION_VISIBILITY_TO_HIDDEN
13 13
14typedef struct random_t { 14typedef struct random_t {
15 /* Random number generators */ 15 /* State of random number generators: */
16 int32_t galois_LFSR; /* Galois LFSR (fast but weak). signed! */ 16
17 uint32_t LCG; /* LCG (fast but weak) */ 17 /* Galois LFSR (fast but weak) */
18 int32_t galois_LFSR; /* must be signed! */
19
20 /* LCG (fast but weak) */
21 uint32_t LCG;
22
23 /* 64-bit xorshift (fast, moderate strength) */
24 uint32_t xs64_x;
25 uint32_t xs64_y;
18} random_t; 26} random_t;
19 27
20#define UNINITED_RANDOM_T(rnd) \ 28#define UNINITED_RANDOM_T(rnd) \
21 ((rnd)->galois_LFSR == 0) 29 ((rnd)->galois_LFSR == 0)
22 30
23#define INIT_RANDOM_T(rnd, nonzero, v) \ 31#define INIT_RANDOM_T(rnd, nonzero, v) \
24 ((rnd)->galois_LFSR = (nonzero), (rnd)->LCG = (v)) 32 ((rnd)->galois_LFSR = (rnd)->xs64_x = (nonzero), (rnd)->LCG = (rnd)->xs64_y = (v))
25 33
26#define CLEAR_RANDOM_T(rnd) \ 34#define CLEAR_RANDOM_T(rnd) \
27 ((rnd)->galois_LFSR = 0) 35 ((rnd)->galois_LFSR = 0)
generated by cgit v1.2.3-55-g6feb (git 2.39.1) at 2025-03-17 00:40:09 +0000