summaryrefslogtreecommitdiff
path: root/lib/rand-isaac.c
diff options
context:
space:
mode:
Diffstat (limited to 'lib/rand-isaac.c')
-rw-r--r--lib/rand-isaac.c300
1 files changed, 300 insertions, 0 deletions
diff --git a/lib/rand-isaac.c b/lib/rand-isaac.c
new file mode 100644
index 000000000..6a0185934
--- /dev/null
+++ b/lib/rand-isaac.c
@@ -0,0 +1,300 @@
+/* Bob Jenkins's cryptographic random number generator, ISAAC.
+
+ Copyright (C) 1999-2006 Free Software Foundation, Inc.
+ Copyright (C) 1997, 1998, 1999 Colin Plumb.
+
+ This program is free software; you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation; either version 2, or (at your option)
+ any later version.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program; if not, write to the Free Software Foundation,
+ Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+
+ Written by Colin Plumb. */
+
+/*
+ * --------------------------------------------------------------------
+ * We need a source of random numbers for some data.
+ * Cryptographically secure is desirable, but it's not life-or-death
+ * so I can be a little bit experimental in the choice of RNGs here.
+ *
+ * This generator is based somewhat on RC4, but has analysis
+ * <http://burtleburtle.net/bob/rand/isaacafa.html>
+ * pointing to it actually being better. I like it because it's nice
+ * and fast, and because the author did good work analyzing it.
+ * --------------------------------------------------------------------
+ */
+
+#include "rand-isaac.h"
+
+#include <string.h>
+#include <unistd.h>
+
+#include "gethrxtime.h"
+
+
+/* This index operation is more efficient on many processors */
+#define ind(mm, x) \
+ (* (uint32_t *) ((char *) (mm) \
+ + ((x) & (ISAAC_WORDS - 1) * sizeof (uint32_t))))
+
+/*
+ * The central step. This uses two temporaries, x and y. mm is the
+ * whole state array, while m is a pointer to the current word. off is
+ * the offset from m to the word ISAAC_WORDS/2 words away in the mm array,
+ * i.e. +/- ISAAC_WORDS/2.
+ */
+#define isaac_step(mix, a, b, mm, m, off, r) \
+( \
+ a = ((a) ^ (mix)) + (m)[off], \
+ x = *(m), \
+ *(m) = y = ind (mm, x) + (a) + (b), \
+ *(r) = b = ind (mm, (y) >> ISAAC_LOG) + x \
+)
+
+/* Use and update *S to generate random data to fill R. */
+void
+isaac_refill (struct isaac_state *s, uint32_t r[ISAAC_WORDS])
+{
+ uint32_t a, b; /* Caches of a and b */
+ uint32_t x, y; /* Temps needed by isaac_step macro */
+ uint32_t *m = s->mm; /* Pointer into state array */
+
+ a = s->a;
+ b = s->b + (++s->c);
+
+ do
+ {
+ isaac_step (a << 13, a, b, s->mm, m, ISAAC_WORDS / 2, r);
+ isaac_step (a >> 6, a, b, s->mm, m + 1, ISAAC_WORDS / 2, r + 1);
+ isaac_step (a << 2, a, b, s->mm, m + 2, ISAAC_WORDS / 2, r + 2);
+ isaac_step (a >> 16, a, b, s->mm, m + 3, ISAAC_WORDS / 2, r + 3);
+ r += 4;
+ }
+ while ((m += 4) < s->mm + ISAAC_WORDS / 2);
+ do
+ {
+ isaac_step (a << 13, a, b, s->mm, m, -ISAAC_WORDS / 2, r);
+ isaac_step (a >> 6, a, b, s->mm, m + 1, -ISAAC_WORDS / 2, r + 1);
+ isaac_step (a << 2, a, b, s->mm, m + 2, -ISAAC_WORDS / 2, r + 2);
+ isaac_step (a >> 16, a, b, s->mm, m + 3, -ISAAC_WORDS / 2, r + 3);
+ r += 4;
+ }
+ while ((m += 4) < s->mm + ISAAC_WORDS);
+ s->a = a;
+ s->b = b;
+}
+
+/*
+ * The basic seed-scrambling step for initialization, based on Bob
+ * Jenkins' 256-bit hash.
+ */
+#define mix(a,b,c,d,e,f,g,h) \
+ ( a ^= b << 11, d += a, \
+ b += c, b ^= c >> 2, e += b, \
+ c += d, c ^= d << 8, f += c, \
+ d += e, d ^= e >> 16, g += d, \
+ e += f, e ^= f << 10, h += e, \
+ f += g, f ^= g >> 4, a += f, \
+ g += h, g ^= h << 8, b += g, \
+ h += a, h ^= a >> 9, c += h, \
+ a += b )
+
+/* The basic ISAAC initialization pass. */
+static void
+isaac_mix (struct isaac_state *s, uint32_t const seed[/* ISAAC_WORDS */])
+{
+ int i;
+ uint32_t a = s->iv[0];
+ uint32_t b = s->iv[1];
+ uint32_t c = s->iv[2];
+ uint32_t d = s->iv[3];
+ uint32_t e = s->iv[4];
+ uint32_t f = s->iv[5];
+ uint32_t g = s->iv[6];
+ uint32_t h = s->iv[7];
+
+ for (i = 0; i < ISAAC_WORDS; i += 8)
+ {
+ a += seed[i];
+ b += seed[i + 1];
+ c += seed[i + 2];
+ d += seed[i + 3];
+ e += seed[i + 4];
+ f += seed[i + 5];
+ g += seed[i + 6];
+ h += seed[i + 7];
+
+ mix (a, b, c, d, e, f, g, h);
+
+ s->mm[i] = a;
+ s->mm[i + 1] = b;
+ s->mm[i + 2] = c;
+ s->mm[i + 3] = d;
+ s->mm[i + 4] = e;
+ s->mm[i + 5] = f;
+ s->mm[i + 6] = g;
+ s->mm[i + 7] = h;
+ }
+
+ s->iv[0] = a;
+ s->iv[1] = b;
+ s->iv[2] = c;
+ s->iv[3] = d;
+ s->iv[4] = e;
+ s->iv[5] = f;
+ s->iv[6] = g;
+ s->iv[7] = h;
+}
+
+#if 0 /* Provided for reference only; not used in this code */
+/*
+ * Initialize the ISAAC RNG with the given seed material.
+ * Its size MUST be a multiple of ISAAC_BYTES, and may be
+ * stored in the s->mm array.
+ *
+ * This is a generalization of the original ISAAC initialization code
+ * to support larger seed sizes. For seed sizes of 0 and ISAAC_BYTES,
+ * it is identical.
+ */
+static void
+isaac_init (struct isaac_state *s, uint32_t const *seed, size_t seedsize)
+{
+ static uint32_t const iv[8] =
+ {
+ 0x1367df5a, 0x95d90059, 0xc3163e4b, 0x0f421ad8,
+ 0xd92a4a78, 0xa51a3c49, 0xc4efea1b, 0x30609119};
+ int i;
+
+# if 0
+ /* The initialization of iv is a precomputed form of: */
+ for (i = 0; i < 7; i++)
+ iv[i] = 0x9e3779b9; /* the golden ratio */
+ for (i = 0; i < 4; ++i) /* scramble it */
+ mix (iv[0], iv[1], iv[2], iv[3], iv[4], iv[5], iv[6], iv[7]);
+# endif
+ s->a = s->b = s->c = 0;
+
+ for (i = 0; i < 8; i++)
+ s->iv[i] = iv[i];
+
+ if (seedsize)
+ {
+ /* First pass (as in reference ISAAC code) */
+ isaac_mix (s, seed);
+ /* Second and subsequent passes (extension to ISAAC) */
+ while (seedsize -= ISAAC_BYTES)
+ {
+ seed += ISAAC_WORDS;
+ for (i = 0; i < ISAAC_WORDS; i++)
+ s->mm[i] += seed[i];
+ isaac_mix (s, s->mm);
+ }
+ }
+ else
+ {
+ /* The no seed case (as in reference ISAAC code) */
+ for (i = 0; i < ISAAC_WORDS; i++)
+ s->mm[i] = 0;
+ }
+
+ /* Final pass */
+ isaac_mix (s, s->mm);
+}
+#endif
+
+/* Initialize *S to a somewhat-random value. */
+static void
+isaac_seed_start (struct isaac_state *s)
+{
+ static uint32_t const iv[8] =
+ {
+ 0x1367df5a, 0x95d90059, 0xc3163e4b, 0x0f421ad8,
+ 0xd92a4a78, 0xa51a3c49, 0xc4efea1b, 0x30609119
+ };
+
+#if 0
+ /* The initialization of iv is a precomputed form of: */
+ int i;
+ for (i = 0; i < 7; i++)
+ iv[i] = 0x9e3779b9; /* the golden ratio */
+ for (i = 0; i < 4; ++i) /* scramble it */
+ mix (iv[0], iv[1], iv[2], iv[3], iv[4], iv[5], iv[6], iv[7]);
+#endif
+
+ memset (s->mm, 0, sizeof s->mm);
+ memcpy (s->iv, iv, sizeof s->iv);
+
+ /* s->c gets used for a data pointer during the seeding phase */
+ s->a = s->b = s->c = 0;
+}
+
+/* Add a buffer of seed material. */
+static void
+isaac_seed_data (struct isaac_state *s, void const *buffer, size_t size)
+{
+ unsigned char const *buf = buffer;
+ unsigned char *p;
+ size_t avail;
+ size_t i;
+
+ avail = sizeof s->mm - s->c; /* s->c is used as a write pointer */
+
+ /* Do any full buffers that are necessary */
+ while (size > avail)
+ {
+ p = (unsigned char *) s->mm + s->c;
+ for (i = 0; i < avail; i++)
+ p[i] ^= buf[i];
+ buf += avail;
+ size -= avail;
+ isaac_mix (s, s->mm);
+ s->c = 0;
+ avail = sizeof s->mm;
+ }
+
+ /* And the final partial block */
+ p = (unsigned char *) s->mm + s->c;
+ for (i = 0; i < size; i++)
+ p[i] ^= buf[i];
+ s->c = size;
+}
+
+
+/* End of seeding phase; get everything ready to produce output. */
+static void
+isaac_seed_finish (struct isaac_state *s)
+{
+ isaac_mix (s, s->mm);
+ isaac_mix (s, s->mm);
+ /* Now reinitialize c to start things off right */
+ s->c = 0;
+}
+#define ISAAC_SEED(s,x) isaac_seed_data (s, &(x), sizeof (x))
+
+/* Initialize *S to a somewhat-random value; this starts seeding,
+ seeds with somewhat-random data, and finishes seeding. */
+void
+isaac_seed (struct isaac_state *s)
+{
+ isaac_seed_start (s);
+
+ { pid_t t = getpid (); ISAAC_SEED (s, t); }
+ { pid_t t = getppid (); ISAAC_SEED (s, t); }
+ { uid_t t = getuid (); ISAAC_SEED (s, t); }
+ { gid_t t = getgid (); ISAAC_SEED (s, t); }
+
+ {
+ xtime_t t = gethrxtime ();
+ ISAAC_SEED (s, t);
+ }
+
+ isaac_seed_finish (s);
+}