1/*- 2 * Copyright (c) 2000-2013 Mark R V Murray 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions 7 * are met: 8 * 1. Redistributions of source code must retain the above copyright 9 * notice, this list of conditions and the following disclaimer 10 * in this position and unchanged. 11 * 2. Redistributions in binary form must reproduce the above copyright 12 * notice, this list of conditions and the following disclaimer in the 13 * documentation and/or other materials provided with the distribution. 14 * 15 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 16 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 17 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 18 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 19 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 20 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 21 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 22 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 23 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 24 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 25 * 26 */ 27 28#include <sys/cdefs.h> 29__FBSDID("$FreeBSD$"); 30 31#include "opt_random.h" 32 33#include <sys/param.h> 34#include <sys/kernel.h> 35#include <sys/lock.h> 36#include <sys/malloc.h> 37#include <sys/mutex.h> 38#include <sys/random.h> 39#include <sys/sysctl.h> 40#include <sys/systm.h> 41 42#include <crypto/rijndael/rijndael-api-fst.h> 43#include <crypto/sha2/sha2.h> 44 45#include <dev/random/hash.h> 46#include <dev/random/random_adaptors.h> 47#include <dev/random/randomdev_soft.h> 48#include <dev/random/yarrow.h> 49 50#define TIMEBIN 16 /* max value for Pt/t */ 51 52#define FAST 0 53#define SLOW 1 54 55/* This is the beastie that needs protecting. It contains all of the 56 * state that we are excited about. 57 * Exactly one is instantiated. 58 */ 59static struct random_state { 60 union { 61 uint8_t byte[BLOCKSIZE]; 62 uint64_t qword[BLOCKSIZE/sizeof(uint64_t)]; 63 } counter; /* C */ 64 struct randomdev_key key; /* K */ 65 u_int gengateinterval; /* Pg */ 66 u_int bins; /* Pt/t */ 67 u_int outputblocks; /* count output blocks for gates */ 68 u_int slowoverthresh; /* slow pool overthreshhold reseed count */ 69 struct pool { 70 struct source { 71 u_int bits; /* estimated bits of entropy */ 72 } source[ENTROPYSOURCE]; 73 u_int thresh; /* pool reseed threshhold */ 74 struct randomdev_hash hash; /* accumulated entropy */ 75 } pool[2]; /* pool[0] is fast, pool[1] is slow */ 76 u_int which; /* toggle - sets the current insertion pool */ 77} random_state; 78 79RANDOM_CHECK_UINT(gengateinterval, 4, 64); 80RANDOM_CHECK_UINT(bins, 2, 16); 81RANDOM_CHECK_UINT(fastthresh, (BLOCKSIZE*8)/4, (BLOCKSIZE*8)); /* Bit counts */ 82RANDOM_CHECK_UINT(slowthresh, (BLOCKSIZE*8)/4, (BLOCKSIZE*8)); /* Bit counts */ 83RANDOM_CHECK_UINT(slowoverthresh, 1, 5); 84 85static void generator_gate(void); 86static void reseed(u_int); 87 88/* The reseed thread mutex */ 89struct mtx random_reseed_mtx; 90 91/* 128-bit C = 0 */ 92/* Nothing to see here, folks, just an ugly mess. */ 93static void 94clear_counter(void) 95{ 96 random_state.counter.qword[0] = 0UL; 97 random_state.counter.qword[1] = 0UL; 98} 99 100/* 128-bit C = C + 1 */ 101/* Nothing to see here, folks, just an ugly mess. */ 102/* TODO: Make a Galois counter instead? */ 103static void 104increment_counter(void) 105{ 106 random_state.counter.qword[0]++; 107 if (!random_state.counter.qword[0]) 108 random_state.counter.qword[1]++; 109} 110 111/* Process a single stochastic event off the harvest queue */ 112void 113random_process_event(struct harvest *event) 114{ 115 u_int pl, overthreshhold[2]; 116 struct source *source; 117 enum esource src; 118 119#if 0 120 /* Do this better with DTrace */ 121 { 122 int i; 123 124 printf("Harvest:%16jX ", event->somecounter); 125 for (i = 0; i < event->size; i++) 126 printf("%02X", event->entropy[i]); 127 for (; i < 16; i++) 128 printf(" "); 129 printf(" %2d %2d %02X\n", event->size, event->bits, event->source); 130 } 131#endif 132 133 /* Accumulate the event into the appropriate pool */ 134 pl = random_state.which; 135 source = &random_state.pool[pl].source[event->source]; 136 randomdev_hash_iterate(&random_state.pool[pl].hash, event, 137 sizeof(*event)); 138 source->bits += event->bits; 139 140 /* Count the over-threshold sources in each pool */ 141 for (pl = 0; pl < 2; pl++) { 142 overthreshhold[pl] = 0; 143 for (src = RANDOM_START; src < ENTROPYSOURCE; src++) { 144 if (random_state.pool[pl].source[src].bits 145 > random_state.pool[pl].thresh) 146 overthreshhold[pl]++; 147 } 148 } 149 150 /* if any fast source over threshhold, reseed */ 151 if (overthreshhold[FAST]) 152 reseed(FAST); 153 154 /* if enough slow sources are over threshhold, reseed */ 155 if (overthreshhold[SLOW] >= random_state.slowoverthresh) 156 reseed(SLOW); 157 158 /* Invert the fast/slow pool selector bit */ 159 random_state.which = !random_state.which; 160} 161 162void 163random_yarrow_init_alg(struct sysctl_ctx_list *clist) 164{ 165 int i; 166 struct sysctl_oid *random_yarrow_o; 167 168 /* Yarrow parameters. Do not adjust these unless you have 169 * have a very good clue about what they do! 170 */ 171 random_yarrow_o = SYSCTL_ADD_NODE(clist, 172 SYSCTL_STATIC_CHILDREN(_kern_random), 173 OID_AUTO, "yarrow", CTLFLAG_RW, 0, 174 "Yarrow Parameters"); 175 176 SYSCTL_ADD_PROC(clist, 177 SYSCTL_CHILDREN(random_yarrow_o), OID_AUTO, 178 "gengateinterval", CTLTYPE_INT|CTLFLAG_RW, 179 &random_state.gengateinterval, 10, 180 random_check_uint_gengateinterval, "I", 181 "Generation gate interval"); 182 183 SYSCTL_ADD_PROC(clist, 184 SYSCTL_CHILDREN(random_yarrow_o), OID_AUTO, 185 "bins", CTLTYPE_INT|CTLFLAG_RW, 186 &random_state.bins, 10, 187 random_check_uint_bins, "I", 188 "Execution time tuner"); 189 190 SYSCTL_ADD_PROC(clist, 191 SYSCTL_CHILDREN(random_yarrow_o), OID_AUTO, 192 "fastthresh", CTLTYPE_INT|CTLFLAG_RW, 193 &random_state.pool[0].thresh, (3*(BLOCKSIZE*8))/4, 194 random_check_uint_fastthresh, "I", 195 "Fast reseed threshold"); 196 197 SYSCTL_ADD_PROC(clist, 198 SYSCTL_CHILDREN(random_yarrow_o), OID_AUTO, 199 "slowthresh", CTLTYPE_INT|CTLFLAG_RW, 200 &random_state.pool[1].thresh, (BLOCKSIZE*8), 201 random_check_uint_slowthresh, "I", 202 "Slow reseed threshold"); 203 204 SYSCTL_ADD_PROC(clist, 205 SYSCTL_CHILDREN(random_yarrow_o), OID_AUTO, 206 "slowoverthresh", CTLTYPE_INT|CTLFLAG_RW, 207 &random_state.slowoverthresh, 2, 208 random_check_uint_slowoverthresh, "I", 209 "Slow over-threshold reseed"); 210 211 random_state.gengateinterval = 10; 212 random_state.bins = 10; 213 random_state.pool[0].thresh = (3*(BLOCKSIZE*8))/4; 214 random_state.pool[1].thresh = (BLOCKSIZE*8); 215 random_state.slowoverthresh = 2; 216 random_state.which = FAST; 217 218 /* Initialise the fast and slow entropy pools */ 219 for (i = 0; i < 2; i++) 220 randomdev_hash_init(&random_state.pool[i].hash); 221 222 /* Clear the counter */ 223 clear_counter(); 224 225 /* Set up a lock for the reseed process */ 226 mtx_init(&random_reseed_mtx, "Yarrow reseed", NULL, MTX_DEF); 227} 228 229void 230random_yarrow_deinit_alg(void) 231{ 232 mtx_destroy(&random_reseed_mtx); 233} 234 235static void 236reseed(u_int fastslow) 237{ 238 /* Interrupt-context stack is a limited resource; make large 239 * structures static. 240 */ 241 static uint8_t v[TIMEBIN][KEYSIZE]; /* v[i] */ 242 static struct randomdev_hash context; 243 uint8_t hash[KEYSIZE]; /* h' */ 244 uint8_t temp[KEYSIZE]; 245 u_int i; 246 enum esource j; 247 248#if 0 249 printf("Yarrow: %s reseed\n", fastslow == FAST ? "fast" : "slow"); 250#endif 251 252 /* The reseed task must not be jumped on */ 253 mtx_lock(&random_reseed_mtx); 254 255 /* 1. Hash the accumulated entropy into v[0] */ 256 257 randomdev_hash_init(&context); 258 /* Feed the slow pool hash in if slow */ 259 if (fastslow == SLOW) 260 randomdev_hash_iterate(&context, 261 &random_state.pool[SLOW].hash, 262 sizeof(struct randomdev_hash)); 263 randomdev_hash_iterate(&context, 264 &random_state.pool[FAST].hash, sizeof(struct randomdev_hash)); 265 randomdev_hash_finish(&context, v[0]); 266 267 /* 2. Compute hash values for all v. _Supposed_ to be computationally 268 * intensive. 269 */ 270 271 if (random_state.bins > TIMEBIN) 272 random_state.bins = TIMEBIN; 273 for (i = 1; i < random_state.bins; i++) { 274 randomdev_hash_init(&context); 275 /* v[i] #= h(v[i - 1]) */ 276 randomdev_hash_iterate(&context, v[i - 1], KEYSIZE); 277 /* v[i] #= h(v[0]) */ 278 randomdev_hash_iterate(&context, v[0], KEYSIZE); 279 /* v[i] #= h(i) */ 280 randomdev_hash_iterate(&context, &i, sizeof(u_int)); 281 /* Return the hashval */ 282 randomdev_hash_finish(&context, v[i]); 283 } 284 285 /* 3. Compute a new key; h' is the identity function here; 286 * it is not being ignored! 287 */ 288 289 randomdev_hash_init(&context); 290 randomdev_hash_iterate(&context, &random_state.key, KEYSIZE); 291 for (i = 1; i < random_state.bins; i++) 292 randomdev_hash_iterate(&context, &v[i], KEYSIZE); 293 randomdev_hash_finish(&context, temp); 294 randomdev_encrypt_init(&random_state.key, temp); 295 296 /* 4. Recompute the counter */ 297 298 clear_counter(); 299 randomdev_encrypt(&random_state.key, random_state.counter.byte, temp, BLOCKSIZE); 300 memcpy(random_state.counter.byte, temp, BLOCKSIZE); 301 302 /* 5. Reset entropy estimate accumulators to zero */ 303 304 for (i = 0; i <= fastslow; i++) 305 for (j = RANDOM_START; j < ENTROPYSOURCE; j++) 306 random_state.pool[i].source[j].bits = 0; 307 308 /* 6. Wipe memory of intermediate values */ 309 310 memset((void *)v, 0, sizeof(v)); 311 memset((void *)temp, 0, sizeof(temp)); 312 memset((void *)hash, 0, sizeof(hash)); 313 314 /* 7. Dump to seed file */ 315 /* XXX Not done here yet */ 316 317 /* Unblock the device if it was blocked due to being unseeded */ 318 randomdev_unblock(); 319 320 /* Release the reseed mutex */ 321 mtx_unlock(&random_reseed_mtx); 322} 323 324/* Internal function to return processed entropy from the PRNG */ 325int 326random_yarrow_read(void *buf, int count) 327{ 328 static int cur = 0; 329 static int gate = 1; 330 static uint8_t genval[KEYSIZE]; 331 size_t tomove; 332 int i; 333 int retval; 334 335 /* Check for final read request */ 336 if (buf == NULL && count == 0) 337 return (0); 338 339 /* The reseed task must not be jumped on */ 340 mtx_lock(&random_reseed_mtx); 341 342 if (gate) { 343 generator_gate(); 344 random_state.outputblocks = 0; 345 gate = 0; 346 } 347 if (count > 0 && (size_t)count >= BLOCKSIZE) { 348 retval = 0; 349 for (i = 0; i < count; i += BLOCKSIZE) { 350 increment_counter(); 351 randomdev_encrypt(&random_state.key, random_state.counter.byte, genval, BLOCKSIZE); 352 tomove = MIN(count - i, BLOCKSIZE); 353 memcpy((char *)buf + i, genval, tomove); 354 if (++random_state.outputblocks >= random_state.gengateinterval) { 355 generator_gate(); 356 random_state.outputblocks = 0; 357 } 358 retval += (int)tomove; 359 cur = 0; 360 } 361 } 362 else { 363 if (!cur) { 364 increment_counter(); 365 randomdev_encrypt(&random_state.key, random_state.counter.byte, genval, BLOCKSIZE); 366 memcpy(buf, genval, (size_t)count); 367 cur = BLOCKSIZE - count; 368 if (++random_state.outputblocks >= random_state.gengateinterval) { 369 generator_gate(); 370 random_state.outputblocks = 0; 371 } 372 retval = count; 373 } 374 else { 375 retval = MIN(cur, count); 376 memcpy(buf, &genval[BLOCKSIZE - cur], (size_t)retval); 377 cur -= retval; 378 } 379 } 380 mtx_unlock(&random_reseed_mtx); 381 return (retval); 382} 383 384static void 385generator_gate(void) 386{ 387 u_int i; 388 uint8_t temp[KEYSIZE]; 389 390 for (i = 0; i < KEYSIZE; i += BLOCKSIZE) { 391 increment_counter(); 392 randomdev_encrypt(&random_state.key, random_state.counter.byte, temp + i, BLOCKSIZE); 393 } 394 395 randomdev_encrypt_init(&random_state.key, temp); 396 memset((void *)temp, 0, KEYSIZE); 397} 398 399/* Helper routine to perform explicit reseeds */ 400void 401random_yarrow_reseed(void) 402{ 403#ifdef RANDOM_DEBUG 404 int i; 405 406 printf("%s(): fast:", __func__); 407 for (i = RANDOM_START; i < ENTROPYSOURCE; ++i) 408 printf(" %d", random_state.pool[FAST].source[i].bits); 409 printf("\n"); 410 printf("%s(): slow:", __func__); 411 for (i = RANDOM_START; i < ENTROPYSOURCE; ++i) 412 printf(" %d", random_state.pool[SLOW].source[i].bits); 413 printf("\n"); 414#endif 415 reseed(SLOW); 416} 417