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