bsd/dev/random/YarrowCoreLib/src/prng.c

   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
  92 static HANDLE Statmutex = NULL;
  93 static DWORD mutexCreatorId = 0;
  94 #endif
  95
  96 #pragma mark -
  97 #pragma mark * * * Static Utility functions * * *
  98
  99 /* All error checking should be done in the function that calls these */
 100
 101 /*
 102  * out := SHA1(IV | out)
 103  */
 104 static void
 105 prng_do_SHA1(GEN_CTX *ctx)
 106 {
 107         YSHA1_CTX sha;
 108
 109         YSHA1Init(&sha);
 110         YSHA1Update(&sha,ctx->IV,20);
 111         YSHA1Update(&sha,ctx->out,20);
 112         YSHA1Final(ctx->out,&sha);
 113         ctx->index = 0;
 114 }
 115
 116 /*
 117  * IV  := newState
 118  * out := SHA1(IV)
 119  *
 120  * Called from init, prngForceReseed(), and prngOutput()
 121  * as anti-backtracking mechanism.
 122  */
 123 static void
 124 prng_make_new_state(GEN_CTX *ctx,BYTE *newState)
 125 {
 126         YSHA1_CTX sha;
 127
 128         memcpy(ctx->IV,newState,20);
 129         YSHA1Init(&sha);
 130         YSHA1Update(&sha,ctx->IV,20);
 131         YSHA1Final(ctx->out,&sha);
 132         ctx->numout = 0;
 133         ctx->index = 0;
 134 }
 135
 136 #if             SLOW_POLL_ENABLE
 137
 138
 139 /* Initialize the secret state with a slow poll */
 140 /* Currently only called from prngInitialize */
 141
 142 #define SPLEN 65536  /* 64K */
 143
 144 static void
 145 prng_slow_init(PRNG *p)
 146 /* This fails silently and must be fixed. */
 147 {
 148         YSHA1_CTX* ctx = NULL;
 149         MMPTR mmctx = MM_NULL;
 150         BYTE* bigbuf = NULL;
 151         MMPTR mmbigbuf = MM_NULL;
 152         BYTE* buf = NULL;
 153         MMPTR mmbuf = MM_NULL;
 154         DWORD polllength;
 155
 156         mmbigbuf = mmMalloc(SPLEN);
 157         if(mmbigbuf == MM_NULL) {goto cleanup_slow_init;}
 158         bigbuf = (BYTE*)mmGetPtr(mmbigbuf);
 159
 160         mmbuf = mmMalloc(20);
 161         if(mmbuf == MM_NULL) {goto cleanup_slow_init;}
 162         buf = (BYTE*)mmGetPtr(mmbuf);
 163
 164         mmctx = mmMalloc(sizeof(YSHA1_CTX));
 165         if(mmctx == MM_NULL) {goto cleanup_slow_init;}
 166         ctx = (YSHA1_CTX*)mmGetPtr(mmctx);
 167
 168
 169         /* Initialize the secret state. */
 170         /* Init entropy pool */
 171         YSHA1Init(&p->pool);
 172         /* Init output generator */
 173         polllength = prng_slow_poll(bigbuf,SPLEN);
 174         YSHA1Init(ctx);
 175         YSHA1Update(ctx,bigbuf,polllength);
 176         YSHA1Final(buf,ctx);
 177         prng_make_new_state(&p->outstate, buf);
 178
 179 cleanup_slow_init:
 180         mmFree(mmctx);
 181         mmFree(mmbigbuf);
 182         mmFree(mmbuf);
 183
 184         return;
 185 }
 186
 187 #endif  /* SLOW_POLL_ENABLE */
 188
 189 /* In-place modifed bubble sort */
 190 static void
 191 bubbleSort( UINT *data, LONG len )
 192 {
 193         LONG    i,last,newlast;
 194         UINT    temp;
 195
 196         last = len-1;
 197         while(last!=-1)
 198         {
 199                 newlast = -1;
 200                 for(i=0;i<last;i++)
 201                 {
 202                         if(data[i+1] > data[i])
 203                         {
 204                                 newlast = i;
 205                                 temp = data[i];
 206                                 data[i] = data[i+1];
 207                                 data[i+1] = temp;
 208                         }
 209                 }
 210                 last = newlast;
 211         }
 212 }
 213
 214 #pragma mark -
 215 #pragma mark * * * Public functions * * *
 216
 217 /* Set up the PRNG */
 218 prng_error_status
 219 prngInitialize(PrngRef *prng)
 220 {
 221         UINT i;
 222         comp_error_status resp;
 223         prng_error_status retval = PRNG_ERR_LOW_MEMORY;
 224         MMPTR   mmp;
 225         PRNG    *p;
 226
 227         mmInit();
 228
 229         #if     MUTEX_ENABLE
 230         /* Create the mutex */
 231         /* NOTE: on return the mutex should bve held, since our caller (prngInitialize)
 232          * will release it.
 233          */
 234         if(mutexCreatorId!=0) {return PRNG_ERR_REINIT;}
 235         Statmutex = CreateMutex(NULL,TRUE,NULL);
 236         if(Statmutex == NULL) {mutexCreatorId = 0; return PRNG_ERR_MUTEX;}
 237         DuplicateHandle(GetCurrentProcess(),Statmutex,GetCurrentProcess(),&mutex,SYNCHRONIZE,FALSE,0);
 238         mutexCreatorId = GetCurrentProcessId();
 239         #endif  /* MUTEX_ENABLE */
 240
 241         /* Assign memory */
 242         mmp = mmMalloc(sizeof(PRNG));
 243         if(mmp==MM_NULL)
 244         {
 245                 goto cleanup_init;
 246         }
 247         else
 248         {
 249                 p = (PRNG*)mmGetPtr(mmp);
 250                 memset(p, 0, sizeof(PRNG));
 251         }
 252
 253         /* Initialize Variables */
 254         for(i=0;i<TOTAL_SOURCES;i++)
 255         {
 256                 p->poolSize[i] = 0;
 257                 p->poolEstBits[i] = 0;
 258         }
 259
 260 #ifdef WIN_NT
 261         /* Setup security on the registry so that remote users cannot predict the slow pool */
 262         prng_set_NT_security();
 263 #endif
 264
 265         /* Initialize the secret state. */
 266         /* FIXME - might want to make this an option here and have the caller
 267          * do it after we return....? */
 268         YSHA1Init(&p->pool);
 269 #if             SLOW_POLL_ENABLE
 270         prng_slow_init(p);      /* Does a slow poll and then calls prng_make_state(...) */
 271 #else
 272         /* NULL init */
 273         prng_do_SHA1(&p->outstate);
 274         prng_make_new_state(&p->outstate, p->outstate.out);
 275 #endif  /* SLOW_POLL_ENABLE */
 276
 277         /* Initialize compression routines */
 278         for(i=0;i<COMP_SOURCES;i++)
 279         {
 280                 resp = comp_init((p->comp_state)+i);
 281                 if(resp!=COMP_SUCCESS) {retval = PRNG_ERR_COMPRESSION; goto cleanup_init;}
 282         }
 283
 284         p->ready = PRNG_READY;
 285         *prng = (PrngRef)p;
 286
 287         return PRNG_SUCCESS;
 288
 289 cleanup_init:
 290         /* Program failed on one of the mmmallocs */
 291         mmFree(mmp);
 292         mmp = MM_NULL;
 293
 294         #if             MUTEX_ENABLE
 295         CloseHandle(Statmutex);
 296         Statmutex = NULL;
 297         mutexCreatorId = 0;
 298         #endif
 299
 300         return retval; /* default PRNG_ERR_LOW_MEMORY */
 301 }
 302
 303 /* Provide output */
 304 prng_error_status
 305 prngOutput(PRNG *p, BYTE *outbuf,UINT outbuflen)
 306 {
 307         UINT i;
 308         GEN_CTX *ctx = &p->outstate;
 309
 310         CHECKSTATE(p);
 311         GENCHECK(p);
 312         PCHECK(outbuf);
 313         chASSERT(BACKTRACKLIMIT > 0);
 314
 315         for(i=0;i<outbuflen;i++,ctx->index++,ctx->numout++)
 316         {
 317                 /* Check backtracklimit */
 318                 if(ctx->numout > BACKTRACKLIMIT)
 319                 {
 320                         prng_do_SHA1(ctx);
 321                         prng_make_new_state(ctx, ctx->out);
 322                 }
 323                 /* Check position in IV */
 324                 if(ctx->index>=20)
 325                 {
 326                         prng_do_SHA1(ctx);
 327                 }
 328                 /* Output data */
 329                 outbuf[i] = (ctx->out)[ctx->index];
 330         }
 331
 332         return PRNG_SUCCESS;
 333 }
 334
 335
 336 /* Cause the PRNG to reseed now regardless of entropy pool */
 337 /* Should this be public? */
 338 prng_error_status
 339 prngForceReseed(PRNG *p, LONGLONG ticks)
 340 {
 341         int i;
 342 #ifdef WIN_NT
 343         FILETIME a,b,c,usertime;
 344 #endif
 345         BYTE buf[64];
 346         BYTE dig[20];
 347 #if     defined(macintosh) || defined(__APPLE__)
 348         #if             (defined(TARGET_API_MAC_OSX) || defined(KERNEL_BUILD))
 349                 struct timeval  tv;
 350                 int64_t                 endTime, curTime;
 351         #else   /* TARGET_API_MAC_CARBON */
 352                 UnsignedWide    uwide;          /* struct needed for Microseconds() */
 353                 LONGLONG                start;
 354                 LONGLONG                now;
 355         #endif
 356 #endif
 357
 358         CHECKSTATE(p);
 359         POOLCHECK(p);
 360         ZCHECK(ticks);
 361
 362         /* Set up start and end times */
 363         #if             defined(macintosh) || defined(__APPLE__)
 364                 #if             (defined(TARGET_API_MAC_OSX) || defined(KERNEL_BUILD))
 365                         /* note we can't loop for more than a million microseconds */
 366             #ifdef KERNEL_BUILD
 367                 microuptime (&tv);
 368             #else
 369                 gettimeofday(&tv, NULL);
 370             #endif
 371                         endTime = (int64_t)tv.tv_sec*1000000LL + (int64_t)tv.tv_usec + ticks;
 372                 #else   /* TARGET_API_MAC_OSX */
 373                         Microseconds(&uwide);
 374                         start = UnsignedWideToUInt64(uwide);
 375                 #endif  /* TARGET_API_xxx */
 376         #endif  /* macintosh */
 377         do
 378         {
 379                 /* Do a couple of iterations between time checks */
 380                 prngOutput(p, buf,64);
 381                 YSHA1Update(&p->pool,buf,64);
 382                 prngOutput(p, buf,64);
 383                 YSHA1Update(&p->pool,buf,64);
 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
 391 #if             defined(macintosh) || defined(__APPLE__)
 392         #if             defined(TARGET_API_MAC_OSX) || defined(KERNEL_BUILD)
 393         #ifdef TARGET_API_MAC_OSX
 394             gettimeofday(&tv, NULL);
 395         #else
 396             microuptime (&tv);
 397             curTime = (int64_t)tv.tv_sec*1000000LL + (int64_t)tv.tv_usec;
 398         #endif
 399         } while(curTime < endTime);
 400         #else
 401                 Microseconds(&uwide);
 402                 now = UnsignedWideToUInt64(uwide);
 403         } while ( (now-start) < ticks) ;
 404         #endif
 405 #else
 406         } while ( (now-start) < ticks) ;
 407 #endif
 408         YSHA1Final(dig,&p->pool);
 409         YSHA1Update(&p->pool,dig,20);
 410         YSHA1Final(dig,&p->pool);
 411
 412         /* Reset secret state */
 413         YSHA1Init(&p->pool);
 414         prng_make_new_state(&p->outstate,dig);
 415
 416         /* Clear counter variables */
 417         for(i=0;i<TOTAL_SOURCES;i++)
 418         {
 419                 p->poolSize[i] = 0;
 420                 p->poolEstBits[i] = 0;
 421         }
 422
 423         /* Cleanup memory */
 424         trashMemory(dig,20*sizeof(char));
 425         trashMemory(buf,64*sizeof(char));
 426
 427         return PRNG_SUCCESS;
 428 }
 429
 430
 431 /* Input a state into the PRNG */
 432 prng_error_status
 433 prngProcessSeedBuffer(PRNG *p, BYTE *buf,LONGLONG ticks)
 434 {
 435         CHECKSTATE(p);
 436         GENCHECK(p);
 437         PCHECK(buf);
 438
 439         /* Put the data into the entropy, add some data from the unknown state, reseed */
 440         YSHA1Update(&p->pool,buf,20);                   /* Put it into the entropy pool */
 441         prng_do_SHA1(&p->outstate);                             /* Output 20 more bytes and     */
 442         YSHA1Update(&p->pool,p->outstate.out,20);/* add it to the pool as well.  */
 443         prngForceReseed(p, ticks);                              /* Do a reseed */
 444         return prngOutput(p, buf,20); /* Return the first 20 bytes of output in buf */
 445 }
 446
 447
 448 /* Take some "random" data and make more "random-looking" data from it */
 449 /* note: this routine has no context, no mutex wrapper */
 450 prng_error_status
 451 prngStretch(BYTE *inbuf,UINT inbuflen,BYTE *outbuf,UINT outbuflen) {
 452         long int left,prev;
 453         YSHA1_CTX ctx;
 454         BYTE dig[20];
 455
 456         PCHECK(inbuf);
 457         PCHECK(outbuf);
 458
 459         if(inbuflen >= outbuflen)
 460         {
 461                 memcpy(outbuf,inbuf,outbuflen);
 462                 return PRNG_SUCCESS;
 463         }
 464         else  /* Extend using SHA1 hash of inbuf */
 465         {
 466                 YSHA1Init(&ctx);
 467                 YSHA1Update(&ctx,inbuf,inbuflen);
 468                 YSHA1Final(dig,&ctx);
 469                 for(prev=0,left=outbuflen;left>0;prev+=20,left-=20)
 470                 {
 471                         YSHA1Update(&ctx,dig,20);
 472                         YSHA1Final(dig,&ctx);
 473                         memcpy(outbuf+prev,dig,(left>20)?20:left);
 474                 }
 475                 trashMemory(dig,20*sizeof(BYTE));
 476
 477                 return PRNG_SUCCESS;
 478         }
 479
 480         return PRNG_ERR_PROGRAM_FLOW;
 481 }
 482
 483
 484 /* Add entropy to the PRNG from a source */
 485 prng_error_status
 486 prngInput(PRNG *p, BYTE *inbuf,UINT inbuflen,UINT poolnum, __unused UINT estbits)
 487 {
 488         #ifndef YARROW_KERNEL
 489         comp_error_status resp;
 490         #endif
 491
 492         CHECKSTATE(p);
 493         POOLCHECK(p);
 494         PCHECK(inbuf);
 495         if(poolnum >= TOTAL_SOURCES) {return PRNG_ERR_OUT_OF_BOUNDS;}
 496
 497         /* Add to entropy pool */
 498         YSHA1Update(&p->pool,inbuf,inbuflen);
 499
 500         #ifndef YARROW_KERNEL
 501         /* skip this step for the kernel */
 502
 503         /* Update pool size, pool user estimate and pool compression context */
 504         p->poolSize[poolnum] += inbuflen;
 505         p->poolEstBits[poolnum] += estbits;
 506         if(poolnum<COMP_SOURCES)
 507         {
 508                 resp = comp_add_data((p->comp_state)+poolnum,inbuf,inbuflen);
 509                 if(resp!=COMP_SUCCESS) {return PRNG_ERR_COMPRESSION;}
 510         }
 511         #endif  /* YARROW_KERNEL */
 512
 513         return PRNG_SUCCESS;
 514 }
 515
 516
 517
 518 /* If we have enough entropy, allow a reseed of the system */
 519 prng_error_status
 520 prngAllowReseed(PRNG *p, LONGLONG ticks)
 521 {
 522         UINT temp[TOTAL_SOURCES];
 523         LONG i;
 524         UINT sum;
 525 #ifndef KERNEL_BUILD
 526         float ratio;
 527 #endif
 528
 529 #ifndef KERNEL_BUILD
 530         comp_error_status resp;
 531 #endif
 532
 533         CHECKSTATE(p);
 534
 535         for(i=0;i<ENTROPY_SOURCES;i++)
 536         {
 537                 /* Make sure that compression-based entropy estimates are current */
 538 #ifndef KERNEL_BUILD // floating point in a kernel is BAD!
 539                 resp = comp_get_ratio((p->comp_state)+i,&ratio);
 540                 if(resp!=COMP_SUCCESS) {return PRNG_ERR_COMPRESSION;}
 541                 /* Use 4 instead of 8 to half compression estimate */
 542                 temp[i] = (int)(ratio*p->poolSize[i]*4);
 543 #else
 544         temp[i] = p->poolSize[i] * 4;
 545 #endif
 546
 547         }
 548         /* Use minumum of user and compression estimate for compressed sources */
 549         for(i=ENTROPY_SOURCES;i<COMP_SOURCES;i++)
 550         {
 551 #ifndef KERNEL_BUILD
 552                 /* Make sure that compression-based entropy estimates are current */
 553                 resp = comp_get_ratio((p->comp_state)+i,&ratio);
 554                 if(resp!=COMP_SUCCESS) {return PRNG_ERR_COMPRESSION;}
 555                 /* Use 4 instead of 8 to half compression estimate */
 556                 temp[i] = _MIN((int)(ratio*p->poolSize[i]*4),(int)p->poolEstBits[i]);
 557 #else
 558         temp[i] = _MIN (p->poolSize[i] * 4, p->poolEstBits[i]);
 559 #endif
 560
 561         }
 562         /* Use user estimate for remaining sources */
 563         for(i=COMP_SOURCES;i<TOTAL_SOURCES;i++) {temp[i] = p->poolEstBits[i];}
 564
 565         if(K > 0) {
 566                 /* pointless if we're not ignoring any sources */
 567                 bubbleSort(temp,TOTAL_SOURCES);
 568         }
 569         for(i=K,sum=0;i<TOTAL_SOURCES;sum+=temp[i++]); /* Stupid C trick */
 570         if(sum>THRESHOLD)
 571                 return prngForceReseed(p, ticks);
 572         else
 573                 return PRNG_ERR_NOT_ENOUGH_ENTROPY;
 574
 575         return PRNG_ERR_PROGRAM_FLOW;
 576 }
 577
 578 #if             SLOW_POLL_ENABLE
 579 /* Call a slow poll and insert the data into the entropy pool */
 580 static prng_error_status
 581 prngSlowPoll(PRNG *p, UINT pollsize)
 582 {
 583         BYTE *buf;
 584         DWORD len;
 585         prng_error_status retval;
 586
 587         CHECKSTATE(p);
 588
 589         buf = (BYTE*)malloc(pollsize);
 590         if(buf==NULL) {return PRNG_ERR_LOW_MEMORY;}
 591         len = prng_slow_poll(buf,pollsize);     /* OS specific call */
 592         retval = prngInput(p, buf,len,SLOWPOLLSOURCE, len * 8);
 593         trashMemory(buf,pollsize);
 594         free(buf);
 595
 596         return retval;
 597 }
 598 #endif  /* SLOW_POLL_ENABLE */
 599
 600
 601 /* Delete the PRNG */
 602 prng_error_status
 603 prngDestroy(PRNG *p)
 604 {
 605         UINT i;
 606
 607         #if     MUTEX_ENABLE
 608         if(GetCurrentProcessId()!=mutexCreatorId) {return PRNG_ERR_WRONG_CALLER;}
 609         #endif
 610         if(p==NULL) {return PRNG_SUCCESS;} /* Well, there is nothing to destroy... */
 611
 612         p->ready = PRNG_NOT_READY;
 613
 614         for(i=0;i<COMP_SOURCES;i++)
 615         {
 616                 comp_end((p->comp_state)+i);
 617         }
 618
 619         #if     MUTEX_ENABLE
 620         CloseHandle(Statmutex);
 621         Statmutex = NULL;
 622         mutexCreatorId = 0;
 623         #endif
 624
 625         return PRNG_SUCCESS;
 626 }
 627
 628