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#include <openssl/fips.h> 130 131#ifdef BN_DEBUG 132# define PREDICT 133#endif 134 135/* #define PREDICT 1 */ 136 137#define STATE_SIZE 1023 138static int state_num=0,state_index=0; 139static unsigned char state[STATE_SIZE+MD_DIGEST_LENGTH]; 140static unsigned char md[MD_DIGEST_LENGTH]; 141static long md_count[2]={0,0}; 142static double entropy=0; 143static int initialized=0; 144 145static unsigned int crypto_lock_rand = 0; /* may be set only when a thread 146 * holds CRYPTO_LOCK_RAND 147 * (to prevent double locking) */ 148/* access to lockin_thread is synchronized by CRYPTO_LOCK_RAND2 */ 149static unsigned long locking_thread = 0; /* valid iff crypto_lock_rand is set */ 150 151 152#ifdef PREDICT 153int rand_predictable=0; 154#endif 155 156const char *RAND_version="RAND" OPENSSL_VERSION_PTEXT; 157 158static void ssleay_rand_cleanup(void); 159static void ssleay_rand_seed(const void *buf, int num); 160static void ssleay_rand_add(const void *buf, int num, double add_entropy); 161static int ssleay_rand_bytes(unsigned char *buf, int num); 162static int ssleay_rand_pseudo_bytes(unsigned char *buf, int num); 163static int ssleay_rand_status(void); 164 165RAND_METHOD rand_ssleay_meth={ 166 ssleay_rand_seed, 167 ssleay_rand_bytes, 168 ssleay_rand_cleanup, 169 ssleay_rand_add, 170 ssleay_rand_pseudo_bytes, 171 ssleay_rand_status 172 }; 173 174RAND_METHOD *RAND_SSLeay(void) 175 { 176 return(&rand_ssleay_meth); 177 } 178 179static void ssleay_rand_cleanup(void) 180 { 181 OPENSSL_cleanse(state,sizeof(state)); 182 state_num=0; 183 state_index=0; 184 OPENSSL_cleanse(md,MD_DIGEST_LENGTH); 185 md_count[0]=0; 186 md_count[1]=0; 187 entropy=0; 188 initialized=0; 189 } 190 191static void ssleay_rand_add(const void *buf, int num, double add) 192 { 193 int i,j,k,st_idx; 194 long md_c[2]; 195 unsigned char local_md[MD_DIGEST_LENGTH]; 196 EVP_MD_CTX m; 197 int do_not_lock; 198 199 /* 200 * (Based on the rand(3) manpage) 201 * 202 * The input is chopped up into units of 20 bytes (or less for 203 * the last block). Each of these blocks is run through the hash 204 * function as follows: The data passed to the hash function 205 * is the current 'md', the same number of bytes from the 'state' 206 * (the location determined by in incremented looping index) as 207 * the current 'block', the new key data 'block', and 'count' 208 * (which is incremented after each use). 209 * The result of this is kept in 'md' and also xored into the 210 * 'state' at the same locations that were used as input into the 211 * hash function. 212 */ 213 214 /* check if we already have the lock */ 215 if (crypto_lock_rand) 216 { 217 CRYPTO_r_lock(CRYPTO_LOCK_RAND2); 218 do_not_lock = (locking_thread == CRYPTO_thread_id()); 219 CRYPTO_r_unlock(CRYPTO_LOCK_RAND2); 220 } 221 else 222 do_not_lock = 0; 223 224 if (!do_not_lock) CRYPTO_w_lock(CRYPTO_LOCK_RAND); 225 st_idx=state_index; 226 227 /* use our own copies of the counters so that even 228 * if a concurrent thread seeds with exactly the 229 * same data and uses the same subarray there's _some_ 230 * difference */ 231 md_c[0] = md_count[0]; 232 md_c[1] = md_count[1]; 233 234 memcpy(local_md, md, sizeof md); 235 236 /* state_index <= state_num <= STATE_SIZE */ 237 state_index += num; 238 if (state_index >= STATE_SIZE) 239 { 240 state_index%=STATE_SIZE; 241 state_num=STATE_SIZE; 242 } 243 else if (state_num < STATE_SIZE) 244 { 245 if (state_index > state_num) 246 state_num=state_index; 247 } 248 /* state_index <= state_num <= STATE_SIZE */ 249 250 /* state[st_idx], ..., state[(st_idx + num - 1) % STATE_SIZE] 251 * are what we will use now, but other threads may use them 252 * as well */ 253 254 md_count[1] += (num / MD_DIGEST_LENGTH) + (num % MD_DIGEST_LENGTH > 0); 255 256 if (!do_not_lock) CRYPTO_w_unlock(CRYPTO_LOCK_RAND); 257 258 EVP_MD_CTX_init(&m); 259 for (i=0; i<num; i+=MD_DIGEST_LENGTH) 260 { 261 j=(num-i); 262 j=(j > MD_DIGEST_LENGTH)?MD_DIGEST_LENGTH:j; 263 264 MD_Init(&m); 265 MD_Update(&m,local_md,MD_DIGEST_LENGTH); 266 k=(st_idx+j)-STATE_SIZE; 267 if (k > 0) 268 { 269 MD_Update(&m,&(state[st_idx]),j-k); 270 MD_Update(&m,&(state[0]),k); 271 } 272 else 273 MD_Update(&m,&(state[st_idx]),j); 274 275 MD_Update(&m,buf,j); 276 MD_Update(&m,(unsigned char *)&(md_c[0]),sizeof(md_c)); 277 MD_Final(&m,local_md); 278 md_c[1]++; 279 280 buf=(const char *)buf + j; 281 282 for (k=0; k<j; k++) 283 { 284 /* Parallel threads may interfere with this, 285 * but always each byte of the new state is 286 * the XOR of some previous value of its 287 * and local_md (itermediate values may be lost). 288 * Alway using locking could hurt performance more 289 * than necessary given that conflicts occur only 290 * when the total seeding is longer than the random 291 * state. */ 292 state[st_idx++]^=local_md[k]; 293 if (st_idx >= STATE_SIZE) 294 st_idx=0; 295 } 296 } 297 EVP_MD_CTX_cleanup(&m); 298 299 if (!do_not_lock) CRYPTO_w_lock(CRYPTO_LOCK_RAND); 300 /* Don't just copy back local_md into md -- this could mean that 301 * other thread's seeding remains without effect (except for 302 * the incremented counter). By XORing it we keep at least as 303 * much entropy as fits into md. */ 304 for (k = 0; k < sizeof md; k++) 305 { 306 md[k] ^= local_md[k]; 307 } 308 if (entropy < ENTROPY_NEEDED) /* stop counting when we have enough */ 309 entropy += add; 310 if (!do_not_lock) CRYPTO_w_unlock(CRYPTO_LOCK_RAND); 311 312#if !defined(OPENSSL_THREADS) && !defined(OPENSSL_SYS_WIN32) 313 assert(md_c[1] == md_count[1]); 314#endif 315 } 316 317static void ssleay_rand_seed(const void *buf, int num) 318 { 319 ssleay_rand_add(buf, num, num); 320 } 321 322static int ssleay_rand_bytes(unsigned char *buf, int num) 323 { 324 static volatile int stirred_pool = 0; 325 int i,j,k,st_num,st_idx; 326 int num_ceil; 327 int ok; 328 long md_c[2]; 329 unsigned char local_md[MD_DIGEST_LENGTH]; 330 EVP_MD_CTX m; 331#ifndef GETPID_IS_MEANINGLESS 332 pid_t curr_pid = getpid(); 333#endif 334 int do_stir_pool = 0; 335 336#ifdef OPENSSL_FIPS 337 if(FIPS_mode()) 338 { 339 FIPSerr(FIPS_F_SSLEAY_RAND_BYTES,FIPS_R_NON_FIPS_METHOD); 340 return 0; 341 } 342#endif 343 344#ifdef PREDICT 345 if (rand_predictable) 346 { 347 static unsigned char val=0; 348 349 for (i=0; i<num; i++) 350 buf[i]=val++; 351 return(1); 352 } 353#endif 354 355 if (num <= 0) 356 return 1; 357 358 EVP_MD_CTX_init(&m); 359 /* round upwards to multiple of MD_DIGEST_LENGTH/2 */ 360 num_ceil = (1 + (num-1)/(MD_DIGEST_LENGTH/2)) * (MD_DIGEST_LENGTH/2); 361 362 /* 363 * (Based on the rand(3) manpage:) 364 * 365 * For each group of 10 bytes (or less), we do the following: 366 * 367 * Input into the hash function the local 'md' (which is initialized from 368 * the global 'md' before any bytes are generated), the bytes that are to 369 * be overwritten by the random bytes, and bytes from the 'state' 370 * (incrementing looping index). From this digest output (which is kept 371 * in 'md'), the top (up to) 10 bytes are returned to the caller and the 372 * bottom 10 bytes are xored into the 'state'. 373 * 374 * Finally, after we have finished 'num' random bytes for the 375 * caller, 'count' (which is incremented) and the local and global 'md' 376 * are fed into the hash function and the results are kept in the 377 * global 'md'. 378 */ 379 380 CRYPTO_w_lock(CRYPTO_LOCK_RAND); 381 382 /* prevent ssleay_rand_bytes() from trying to obtain the lock again */ 383 CRYPTO_w_lock(CRYPTO_LOCK_RAND2); 384 locking_thread = CRYPTO_thread_id(); 385 CRYPTO_w_unlock(CRYPTO_LOCK_RAND2); 386 crypto_lock_rand = 1; 387 388 if (!initialized) 389 { 390 RAND_poll(); 391 initialized = 1; 392 } 393 394 if (!stirred_pool) 395 do_stir_pool = 1; 396 397 ok = (entropy >= ENTROPY_NEEDED); 398 if (!ok) 399 { 400 /* If the PRNG state is not yet unpredictable, then seeing 401 * the PRNG output may help attackers to determine the new 402 * state; thus we have to decrease the entropy estimate. 403 * Once we've had enough initial seeding we don't bother to 404 * adjust the entropy count, though, because we're not ambitious 405 * to provide *information-theoretic* randomness. 406 * 407 * NOTE: This approach fails if the program forks before 408 * we have enough entropy. Entropy should be collected 409 * in a separate input pool and be transferred to the 410 * output pool only when the entropy limit has been reached. 411 */ 412 entropy -= num; 413 if (entropy < 0) 414 entropy = 0; 415 } 416 417 if (do_stir_pool) 418 { 419 /* In the output function only half of 'md' remains secret, 420 * so we better make sure that the required entropy gets 421 * 'evenly distributed' through 'state', our randomness pool. 422 * The input function (ssleay_rand_add) chains all of 'md', 423 * which makes it more suitable for this purpose. 424 */ 425 426 int n = STATE_SIZE; /* so that the complete pool gets accessed */ 427 while (n > 0) 428 { 429#if MD_DIGEST_LENGTH > 20 430# error "Please adjust DUMMY_SEED." 431#endif 432#define DUMMY_SEED "...................." /* at least MD_DIGEST_LENGTH */ 433 /* Note that the seed does not matter, it's just that 434 * ssleay_rand_add expects to have something to hash. */ 435 ssleay_rand_add(DUMMY_SEED, MD_DIGEST_LENGTH, 0.0); 436 n -= MD_DIGEST_LENGTH; 437 } 438 if (ok) 439 stirred_pool = 1; 440 } 441 442 st_idx=state_index; 443 st_num=state_num; 444 md_c[0] = md_count[0]; 445 md_c[1] = md_count[1]; 446 memcpy(local_md, md, sizeof md); 447 448 state_index+=num_ceil; 449 if (state_index > state_num) 450 state_index %= state_num; 451 452 /* state[st_idx], ..., state[(st_idx + num_ceil - 1) % st_num] 453 * are now ours (but other threads may use them too) */ 454 455 md_count[0] += 1; 456 457 /* before unlocking, we must clear 'crypto_lock_rand' */ 458 crypto_lock_rand = 0; 459 CRYPTO_w_unlock(CRYPTO_LOCK_RAND); 460 461 while (num > 0) 462 { 463 /* num_ceil -= MD_DIGEST_LENGTH/2 */ 464 j=(num >= MD_DIGEST_LENGTH/2)?MD_DIGEST_LENGTH/2:num; 465 num-=j; 466 MD_Init(&m); 467#ifndef GETPID_IS_MEANINGLESS 468 if (curr_pid) /* just in the first iteration to save time */ 469 { 470 MD_Update(&m,(unsigned char*)&curr_pid,sizeof curr_pid); 471 curr_pid = 0; 472 } 473#endif 474 MD_Update(&m,local_md,MD_DIGEST_LENGTH); 475 MD_Update(&m,(unsigned char *)&(md_c[0]),sizeof(md_c)); 476#ifndef PURIFY 477 MD_Update(&m,buf,j); /* purify complains */ 478#endif 479 k=(st_idx+MD_DIGEST_LENGTH/2)-st_num; 480 if (k > 0) 481 { 482 MD_Update(&m,&(state[st_idx]),MD_DIGEST_LENGTH/2-k); 483 MD_Update(&m,&(state[0]),k); 484 } 485 else 486 MD_Update(&m,&(state[st_idx]),MD_DIGEST_LENGTH/2); 487 MD_Final(&m,local_md); 488 489 for (i=0; i<MD_DIGEST_LENGTH/2; i++) 490 { 491 state[st_idx++]^=local_md[i]; /* may compete with other threads */ 492 if (st_idx >= st_num) 493 st_idx=0; 494 if (i < j) 495 *(buf++)=local_md[i+MD_DIGEST_LENGTH/2]; 496 } 497 } 498 499 MD_Init(&m); 500 MD_Update(&m,(unsigned char *)&(md_c[0]),sizeof(md_c)); 501 MD_Update(&m,local_md,MD_DIGEST_LENGTH); 502 CRYPTO_w_lock(CRYPTO_LOCK_RAND); 503 MD_Update(&m,md,MD_DIGEST_LENGTH); 504 MD_Final(&m,md); 505 CRYPTO_w_unlock(CRYPTO_LOCK_RAND); 506 507 EVP_MD_CTX_cleanup(&m); 508 if (ok) 509 return(1); 510 else 511 { 512 RANDerr(RAND_F_SSLEAY_RAND_BYTES,RAND_R_PRNG_NOT_SEEDED); 513 ERR_add_error_data(1, "You need to read the OpenSSL FAQ, " 514 "http://www.openssl.org/support/faq.html"); 515 return(0); 516 } 517 } 518 519/* pseudo-random bytes that are guaranteed to be unique but not 520 unpredictable */ 521static int ssleay_rand_pseudo_bytes(unsigned char *buf, int num) 522 { 523 int ret; 524 unsigned long err; 525 526 ret = RAND_bytes(buf, num); 527 if (ret == 0) 528 { 529 err = ERR_peek_error(); 530 if (ERR_GET_LIB(err) == ERR_LIB_RAND && 531 ERR_GET_REASON(err) == RAND_R_PRNG_NOT_SEEDED) 532 (void)ERR_get_error(); 533 } 534 return (ret); 535 } 536 537static int ssleay_rand_status(void) 538 { 539 int ret; 540 int do_not_lock; 541 542 /* check if we already have the lock 543 * (could happen if a RAND_poll() implementation calls RAND_status()) */ 544 if (crypto_lock_rand) 545 { 546 CRYPTO_r_lock(CRYPTO_LOCK_RAND2); 547 do_not_lock = (locking_thread == CRYPTO_thread_id()); 548 CRYPTO_r_unlock(CRYPTO_LOCK_RAND2); 549 } 550 else 551 do_not_lock = 0; 552 553 if (!do_not_lock) 554 { 555 CRYPTO_w_lock(CRYPTO_LOCK_RAND); 556 557 /* prevent ssleay_rand_bytes() from trying to obtain the lock again */ 558 CRYPTO_w_lock(CRYPTO_LOCK_RAND2); 559 locking_thread = CRYPTO_thread_id(); 560 CRYPTO_w_unlock(CRYPTO_LOCK_RAND2); 561 crypto_lock_rand = 1; 562 } 563 564 if (!initialized) 565 { 566 RAND_poll(); 567 initialized = 1; 568 } 569 570 ret = entropy >= ENTROPY_NEEDED; 571 572 if (!do_not_lock) 573 { 574 /* before unlocking, we must clear 'crypto_lock_rand' */ 575 crypto_lock_rand = 0; 576 577 CRYPTO_w_unlock(CRYPTO_LOCK_RAND); 578 } 579 580 return ret; 581 } 582