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