1/* Bob Jenkins's cryptographic random number generator, ISAAC.
2
3   Copyright (C) 1999-2006, 2009-2010 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.  */
63void
64isaac_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  uint32_t *m = s->mm;	/* Pointer into state array */
69
70  a = s->a;
71  b = s->b + (++s->c);
72
73  do
74    {
75      isaac_step (a << 13, a, b, s->mm, m, ISAAC_WORDS / 2, r);
76      isaac_step (a >> 6, a, b, s->mm, m + 1, ISAAC_WORDS / 2, r + 1);
77      isaac_step (a << 2, a, b, s->mm, m + 2, ISAAC_WORDS / 2, r + 2);
78      isaac_step (a >> 16, a, b, s->mm, m + 3, ISAAC_WORDS / 2, r + 3);
79      r += 4;
80    }
81  while ((m += 4) < s->mm + ISAAC_WORDS / 2);
82  do
83    {
84      isaac_step (a << 13, a, b, s->mm, m, -ISAAC_WORDS / 2, r);
85      isaac_step (a >> 6, a, b, s->mm, m + 1, -ISAAC_WORDS / 2, r + 1);
86      isaac_step (a << 2, a, b, s->mm, m + 2, -ISAAC_WORDS / 2, r + 2);
87      isaac_step (a >> 16, a, b, s->mm, m + 3, -ISAAC_WORDS / 2, r + 3);
88      r += 4;
89    }
90  while ((m += 4) < s->mm + ISAAC_WORDS);
91  s->a = a;
92  s->b = b;
93}
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.  */
111static void
112isaac_mix (struct isaac_state *s, uint32_t const seed[/* ISAAC_WORDS */])
113{
114  int i;
115  uint32_t a = s->iv[0];
116  uint32_t b = s->iv[1];
117  uint32_t c = s->iv[2];
118  uint32_t d = s->iv[3];
119  uint32_t e = s->iv[4];
120  uint32_t f = s->iv[5];
121  uint32_t g = s->iv[6];
122  uint32_t h = s->iv[7];
123
124  for (i = 0; i < ISAAC_WORDS; i += 8)
125    {
126      a += seed[i];
127      b += seed[i + 1];
128      c += seed[i + 2];
129      d += seed[i + 3];
130      e += seed[i + 4];
131      f += seed[i + 5];
132      g += seed[i + 6];
133      h += seed[i + 7];
134
135      mix (a, b, c, d, e, f, g, h);
136
137      s->mm[i] = a;
138      s->mm[i + 1] = b;
139      s->mm[i + 2] = c;
140      s->mm[i + 3] = d;
141      s->mm[i + 4] = e;
142      s->mm[i + 5] = f;
143      s->mm[i + 6] = g;
144      s->mm[i + 7] = h;
145    }
146
147  s->iv[0] = a;
148  s->iv[1] = b;
149  s->iv[2] = c;
150  s->iv[3] = d;
151  s->iv[4] = e;
152  s->iv[5] = f;
153  s->iv[6] = g;
154  s->iv[7] = h;
155}
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 */
167static void
168isaac_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.  */
214static void
215isaac_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  memset (s->mm, 0, sizeof s->mm);
233  memcpy (s->iv, iv, sizeof s->iv);
234
235  /* s->c gets used for a data pointer during the seeding phase */
236  s->a = s->b = s->c = 0;
237}
238
239/* Add a buffer of seed material.  */
240static void
241isaac_seed_data (struct isaac_state *s, void const *buffer, size_t size)
242{
243  unsigned char const *buf = buffer;
244  unsigned char *p;
245  size_t avail;
246  size_t i;
247
248  avail = sizeof s->mm - s->c;	/* s->c is used as a write pointer */
249
250  /* Do any full buffers that are necessary */
251  while (size > avail)
252    {
253      p = (unsigned char *) s->mm + s->c;
254      for (i = 0; i < avail; i++)
255        p[i] ^= buf[i];
256      buf += avail;
257      size -= avail;
258      isaac_mix (s, s->mm);
259      s->c = 0;
260      avail = sizeof s->mm;
261    }
262
263  /* And the final partial block */
264  p = (unsigned char *) s->mm + s->c;
265  for (i = 0; i < size; i++)
266    p[i] ^= buf[i];
267  s->c = size;
268}
269
270
271/* End of seeding phase; get everything ready to produce output. */
272static void
273isaac_seed_finish (struct isaac_state *s)
274{
275  isaac_mix (s, s->mm);
276  isaac_mix (s, s->mm);
277  /* Now reinitialize c to start things off right */
278  s->c = 0;
279}
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.  */
284void
285isaac_seed (struct isaac_state *s)
286{
287  isaac_seed_start (s);
288
289  { pid_t t = getpid ();   ISAAC_SEED (s, t); }
290  { pid_t t = getppid ();  ISAAC_SEED (s, t); }
291  { uid_t t = getuid ();   ISAAC_SEED (s, t); }
292  { gid_t t = getgid ();   ISAAC_SEED (s, t); }
293
294  {
295    xtime_t t = gethrxtime ();
296    ISAAC_SEED (s, t);
297  }
298
299  isaac_seed_finish (s);
300}
301