]> git.saurik.com Git - apple/xnu.git/blob - bsd/dev/random/YarrowCoreLib/src/prng.c
xnu-792.10.96.tar.gz
[apple/xnu.git] / bsd / dev / random / YarrowCoreLib / src / prng.c
1 /*
2 * Copyright (c) 1999, 2000-2001 Apple Computer, Inc. All rights reserved.
3 *
4 * @APPLE_LICENSE_HEADER_START@
5 *
6 * The contents of this file constitute Original Code as defined in and
7 * are subject to the Apple Public Source License Version 1.1 (the
8 * "License"). You may not use this file except in compliance with the
9 * License. Please obtain a copy of the License at
10 * http://www.apple.com/publicsource and read it before using this file.
11 *
12 * This Original Code and all software distributed under the License are
13 * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER
14 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
15 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
16 * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT. Please see the
17 * License for the specific language governing rights and limitations
18 * under the License.
19 *
20 * @APPLE_LICENSE_HEADER_END@
21 */
22
23 /*
24 File: prng.c
25
26 Contains: Core routines for the Counterpane Yarrow PRNG.
27
28 Written by: Counterpane, Inc.
29
30 Copyright: (c) 2000 by Apple Computer, Inc., all rights reserved.
31
32 Change History (most recent first):
33
34 02/10/99 dpm Created, based on Counterpane source.
35
36 */
37 /*
38 prng.c
39
40 Core routines for the Counterpane PRNG
41 */
42 #include "userdefines.h"
43 #include "assertverify.h"
44 #include "dev/random/YarrowCoreLib/include/yarrowUtils.h"
45
46 #if defined(macintosh) || defined(__APPLE__)
47 /* FIXME - this file needs to be in a platform-independent place */
48
49 #include "macOnly.h"
50 #endif /* macintosh */
51 #include "smf.h"
52 #include "sha1mod.h"
53 #include "entropysources.h"
54 #include "comp.h"
55 #include "dev/random/YarrowCoreLib/include/yarrow.h"
56 #include "prng.h"
57 #include "prngpriv.h"
58
59
60 #define _MAX(a,b) (((a)>(b))?(a):(b))
61 #define _MIN(a,b) (((a)<(b))?(a):(b))
62
63 #if defined(macintosh) || defined(__APPLE__)
64 /*
65 * No mutexes in this module for Macintosh/OSX. We handle the
66 * required locking elsewhere.
67 */
68 #define MUTEX_ENABLE 0
69
70 #include <string.h> /* memcpy, etc. */
71 #if TARGET_API_MAC_OSX
72 #include <sys/time.h> /* for timespec */
73 #elif TARGET_API_MAC_CARBON
74 #include <Timer.h> /* Microseconds */
75 #include <Math64.h>
76 #elif KERNEL_BUILD
77 #include <sys/time.h>
78 #else
79 #error Unknown TARGET_API
80 #endif /* TARGET_API */
81 #else
82 #define MUTEX_ENABLE 1
83 #endif /* macintosh */
84
85 #if MUTEX_ENABLE
86 static HANDLE Statmutex = NULL;
87 static DWORD mutexCreatorId = 0;
88 #endif
89
90 #pragma mark -
91 #pragma mark * * * Static Utility functions * * *
92
93 /* All error checking should be done in the function that calls these */
94
95 /*
96 * out := SHA1(IV | out)
97 */
98 static void
99 prng_do_SHA1(GEN_CTX *ctx)
100 {
101 SHA1_CTX sha;
102
103 SHA1Init(&sha);
104 SHA1Update(&sha,ctx->IV,20);
105 SHA1Update(&sha,ctx->out,20);
106 SHA1Final(ctx->out,&sha);
107 ctx->index = 0;
108 }
109
110 /*
111 * IV := newState
112 * out := SHA1(IV)
113 *
114 * Called from init, prngForceReseed(), and prngOutput()
115 * as anti-backtracking mechanism.
116 */
117 static void
118 prng_make_new_state(GEN_CTX *ctx,BYTE *newState)
119 {
120 SHA1_CTX sha;
121
122 memcpy(ctx->IV,newState,20);
123 SHA1Init(&sha);
124 SHA1Update(&sha,ctx->IV,20);
125 SHA1Final(ctx->out,&sha);
126 ctx->numout = 0;
127 ctx->index = 0;
128 }
129
130 #if SLOW_POLL_ENABLE
131
132
133 /* Initialize the secret state with a slow poll */
134 /* Currently only called from prngInitialize */
135
136 #define SPLEN 65536 /* 64K */
137
138 static void
139 prng_slow_init(PRNG *p)
140 /* This fails silently and must be fixed. */
141 {
142 SHA1_CTX* ctx = NULL;
143 MMPTR mmctx = MM_NULL;
144 BYTE* bigbuf = NULL;
145 MMPTR mmbigbuf = MM_NULL;
146 BYTE* buf = NULL;
147 MMPTR mmbuf = MM_NULL;
148 DWORD polllength;
149
150 mmbigbuf = mmMalloc(SPLEN);
151 if(mmbigbuf == MM_NULL) {goto cleanup_slow_init;}
152 bigbuf = (BYTE*)mmGetPtr(mmbigbuf);
153
154 mmbuf = mmMalloc(20);
155 if(mmbuf == MM_NULL) {goto cleanup_slow_init;}
156 buf = (BYTE*)mmGetPtr(mmbuf);
157
158 mmctx = mmMalloc(sizeof(SHA1_CTX));
159 if(mmctx == MM_NULL) {goto cleanup_slow_init;}
160 ctx = (SHA1_CTX*)mmGetPtr(mmctx);
161
162
163 /* Initialize the secret state. */
164 /* Init entropy pool */
165 SHA1Init(&p->pool);
166 /* Init output generator */
167 polllength = prng_slow_poll(bigbuf,SPLEN);
168 SHA1Init(ctx);
169 SHA1Update(ctx,bigbuf,polllength);
170 SHA1Final(buf,ctx);
171 prng_make_new_state(&p->outstate, buf);
172
173 cleanup_slow_init:
174 mmFree(mmctx);
175 mmFree(mmbigbuf);
176 mmFree(mmbuf);
177
178 return;
179 }
180
181 #endif /* SLOW_POLL_ENABLE */
182
183 /* In-place modifed bubble sort */
184 static void
185 bubbleSort( UINT *data, LONG len )
186 {
187 LONG i,last,newlast;
188 UINT temp;
189
190 last = len-1;
191 while(last!=-1)
192 {
193 newlast = -1;
194 for(i=0;i<last;i++)
195 {
196 if(data[i+1] > data[i])
197 {
198 newlast = i;
199 temp = data[i];
200 data[i] = data[i+1];
201 data[i+1] = temp;
202 }
203 }
204 last = newlast;
205 }
206 }
207
208 #pragma mark -
209 #pragma mark * * * Public functions * * *
210
211 /* Set up the PRNG */
212 prng_error_status
213 prngInitialize(PrngRef *prng)
214 {
215 UINT i;
216 comp_error_status resp;
217 prng_error_status retval = PRNG_ERR_LOW_MEMORY;
218 MMPTR mmp;
219 PRNG *p;
220
221 mmInit();
222
223 #if MUTEX_ENABLE
224 /* Create the mutex */
225 /* NOTE: on return the mutex should bve held, since our caller (prngInitialize)
226 * will release it.
227 */
228 if(mutexCreatorId!=0) {return PRNG_ERR_REINIT;}
229 Statmutex = CreateMutex(NULL,TRUE,NULL);
230 if(Statmutex == NULL) {mutexCreatorId = 0; return PRNG_ERR_MUTEX;}
231 DuplicateHandle(GetCurrentProcess(),Statmutex,GetCurrentProcess(),&mutex,SYNCHRONIZE,FALSE,0);
232 mutexCreatorId = GetCurrentProcessId();
233 #endif /* MUTEX_ENABLE */
234
235 /* Assign memory */
236 mmp = mmMalloc(sizeof(PRNG));
237 if(mmp==MM_NULL)
238 {
239 goto cleanup_init;
240 }
241 else
242 {
243 p = (PRNG*)mmGetPtr(mmp);
244 memset(p, 0, sizeof(PRNG));
245 }
246
247 /* Initialize Variables */
248 for(i=0;i<TOTAL_SOURCES;i++)
249 {
250 p->poolSize[i] = 0;
251 p->poolEstBits[i] = 0;
252 }
253
254 #ifdef WIN_NT
255 /* Setup security on the registry so that remote users cannot predict the slow pool */
256 prng_set_NT_security();
257 #endif
258
259 /* Initialize the secret state. */
260 /* FIXME - might want to make this an option here and have the caller
261 * do it after we return....? */
262 SHA1Init(&p->pool);
263 #if SLOW_POLL_ENABLE
264 prng_slow_init(p); /* Does a slow poll and then calls prng_make_state(...) */
265 #else
266 /* NULL init */
267 prng_do_SHA1(&p->outstate);
268 prng_make_new_state(&p->outstate, p->outstate.out);
269 #endif /* SLOW_POLL_ENABLE */
270
271 /* Initialize compression routines */
272 for(i=0;i<COMP_SOURCES;i++)
273 {
274 resp = comp_init((p->comp_state)+i);
275 if(resp!=COMP_SUCCESS) {retval = PRNG_ERR_COMPRESSION; goto cleanup_init;}
276 }
277
278 p->ready = PRNG_READY;
279 *prng = (PrngRef)p;
280
281 return PRNG_SUCCESS;
282
283 cleanup_init:
284 /* Program failed on one of the mmmallocs */
285 mmFree(mmp);
286 mmp = MM_NULL;
287
288 #if MUTEX_ENABLE
289 CloseHandle(Statmutex);
290 Statmutex = NULL;
291 mutexCreatorId = 0;
292 #endif
293
294 return retval; /* default PRNG_ERR_LOW_MEMORY */
295 }
296
297 /* Provide output */
298 prng_error_status
299 prngOutput(PRNG *p, BYTE *outbuf,UINT outbuflen)
300 {
301 UINT i;
302 GEN_CTX *ctx = &p->outstate;
303
304 CHECKSTATE(p);
305 GENCHECK(p);
306 PCHECK(outbuf);
307 chASSERT(BACKTRACKLIMIT > 0);
308
309 for(i=0;i<outbuflen;i++,ctx->index++,ctx->numout++)
310 {
311 /* Check backtracklimit */
312 if(ctx->numout > BACKTRACKLIMIT)
313 {
314 prng_do_SHA1(ctx);
315 prng_make_new_state(ctx, ctx->out);
316 }
317 /* Check position in IV */
318 if(ctx->index>=20)
319 {
320 prng_do_SHA1(ctx);
321 }
322 /* Output data */
323 outbuf[i] = (ctx->out)[ctx->index];
324 }
325
326 return PRNG_SUCCESS;
327 }
328
329
330 /* Cause the PRNG to reseed now regardless of entropy pool */
331 /* Should this be public? */
332 prng_error_status
333 prngForceReseed(PRNG *p, LONGLONG ticks)
334 {
335 int i;
336 #ifdef WIN_NT
337 FILETIME a,b,c,usertime;
338 #endif
339 BYTE buf[64];
340 BYTE dig[20];
341 #if defined(macintosh) || defined(__APPLE__)
342 #if (defined(TARGET_API_MAC_OSX) || defined(KERNEL_BUILD))
343 struct timeval tv;
344 int64_t endTime, curTime;
345 #else /* TARGET_API_MAC_CARBON */
346 UnsignedWide uwide; /* struct needed for Microseconds() */
347 LONGLONG start;
348 LONGLONG now;
349 #endif
350 #endif
351
352 CHECKSTATE(p);
353 POOLCHECK(p);
354 ZCHECK(ticks);
355
356 /* Set up start and end times */
357 #if defined(macintosh) || defined(__APPLE__)
358 #if (defined(TARGET_API_MAC_OSX) || defined(KERNEL_BUILD))
359 /* note we can't loop for more than a million microseconds */
360 #ifdef KERNEL_BUILD
361 microuptime (&tv);
362 #else
363 gettimeofday(&tv, NULL);
364 #endif
365 endTime = (int64_t)tv.tv_sec*1000000LL + (int64_t)tv.tv_usec + ticks;
366 #else /* TARGET_API_MAC_OSX */
367 Microseconds(&uwide);
368 start = UnsignedWideToUInt64(uwide);
369 #endif /* TARGET_API_xxx */
370 #endif /* macintosh */
371 do
372 {
373 /* Do a couple of iterations between time checks */
374 prngOutput(p, buf,64);
375 SHA1Update(&p->pool,buf,64);
376 prngOutput(p, buf,64);
377 SHA1Update(&p->pool,buf,64);
378 prngOutput(p, buf,64);
379 SHA1Update(&p->pool,buf,64);
380 prngOutput(p, buf,64);
381 SHA1Update(&p->pool,buf,64);
382 prngOutput(p, buf,64);
383 SHA1Update(&p->pool,buf,64);
384
385 #if defined(macintosh) || defined(__APPLE__)
386 #if defined(TARGET_API_MAC_OSX) || defined(KERNEL_BUILD)
387 #ifdef TARGET_API_MAC_OSX
388 gettimeofday(&tv, NULL);
389 #else
390 microuptime (&tv);
391 curTime = (int64_t)tv.tv_sec*1000000LL + (int64_t)tv.tv_usec;
392 #endif
393 } while(curTime < endTime);
394 #else
395 Microseconds(&uwide);
396 now = UnsignedWideToUInt64(uwide);
397 } while ( (now-start) < ticks) ;
398 #endif
399 #else
400 } while ( (now-start) < ticks) ;
401 #endif
402 SHA1Final(dig,&p->pool);
403 SHA1Update(&p->pool,dig,20);
404 SHA1Final(dig,&p->pool);
405
406 /* Reset secret state */
407 SHA1Init(&p->pool);
408 prng_make_new_state(&p->outstate,dig);
409
410 /* Clear counter variables */
411 for(i=0;i<TOTAL_SOURCES;i++)
412 {
413 p->poolSize[i] = 0;
414 p->poolEstBits[i] = 0;
415 }
416
417 /* Cleanup memory */
418 trashMemory(dig,20*sizeof(char));
419 trashMemory(buf,64*sizeof(char));
420
421 return PRNG_SUCCESS;
422 }
423
424
425 /* Input a state into the PRNG */
426 prng_error_status
427 prngProcessSeedBuffer(PRNG *p, BYTE *buf,LONGLONG ticks)
428 {
429 CHECKSTATE(p);
430 GENCHECK(p);
431 PCHECK(buf);
432
433 /* Put the data into the entropy, add some data from the unknown state, reseed */
434 SHA1Update(&p->pool,buf,20); /* Put it into the entropy pool */
435 prng_do_SHA1(&p->outstate); /* Output 20 more bytes and */
436 SHA1Update(&p->pool,p->outstate.out,20);/* add it to the pool as well. */
437 prngForceReseed(p, ticks); /* Do a reseed */
438 return prngOutput(p, buf,20); /* Return the first 20 bytes of output in buf */
439 }
440
441
442 /* Take some "random" data and make more "random-looking" data from it */
443 /* note: this routine has no context, no mutex wrapper */
444 prng_error_status
445 prngStretch(BYTE *inbuf,UINT inbuflen,BYTE *outbuf,UINT outbuflen) {
446 long int left,prev;
447 SHA1_CTX ctx;
448 BYTE dig[20];
449
450 PCHECK(inbuf);
451 PCHECK(outbuf);
452
453 if(inbuflen >= outbuflen)
454 {
455 memcpy(outbuf,inbuf,outbuflen);
456 return PRNG_SUCCESS;
457 }
458 else /* Extend using SHA1 hash of inbuf */
459 {
460 SHA1Init(&ctx);
461 SHA1Update(&ctx,inbuf,inbuflen);
462 SHA1Final(dig,&ctx);
463 for(prev=0,left=outbuflen;left>0;prev+=20,left-=20)
464 {
465 SHA1Update(&ctx,dig,20);
466 SHA1Final(dig,&ctx);
467 memcpy(outbuf+prev,dig,(left>20)?20:left);
468 }
469 trashMemory(dig,20*sizeof(BYTE));
470
471 return PRNG_SUCCESS;
472 }
473
474 return PRNG_ERR_PROGRAM_FLOW;
475 }
476
477
478 /* Add entropy to the PRNG from a source */
479 prng_error_status
480 prngInput(PRNG *p, BYTE *inbuf,UINT inbuflen,UINT poolnum, __unused UINT estbits)
481 {
482 #ifndef YARROW_KERNEL
483 comp_error_status resp;
484 #endif
485
486 CHECKSTATE(p);
487 POOLCHECK(p);
488 PCHECK(inbuf);
489 if(poolnum >= TOTAL_SOURCES) {return PRNG_ERR_OUT_OF_BOUNDS;}
490
491 /* Add to entropy pool */
492 SHA1Update(&p->pool,inbuf,inbuflen);
493
494 #ifndef YARROW_KERNEL
495 /* skip this step for the kernel */
496
497 /* Update pool size, pool user estimate and pool compression context */
498 p->poolSize[poolnum] += inbuflen;
499 p->poolEstBits[poolnum] += estbits;
500 if(poolnum<COMP_SOURCES)
501 {
502 resp = comp_add_data((p->comp_state)+poolnum,inbuf,inbuflen);
503 if(resp!=COMP_SUCCESS) {return PRNG_ERR_COMPRESSION;}
504 }
505 #endif /* YARROW_KERNEL */
506
507 return PRNG_SUCCESS;
508 }
509
510
511
512 /* If we have enough entropy, allow a reseed of the system */
513 prng_error_status
514 prngAllowReseed(PRNG *p, LONGLONG ticks)
515 {
516 UINT temp[TOTAL_SOURCES];
517 LONG i;
518 UINT sum;
519 #ifndef KERNEL_BUILD
520 float ratio;
521 #endif
522
523 #ifndef KERNEL_BUILD
524 comp_error_status resp;
525 #endif
526
527 CHECKSTATE(p);
528
529 for(i=0;i<ENTROPY_SOURCES;i++)
530 {
531 /* Make sure that compression-based entropy estimates are current */
532 #ifndef KERNEL_BUILD // floating point in a kernel is BAD!
533 resp = comp_get_ratio((p->comp_state)+i,&ratio);
534 if(resp!=COMP_SUCCESS) {return PRNG_ERR_COMPRESSION;}
535 /* Use 4 instead of 8 to half compression estimate */
536 temp[i] = (int)(ratio*p->poolSize[i]*4);
537 #else
538 temp[i] = p->poolSize[i] * 4;
539 #endif
540
541 }
542 /* Use minumum of user and compression estimate for compressed sources */
543 for(i=ENTROPY_SOURCES;i<COMP_SOURCES;i++)
544 {
545 #ifndef KERNEL_BUILD
546 /* Make sure that compression-based entropy estimates are current */
547 resp = comp_get_ratio((p->comp_state)+i,&ratio);
548 if(resp!=COMP_SUCCESS) {return PRNG_ERR_COMPRESSION;}
549 /* Use 4 instead of 8 to half compression estimate */
550 temp[i] = _MIN((int)(ratio*p->poolSize[i]*4),(int)p->poolEstBits[i]);
551 #else
552 temp[i] = _MIN (p->poolSize[i] * 4, p->poolEstBits[i]);
553 #endif
554
555 }
556 /* Use user estimate for remaining sources */
557 for(i=COMP_SOURCES;i<TOTAL_SOURCES;i++) {temp[i] = p->poolEstBits[i];}
558
559 if(K > 0) {
560 /* pointless if we're not ignoring any sources */
561 bubbleSort(temp,TOTAL_SOURCES);
562 }
563 for(i=K,sum=0;i<TOTAL_SOURCES;sum+=temp[i++]); /* Stupid C trick */
564 if(sum>THRESHOLD)
565 return prngForceReseed(p, ticks);
566 else
567 return PRNG_ERR_NOT_ENOUGH_ENTROPY;
568
569 return PRNG_ERR_PROGRAM_FLOW;
570 }
571
572 #if SLOW_POLL_ENABLE
573 /* Call a slow poll and insert the data into the entropy pool */
574 static prng_error_status
575 prngSlowPoll(PRNG *p, UINT pollsize)
576 {
577 BYTE *buf;
578 DWORD len;
579 prng_error_status retval;
580
581 CHECKSTATE(p);
582
583 buf = (BYTE*)malloc(pollsize);
584 if(buf==NULL) {return PRNG_ERR_LOW_MEMORY;}
585 len = prng_slow_poll(buf,pollsize); /* OS specific call */
586 retval = prngInput(p, buf,len,SLOWPOLLSOURCE, len * 8);
587 trashMemory(buf,pollsize);
588 free(buf);
589
590 return retval;
591 }
592 #endif /* SLOW_POLL_ENABLE */
593
594
595 /* Delete the PRNG */
596 prng_error_status
597 prngDestroy(PRNG *p)
598 {
599 UINT i;
600
601 #if MUTEX_ENABLE
602 if(GetCurrentProcessId()!=mutexCreatorId) {return PRNG_ERR_WRONG_CALLER;}
603 #endif
604 if(p==NULL) {return PRNG_SUCCESS;} /* Well, there is nothing to destroy... */
605
606 p->ready = PRNG_NOT_READY;
607
608 for(i=0;i<COMP_SOURCES;i++)
609 {
610 comp_end((p->comp_state)+i);
611 }
612
613 #if MUTEX_ENABLE
614 CloseHandle(Statmutex);
615 Statmutex = NULL;
616 mutexCreatorId = 0;
617 #endif
618
619 return PRNG_SUCCESS;
620 }
621
622