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