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