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 <dev/random/YarrowCoreLib/include/macos_defs.h>
  50
  51 #include "macOnly.h"
  52 #endif  /* macintosh */
  53 #include "smf.h"
  54 #include "sha1mod.h"
  55 #include "entropysources.h"
  56 #include "comp.h"
  57 #include "dev/random/YarrowCoreLib/include/yarrow.h"
  58 #include "prng.h"
  59 #include "prngpriv.h"
  60
  61
  62 #define _MAX(a,b) (((a)>(b))?(a):(b))
  63 #define _MIN(a,b) (((a)<(b))?(a):(b))
  64
  65 #if             defined(macintosh) || defined(__APPLE__)
  66 /*
  67  * No mutexes in this module for Macintosh/OSX. We handle the
  68  * required locking elsewhere.
  69  */
  70 #define MUTEX_ENABLE    0
  71
  72 #include <string.h>             /* memcpy, etc. */
  73 #if             TARGET_API_MAC_OSX
  74         #include <sys/time.h>           /* for timespec */
  75 #elif   TARGET_API_MAC_CARBON
  76         #include <Timer.h>                              /* Microseconds */
  77         #include <Math64.h>
  78 #elif   KERNEL_BUILD
  79     #include <sys/time.h>
  80 #else
  81         #error Unknown TARGET_API
  82 #endif  /* TARGET_API */
  83 #else
  84 #define MUTEX_ENABLE    1
  85 #endif  /* macintosh */
  86
  87 #if             MUTEX_ENABLE
  88 static HANDLE Statmutex = NULL;
  89 static DWORD mutexCreatorId = 0;
  90 #endif
  91
  92 #pragma mark -
  93 #pragma mark * * * Static Utility functions * * *
  94
  95 /* All error checking should be done in the function that calls these */
  96
  97 /*
  98  * out := SHA1(IV | out)
  99  */
 100 static void
 101 prng_do_SHA1(GEN_CTX *ctx)
 102 {
 103         SHA1_CTX sha;
 104
 105         SHA1Init(&sha);
 106         SHA1Update(&sha,ctx->IV,20);
 107         SHA1Update(&sha,ctx->out,20);
 108         SHA1Final(ctx->out,&sha);
 109         ctx->index = 0;
 110 }
 111
 112 /*
 113  * IV  := newState
 114  * out := SHA1(IV)
 115  *
 116  * Called from init, prngForceReseed(), and prngOutput()
 117  * as anti-backtracking mechanism.
 118  */
 119 static void
 120 prng_make_new_state(GEN_CTX *ctx,BYTE *newState)
 121 {
 122         SHA1_CTX sha;
 123
 124         memcpy(ctx->IV,newState,20);
 125         SHA1Init(&sha);
 126         SHA1Update(&sha,ctx->IV,20);
 127         SHA1Final(ctx->out,&sha);
 128         ctx->numout = 0;
 129         ctx->index = 0;
 130 }
 131
 132 #if             SLOW_POLL_ENABLE
 133
 134
 135 /* Initialize the secret state with a slow poll */
 136 /* Currently only called from prngInitialize */
 137
 138 #define SPLEN 65536  /* 64K */
 139
 140 static void
 141 prng_slow_init(PRNG *p)
 142 /* This fails silently and must be fixed. */
 143 {
 144         SHA1_CTX* ctx = NULL;
 145         MMPTR mmctx = MM_NULL;
 146         BYTE* bigbuf = NULL;
 147         MMPTR mmbigbuf = MM_NULL;
 148         BYTE* buf = NULL;
 149         MMPTR mmbuf = MM_NULL;
 150         DWORD polllength;
 151
 152         mmbigbuf = mmMalloc(SPLEN);
 153         if(mmbigbuf == MM_NULL) {goto cleanup_slow_init;}
 154         bigbuf = (BYTE*)mmGetPtr(mmbigbuf);
 155
 156         mmbuf = mmMalloc(20);
 157         if(mmbuf == MM_NULL) {goto cleanup_slow_init;}
 158         buf = (BYTE*)mmGetPtr(mmbuf);
 159
 160         mmctx = mmMalloc(sizeof(SHA1_CTX));
 161         if(mmctx == MM_NULL) {goto cleanup_slow_init;}
 162         ctx = (SHA1_CTX*)mmGetPtr(mmctx);
 163
 164
 165         /* Initialize the secret state. */
 166         /* Init entropy pool */
 167         SHA1Init(&p->pool);
 168         /* Init output generator */
 169         polllength = prng_slow_poll(bigbuf,SPLEN);
 170         SHA1Init(ctx);
 171         SHA1Update(ctx,bigbuf,polllength);
 172         SHA1Final(buf,ctx);
 173         prng_make_new_state(&p->outstate, buf);
 174
 175 cleanup_slow_init:
 176         mmFree(mmctx);
 177         mmFree(mmbigbuf);
 178         mmFree(mmbuf);
 179
 180         return;
 181 }
 182
 183 #endif  /* SLOW_POLL_ENABLE */
 184
 185 /* In-place modifed bubble sort */
 186 static void
 187 bubbleSort(UINT *data,UINT len)
 188 {
 189         UINT i,last,newlast,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                 int32_t                 endTime;
 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                 microtime (&tv);
 363             #else
 364                 gettimeofday(&tv, NULL);
 365             #endif
 366                         endTime = tv.tv_usec + ticks;
 367                         if(endTime > 1000000) {
 368                                 /* handle rollover now */
 369                                 endTime -= 1000000;
 370                         }
 371                 #else   /* TARGET_API_MAC_OSX */
 372                         Microseconds(&uwide);
 373                         start = UnsignedWideToUInt64(uwide);
 374                 #endif  /* TARGET_API_xxx */
 375         #endif  /* macintosh */
 376         do
 377         {
 378                 /* Do a couple of iterations between time checks */
 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                 prngOutput(p, buf,64);
 386                 SHA1Update(&p->pool,buf,64);
 387                 prngOutput(p, buf,64);
 388                 SHA1Update(&p->pool,buf,64);
 389
 390 #if             defined(macintosh) || defined(__APPLE__)
 391         #if             defined(TARGET_API_MAC_OSX) || defined(KERNEL_BUILD)
 392         #ifdef TARGET_API_MAC_OSX
 393             gettimeofday(&tv, NULL);
 394         #else
 395             microtime (&tv);
 396         #endif
 397         } while(tv.tv_usec < endTime);
 398         #else
 399                 Microseconds(&uwide);
 400                 now = UnsignedWideToUInt64(uwide);
 401         } while ( (now-start) < ticks) ;
 402         #endif
 403 #else
 404         } while ( (now-start) < ticks) ;
 405 #endif
 406         SHA1Final(dig,&p->pool);
 407         SHA1Update(&p->pool,dig,20);
 408         SHA1Final(dig,&p->pool);
 409
 410         /* Reset secret state */
 411         SHA1Init(&p->pool);
 412         prng_make_new_state(&p->outstate,dig);
 413
 414         /* Clear counter variables */
 415         for(i=0;i<TOTAL_SOURCES;i++)
 416         {
 417                 p->poolSize[i] = 0;
 418                 p->poolEstBits[i] = 0;
 419         }
 420
 421         /* Cleanup memory */
 422         trashMemory(dig,20*sizeof(char));
 423         trashMemory(buf,64*sizeof(char));
 424
 425         return PRNG_SUCCESS;
 426 }
 427
 428
 429 /* Input a state into the PRNG */
 430 prng_error_status
 431 prngProcessSeedBuffer(PRNG *p, BYTE *buf,LONGLONG ticks)
 432 {
 433         CHECKSTATE(p);
 434         GENCHECK(p);
 435         PCHECK(buf);
 436
 437         /* Put the data into the entropy, add some data from the unknown state, reseed */
 438         SHA1Update(&p->pool,buf,20);                    /* Put it into the entropy pool */
 439         prng_do_SHA1(&p->outstate);                             /* Output 20 more bytes and     */
 440         SHA1Update(&p->pool,p->outstate.out,20);/* add it to the pool as well.  */
 441         prngForceReseed(p, ticks);                              /* Do a reseed */
 442         return prngOutput(p, buf,20); /* Return the first 20 bytes of output in buf */
 443 }
 444
 445
 446 /* Take some "random" data and make more "random-looking" data from it */
 447 /* note: this routine has no context, no mutex wrapper */
 448 prng_error_status
 449 prngStretch(BYTE *inbuf,UINT inbuflen,BYTE *outbuf,UINT outbuflen) {
 450         long int left,prev;
 451         SHA1_CTX ctx;
 452         BYTE dig[20];
 453
 454         PCHECK(inbuf);
 455         PCHECK(outbuf);
 456
 457         if(inbuflen >= outbuflen)
 458         {
 459                 memcpy(outbuf,inbuf,outbuflen);
 460                 return PRNG_SUCCESS;
 461         }
 462         else  /* Extend using SHA1 hash of inbuf */
 463         {
 464                 SHA1Init(&ctx);
 465                 SHA1Update(&ctx,inbuf,inbuflen);
 466                 SHA1Final(dig,&ctx);
 467                 for(prev=0,left=outbuflen;left>0;prev+=20,left-=20)
 468                 {
 469                         SHA1Update(&ctx,dig,20);
 470                         SHA1Final(dig,&ctx);
 471                         memcpy(outbuf+prev,dig,(left>20)?20:left);
 472                 }
 473                 trashMemory(dig,20*sizeof(BYTE));
 474
 475                 return PRNG_SUCCESS;
 476         }
 477
 478         return PRNG_ERR_PROGRAM_FLOW;
 479 }
 480
 481
 482 /* Add entropy to the PRNG from a source */
 483 prng_error_status
 484 prngInput(PRNG *p, BYTE *inbuf,UINT inbuflen,UINT poolnum,UINT estbits)
 485 {
 486         #ifndef YARROW_KERNEL
 487         comp_error_status resp;
 488         #endif
 489
 490         CHECKSTATE(p);
 491         POOLCHECK(p);
 492         PCHECK(inbuf);
 493         if(poolnum >= TOTAL_SOURCES) {return PRNG_ERR_OUT_OF_BOUNDS;}
 494
 495         /* Add to entropy pool */
 496         SHA1Update(&p->pool,inbuf,inbuflen);
 497
 498         #ifndef YARROW_KERNEL
 499         /* skip this step for the kernel */
 500
 501         /* Update pool size, pool user estimate and pool compression context */
 502         p->poolSize[poolnum] += inbuflen;
 503         p->poolEstBits[poolnum] += estbits;
 504         if(poolnum<COMP_SOURCES)
 505         {
 506                 resp = comp_add_data((p->comp_state)+poolnum,inbuf,inbuflen);
 507                 if(resp!=COMP_SUCCESS) {return PRNG_ERR_COMPRESSION;}
 508         }
 509         #endif  /* YARROW_KERNEL */
 510
 511         return PRNG_SUCCESS;
 512 }
 513
 514
 515
 516 /* If we have enough entropy, allow a reseed of the system */
 517 prng_error_status
 518 prngAllowReseed(PRNG *p, LONGLONG ticks)
 519 {
 520         UINT temp[TOTAL_SOURCES];
 521         UINT i,sum;
 522 #ifndef KERNEL_BUILD
 523         float ratio;
 524 #endif
 525
 526         comp_error_status resp;
 527
 528
 529         CHECKSTATE(p);
 530
 531         for(i=0;i<ENTROPY_SOURCES;i++)
 532         {
 533                 /* Make sure that compression-based entropy estimates are current */
 534 #ifndef KERNEL_BUILD // floating point in a kernel is BAD!
 535                 resp = comp_get_ratio((p->comp_state)+i,&ratio);
 536                 if(resp!=COMP_SUCCESS) {return PRNG_ERR_COMPRESSION;}
 537                 /* Use 4 instead of 8 to half compression estimate */
 538                 temp[i] = (int)(ratio*p->poolSize[i]*4);
 539 #else
 540         temp[i] = p->poolSize[i] * 4;
 541 #endif
 542
 543         }
 544         /* Use minumum of user and compression estimate for compressed sources */
 545         for(i=ENTROPY_SOURCES;i<COMP_SOURCES;i++)
 546         {
 547 #ifndef KERNEL_BUILD
 548                 /* Make sure that compression-based entropy estimates are current */
 549                 resp = comp_get_ratio((p->comp_state)+i,&ratio);
 550                 if(resp!=COMP_SUCCESS) {return PRNG_ERR_COMPRESSION;}
 551                 /* Use 4 instead of 8 to half compression estimate */
 552                 temp[i] = _MIN((int)(ratio*p->poolSize[i]*4),(int)p->poolEstBits[i]);
 553 #else
 554         temp[i] = _MIN (p->poolSize[i] * 4, p->poolEstBits[i]);
 555 #endif
 556
 557         }
 558         /* Use user estimate for remaining sources */
 559         for(i=COMP_SOURCES;i<TOTAL_SOURCES;i++) {temp[i] = p->poolEstBits[i];}
 560
 561         if(K > 0) {
 562                 /* pointless if we're not ignoring any sources */
 563                 bubbleSort(temp,TOTAL_SOURCES);
 564         }
 565         for(i=K,sum=0;i<TOTAL_SOURCES;sum+=temp[i++]); /* Stupid C trick */
 566         if(sum>THRESHOLD)
 567                 return prngForceReseed(p, ticks);
 568         else
 569                 return PRNG_ERR_NOT_ENOUGH_ENTROPY;
 570
 571         return PRNG_ERR_PROGRAM_FLOW;
 572 }
 573
 574 #if             SLOW_POLL_ENABLE
 575 /* Call a slow poll and insert the data into the entropy pool */
 576 static prng_error_status
 577 prngSlowPoll(PRNG *p, UINT pollsize)
 578 {
 579         BYTE *buf;
 580         DWORD len;
 581         prng_error_status retval;
 582
 583         CHECKSTATE(p);
 584
 585         buf = (BYTE*)malloc(pollsize);
 586         if(buf==NULL) {return PRNG_ERR_LOW_MEMORY;}
 587         len = prng_slow_poll(buf,pollsize);     /* OS specific call */
 588         retval = prngInput(p, buf,len,SLOWPOLLSOURCE, len * 8);
 589         trashMemory(buf,pollsize);
 590         free(buf);
 591
 592         return retval;
 593 }
 594 #endif  /* SLOW_POLL_ENABLE */
 595
 596
 597 /* Delete the PRNG */
 598 prng_error_status
 599 prngDestroy(PRNG *p)
 600 {
 601         UINT i;
 602
 603         #if     MUTEX_ENABLE
 604         if(GetCurrentProcessId()!=mutexCreatorId) {return PRNG_ERR_WRONG_CALLER;}
 605         #endif
 606         if(p==NULL) {return PRNG_SUCCESS;} /* Well, there is nothing to destroy... */
 607
 608         p->ready = PRNG_NOT_READY;
 609
 610         for(i=0;i<COMP_SOURCES;i++)
 611         {
 612                 comp_end((p->comp_state)+i);
 613         }
 614
 615         #if     MUTEX_ENABLE
 616         CloseHandle(Statmutex);
 617         Statmutex = NULL;
 618         mutexCreatorId = 0;
 619         #endif
 620
 621         return PRNG_SUCCESS;
 622 }
 623
 624