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