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