1/* crypto/rand/md_rand.c */ 2/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) 3 * All rights reserved. 4 * 5 * This package is an SSL implementation written 6 * by Eric Young (eay@cryptsoft.com). 7 * The implementation was written so as to conform with Netscapes SSL. 8 * 9 * This library is free for commercial and non-commercial use as long as 10 * the following conditions are aheared to. The following conditions 11 * apply to all code found in this distribution, be it the RC4, RSA, 12 * lhash, DES, etc., code; not just the SSL code. The SSL documentation 13 * included with this distribution is covered by the same copyright terms 14 * except that the holder is Tim Hudson (tjh@cryptsoft.com). 15 * 16 * Copyright remains Eric Young's, and as such any Copyright notices in 17 * the code are not to be removed. 18 * If this package is used in a product, Eric Young should be given attribution 19 * as the author of the parts of the library used. 20 * This can be in the form of a textual message at program startup or 21 * in documentation (online or textual) provided with the package. 22 * 23 * Redistribution and use in source and binary forms, with or without 24 * modification, are permitted provided that the following conditions 25 * are met: 26 * 1. Redistributions of source code must retain the copyright 27 * notice, this list of conditions and the following disclaimer. 28 * 2. Redistributions in binary form must reproduce the above copyright 29 * notice, this list of conditions and the following disclaimer in the 30 * documentation and/or other materials provided with the distribution. 31 * 3. All advertising materials mentioning features or use of this software 32 * must display the following acknowledgement: 33 * "This product includes cryptographic software written by 34 * Eric Young (eay@cryptsoft.com)" 35 * The word 'cryptographic' can be left out if the rouines from the library 36 * being used are not cryptographic related :-). 37 * 4. If you include any Windows specific code (or a derivative thereof) from 38 * the apps directory (application code) you must include an acknowledgement: 39 * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)" 40 * 41 * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND 42 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 43 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 44 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 45 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 46 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 47 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 48 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 49 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 50 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 51 * SUCH DAMAGE. 52 * 53 * The licence and distribution terms for any publically available version or 54 * derivative of this code cannot be changed. i.e. this code cannot simply be 55 * copied and put under another distribution licence 56 * [including the GNU Public Licence.] 57 */ 58/* ==================================================================== 59 * Copyright (c) 1998-2001 The OpenSSL Project. All rights reserved. 60 * 61 * Redistribution and use in source and binary forms, with or without 62 * modification, are permitted provided that the following conditions 63 * are met: 64 * 65 * 1. Redistributions of source code must retain the above copyright 66 * notice, this list of conditions and the following disclaimer. 67 * 68 * 2. Redistributions in binary form must reproduce the above copyright 69 * notice, this list of conditions and the following disclaimer in 70 * the documentation and/or other materials provided with the 71 * distribution. 72 * 73 * 3. All advertising materials mentioning features or use of this 74 * software must display the following acknowledgment: 75 * "This product includes software developed by the OpenSSL Project 76 * for use in the OpenSSL Toolkit. (http://www.openssl.org/)" 77 * 78 * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to 79 * endorse or promote products derived from this software without 80 * prior written permission. For written permission, please contact 81 * openssl-core@openssl.org. 82 * 83 * 5. Products derived from this software may not be called "OpenSSL" 84 * nor may "OpenSSL" appear in their names without prior written 85 * permission of the OpenSSL Project. 86 * 87 * 6. Redistributions of any form whatsoever must retain the following 88 * acknowledgment: 89 * "This product includes software developed by the OpenSSL Project 90 * for use in the OpenSSL Toolkit (http://www.openssl.org/)" 91 * 92 * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY 93 * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 94 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 95 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR 96 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 97 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 98 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 99 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 100 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 101 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 102 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED 103 * OF THE POSSIBILITY OF SUCH DAMAGE. 104 * ==================================================================== 105 * 106 * This product includes cryptographic software written by Eric Young 107 * (eay@cryptsoft.com). This product includes software written by Tim 108 * Hudson (tjh@cryptsoft.com). 109 * 110 */ 111 112#ifdef MD_RAND_DEBUG 113# ifndef NDEBUG 114# define NDEBUG 115# endif 116#endif 117 118#include <assert.h> 119#include <stdio.h> 120#include <string.h> 121 122#include "e_os.h" 123 124#include <openssl/rand.h> 125#include "rand_lcl.h" 126 127#include <openssl/crypto.h> 128#include <openssl/err.h> 129#ifdef OPENSSL_FIPS 130#include <openssl/fips.h> 131#endif 132 133 134#ifdef BN_DEBUG 135# define PREDICT 136#endif 137 138/* #define PREDICT 1 */ 139 140#define STATE_SIZE 1023 141static int state_num=0,state_index=0; 142static unsigned char state[STATE_SIZE+MD_DIGEST_LENGTH]; 143static unsigned char md[MD_DIGEST_LENGTH]; 144static long md_count[2]={0,0}; 145static double entropy=0; 146static int initialized=0; 147 148static unsigned int crypto_lock_rand = 0; /* may be set only when a thread 149 * holds CRYPTO_LOCK_RAND 150 * (to prevent double locking) */ 151/* access to lockin_thread is synchronized by CRYPTO_LOCK_RAND2 */ 152static unsigned long locking_thread = 0; /* valid iff crypto_lock_rand is set */ 153 154 155#ifdef PREDICT 156int rand_predictable=0; 157#endif 158 159const char RAND_version[]="RAND" OPENSSL_VERSION_PTEXT; 160 161static void ssleay_rand_cleanup(void); 162static void ssleay_rand_seed(const void *buf, int num); 163static void ssleay_rand_add(const void *buf, int num, double add_entropy); 164static int ssleay_rand_bytes(unsigned char *buf, int num); 165static int ssleay_rand_pseudo_bytes(unsigned char *buf, int num); 166static int ssleay_rand_status(void); 167 168RAND_METHOD rand_ssleay_meth={ 169 ssleay_rand_seed, 170 ssleay_rand_bytes, 171 ssleay_rand_cleanup, 172 ssleay_rand_add, 173 ssleay_rand_pseudo_bytes, 174 ssleay_rand_status 175 }; 176 177RAND_METHOD *RAND_SSLeay(void) 178 { 179 return(&rand_ssleay_meth); 180 } 181 182static void ssleay_rand_cleanup(void) 183 { 184 OPENSSL_cleanse(state,sizeof(state)); 185 state_num=0; 186 state_index=0; 187 OPENSSL_cleanse(md,MD_DIGEST_LENGTH); 188 md_count[0]=0; 189 md_count[1]=0; 190 entropy=0; 191 initialized=0; 192 } 193 194static void ssleay_rand_add(const void *buf, int num, double add) 195 { 196 int i,j,k,st_idx; 197 long md_c[2]; 198 unsigned char local_md[MD_DIGEST_LENGTH]; 199 EVP_MD_CTX m; 200 int do_not_lock; 201 202 /* 203 * (Based on the rand(3) manpage) 204 * 205 * The input is chopped up into units of 20 bytes (or less for 206 * the last block). Each of these blocks is run through the hash 207 * function as follows: The data passed to the hash function 208 * is the current 'md', the same number of bytes from the 'state' 209 * (the location determined by in incremented looping index) as 210 * the current 'block', the new key data 'block', and 'count' 211 * (which is incremented after each use). 212 * The result of this is kept in 'md' and also xored into the 213 * 'state' at the same locations that were used as input into the 214 * hash function. 215 */ 216 217 /* check if we already have the lock */ 218 if (crypto_lock_rand) 219 { 220 CRYPTO_r_lock(CRYPTO_LOCK_RAND2); 221 do_not_lock = (locking_thread == CRYPTO_thread_id()); 222 CRYPTO_r_unlock(CRYPTO_LOCK_RAND2); 223 } 224 else 225 do_not_lock = 0; 226 227 if (!do_not_lock) CRYPTO_w_lock(CRYPTO_LOCK_RAND); 228 st_idx=state_index; 229 230 /* use our own copies of the counters so that even 231 * if a concurrent thread seeds with exactly the 232 * same data and uses the same subarray there's _some_ 233 * difference */ 234 md_c[0] = md_count[0]; 235 md_c[1] = md_count[1]; 236 237 memcpy(local_md, md, sizeof md); 238 239 /* state_index <= state_num <= STATE_SIZE */ 240 state_index += num; 241 if (state_index >= STATE_SIZE) 242 { 243 state_index%=STATE_SIZE; 244 state_num=STATE_SIZE; 245 } 246 else if (state_num < STATE_SIZE) 247 { 248 if (state_index > state_num) 249 state_num=state_index; 250 } 251 /* state_index <= state_num <= STATE_SIZE */ 252 253 /* state[st_idx], ..., state[(st_idx + num - 1) % STATE_SIZE] 254 * are what we will use now, but other threads may use them 255 * as well */ 256 257 md_count[1] += (num / MD_DIGEST_LENGTH) + (num % MD_DIGEST_LENGTH > 0); 258 259 if (!do_not_lock) CRYPTO_w_unlock(CRYPTO_LOCK_RAND); 260 261 EVP_MD_CTX_init(&m); 262 for (i=0; i<num; i+=MD_DIGEST_LENGTH) 263 { 264 j=(num-i); 265 j=(j > MD_DIGEST_LENGTH)?MD_DIGEST_LENGTH:j; 266 267 MD_Init(&m); 268 MD_Update(&m,local_md,MD_DIGEST_LENGTH); 269 k=(st_idx+j)-STATE_SIZE; 270 if (k > 0) 271 { 272 MD_Update(&m,&(state[st_idx]),j-k); 273 MD_Update(&m,&(state[0]),k); 274 } 275 else 276 MD_Update(&m,&(state[st_idx]),j); 277 278 MD_Update(&m,buf,j); 279 MD_Update(&m,(unsigned char *)&(md_c[0]),sizeof(md_c)); 280 MD_Final(&m,local_md); 281 md_c[1]++; 282 283 buf=(const char *)buf + j; 284 285 for (k=0; k<j; k++) 286 { 287 /* Parallel threads may interfere with this, 288 * but always each byte of the new state is 289 * the XOR of some previous value of its 290 * and local_md (itermediate values may be lost). 291 * Alway using locking could hurt performance more 292 * than necessary given that conflicts occur only 293 * when the total seeding is longer than the random 294 * state. */ 295 state[st_idx++]^=local_md[k]; 296 if (st_idx >= STATE_SIZE) 297 st_idx=0; 298 } 299 } 300 EVP_MD_CTX_cleanup(&m); 301 302 if (!do_not_lock) CRYPTO_w_lock(CRYPTO_LOCK_RAND); 303 /* Don't just copy back local_md into md -- this could mean that 304 * other thread's seeding remains without effect (except for 305 * the incremented counter). By XORing it we keep at least as 306 * much entropy as fits into md. */ 307 for (k = 0; k < (int)sizeof(md); k++) 308 { 309 md[k] ^= local_md[k]; 310 } 311 if (entropy < ENTROPY_NEEDED) /* stop counting when we have enough */ 312 entropy += add; 313 if (!do_not_lock) CRYPTO_w_unlock(CRYPTO_LOCK_RAND); 314 315#if !defined(OPENSSL_THREADS) && !defined(OPENSSL_SYS_WIN32) 316 assert(md_c[1] == md_count[1]); 317#endif 318 } 319 320static void ssleay_rand_seed(const void *buf, int num) 321 { 322 ssleay_rand_add(buf, num, (double)num); 323 } 324 325static int ssleay_rand_bytes(unsigned char *buf, int num) 326 { 327 static volatile int stirred_pool = 0; 328 int i,j,k,st_num,st_idx; 329 int num_ceil; 330 int ok; 331 long md_c[2]; 332 unsigned char local_md[MD_DIGEST_LENGTH]; 333 EVP_MD_CTX m; 334#ifndef GETPID_IS_MEANINGLESS 335 pid_t curr_pid = getpid(); 336#endif 337 int do_stir_pool = 0; 338 339#ifdef OPENSSL_FIPS 340 if(FIPS_mode()) 341 { 342 FIPSerr(FIPS_F_SSLEAY_RAND_BYTES,FIPS_R_NON_FIPS_METHOD); 343 return 0; 344 } 345#endif 346 347#ifdef PREDICT 348 if (rand_predictable) 349 { 350 static unsigned char val=0; 351 352 for (i=0; i<num; i++) 353 buf[i]=val++; 354 return(1); 355 } 356#endif 357 358 if (num <= 0) 359 return 1; 360 361 EVP_MD_CTX_init(&m); 362 /* round upwards to multiple of MD_DIGEST_LENGTH/2 */ 363 num_ceil = (1 + (num-1)/(MD_DIGEST_LENGTH/2)) * (MD_DIGEST_LENGTH/2); 364 365 /* 366 * (Based on the rand(3) manpage:) 367 * 368 * For each group of 10 bytes (or less), we do the following: 369 * 370 * Input into the hash function the local 'md' (which is initialized from 371 * the global 'md' before any bytes are generated), the bytes that are to 372 * be overwritten by the random bytes, and bytes from the 'state' 373 * (incrementing looping index). From this digest output (which is kept 374 * in 'md'), the top (up to) 10 bytes are returned to the caller and the 375 * bottom 10 bytes are xored into the 'state'. 376 * 377 * Finally, after we have finished 'num' random bytes for the 378 * caller, 'count' (which is incremented) and the local and global 'md' 379 * are fed into the hash function and the results are kept in the 380 * global 'md'. 381 */ 382 383 CRYPTO_w_lock(CRYPTO_LOCK_RAND); 384 385 /* prevent ssleay_rand_bytes() from trying to obtain the lock again */ 386 CRYPTO_w_lock(CRYPTO_LOCK_RAND2); 387 locking_thread = CRYPTO_thread_id(); 388 CRYPTO_w_unlock(CRYPTO_LOCK_RAND2); 389 crypto_lock_rand = 1; 390 391 if (!initialized) 392 { 393 RAND_poll(); 394 initialized = 1; 395 } 396 397 if (!stirred_pool) 398 do_stir_pool = 1; 399 400 ok = (entropy >= ENTROPY_NEEDED); 401 if (!ok) 402 { 403 /* If the PRNG state is not yet unpredictable, then seeing 404 * the PRNG output may help attackers to determine the new 405 * state; thus we have to decrease the entropy estimate. 406 * Once we've had enough initial seeding we don't bother to 407 * adjust the entropy count, though, because we're not ambitious 408 * to provide *information-theoretic* randomness. 409 * 410 * NOTE: This approach fails if the program forks before 411 * we have enough entropy. Entropy should be collected 412 * in a separate input pool and be transferred to the 413 * output pool only when the entropy limit has been reached. 414 */ 415 entropy -= num; 416 if (entropy < 0) 417 entropy = 0; 418 } 419 420 if (do_stir_pool) 421 { 422 /* In the output function only half of 'md' remains secret, 423 * so we better make sure that the required entropy gets 424 * 'evenly distributed' through 'state', our randomness pool. 425 * The input function (ssleay_rand_add) chains all of 'md', 426 * which makes it more suitable for this purpose. 427 */ 428 429 int n = STATE_SIZE; /* so that the complete pool gets accessed */ 430 while (n > 0) 431 { 432#if MD_DIGEST_LENGTH > 20 433# error "Please adjust DUMMY_SEED." 434#endif 435#define DUMMY_SEED "...................." /* at least MD_DIGEST_LENGTH */ 436 /* Note that the seed does not matter, it's just that 437 * ssleay_rand_add expects to have something to hash. */ 438 ssleay_rand_add(DUMMY_SEED, MD_DIGEST_LENGTH, 0.0); 439 n -= MD_DIGEST_LENGTH; 440 } 441 if (ok) 442 stirred_pool = 1; 443 } 444 445 st_idx=state_index; 446 st_num=state_num; 447 md_c[0] = md_count[0]; 448 md_c[1] = md_count[1]; 449 memcpy(local_md, md, sizeof md); 450 451 state_index+=num_ceil; 452 if (state_index > state_num) 453 state_index %= state_num; 454 455 /* state[st_idx], ..., state[(st_idx + num_ceil - 1) % st_num] 456 * are now ours (but other threads may use them too) */ 457 458 md_count[0] += 1; 459 460 /* before unlocking, we must clear 'crypto_lock_rand' */ 461 crypto_lock_rand = 0; 462 CRYPTO_w_unlock(CRYPTO_LOCK_RAND); 463 464 while (num > 0) 465 { 466 /* num_ceil -= MD_DIGEST_LENGTH/2 */ 467 j=(num >= MD_DIGEST_LENGTH/2)?MD_DIGEST_LENGTH/2:num; 468 num-=j; 469 MD_Init(&m); 470#ifndef GETPID_IS_MEANINGLESS 471 if (curr_pid) /* just in the first iteration to save time */ 472 { 473 MD_Update(&m,(unsigned char*)&curr_pid,sizeof curr_pid); 474 curr_pid = 0; 475 } 476#endif 477 MD_Update(&m,local_md,MD_DIGEST_LENGTH); 478 MD_Update(&m,(unsigned char *)&(md_c[0]),sizeof(md_c)); 479#ifndef PURIFY 480 MD_Update(&m,buf,j); /* purify complains */ 481#endif 482 k=(st_idx+MD_DIGEST_LENGTH/2)-st_num; 483 if (k > 0) 484 { 485 MD_Update(&m,&(state[st_idx]),MD_DIGEST_LENGTH/2-k); 486 MD_Update(&m,&(state[0]),k); 487 } 488 else 489 MD_Update(&m,&(state[st_idx]),MD_DIGEST_LENGTH/2); 490 MD_Final(&m,local_md); 491 492 for (i=0; i<MD_DIGEST_LENGTH/2; i++) 493 { 494 state[st_idx++]^=local_md[i]; /* may compete with other threads */ 495 if (st_idx >= st_num) 496 st_idx=0; 497 if (i < j) 498 *(buf++)=local_md[i+MD_DIGEST_LENGTH/2]; 499 } 500 } 501 502 MD_Init(&m); 503 MD_Update(&m,(unsigned char *)&(md_c[0]),sizeof(md_c)); 504 MD_Update(&m,local_md,MD_DIGEST_LENGTH); 505 CRYPTO_w_lock(CRYPTO_LOCK_RAND); 506 MD_Update(&m,md,MD_DIGEST_LENGTH); 507 MD_Final(&m,md); 508 CRYPTO_w_unlock(CRYPTO_LOCK_RAND); 509 510 EVP_MD_CTX_cleanup(&m); 511 if (ok) 512 return(1); 513 else 514 { 515 RANDerr(RAND_F_SSLEAY_RAND_BYTES,RAND_R_PRNG_NOT_SEEDED); 516 ERR_add_error_data(1, "You need to read the OpenSSL FAQ, " 517 "http://www.openssl.org/support/faq.html"); 518 return(0); 519 } 520 } 521 522/* pseudo-random bytes that are guaranteed to be unique but not 523 unpredictable */ 524static int ssleay_rand_pseudo_bytes(unsigned char *buf, int num) 525 { 526 int ret; 527 unsigned long err; 528 529 ret = RAND_bytes(buf, num); 530 if (ret == 0) 531 { 532 err = ERR_peek_error(); 533 if (ERR_GET_LIB(err) == ERR_LIB_RAND && 534 ERR_GET_REASON(err) == RAND_R_PRNG_NOT_SEEDED) 535 ERR_clear_error(); 536 } 537 return (ret); 538 } 539 540static int ssleay_rand_status(void) 541 { 542 int ret; 543 int do_not_lock; 544 545 /* check if we already have the lock 546 * (could happen if a RAND_poll() implementation calls RAND_status()) */ 547 if (crypto_lock_rand) 548 { 549 CRYPTO_r_lock(CRYPTO_LOCK_RAND2); 550 do_not_lock = (locking_thread == CRYPTO_thread_id()); 551 CRYPTO_r_unlock(CRYPTO_LOCK_RAND2); 552 } 553 else 554 do_not_lock = 0; 555 556 if (!do_not_lock) 557 { 558 CRYPTO_w_lock(CRYPTO_LOCK_RAND); 559 560 /* prevent ssleay_rand_bytes() from trying to obtain the lock again */ 561 CRYPTO_w_lock(CRYPTO_LOCK_RAND2); 562 locking_thread = CRYPTO_thread_id(); 563 CRYPTO_w_unlock(CRYPTO_LOCK_RAND2); 564 crypto_lock_rand = 1; 565 } 566 567 if (!initialized) 568 { 569 RAND_poll(); 570 initialized = 1; 571 } 572 573 ret = entropy >= ENTROPY_NEEDED; 574 575 if (!do_not_lock) 576 { 577 /* before unlocking, we must clear 'crypto_lock_rand' */ 578 crypto_lock_rand = 0; 579 580 CRYPTO_w_unlock(CRYPTO_LOCK_RAND); 581 } 582 583 return ret; 584 } 585