yarrow.c revision 91600
1/*- 2 * Copyright (c) 2000 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 * $FreeBSD: head/sys/dev/random/yarrow.c 91600 2002-03-03 19:44:22Z markm $ 27 */ 28 29#include <sys/param.h> 30#include <sys/systm.h> 31#include <sys/kernel.h> 32#include <sys/lock.h> 33#include <sys/mutex.h> 34#include <sys/random.h> 35#include <sys/sysctl.h> 36 37#include <crypto/rijndael/rijndael.h> 38 39#include <dev/random/hash.h> 40#include <dev/random/randomdev.h> 41#include <dev/random/yarrow.h> 42 43/* #define DEBUG */ 44 45RANDOM_CHECK_UINT(gengateinterval, 4, 64); 46RANDOM_CHECK_UINT(bins, 2, 16); 47RANDOM_CHECK_UINT(fastthresh, BLOCKSIZE/4, BLOCKSIZE); 48RANDOM_CHECK_UINT(slowthresh, BLOCKSIZE/4, BLOCKSIZE); 49RANDOM_CHECK_UINT(slowoverthresh, 1, 5); 50 51/* Structure holding the entropy state */ 52static struct random_state random_state; 53 54SYSCTL_NODE(_kern_random, OID_AUTO, yarrow, CTLFLAG_RW, 0, "Yarrow Parameters"); 55SYSCTL_PROC(_kern_random_yarrow, OID_AUTO, gengateinterval, 56 CTLTYPE_INT|CTLFLAG_RW, &random_state.gengateinterval, 10, 57 random_check_uint_gengateinterval, "I", "Generator Gate Interval"); 58SYSCTL_PROC(_kern_random_yarrow, OID_AUTO, bins, 59 CTLTYPE_INT|CTLFLAG_RW, &random_state.bins, 10, 60 random_check_uint_bins, "I", "Execution time tuner"); 61SYSCTL_PROC(_kern_random_yarrow, OID_AUTO, fastthresh, 62 CTLTYPE_INT|CTLFLAG_RW, &random_state.pool[0].thresh, (3*BLOCKSIZE)/4, 63 random_check_uint_fastthresh, "I", "Fast reseed threshold"); 64SYSCTL_PROC(_kern_random_yarrow, OID_AUTO, slowthresh, 65 CTLTYPE_INT|CTLFLAG_RW, &random_state.pool[1].thresh, BLOCKSIZE, 66 random_check_uint_slowthresh, "I", "Slow reseed threshold"); 67SYSCTL_PROC(_kern_random_yarrow, OID_AUTO, slowoverthresh, 68 CTLTYPE_INT|CTLFLAG_RW, &random_state.slowoverthresh, 2, 69 random_check_uint_slowoverthresh, "I", "Slow over-threshold reseed"); 70 71static void generator_gate(void); 72static void reseed(u_int); 73 74/* The reseed thread mutex */ 75static struct mtx random_reseed_mtx; 76 77/* Process a single stochastic event off the harvest queue */ 78void 79random_process_event(struct harvest *event) 80{ 81 u_int pl, overthreshhold[2]; 82 struct source *source; 83 enum esource src; 84 85 /* Unpack the event into the appropriate source accumulator */ 86 pl = random_state.which; 87 source = &random_state.pool[pl].source[event->source]; 88 yarrow_hash_iterate(&random_state.pool[pl].hash, event->entropy, 89 sizeof(event->entropy)); 90 yarrow_hash_iterate(&random_state.pool[pl].hash, &event->somecounter, 91 sizeof(event->somecounter)); 92 source->frac += event->frac; 93 source->bits += event->bits + source->frac/1024; 94 source->frac %= 1024; 95 96 /* Count the over-threshold sources in each pool */ 97 for (pl = 0; pl < 2; pl++) { 98 overthreshhold[pl] = 0; 99 for (src = RANDOM_START; src < ENTROPYSOURCE; src++) { 100 if (random_state.pool[pl].source[src].bits 101 > random_state.pool[pl].thresh) 102 overthreshhold[pl]++; 103 } 104 } 105 106 /* if any fast source over threshhold, reseed */ 107 if (overthreshhold[FAST]) 108 reseed(FAST); 109 110 /* if enough slow sources are over threshhold, reseed */ 111 if (overthreshhold[SLOW] >= random_state.slowoverthresh) 112 reseed(SLOW); 113 114 /* Invert the fast/slow pool selector bit */ 115 random_state.which = !random_state.which; 116} 117 118void 119random_init(void) 120{ 121 int i; 122 123 /* Yarrow parameters. Do not adjust these unless you have 124 * have a very good clue about what they do! 125 */ 126 random_state.gengateinterval = 10; 127 random_state.bins = 10; 128 random_state.pool[0].thresh = (3*BLOCKSIZE)/4; 129 random_state.pool[1].thresh = BLOCKSIZE; 130 random_state.slowoverthresh = 2; 131 random_state.which = FAST; 132 133 /* Initialise the fast and slow entropy pools */ 134 for (i = 0; i < 2; i++) 135 yarrow_hash_init(&random_state.pool[i].hash); 136 137 /* Clear the counter */ 138 for (i = 0; i < 4; i++) 139 random_state.counter[i] = 0; 140 141 /* Set up a lock for the reseed process */ 142 mtx_init(&random_reseed_mtx, "random reseed", MTX_DEF); 143} 144 145void 146random_deinit(void) 147{ 148 mtx_destroy(&random_reseed_mtx); 149} 150 151static void 152reseed(u_int fastslow) 153{ 154 /* Interrupt-context stack is a limited resource; make large 155 * structures static. 156 */ 157 static u_char v[TIMEBIN][KEYSIZE]; /* v[i] */ 158 static struct yarrowhash context; 159 u_char hash[KEYSIZE]; /* h' */ 160 u_char temp[KEYSIZE]; 161 u_int i; 162 enum esource j; 163 164#ifdef DEBUG 165 mtx_lock(&Giant); 166 printf("Reseed type %d\n", fastslow); 167 mtx_unlock(&Giant); 168#endif 169 170 /* The reseed task must not be jumped on */ 171 mtx_lock(&random_reseed_mtx); 172 173 /* 1. Hash the accumulated entropy into v[0] */ 174 175 yarrow_hash_init(&context); 176 /* Feed the slow pool hash in if slow */ 177 if (fastslow == SLOW) 178 yarrow_hash_iterate(&context, 179 &random_state.pool[SLOW].hash, 180 sizeof(struct yarrowhash)); 181 yarrow_hash_iterate(&context, 182 &random_state.pool[FAST].hash, sizeof(struct yarrowhash)); 183 yarrow_hash_finish(&context, v[0]); 184 185 /* 2. Compute hash values for all v. _Supposed_ to be computationally 186 * intensive. 187 */ 188 189 if (random_state.bins > TIMEBIN) 190 random_state.bins = TIMEBIN; 191 for (i = 1; i < random_state.bins; i++) { 192 yarrow_hash_init(&context); 193 /* v[i] #= h(v[i - 1]) */ 194 yarrow_hash_iterate(&context, v[i - 1], KEYSIZE); 195 /* v[i] #= h(v[0]) */ 196 yarrow_hash_iterate(&context, v[0], KEYSIZE); 197 /* v[i] #= h(i) */ 198 yarrow_hash_iterate(&context, &i, sizeof(u_int)); 199 /* Return the hashval */ 200 yarrow_hash_finish(&context, v[i]); 201 } 202 203 /* 3. Compute a new key; h' is the identity function here; 204 * it is not being ignored! 205 */ 206 207 yarrow_hash_init(&context); 208 yarrow_hash_iterate(&context, &random_state.key, KEYSIZE); 209 for (i = 1; i < random_state.bins; i++) 210 yarrow_hash_iterate(&context, &v[i], KEYSIZE); 211 yarrow_hash_finish(&context, temp); 212 yarrow_encrypt_init(&random_state.key, temp); 213 214 /* 4. Recompute the counter */ 215 216 for (i = 0; i < 4; i++) 217 random_state.counter[i] = 0; 218 yarrow_encrypt(&random_state.key, random_state.counter, temp); 219 memcpy(random_state.counter, temp, sizeof(random_state.counter)); 220 221 /* 5. Reset entropy estimate accumulators to zero */ 222 223 for (i = 0; i <= fastslow; i++) { 224 for (j = RANDOM_START; j < ENTROPYSOURCE; j++) { 225 random_state.pool[i].source[j].bits = 0; 226 random_state.pool[i].source[j].frac = 0; 227 } 228 } 229 230 /* 6. Wipe memory of intermediate values */ 231 232 memset((void *)v, 0, sizeof(v)); 233 memset((void *)temp, 0, sizeof(temp)); 234 memset((void *)hash, 0, sizeof(hash)); 235 236 /* 7. Dump to seed file */ 237 /* XXX Not done here yet */ 238 239 /* Release the reseed mutex */ 240 mtx_unlock(&random_reseed_mtx); 241 242#ifdef DEBUG 243 mtx_lock(&Giant); 244 printf("Reseed finish\n"); 245 mtx_unlock(&Giant); 246#endif 247 248 /* Unblock the device if it was blocked due to being unseeded */ 249 random_unblock(); 250} 251 252/* Internal function to do return processed entropy from the 253 * Yarrow PRNG 254 */ 255int 256read_random_real(void *buf, int count) 257{ 258 static int cur = 0; 259 static int gate = 1; 260 static u_char genval[KEYSIZE]; 261 int i; 262 int retval; 263 264 /* The reseed task must not be jumped on */ 265 mtx_lock(&random_reseed_mtx); 266 267 if (gate) { 268 generator_gate(); 269 random_state.outputblocks = 0; 270 gate = 0; 271 } 272 if (count > 0 && (size_t)count >= sizeof(random_state.counter)) { 273 retval = 0; 274 for (i = 0; i < count; i += (int)sizeof(random_state.counter)) { 275 random_state.counter[0]++; 276 yarrow_encrypt(&random_state.key, random_state.counter, 277 genval); 278 memcpy((char *)buf + i, genval, 279 sizeof(random_state.counter)); 280 if (++random_state.outputblocks >= 281 random_state.gengateinterval) { 282 generator_gate(); 283 random_state.outputblocks = 0; 284 } 285 retval += (int)sizeof(random_state.counter); 286 } 287 } 288 else { 289 if (!cur) { 290 random_state.counter[0]++; 291 yarrow_encrypt(&random_state.key, random_state.counter, 292 genval); 293 memcpy(buf, genval, (size_t)count); 294 cur = (int)sizeof(random_state.counter) - count; 295 if (++random_state.outputblocks >= 296 random_state.gengateinterval) { 297 generator_gate(); 298 random_state.outputblocks = 0; 299 } 300 retval = count; 301 } 302 else { 303 retval = cur < count ? cur : count; 304 memcpy(buf, 305 &genval[(int)sizeof(random_state.counter) - cur], 306 (size_t)retval); 307 cur -= retval; 308 } 309 } 310 mtx_unlock(&random_reseed_mtx); 311 return retval; 312} 313 314static void 315generator_gate(void) 316{ 317 u_int i; 318 u_char temp[KEYSIZE]; 319 320#ifdef DEBUG 321 mtx_lock(&Giant); 322 printf("Generator gate\n"); 323 mtx_unlock(&Giant); 324#endif 325 326 for (i = 0; i < KEYSIZE; i += sizeof(random_state.counter)) { 327 random_state.counter[0]++; 328 yarrow_encrypt(&random_state.key, random_state.counter, 329 &(temp[i])); 330 } 331 332 yarrow_encrypt_init(&random_state.key, temp); 333 memset((void *)temp, 0, KEYSIZE); 334 335#ifdef DEBUG 336 mtx_lock(&Giant); 337 printf("Generator gate finish\n"); 338 mtx_unlock(&Giant); 339#endif 340} 341 342/* Helper routine to perform explicit reseeds */ 343void 344random_reseed(void) 345{ 346 reseed(FAST); 347} 348