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