random.c revision 249141
1351278Sdim/* 2351278Sdim * util/random.c - thread safe random generator, which is reasonably secure. 3351278Sdim * 4351278Sdim * Copyright (c) 2007, NLnet Labs. All rights reserved. 5351278Sdim * 6351278Sdim * This software is open source. 7351278Sdim * 8351278Sdim * Redistribution and use in source and binary forms, with or without 9351278Sdim * modification, are permitted provided that the following conditions 10351278Sdim * are met: 11351278Sdim * 12351278Sdim * Redistributions of source code must retain the above copyright notice, 13351278Sdim * this list of conditions and the following disclaimer. 14351278Sdim * 15351278Sdim * Redistributions in binary form must reproduce the above copyright notice, 16351278Sdim * this list of conditions and the following disclaimer in the documentation 17351278Sdim * and/or other materials provided with the distribution. 18351278Sdim * 19351278Sdim * Neither the name of the NLNET LABS nor the names of its contributors may 20351278Sdim * be used to endorse or promote products derived from this software without 21351278Sdim * specific prior written permission. 22351278Sdim * 23351278Sdim * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 24351278Sdim * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 25351278Sdim * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 26351278Sdim * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE 27351278Sdim * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 28351278Sdim * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 29351278Sdim * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 30351278Sdim * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 31351278Sdim * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 32351278Sdim * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 33351278Sdim * POSSIBILITY OF SUCH DAMAGE. 34351278Sdim */ 35351278Sdim 36351278Sdim/** 37351278Sdim * \file 38351278Sdim * Thread safe random functions. Similar to arc4random() with an explicit 39351278Sdim * initialisation routine. 40351278Sdim * 41351278Sdim * The code in this file is based on arc4random from 42351278Sdim * openssh-4.0p1/openbsd-compat/bsd-arc4random.c 43351278Sdim * That code is also BSD licensed. Here is their statement: 44351278Sdim * 45351278Sdim * Copyright (c) 1996, David Mazieres <dm@uun.org> 46351278Sdim * Copyright (c) 2008, Damien Miller <djm@openbsd.org> 47351278Sdim * 48351278Sdim * Permission to use, copy, modify, and distribute this software for any 49351278Sdim * purpose with or without fee is hereby granted, provided that the above 50351278Sdim * copyright notice and this permission notice appear in all copies. 51351278Sdim * 52351278Sdim * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 53351278Sdim * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 54351278Sdim * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR 55351278Sdim * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 56351278Sdim * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 57351278Sdim * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF 58351278Sdim * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 59351278Sdim */ 60351278Sdim#include "config.h" 61351278Sdim#include "util/random.h" 62351278Sdim#include "util/log.h" 63351278Sdim#ifdef HAVE_SSL 64351278Sdim#include <openssl/rand.h> 65351278Sdim#include <openssl/rc4.h> 66351278Sdim#include <openssl/err.h> 67351278Sdim#elif defined(HAVE_NSS) 68351278Sdim/* nspr4 */ 69351278Sdim#include "prerror.h" 70351278Sdim/* nss3 */ 71351278Sdim#include "secport.h" 72351278Sdim#include "pk11pub.h" 73351278Sdim#endif 74351278Sdim 75351278Sdim/** 76351278Sdim * Max random value. Similar to RAND_MAX, but more portable 77351278Sdim * (mingw uses only 15 bits random). 78351278Sdim */ 79351278Sdim#define MAX_VALUE 0x7fffffff 80351278Sdim 81351278Sdim#ifdef HAVE_SSL 82351278Sdim/** 83351278Sdim * Struct with per-thread random state. 84351278Sdim * Keeps SSL types away from the header file. 85351278Sdim */ 86351278Sdimstruct ub_randstate { 87351278Sdim /** key used for arc4random generation */ 88351278Sdim RC4_KEY rc4; 89351278Sdim /** keeps track of key usage */ 90351278Sdim int rc4_ready; 91351278Sdim}; 92351278Sdim 93351278Sdim/** Size of key to use (must be multiple of 8) */ 94351278Sdim#define SEED_SIZE 24 95351278Sdim 96351278Sdim/** Number of bytes to reseed after */ 97351278Sdim#define REKEY_BYTES (1 << 24) 98351278Sdim 99351278Sdim/* (re)setup system seed */ 100351278Sdimvoid 101351278Sdimub_systemseed(unsigned int seed) 102351278Sdim{ 103351278Sdim /* RAND_ is threadsafe, by the way */ 104351278Sdim if(!RAND_status()) { 105351278Sdim /* try to seed it */ 106351278Sdim unsigned char buf[256]; 107351278Sdim unsigned int v = seed; 108351278Sdim size_t i; 109351278Sdim for(i=0; i<256/sizeof(seed); i++) { 110351278Sdim memmove(buf+i*sizeof(seed), &v, sizeof(seed)); 111351278Sdim v = v*seed + (unsigned int)i; 112351278Sdim } 113351278Sdim RAND_seed(buf, 256); 114351278Sdim if(!RAND_status()) { 115351278Sdim log_err("Random generator has no entropy " 116351278Sdim "(error %ld)", ERR_get_error()); 117351278Sdim } else { 118351278Sdim verbose(VERB_OPS, "openssl has no entropy, " 119351278Sdim "seeding with time and pid"); 120351278Sdim } 121351278Sdim } 122351278Sdim} 123351278Sdim 124351278Sdim/** reseed random generator */ 125351278Sdimstatic void 126351278Sdimub_arc4random_stir(struct ub_randstate* s, struct ub_randstate* from) 127351278Sdim{ 128351278Sdim /* not as unsigned char, but longerint so that it is 129351278Sdim aligned properly on alignment sensitive platforms */ 130351278Sdim uint64_t rand_buf[SEED_SIZE/sizeof(uint64_t)]; 131351278Sdim int i; 132351278Sdim 133351278Sdim memset(&s->rc4, 0, sizeof(s->rc4)); 134351278Sdim memset(rand_buf, 0xc, sizeof(rand_buf)); 135351278Sdim if (from) { 136351278Sdim uint8_t* rbuf = (uint8_t*)rand_buf; 137351278Sdim for(i=0; i<SEED_SIZE; i++) 138351278Sdim rbuf[i] = (uint8_t)ub_random(from); 139351278Sdim } else { 140351278Sdim if(!RAND_status()) 141351278Sdim ub_systemseed((unsigned)getpid()^(unsigned)time(NULL)); 142351278Sdim if (RAND_bytes((unsigned char*)rand_buf, 143351278Sdim (int)sizeof(rand_buf)) <= 0) { 144351278Sdim /* very unlikely that this happens, since we seeded 145351278Sdim * above, if it does; complain and keep going */ 146351278Sdim log_err("Couldn't obtain random bytes (error %ld)", 147351278Sdim ERR_get_error()); 148351278Sdim s->rc4_ready = 256; 149351278Sdim return; 150351278Sdim } 151351278Sdim } 152351278Sdim#ifdef HAVE_FIPS_MODE 153351278Sdim if(FIPS_mode()) { 154351278Sdim /* RC4 is not allowed, get some trustworthy randomness */ 155351278Sdim /* double certainty here, this routine should not be 156351278Sdim * called in FIPS_mode */ 157351278Sdim memset(rand_buf, 0, sizeof(rand_buf)); 158351278Sdim s->rc4_ready = REKEY_BYTES; 159351278Sdim return; 160351278Sdim } 161351278Sdim#endif /* FIPS_MODE */ 162351278Sdim RC4_set_key(&s->rc4, SEED_SIZE, (unsigned char*)rand_buf); 163351278Sdim 164351278Sdim /* 165351278Sdim * Discard early keystream, as per recommendations in: 166351278Sdim * http://www.wisdom.weizmann.ac.il/~itsik/RC4/Papers/Rc4_ksa.ps 167351278Sdim */ 168351278Sdim for(i = 0; i <= 256; i += sizeof(rand_buf)) 169351278Sdim RC4(&s->rc4, sizeof(rand_buf), (unsigned char*)rand_buf, 170351278Sdim (unsigned char*)rand_buf); 171351278Sdim 172351278Sdim memset(rand_buf, 0, sizeof(rand_buf)); 173351278Sdim 174351278Sdim s->rc4_ready = REKEY_BYTES; 175351278Sdim} 176351278Sdim 177351278Sdimstruct ub_randstate* 178351278Sdimub_initstate(unsigned int seed, struct ub_randstate* from) 179351278Sdim{ 180351278Sdim struct ub_randstate* s = (struct ub_randstate*)calloc(1, sizeof(*s)); 181351278Sdim if(!s) { 182351278Sdim log_err("malloc failure in random init"); 183351278Sdim return NULL; 184351278Sdim } 185351278Sdim ub_systemseed(seed); 186351278Sdim#ifdef HAVE_FIPS_MODE 187351278Sdim if(!FIPS_mode()) 188351278Sdim#endif 189351278Sdim ub_arc4random_stir(s, from); 190351278Sdim return s; 191351278Sdim} 192351278Sdim 193351278Sdimlong int 194351278Sdimub_random(struct ub_randstate* s) 195351278Sdim{ 196351278Sdim unsigned int r = 0; 197351278Sdim#ifdef HAVE_FIPS_MODE 198351278Sdim if(FIPS_mode()) { 199351278Sdim /* RC4 is not allowed, get some trustworthy randomness */ 200351278Sdim /* we use pseudo bytes: it tries to return secure randomness 201351278Sdim * but returns 'something' if that fails. We need something 202351278Sdim * else if it fails, because we cannot block here */ 203351278Sdim if(RAND_pseudo_bytes((unsigned char*)&r, (int)sizeof(r)) 204351278Sdim == -1) { 205351278Sdim log_err("FIPSmode, no arc4random but RAND failed " 206351278Sdim "(error %ld)", ERR_get_error()); 207351278Sdim } 208351278Sdim return (long int)((r) % (((unsigned)MAX_VALUE + 1))); 209351278Sdim } 210351278Sdim#endif /* FIPS_MODE */ 211351278Sdim if (s->rc4_ready <= 0) { 212351278Sdim ub_arc4random_stir(s, NULL); 213351278Sdim } 214351278Sdim 215351278Sdim RC4(&s->rc4, sizeof(r), 216351278Sdim (unsigned char *)&r, (unsigned char *)&r); 217351278Sdim s->rc4_ready -= sizeof(r); 218351278Sdim return (long int)((r) % (((unsigned)MAX_VALUE + 1))); 219351278Sdim} 220351278Sdim 221351278Sdim#elif defined(HAVE_NSS) 222351278Sdim 223351278Sdim/* not much to remember for NSS since we use its pk11_random, placeholder */ 224351278Sdimstruct ub_randstate { 225351278Sdim int ready; 226351278Sdim}; 227351278Sdim 228351278Sdimvoid ub_systemseed(unsigned int ATTR_UNUSED(seed)) 229351278Sdim{ 230351278Sdim} 231351278Sdim 232351278Sdimstruct ub_randstate* ub_initstate(unsigned int ATTR_UNUSED(seed), 233351278Sdim struct ub_randstate* ATTR_UNUSED(from)) 234351278Sdim{ 235351278Sdim struct ub_randstate* s = (struct ub_randstate*)calloc(1, sizeof(*s)); 236351278Sdim if(!s) { 237351278Sdim log_err("malloc failure in random init"); 238351278Sdim return NULL; 239351278Sdim } 240351278Sdim return s; 241351278Sdim} 242351278Sdim 243351278Sdimlong int ub_random(struct ub_randstate* ATTR_UNUSED(state)) 244{ 245 long int x; 246 /* random 31 bit value. */ 247 SECStatus s = PK11_GenerateRandom((unsigned char*)&x, (int)sizeof(x)); 248 if(s != SECSuccess) { 249 log_err("PK11_GenerateRandom error: %s", 250 PORT_ErrorToString(PORT_GetError())); 251 } 252 return x & MAX_VALUE; 253} 254 255#endif /* HAVE_SSL or HAVE_NSS */ 256 257long int 258ub_random_max(struct ub_randstate* state, long int x) 259{ 260 /* make sure we fetch in a range that is divisible by x. ignore 261 * values from d .. MAX_VALUE, instead draw a new number */ 262 long int d = MAX_VALUE - (MAX_VALUE % x); /* d is divisible by x */ 263 long int v = ub_random(state); 264 while(d <= v) 265 v = ub_random(state); 266 return (v % x); 267} 268 269void 270ub_randfree(struct ub_randstate* s) 271{ 272 if(s) 273 free(s); 274 /* user app must do RAND_cleanup(); */ 275} 276