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