Line data Source code
1 : /* Bob Jenkins's cryptographic random number generator, ISAAC.
2 :
3 : Copyright (C) 1999-2006 Free Software Foundation, Inc.
4 : Copyright (C) 1997, 1998, 1999 Colin Plumb.
5 :
6 : This program is free software: you can redistribute it and/or modify
7 : it under the terms of the GNU General Public License as published by
8 : the Free Software Foundation, either version 3 of the License, or
9 : (at your option) any later version.
10 :
11 : This program is distributed in the hope that it will be useful,
12 : but WITHOUT ANY WARRANTY; without even the implied warranty of
13 : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 : GNU General Public License for more details.
15 :
16 : You should have received a copy of the GNU General Public License
17 : along with this program. If not, see <http://www.gnu.org/licenses/>.
18 :
19 : Written by Colin Plumb. */
20 :
21 : /*
22 : * --------------------------------------------------------------------
23 : * We need a source of random numbers for some data.
24 : * Cryptographically secure is desirable, but it's not life-or-death
25 : * so I can be a little bit experimental in the choice of RNGs here.
26 : *
27 : * This generator is based somewhat on RC4, but has analysis
28 : * <http://burtleburtle.net/bob/rand/isaacafa.html>
29 : * pointing to it actually being better. I like it because it's nice
30 : * and fast, and because the author did good work analyzing it.
31 : * --------------------------------------------------------------------
32 : */
33 : #include <config.h>
34 :
35 : #include "rand-isaac.h"
36 :
37 : #include <string.h>
38 : #include <unistd.h>
39 :
40 : #include "gethrxtime.h"
41 :
42 :
43 : /* This index operation is more efficient on many processors */
44 : #define ind(mm, x) \
45 : (* (uint32_t *) ((char *) (mm) \
46 : + ((x) & (ISAAC_WORDS - 1) * sizeof (uint32_t))))
47 :
48 : /*
49 : * The central step. This uses two temporaries, x and y. mm is the
50 : * whole state array, while m is a pointer to the current word. off is
51 : * the offset from m to the word ISAAC_WORDS/2 words away in the mm array,
52 : * i.e. +/- ISAAC_WORDS/2.
53 : */
54 : #define isaac_step(mix, a, b, mm, m, off, r) \
55 : ( \
56 : a = ((a) ^ (mix)) + (m)[off], \
57 : x = *(m), \
58 : *(m) = y = ind (mm, x) + (a) + (b), \
59 : *(r) = b = ind (mm, (y) >> ISAAC_LOG) + x \
60 : )
61 :
62 : /* Use and update *S to generate random data to fill R. */
63 : void
64 0 : isaac_refill (struct isaac_state *s, uint32_t r[ISAAC_WORDS])
65 : {
66 : uint32_t a, b; /* Caches of a and b */
67 : uint32_t x, y; /* Temps needed by isaac_step macro */
68 0 : uint32_t *m = s->mm; /* Pointer into state array */
69 :
70 0 : a = s->a;
71 0 : b = s->b + (++s->c);
72 :
73 : do
74 : {
75 0 : isaac_step (a << 13, a, b, s->mm, m, ISAAC_WORDS / 2, r);
76 0 : isaac_step (a >> 6, a, b, s->mm, m + 1, ISAAC_WORDS / 2, r + 1);
77 0 : isaac_step (a << 2, a, b, s->mm, m + 2, ISAAC_WORDS / 2, r + 2);
78 0 : isaac_step (a >> 16, a, b, s->mm, m + 3, ISAAC_WORDS / 2, r + 3);
79 0 : r += 4;
80 : }
81 0 : while ((m += 4) < s->mm + ISAAC_WORDS / 2);
82 : do
83 : {
84 0 : isaac_step (a << 13, a, b, s->mm, m, -ISAAC_WORDS / 2, r);
85 0 : isaac_step (a >> 6, a, b, s->mm, m + 1, -ISAAC_WORDS / 2, r + 1);
86 0 : isaac_step (a << 2, a, b, s->mm, m + 2, -ISAAC_WORDS / 2, r + 2);
87 0 : isaac_step (a >> 16, a, b, s->mm, m + 3, -ISAAC_WORDS / 2, r + 3);
88 0 : r += 4;
89 : }
90 0 : while ((m += 4) < s->mm + ISAAC_WORDS);
91 0 : s->a = a;
92 0 : s->b = b;
93 0 : }
94 :
95 : /*
96 : * The basic seed-scrambling step for initialization, based on Bob
97 : * Jenkins' 256-bit hash.
98 : */
99 : #define mix(a,b,c,d,e,f,g,h) \
100 : ( a ^= b << 11, d += a, \
101 : b += c, b ^= c >> 2, e += b, \
102 : c += d, c ^= d << 8, f += c, \
103 : d += e, d ^= e >> 16, g += d, \
104 : e += f, e ^= f << 10, h += e, \
105 : f += g, f ^= g >> 4, a += f, \
106 : g += h, g ^= h << 8, b += g, \
107 : h += a, h ^= a >> 9, c += h, \
108 : a += b )
109 :
110 : /* The basic ISAAC initialization pass. */
111 : static void
112 0 : isaac_mix (struct isaac_state *s, uint32_t const seed[/* ISAAC_WORDS */])
113 : {
114 : int i;
115 0 : uint32_t a = s->iv[0];
116 0 : uint32_t b = s->iv[1];
117 0 : uint32_t c = s->iv[2];
118 0 : uint32_t d = s->iv[3];
119 0 : uint32_t e = s->iv[4];
120 0 : uint32_t f = s->iv[5];
121 0 : uint32_t g = s->iv[6];
122 0 : uint32_t h = s->iv[7];
123 :
124 0 : for (i = 0; i < ISAAC_WORDS; i += 8)
125 : {
126 0 : a += seed[i];
127 0 : b += seed[i + 1];
128 0 : c += seed[i + 2];
129 0 : d += seed[i + 3];
130 0 : e += seed[i + 4];
131 0 : f += seed[i + 5];
132 0 : g += seed[i + 6];
133 0 : h += seed[i + 7];
134 :
135 0 : mix (a, b, c, d, e, f, g, h);
136 :
137 0 : s->mm[i] = a;
138 0 : s->mm[i + 1] = b;
139 0 : s->mm[i + 2] = c;
140 0 : s->mm[i + 3] = d;
141 0 : s->mm[i + 4] = e;
142 0 : s->mm[i + 5] = f;
143 0 : s->mm[i + 6] = g;
144 0 : s->mm[i + 7] = h;
145 : }
146 :
147 0 : s->iv[0] = a;
148 0 : s->iv[1] = b;
149 0 : s->iv[2] = c;
150 0 : s->iv[3] = d;
151 0 : s->iv[4] = e;
152 0 : s->iv[5] = f;
153 0 : s->iv[6] = g;
154 0 : s->iv[7] = h;
155 0 : }
156 :
157 : #if 0 /* Provided for reference only; not used in this code */
158 : /*
159 : * Initialize the ISAAC RNG with the given seed material.
160 : * Its size MUST be a multiple of ISAAC_BYTES, and may be
161 : * stored in the s->mm array.
162 : *
163 : * This is a generalization of the original ISAAC initialization code
164 : * to support larger seed sizes. For seed sizes of 0 and ISAAC_BYTES,
165 : * it is identical.
166 : */
167 : static void
168 : isaac_init (struct isaac_state *s, uint32_t const *seed, size_t seedsize)
169 : {
170 : static uint32_t const iv[8] =
171 : {
172 : 0x1367df5a, 0x95d90059, 0xc3163e4b, 0x0f421ad8,
173 : 0xd92a4a78, 0xa51a3c49, 0xc4efea1b, 0x30609119};
174 : int i;
175 :
176 : # if 0
177 : /* The initialization of iv is a precomputed form of: */
178 : for (i = 0; i < 7; i++)
179 : iv[i] = 0x9e3779b9; /* the golden ratio */
180 : for (i = 0; i < 4; ++i) /* scramble it */
181 : mix (iv[0], iv[1], iv[2], iv[3], iv[4], iv[5], iv[6], iv[7]);
182 : # endif
183 : s->a = s->b = s->c = 0;
184 :
185 : for (i = 0; i < 8; i++)
186 : s->iv[i] = iv[i];
187 :
188 : if (seedsize)
189 : {
190 : /* First pass (as in reference ISAAC code) */
191 : isaac_mix (s, seed);
192 : /* Second and subsequent passes (extension to ISAAC) */
193 : while (seedsize -= ISAAC_BYTES)
194 : {
195 : seed += ISAAC_WORDS;
196 : for (i = 0; i < ISAAC_WORDS; i++)
197 : s->mm[i] += seed[i];
198 : isaac_mix (s, s->mm);
199 : }
200 : }
201 : else
202 : {
203 : /* The no seed case (as in reference ISAAC code) */
204 : for (i = 0; i < ISAAC_WORDS; i++)
205 : s->mm[i] = 0;
206 : }
207 :
208 : /* Final pass */
209 : isaac_mix (s, s->mm);
210 : }
211 : #endif
212 :
213 : /* Initialize *S to a somewhat-random value. */
214 : static void
215 0 : isaac_seed_start (struct isaac_state *s)
216 : {
217 : static uint32_t const iv[8] =
218 : {
219 : 0x1367df5a, 0x95d90059, 0xc3163e4b, 0x0f421ad8,
220 : 0xd92a4a78, 0xa51a3c49, 0xc4efea1b, 0x30609119
221 : };
222 :
223 : #if 0
224 : /* The initialization of iv is a precomputed form of: */
225 : int i;
226 : for (i = 0; i < 7; i++)
227 : iv[i] = 0x9e3779b9; /* the golden ratio */
228 : for (i = 0; i < 4; ++i) /* scramble it */
229 : mix (iv[0], iv[1], iv[2], iv[3], iv[4], iv[5], iv[6], iv[7]);
230 : #endif
231 :
232 0 : memset (s->mm, 0, sizeof s->mm);
233 0 : memcpy (s->iv, iv, sizeof s->iv);
234 :
235 : /* s->c gets used for a data pointer during the seeding phase */
236 0 : s->a = s->b = s->c = 0;
237 0 : }
238 :
239 : /* Add a buffer of seed material. */
240 : static void
241 0 : isaac_seed_data (struct isaac_state *s, void const *buffer, size_t size)
242 : {
243 0 : unsigned char const *buf = buffer;
244 : unsigned char *p;
245 : size_t avail;
246 : size_t i;
247 :
248 0 : avail = sizeof s->mm - s->c; /* s->c is used as a write pointer */
249 :
250 : /* Do any full buffers that are necessary */
251 0 : while (size > avail)
252 : {
253 0 : p = (unsigned char *) s->mm + s->c;
254 0 : for (i = 0; i < avail; i++)
255 0 : p[i] ^= buf[i];
256 0 : buf += avail;
257 0 : size -= avail;
258 0 : isaac_mix (s, s->mm);
259 0 : s->c = 0;
260 0 : avail = sizeof s->mm;
261 : }
262 :
263 : /* And the final partial block */
264 0 : p = (unsigned char *) s->mm + s->c;
265 0 : for (i = 0; i < size; i++)
266 0 : p[i] ^= buf[i];
267 0 : s->c = size;
268 0 : }
269 :
270 :
271 : /* End of seeding phase; get everything ready to produce output. */
272 : static void
273 0 : isaac_seed_finish (struct isaac_state *s)
274 : {
275 0 : isaac_mix (s, s->mm);
276 0 : isaac_mix (s, s->mm);
277 : /* Now reinitialize c to start things off right */
278 0 : s->c = 0;
279 0 : }
280 : #define ISAAC_SEED(s,x) isaac_seed_data (s, &(x), sizeof (x))
281 :
282 : /* Initialize *S to a somewhat-random value; this starts seeding,
283 : seeds with somewhat-random data, and finishes seeding. */
284 : void
285 0 : isaac_seed (struct isaac_state *s)
286 : {
287 0 : isaac_seed_start (s);
288 :
289 0 : { pid_t t = getpid (); ISAAC_SEED (s, t); }
290 0 : { pid_t t = getppid (); ISAAC_SEED (s, t); }
291 0 : { uid_t t = getuid (); ISAAC_SEED (s, t); }
292 0 : { gid_t t = getgid (); ISAAC_SEED (s, t); }
293 :
294 : {
295 0 : xtime_t t = gethrxtime ();
296 0 : ISAAC_SEED (s, t);
297 : }
298 :
299 0 : isaac_seed_finish (s);
300 0 : }
|
