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