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