1 /* 2 * util/random.c - thread safe random generator, which is reasonably secure. 3 * 4 * Copyright (c) 2007, NLnet Labs. All rights reserved. 5 * 6 * This software is open source. 7 * 8 * Redistribution and use in source and binary forms, with or without 9 * modification, are permitted provided that the following conditions 10 * are met: 11 * 12 * Redistributions of source code must retain the above copyright notice, 13 * this list of conditions and the following disclaimer. 14 * 15 * Redistributions in binary form must reproduce the above copyright notice, 16 * this list of conditions and the following disclaimer in the documentation 17 * and/or other materials provided with the distribution. 18 * 19 * Neither the name of the NLNET LABS nor the names of its contributors may 20 * be used to endorse or promote products derived from this software without 21 * specific prior written permission. 22 * 23 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 24 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 25 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 26 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE 27 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 28 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 29 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 30 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 31 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 32 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 33 * POSSIBILITY OF SUCH DAMAGE. 34 */ 35 36 /** 37 * \file 38 * Thread safe random functions. Similar to arc4random() with an explicit 39 * initialisation routine. 40 * 41 * The code in this file is based on arc4random from 42 * openssh-4.0p1/openbsd-compat/bsd-arc4random.c 43 * That code is also BSD licensed. Here is their statement: 44 * 45 * Copyright (c) 1996, David Mazieres <dm@uun.org> 46 * Copyright (c) 2008, Damien Miller <djm@openbsd.org> 47 * 48 * Permission to use, copy, modify, and distribute this software for any 49 * purpose with or without fee is hereby granted, provided that the above 50 * copyright notice and this permission notice appear in all copies. 51 * 52 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 53 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 54 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR 55 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 56 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 57 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF 58 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 59 */ 60 #include "config.h" 61 #include "util/random.h" 62 #include "util/log.h" 63 #include <openssl/rand.h> 64 #include <openssl/rc4.h> 65 #include <openssl/err.h> 66 67 /** 68 * Struct with per-thread random state. 69 * Keeps SSL types away from the header file. 70 */ 71 struct ub_randstate { 72 /** key used for arc4random generation */ 73 RC4_KEY rc4; 74 /** keeps track of key usage */ 75 int rc4_ready; 76 }; 77 78 /** Size of key to use */ 79 #define SEED_SIZE 20 80 81 /** 82 * Max random value. Similar to RAND_MAX, but more portable 83 * (mingw uses only 15 bits random). 84 */ 85 #define MAX_VALUE 0x7fffffff 86 87 /** Number of bytes to reseed after */ 88 #define REKEY_BYTES (1 << 24) 89 90 /* (re)setup system seed */ 91 void 92 ub_systemseed(unsigned int seed) 93 { 94 /* RAND_ is threadsafe, by the way */ 95 if(!RAND_status()) { 96 /* try to seed it */ 97 unsigned char buf[256]; 98 unsigned int v = seed; 99 size_t i; 100 for(i=0; i<256/sizeof(seed); i++) { 101 memmove(buf+i*sizeof(seed), &v, sizeof(seed)); 102 v = v*seed + (unsigned int)i; 103 } 104 RAND_seed(buf, 256); 105 if(!RAND_status()) { 106 log_err("Random generator has no entropy " 107 "(error %ld)", ERR_get_error()); 108 } else { 109 verbose(VERB_OPS, "openssl has no entropy, " 110 "seeding with time and pid"); 111 } 112 } 113 } 114 115 /** reseed random generator */ 116 static void 117 ub_arc4random_stir(struct ub_randstate* s, struct ub_randstate* from) 118 { 119 unsigned char rand_buf[SEED_SIZE]; 120 int i; 121 122 memset(&s->rc4, 0, sizeof(s->rc4)); 123 memset(rand_buf, 0xc, sizeof(rand_buf)); 124 if (from) { 125 for(i=0; i<SEED_SIZE; i++) 126 rand_buf[i] = (unsigned char)ub_random(from); 127 } else { 128 if(!RAND_status()) 129 ub_systemseed((unsigned)getpid()^(unsigned)time(NULL)); 130 if (RAND_bytes(rand_buf, (int)sizeof(rand_buf)) <= 0) { 131 /* very unlikely that this happens, since we seeded 132 * above, if it does; complain and keep going */ 133 log_err("Couldn't obtain random bytes (error %ld)", 134 ERR_get_error()); 135 s->rc4_ready = 256; 136 return; 137 } 138 } 139 RC4_set_key(&s->rc4, SEED_SIZE, rand_buf); 140 141 /* 142 * Discard early keystream, as per recommendations in: 143 * http://www.wisdom.weizmann.ac.il/~itsik/RC4/Papers/Rc4_ksa.ps 144 */ 145 for(i = 0; i <= 256; i += sizeof(rand_buf)) 146 RC4(&s->rc4, sizeof(rand_buf), rand_buf, rand_buf); 147 148 memset(rand_buf, 0, sizeof(rand_buf)); 149 150 s->rc4_ready = REKEY_BYTES; 151 } 152 153 struct ub_randstate* 154 ub_initstate(unsigned int seed, struct ub_randstate* from) 155 { 156 struct ub_randstate* s = (struct ub_randstate*)calloc(1, sizeof(*s)); 157 if(!s) { 158 log_err("malloc failure in random init"); 159 return NULL; 160 } 161 ub_systemseed(seed); 162 ub_arc4random_stir(s, from); 163 return s; 164 } 165 166 long int 167 ub_random(struct ub_randstate* s) 168 { 169 unsigned int r = 0; 170 if (s->rc4_ready <= 0) { 171 ub_arc4random_stir(s, NULL); 172 } 173 174 RC4(&s->rc4, sizeof(r), 175 (unsigned char *)&r, (unsigned char *)&r); 176 s->rc4_ready -= sizeof(r); 177 return (long int)((r) % (((unsigned)MAX_VALUE + 1))); 178 } 179 180 long int 181 ub_random_max(struct ub_randstate* state, long int x) 182 { 183 /* make sure we fetch in a range that is divisible by x. ignore 184 * values from d .. MAX_VALUE, instead draw a new number */ 185 long int d = MAX_VALUE - (MAX_VALUE % x); /* d is divisible by x */ 186 long int v = ub_random(state); 187 while(d <= v) 188 v = ub_random(state); 189 return (v % x); 190 } 191 192 void 193 ub_randfree(struct ub_randstate* s) 194 { 195 if(s) 196 free(s); 197 /* user app must do RAND_cleanup(); */ 198 } 199