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

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