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