lib/rand-isaac.c

   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 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   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.  */
 111 static void
 112 isaac_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  */
 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 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   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.  */
 240 static void
 241 isaac_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. */
 272 static void
 273 isaac_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.  */
 284 void
 285 isaac_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 }