1 /* Yarrow Random Number Generator (True Randomness Achieved in Software) * 2 * Copyright (c) 1998-2000 by Yarrow Charnot, Identikey <mailto://ycharnot@identikey.com> 3 * All Lefts, Rights, Ups, Downs, Forwards, Backwards, Pasts and Futures Reserved * 4 */ 5 6 /* Made into a BeOS /dev/random and /dev/urandom by Daniel Berlin */ 7 8 9 #include "yarrow_rng.h" 10 11 #include <stdlib.h> 12 #include <thread.h> 13 14 15 //#define TRACE_DRIVER 16 #ifdef TRACE_DRIVER 17 # define TRACE(x...) dprintf("random: " x) 18 #else 19 # define TRACE(x...) ; 20 #endif 21 #define CALLED() TRACE("CALLED %s\n", __PRETTY_FUNCTION__) 22 23 24 #define rotr32(x, n) ((((uint32)(x)) >> ((int) ((n) & 31))) | (((uint32)(x)) << ((int) ((32 - ((n) & 31)))))) 25 #define rotl32(x, n) ((((uint32)(x)) << ((int) ((n) & 31))) | (((uint32)(x)) >> ((int) ((32 - ((n) & 31)))))) 26 27 #define bswap32(x) \ 28 ((rotl32((uint32)(x), 8) & 0x00ff00ff) | (rotr32((uint32)(x), 8) & 0xff00ff00)) 29 30 typedef union _OCTET { 31 uint64 Q[1]; 32 uint32 D[2]; 33 uint16 W[4]; 34 uint8 B[8]; 35 } OCTET; 36 37 #define NK 257 /* internal state size */ 38 #define NI 120 /* seed in increment */ 39 #define NA 70 /* rand out increment A */ 40 #define NB 139 /* rand out increment B */ 41 42 typedef struct _ch_randgen { 43 OCTET ira[NK]; /* numbers live here */ 44 OCTET *seedptr; /* next seed pointer */ 45 OCTET *rndptrA; /* randomizing pointer #1 */ 46 OCTET *rndptrB; /* randomizing pointer #2 */ 47 OCTET *rndptrX; /* main randout pointer */ 48 OCTET rndLeft; /* left rand accumulator */ 49 OCTET rndRite; /* rite rand accumulator */ 50 } ch_randgen; 51 52 53 static ch_randgen *sRandomEnv; 54 static uint32 sRandomCount = 0; 55 56 extern void hash_block(const unsigned char *block, const unsigned int block_byte_size, unsigned char *md); 57 58 59 #define HASH_BITS 160 /* I use Tiger. Modify it to match your HASH */ 60 #define HASH_BLOCK_BITS 512 /* I use Tiger. Modify it to match your HASH */ 61 #define HASH_BYTES (HASH_BITS / 8) 62 #define HASH_BLOCK_BYTES (HASH_BLOCK_BITS / 8) 63 #define HASH_OCTETS (HASH_BITS / 64) 64 #define HASH_BLOCK_OCTETS (HASH_BLOCK_BITS / 64) 65 66 67 /* attach by Yarrow Charnot. attaches x to y. can be seen as about 2-3 rounds of RC6 encryption 68 */ 69 70 static inline void 71 attach(OCTET *y, const OCTET *x, const uint32 anyA, const uint32 anyB, 72 const uint32 oddC, const uint32 oddD) 73 { 74 register OCTET _x; 75 register OCTET _y; 76 77 _x.D[0] = x->D[0]; 78 _x.D[1] = x->D[1]; 79 _y.D[0] = y->D[0]; 80 _y.D[1] = y->D[1]; 81 _x.D[0] = rotl32(((bswap32(_x.D[0]) | 1) * x->D[1]), 5); 82 _x.D[1] = rotl32((bswap32(_x.D[1]) | 1) * x->D[0], 5); 83 _y.D[0] = (bswap32(rotl32(_y.D[0] ^ _x.D[0], _x.D[1])) + anyA) * oddC; 84 _y.D[1] = (bswap32(rotl32(_y.D[1] ^ _x.D[1], _x.D[0])) + anyB) * oddD; 85 y->D[1] = _y.D[0]; 86 y->D[0] = _y.D[1]; 87 } 88 89 90 /** detach by Yarrow Charnot. detaches x from y. can be seen as about 91 * 2-3 rounds of RC6 decryption. 92 */ 93 94 static inline void 95 detach(OCTET *y, const OCTET *x, const uint32 sameA, const uint32 sameB, 96 const uint32 invoddC, const uint32 invoddD) 97 { 98 register OCTET _x; 99 register OCTET _y; 100 101 _x.D[0] = x->D[0]; 102 _x.D[1] = x->D[1]; 103 _y.D[0] = y->D[1]; 104 _y.D[1] = y->D[0]; 105 _x.D[0] = rotl32((bswap32(_x.D[0]) | 1) * x->D[1], 5); 106 _x.D[1] = rotl32((bswap32(_x.D[1]) | 1) * x->D[0], 5); 107 _y.D[0] = rotr32(bswap32(_y.D[0] * invoddC - sameA), _x.D[1]) ^ _x.D[0]; 108 _y.D[1] = rotr32(bswap32(_y.D[1] * invoddD - sameB), _x.D[0]) ^ _x.D[1]; 109 y->D[0] = _y.D[0]; 110 y->D[1] = _y.D[1]; 111 } 112 113 114 /** QUICKLY seeds in a 64 bit number, modified so that a subsequent call really 115 * "stirs" in another seed value (no bullshit XOR here!) 116 */ 117 118 static inline void 119 chseed(ch_randgen *prandgen, const uint64 seed) 120 { 121 prandgen->seedptr += NI; 122 if (prandgen->seedptr >= (prandgen->ira + NK)) 123 prandgen->seedptr -= NK; 124 125 attach(prandgen->seedptr, (OCTET *) &seed, 0x213D42F6U, 0x6552DAF9U, 126 0x2E496B7BU, 0x1749A255U); 127 } 128 129 130 /** The heart of Yarrow 2000 Chuma Random Number Generator: fast and reliable 131 * randomness collection. 132 * Thread yielding function is the most OPTIMAL source of randomness combined 133 * with a clock counter. 134 * It doesn't have to switch to another thread, the call itself is random enough. 135 * Test it yourself. 136 * This FASTEST way to collect minimal randomness on each step couldn't use the 137 * processor any LESS. Even functions based on just creation of threads and their 138 * destruction can not compare by speed. 139 * Temporary file creation is just a little extra thwart to bewilder the processor 140 * cache and pipes. 141 * If you make clock_counter() (system_time()) return all 0's, still produces a 142 * stream indistinguishable from random. 143 */ 144 145 static void 146 reseed(ch_randgen *prandgen, const uint32 initTimes) 147 { 148 volatile uint32 i, j; 149 OCTET x, y; 150 151 x.Q[0] = 0; 152 153 for (j = initTimes; j; j--) { 154 for (i = NK * initTimes; i; i--) { 155 // TODO: Yielding sounds all nice in principle, but this will take 156 // ages (at least initTimes * initTimes * NK * quantum, i.e. ca. 49s 157 // for initTimes == 8) in a busy system. Since perl initializes its 158 // random seed on startup by reading from /dev/urandom, perl 159 // programs are all but unusable when at least one other thread 160 // hogs the CPU. 161 thread_yield(); 162 163 // TODO: Introduce a clock_counter() function that directly returns 164 // the value of the hardware clock counter. This will be cheaper 165 // and will yield more randomness. 166 y.Q[0] += system_time(); 167 attach(&x, &y, 0x52437EFFU, 0x026A4CEBU, 0xD9E66AC9U, 0x56E5A975U); 168 attach(&y, &x, 0xC70B8B41U, 0x9126B036U, 0x36CC6FDBU, 0x31D477F7U); 169 chseed(prandgen, y.Q[0]); 170 } 171 } 172 } 173 174 175 /* returns a 64 bit of Yarrow 2000 Chuma RNG random number */ 176 177 static inline uint64 178 chrand(ch_randgen *prandgen) 179 { 180 prandgen->rndptrX++; 181 prandgen->rndptrA += NA; 182 prandgen->rndptrB += NB; 183 if (prandgen->rndptrX >= (prandgen->ira + NK)) { 184 prandgen->rndptrX -= NK; 185 reseed (prandgen, 1); 186 } 187 188 if (prandgen->rndptrA >= (prandgen->ira + NK)) 189 prandgen->rndptrA -= NK; 190 if (prandgen->rndptrB >= (prandgen->ira + NK)) 191 prandgen->rndptrB -= NK; 192 193 attach(&prandgen->rndLeft, prandgen->rndptrX, prandgen->rndptrA->D[0], 194 prandgen->rndptrA->D[1], 0x49A3BC71UL, 0x60E285FDUL); 195 attach(&prandgen->rndRite, &prandgen->rndLeft, prandgen->rndptrB->D[0], 196 prandgen->rndptrB->D[1], 0xC366A5FDUL, 0x20C763EFUL); 197 198 chseed(prandgen, prandgen->rndRite.Q[0]); 199 200 return prandgen->rndRite.Q[0] ^ prandgen->rndLeft.Q[0]; 201 } 202 203 204 /** returns a 32 bit random number */ 205 206 static inline uint32 207 chrand32(ch_randgen *prandgen) 208 { 209 OCTET r = {{chrand(prandgen)}}; 210 return r.D[0] ^ r.D[1]; 211 } 212 213 214 /** returns an 8 bit random number */ 215 216 static inline uint8 217 chrand8(ch_randgen *prandgen) 218 { 219 OCTET r = {{chrand(prandgen)}}; 220 return r.B[0] ^ r.B[1] ^ r.B[2] ^ r.B[3] ^ r.B[4] ^ r.B[5] ^ r.B[6] ^ r.B[7]; 221 } 222 223 /* generates a cryptographically secure random big number 0 <= x < 32^n */ 224 /* automatically reseeds if necessary or if requested 1/16 of the internal state or more */ 225 /* 226 __inline void bigrand (ch_randgen *prandgen, unsigned __int32 *x, unsigned __int32 n) 227 { 228 unsigned int i; 229 OCTET block[HASH_BLOCK_OCTETS]; 230 OCTET hash[HASH_OCTETS]; 231 OCTET *j; 232 if (n >= NK/8) reseed (prandgen, 1); 233 for (*x++ = n; (signed) n > 0; ) 234 { 235 for (i = 0; i < HASH_BLOCK_OCTETS; i++) block->Q[i] += chrand (prandgen) + hash 236 ->Q[i % HASH_OCTETS]; 237 hash_block (block->B, HASH_BLOCK_BYTES, hash->B); 238 for (i = HASH_OCTETS, j = hash; i && ((signed) n > 0); i--, j++, x += 2, n -= 2) 239 { 240 attach ((OCTET *) &x, j, 0x0AEF7ED2U, 0x3F85C5C1U, 0xD3EFB373U, 241 0x13ECF0B9U); 242 } 243 } 244 } 245 */ 246 247 248 /** Initializes Yarrow 2000 Chuma Random Number Generator. 249 * Reseeding about 8 times prior to the first use is recommended. 250 * More than 16 will probably be a bit too much as time increases 251 * by n^2. 252 */ 253 254 static ch_randgen * 255 new_chrand(const unsigned int inittimes) 256 { 257 ch_randgen *prandgen; 258 259 prandgen = (ch_randgen *)malloc(sizeof(ch_randgen)); 260 if (prandgen == NULL) 261 return NULL; 262 263 prandgen->seedptr = prandgen->ira; 264 prandgen->rndptrX = prandgen->ira; 265 prandgen->rndptrA = prandgen->ira; 266 prandgen->rndptrB = prandgen->ira; 267 prandgen->rndLeft.Q[0] = 0x1A4B385C72D69E0FULL; 268 prandgen->rndRite.Q[0] = 0x9C805FE7361A42DBULL; 269 reseed (prandgen, inittimes); 270 271 prandgen->seedptr = prandgen->ira + chrand (prandgen) % NK; 272 prandgen->rndptrX = prandgen->ira + chrand (prandgen) % NK; 273 prandgen->rndptrA = prandgen->ira + chrand (prandgen) % NK; 274 prandgen->rndptrB = prandgen->ira + chrand (prandgen) % NK; 275 return prandgen; 276 } 277 278 279 /** Clean up after chuma */ 280 281 static void 282 kill_chrand(ch_randgen *randgen) 283 { 284 free(sRandomEnv); 285 } 286 287 288 // #pragma mark - 289 // Random interface 290 291 292 static status_t 293 yarrow_rng_read(void* cookie, void *_buffer, size_t *_numBytes) 294 { 295 sRandomCount += *_numBytes; 296 297 /* Reseed if we have or are gonna use up > 1/16th the entropy around */ 298 if (sRandomCount >= NK/8) { 299 sRandomCount = 0; 300 reseed(sRandomEnv, 1); 301 } 302 303 /* ToDo: Yes, i know this is not the way we should do it. What we really should do is 304 * take the md5 or sha1 hash of the state of the pool, and return that. Someday. 305 */ 306 int32 *buffer = (int32 *)_buffer; 307 uint32 i; 308 for (i = 0; i < *_numBytes / 4; i++) 309 buffer[i] = chrand32(sRandomEnv); 310 uint8 *buffer8 = (uint8 *)_buffer; 311 for (uint32 j = 0; j < *_numBytes % 4; j++) 312 buffer8[(i * 4) + j] = chrand8(sRandomEnv); 313 314 return B_OK; 315 } 316 317 318 static status_t 319 yarrow_rng_write(void* cookie, const void *buffer, size_t *_numBytes) 320 { 321 OCTET* data = (OCTET*)buffer; 322 for (size_t i = 0; i < *_numBytes / sizeof(OCTET); i++) { 323 chseed(sRandomEnv, data->Q[0]); 324 data++; 325 } 326 return B_OK; 327 } 328 329 330 // #pragma mark - 331 332 333 static status_t 334 yarrow_init_bus(device_node* node, void** bus_cookie) 335 { 336 CALLED(); 337 sRandomEnv = new_chrand(8); 338 if (sRandomEnv == NULL) 339 return B_NO_MEMORY; 340 return B_OK; 341 } 342 343 344 static void 345 yarrow_uninit_bus(void* bus_cookie) 346 { 347 CALLED(); 348 kill_chrand(sRandomEnv); 349 } 350 351 352 static void 353 yarrow_bus_removed(void* bus_cookie) 354 { 355 return; 356 } 357 358 359 // #pragma mark - 360 361 362 random_module_info gYarrowRandomModule = { 363 { 364 { 365 YARROW_RNG_SIM_MODULE_NAME, 366 0, 367 NULL 368 }, 369 370 NULL, // supports_device, 371 NULL, // register_device, 372 yarrow_init_bus, 373 yarrow_uninit_bus, 374 NULL, // register child devices 375 NULL, // rescan 376 yarrow_bus_removed, 377 }, 378 yarrow_rng_read, 379 yarrow_rng_write 380 }; 381