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