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                 int64_t                 endTime, curTime;
 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                 microuptime (&tv);
 361             #else
 362                 gettimeofday(&tv, NULL);
 363             #endif
 364                         endTime = (int64_t)tv.tv_sec*1000000LL + (int64_t)tv.tv_usec + ticks;
 365                 #else   /* TARGET_API_MAC_OSX */
 366                         Microseconds(&uwide);
 367                         start = UnsignedWideToUInt64(uwide);
 368                 #endif  /* TARGET_API_xxx */
 369         #endif  /* macintosh */
 370         do
 371         {
 372                 /* Do a couple of iterations between time checks */
 373                 prngOutput(p, buf,64);
 374                 SHA1Update(&p->pool,buf,64);
 375                 prngOutput(p, buf,64);
 376                 SHA1Update(&p->pool,buf,64);
 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
 384 #if             defined(macintosh) || defined(__APPLE__)
 385         #if             defined(TARGET_API_MAC_OSX) || defined(KERNEL_BUILD)
 386         #ifdef TARGET_API_MAC_OSX
 387             gettimeofday(&tv, NULL);
 388         #else
 389             microuptime (&tv);
 390             curTime = (int64_t)tv.tv_sec*1000000LL + (int64_t)tv.tv_usec;
 391         #endif
 392         } while(curTime < endTime);
 393         #else
 394                 Microseconds(&uwide);
 395                 now = UnsignedWideToUInt64(uwide);
 396         } while ( (now-start) < ticks) ;
 397         #endif
 398 #else
 399         } while ( (now-start) < ticks) ;
 400 #endif
 401         SHA1Final(dig,&p->pool);
 402         SHA1Update(&p->pool,dig,20);
 403         SHA1Final(dig,&p->pool);
 404
 405         /* Reset secret state */
 406         SHA1Init(&p->pool);
 407         prng_make_new_state(&p->outstate,dig);
 408
 409         /* Clear counter variables */
 410         for(i=0;i<TOTAL_SOURCES;i++)
 411         {
 412                 p->poolSize[i] = 0;
 413                 p->poolEstBits[i] = 0;
 414         }
 415
 416         /* Cleanup memory */
 417         trashMemory(dig,20*sizeof(char));
 418         trashMemory(buf,64*sizeof(char));
 419
 420         return PRNG_SUCCESS;
 421 }
 422
 423
 424 /* Input a state into the PRNG */
 425 prng_error_status
 426 prngProcessSeedBuffer(PRNG *p, BYTE *buf,LONGLONG ticks)
 427 {
 428         CHECKSTATE(p);
 429         GENCHECK(p);
 430         PCHECK(buf);
 431
 432         /* Put the data into the entropy, add some data from the unknown state, reseed */
 433         SHA1Update(&p->pool,buf,20);                    /* Put it into the entropy pool */
 434         prng_do_SHA1(&p->outstate);                             /* Output 20 more bytes and     */
 435         SHA1Update(&p->pool,p->outstate.out,20);/* add it to the pool as well.  */
 436         prngForceReseed(p, ticks);                              /* Do a reseed */
 437         return prngOutput(p, buf,20); /* Return the first 20 bytes of output in buf */
 438 }
 439
 440
 441 /* Take some "random" data and make more "random-looking" data from it */
 442 /* note: this routine has no context, no mutex wrapper */
 443 prng_error_status
 444 prngStretch(BYTE *inbuf,UINT inbuflen,BYTE *outbuf,UINT outbuflen) {
 445         long int left,prev;
 446         SHA1_CTX ctx;
 447         BYTE dig[20];
 448
 449         PCHECK(inbuf);
 450         PCHECK(outbuf);
 451
 452         if(inbuflen >= outbuflen)
 453         {
 454                 memcpy(outbuf,inbuf,outbuflen);
 455                 return PRNG_SUCCESS;
 456         }
 457         else  /* Extend using SHA1 hash of inbuf */
 458         {
 459                 SHA1Init(&ctx);
 460                 SHA1Update(&ctx,inbuf,inbuflen);
 461                 SHA1Final(dig,&ctx);
 462                 for(prev=0,left=outbuflen;left>0;prev+=20,left-=20)
 463                 {
 464                         SHA1Update(&ctx,dig,20);
 465                         SHA1Final(dig,&ctx);
 466                         memcpy(outbuf+prev,dig,(left>20)?20:left);
 467                 }
 468                 trashMemory(dig,20*sizeof(BYTE));
 469
 470                 return PRNG_SUCCESS;
 471         }
 472
 473         return PRNG_ERR_PROGRAM_FLOW;
 474 }
 475
 476
 477 /* Add entropy to the PRNG from a source */
 478 prng_error_status
 479 prngInput(PRNG *p, BYTE *inbuf,UINT inbuflen,UINT poolnum,UINT estbits)
 480 {
 481         #ifndef YARROW_KERNEL
 482         comp_error_status resp;
 483         #endif
 484
 485         CHECKSTATE(p);
 486         POOLCHECK(p);
 487         PCHECK(inbuf);
 488         if(poolnum >= TOTAL_SOURCES) {return PRNG_ERR_OUT_OF_BOUNDS;}
 489
 490         /* Add to entropy pool */
 491         SHA1Update(&p->pool,inbuf,inbuflen);
 492
 493         #ifndef YARROW_KERNEL
 494         /* skip this step for the kernel */
 495
 496         /* Update pool size, pool user estimate and pool compression context */
 497         p->poolSize[poolnum] += inbuflen;
 498         p->poolEstBits[poolnum] += estbits;
 499         if(poolnum<COMP_SOURCES)
 500         {
 501                 resp = comp_add_data((p->comp_state)+poolnum,inbuf,inbuflen);
 502                 if(resp!=COMP_SUCCESS) {return PRNG_ERR_COMPRESSION;}
 503         }
 504         #endif  /* YARROW_KERNEL */
 505
 506         return PRNG_SUCCESS;
 507 }
 508
 509
 510
 511 /* If we have enough entropy, allow a reseed of the system */
 512 prng_error_status
 513 prngAllowReseed(PRNG *p, LONGLONG ticks)
 514 {
 515         UINT temp[TOTAL_SOURCES];
 516         UINT i,sum;
 517 #ifndef KERNEL_BUILD
 518         float ratio;
 519 #endif
 520
 521         comp_error_status resp;
 522
 523
 524         CHECKSTATE(p);
 525
 526         for(i=0;i<ENTROPY_SOURCES;i++)
 527         {
 528                 /* Make sure that compression-based entropy estimates are current */
 529 #ifndef KERNEL_BUILD // floating point in a kernel is BAD!
 530                 resp = comp_get_ratio((p->comp_state)+i,&ratio);
 531                 if(resp!=COMP_SUCCESS) {return PRNG_ERR_COMPRESSION;}
 532                 /* Use 4 instead of 8 to half compression estimate */
 533                 temp[i] = (int)(ratio*p->poolSize[i]*4);
 534 #else
 535         temp[i] = p->poolSize[i] * 4;
 536 #endif
 537
 538         }
 539         /* Use minumum of user and compression estimate for compressed sources */
 540         for(i=ENTROPY_SOURCES;i<COMP_SOURCES;i++)
 541         {
 542 #ifndef KERNEL_BUILD
 543                 /* Make sure that compression-based entropy estimates are current */
 544                 resp = comp_get_ratio((p->comp_state)+i,&ratio);
 545                 if(resp!=COMP_SUCCESS) {return PRNG_ERR_COMPRESSION;}
 546                 /* Use 4 instead of 8 to half compression estimate */
 547                 temp[i] = _MIN((int)(ratio*p->poolSize[i]*4),(int)p->poolEstBits[i]);
 548 #else
 549         temp[i] = _MIN (p->poolSize[i] * 4, p->poolEstBits[i]);
 550 #endif
 551
 552         }
 553         /* Use user estimate for remaining sources */
 554         for(i=COMP_SOURCES;i<TOTAL_SOURCES;i++) {temp[i] = p->poolEstBits[i];}
 555
 556         if(K > 0) {
 557                 /* pointless if we're not ignoring any sources */
 558                 bubbleSort(temp,TOTAL_SOURCES);
 559         }
 560         for(i=K,sum=0;i<TOTAL_SOURCES;sum+=temp[i++]); /* Stupid C trick */
 561         if(sum>THRESHOLD)
 562                 return prngForceReseed(p, ticks);
 563         else
 564                 return PRNG_ERR_NOT_ENOUGH_ENTROPY;
 565
 566         return PRNG_ERR_PROGRAM_FLOW;
 567 }
 568
 569 #if             SLOW_POLL_ENABLE
 570 /* Call a slow poll and insert the data into the entropy pool */
 571 static prng_error_status
 572 prngSlowPoll(PRNG *p, UINT pollsize)
 573 {
 574         BYTE *buf;
 575         DWORD len;
 576         prng_error_status retval;
 577
 578         CHECKSTATE(p);
 579
 580         buf = (BYTE*)malloc(pollsize);
 581         if(buf==NULL) {return PRNG_ERR_LOW_MEMORY;}
 582         len = prng_slow_poll(buf,pollsize);     /* OS specific call */
 583         retval = prngInput(p, buf,len,SLOWPOLLSOURCE, len * 8);
 584         trashMemory(buf,pollsize);
 585         free(buf);
 586
 587         return retval;
 588 }
 589 #endif  /* SLOW_POLL_ENABLE */
 590
 591
 592 /* Delete the PRNG */
 593 prng_error_status
 594 prngDestroy(PRNG *p)
 595 {
 596         UINT i;
 597
 598         #if     MUTEX_ENABLE
 599         if(GetCurrentProcessId()!=mutexCreatorId) {return PRNG_ERR_WRONG_CALLER;}
 600         #endif
 601         if(p==NULL) {return PRNG_SUCCESS;} /* Well, there is nothing to destroy... */
 602
 603         p->ready = PRNG_NOT_READY;
 604
 605         for(i=0;i<COMP_SOURCES;i++)
 606         {
 607                 comp_end((p->comp_state)+i);
 608         }
 609
 610         #if     MUTEX_ENABLE
 611         CloseHandle(Statmutex);
 612         Statmutex = NULL;
 613         mutexCreatorId = 0;
 614         #endif
 615
 616         return PRNG_SUCCESS;
 617 }
 618
 619