md_rand.c revision 280304
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 }; 143 144static double entropy = 0; 145static int initialized = 0; 146 147static unsigned int crypto_lock_rand = 0; /* may be set only when a thread 148 * holds CRYPTO_LOCK_RAND (to 149 * prevent double locking) */ 150/* access to lockin_thread is synchronized by CRYPTO_LOCK_RAND2 */ 151/* valid iff crypto_lock_rand is set */ 152static CRYPTO_THREADID locking_threadid; 153 154#ifdef PREDICT 155int rand_predictable = 0; 156#endif 157 158const char RAND_version[] = "RAND" OPENSSL_VERSION_PTEXT; 159 160static void ssleay_rand_cleanup(void); 161static void ssleay_rand_seed(const void *buf, int num); 162static void ssleay_rand_add(const void *buf, int num, double add_entropy); 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 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 } else 227 do_not_lock = 0; 228 229 if (!do_not_lock) 230 CRYPTO_w_lock(CRYPTO_LOCK_RAND); 231 st_idx = state_index; 232 233 /* 234 * use our own copies of the counters so that even if a concurrent thread 235 * seeds with exactly the same data and uses the same subarray there's 236 * _some_ difference 237 */ 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 state_index %= STATE_SIZE; 247 state_num = STATE_SIZE; 248 } else if (state_num < STATE_SIZE) { 249 if (state_index > state_num) 250 state_num = state_index; 251 } 252 /* state_index <= state_num <= STATE_SIZE */ 253 254 /* 255 * state[st_idx], ..., state[(st_idx + num - 1) % STATE_SIZE] are what we 256 * will use now, but other threads may use them as well 257 */ 258 259 md_count[1] += (num / MD_DIGEST_LENGTH) + (num % MD_DIGEST_LENGTH > 0); 260 261 if (!do_not_lock) 262 CRYPTO_w_unlock(CRYPTO_LOCK_RAND); 263 264 EVP_MD_CTX_init(&m); 265 for (i = 0; i < num; i += MD_DIGEST_LENGTH) { 266 j = (num - i); 267 j = (j > MD_DIGEST_LENGTH) ? MD_DIGEST_LENGTH : j; 268 269 MD_Init(&m); 270 MD_Update(&m, local_md, MD_DIGEST_LENGTH); 271 k = (st_idx + j) - STATE_SIZE; 272 if (k > 0) { 273 MD_Update(&m, &(state[st_idx]), j - k); 274 MD_Update(&m, &(state[0]), k); 275 } else 276 MD_Update(&m, &(state[st_idx]), j); 277 278 /* DO NOT REMOVE THE FOLLOWING CALL TO MD_Update()! */ 279 MD_Update(&m, buf, j); 280 /* 281 * We know that line may cause programs such as purify and valgrind 282 * to complain about use of uninitialized data. The problem is not, 283 * it's with the caller. Removing that line will make sure you get 284 * really bad randomness and thereby other problems such as very 285 * insecure keys. 286 */ 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, but always each byte 297 * of the new state is the XOR of some previous value of its and 298 * local_md (itermediate values may be lost). Alway using locking 299 * could hurt performance more than necessary given that 300 * conflicts occur only when the total seeding is longer than the 301 * random state. 302 */ 303 state[st_idx++] ^= local_md[k]; 304 if (st_idx >= STATE_SIZE) 305 st_idx = 0; 306 } 307 } 308 EVP_MD_CTX_cleanup(&m); 309 310 if (!do_not_lock) 311 CRYPTO_w_lock(CRYPTO_LOCK_RAND); 312 /* 313 * Don't just copy back local_md into md -- this could mean that other 314 * thread's seeding remains without effect (except for the incremented 315 * counter). By XORing it we keep at least as much entropy as fits into 316 * md. 317 */ 318 for (k = 0; k < (int)sizeof(md); k++) { 319 md[k] ^= local_md[k]; 320 } 321 if (entropy < ENTROPY_NEEDED) /* stop counting when we have enough */ 322 entropy += add; 323 if (!do_not_lock) 324 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 static unsigned char val = 0; 353 354 for (i = 0; i < num; i++) 355 buf[i] = val++; 356 return (1); 357 } 358#endif 359 360 if (num <= 0) 361 return 1; 362 363 EVP_MD_CTX_init(&m); 364 /* round upwards to multiple of MD_DIGEST_LENGTH/2 */ 365 num_ceil = 366 (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 RAND_poll(); 396 initialized = 1; 397 } 398 399 if (!stirred_pool) 400 do_stir_pool = 1; 401 402 ok = (entropy >= ENTROPY_NEEDED); 403 if (!ok) { 404 /* 405 * If the PRNG state is not yet unpredictable, then seeing the PRNG 406 * output may help attackers to determine the new state; thus we have 407 * to decrease the entropy estimate. Once we've had enough initial 408 * seeding we don't bother to adjust the entropy count, though, 409 * because we're not ambitious to provide *information-theoretic* 410 * randomness. NOTE: This approach fails if the program forks before 411 * we have enough entropy. Entropy should be collected in a separate 412 * input pool and be transferred to the output pool only when the 413 * entropy limit has been reached. 414 */ 415 entropy -= num; 416 if (entropy < 0) 417 entropy = 0; 418 } 419 420 if (do_stir_pool) { 421 /* 422 * In the output function only half of 'md' remains secret, so we 423 * better make sure that the required entropy gets 'evenly 424 * distributed' through 'state', our randomness pool. The input 425 * function (ssleay_rand_add) chains all of 'md', which makes it more 426 * suitable for this purpose. 427 */ 428 429 int n = STATE_SIZE; /* so that the complete pool gets accessed */ 430 while (n > 0) { 431#if MD_DIGEST_LENGTH > 20 432# error "Please adjust DUMMY_SEED." 433#endif 434#define DUMMY_SEED "...................." /* at least MD_DIGEST_LENGTH */ 435 /* 436 * Note that the seed does not matter, it's just that 437 * ssleay_rand_add expects to have something to hash. 438 */ 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 /* 457 * state[st_idx], ..., state[(st_idx + num_ceil - 1) % st_num] are now 458 * ours (but other threads may use them too) 459 */ 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 /* num_ceil -= MD_DIGEST_LENGTH/2 */ 470 j = (num >= MD_DIGEST_LENGTH / 2) ? MD_DIGEST_LENGTH / 2 : num; 471 num -= j; 472 MD_Init(&m); 473#ifndef GETPID_IS_MEANINGLESS 474 if (curr_pid) { /* just in the first iteration to save time */ 475 MD_Update(&m, (unsigned char *)&curr_pid, sizeof curr_pid); 476 curr_pid = 0; 477 } 478#endif 479 MD_Update(&m, local_md, MD_DIGEST_LENGTH); 480 MD_Update(&m, (unsigned char *)&(md_c[0]), sizeof(md_c)); 481 482#ifndef PURIFY /* purify complains */ 483 /* 484 * The following line uses the supplied buffer as a small source of 485 * entropy: since this buffer is often uninitialised it may cause 486 * programs such as purify or valgrind to complain. So for those 487 * builds it is not used: the removal of such a small source of 488 * entropy has negligible impact on security. 489 */ 490 MD_Update(&m, buf, j); 491#endif 492 493 k = (st_idx + MD_DIGEST_LENGTH / 2) - st_num; 494 if (k > 0) { 495 MD_Update(&m, &(state[st_idx]), MD_DIGEST_LENGTH / 2 - k); 496 MD_Update(&m, &(state[0]), k); 497 } else 498 MD_Update(&m, &(state[st_idx]), MD_DIGEST_LENGTH / 2); 499 MD_Final(&m, local_md); 500 501 for (i = 0; i < MD_DIGEST_LENGTH / 2; i++) { 502 /* may compete with other threads */ 503 state[st_idx++] ^= local_md[i]; 504 if (st_idx >= st_num) 505 st_idx = 0; 506 if (i < j) 507 *(buf++) = local_md[i + MD_DIGEST_LENGTH / 2]; 508 } 509 } 510 511 MD_Init(&m); 512 MD_Update(&m, (unsigned char *)&(md_c[0]), sizeof(md_c)); 513 MD_Update(&m, local_md, MD_DIGEST_LENGTH); 514 if (lock) 515 CRYPTO_w_lock(CRYPTO_LOCK_RAND); 516 MD_Update(&m, md, MD_DIGEST_LENGTH); 517 MD_Final(&m, md); 518 if (lock) 519 CRYPTO_w_unlock(CRYPTO_LOCK_RAND); 520 521 EVP_MD_CTX_cleanup(&m); 522 if (ok) 523 return (1); 524 else if (pseudo) 525 return 0; 526 else { 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 534static int ssleay_rand_nopseudo_bytes(unsigned char *buf, int num) 535{ 536 return ssleay_rand_bytes(buf, num, 0, 1); 537} 538 539/* 540 * pseudo-random bytes that are guaranteed to be unique but not unpredictable 541 */ 542static int ssleay_rand_pseudo_bytes(unsigned char *buf, int num) 543{ 544 return ssleay_rand_bytes(buf, num, 1, 1); 545} 546 547static int ssleay_rand_status(void) 548{ 549 CRYPTO_THREADID cur; 550 int ret; 551 int do_not_lock; 552 553 CRYPTO_THREADID_current(&cur); 554 /* 555 * check if we already have the lock (could happen if a RAND_poll() 556 * implementation calls RAND_status()) 557 */ 558 if (crypto_lock_rand) { 559 CRYPTO_r_lock(CRYPTO_LOCK_RAND2); 560 do_not_lock = !CRYPTO_THREADID_cmp(&locking_threadid, &cur); 561 CRYPTO_r_unlock(CRYPTO_LOCK_RAND2); 562 } else 563 do_not_lock = 0; 564 565 if (!do_not_lock) { 566 CRYPTO_w_lock(CRYPTO_LOCK_RAND); 567 568 /* 569 * prevent ssleay_rand_bytes() from trying to obtain the lock again 570 */ 571 CRYPTO_w_lock(CRYPTO_LOCK_RAND2); 572 CRYPTO_THREADID_cpy(&locking_threadid, &cur); 573 CRYPTO_w_unlock(CRYPTO_LOCK_RAND2); 574 crypto_lock_rand = 1; 575 } 576 577 if (!initialized) { 578 RAND_poll(); 579 initialized = 1; 580 } 581 582 ret = entropy >= ENTROPY_NEEDED; 583 584 if (!do_not_lock) { 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