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