1/* Licensed to the Apache Software Foundation (ASF) under one or more 2 * contributor license agreements. See the NOTICE file distributed with 3 * this work for additional information regarding copyright ownership. 4 * The ASF licenses this file to You under the Apache License, Version 2.0 5 * (the "License"); you may not use this file except in compliance with 6 * the License. You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16/* 17 * See the paper "On Randomness" by Ben Laurie for an explanation of this PRNG. 18 * http://www.apache-ssl.org/randomness.pdf 19 * XXX: Is there a formal proof of this PRNG? Couldn't we use the more popular 20 * Mersenne Twister PRNG (and BSD licensed)? 21 */ 22 23#include "apr.h" 24#include "apr_pools.h" 25#include "apr_random.h" 26#include "apr_thread_proc.h" 27#include <assert.h> 28 29#ifdef min 30#undef min 31#endif 32#define min(a,b) ((a) < (b) ? (a) : (b)) 33 34#define APR_RANDOM_DEFAULT_POOLS 32 35#define APR_RANDOM_DEFAULT_REHASH_SIZE 1024 36#define APR_RANDOM_DEFAULT_RESEED_SIZE 32 37#define APR_RANDOM_DEFAULT_HASH_SECRET_SIZE 32 38#define APR_RANDOM_DEFAULT_G_FOR_INSECURE 32 39#define APR_RANDOM_DEFAULT_G_FOR_SECURE 320 40 41typedef struct apr_random_pool_t { 42 unsigned char *pool; 43 unsigned int bytes; 44 unsigned int pool_size; 45} apr_random_pool_t; 46 47#define hash_init(h) (h)->init(h) 48#define hash_add(h,b,n) (h)->add(h,b,n) 49#define hash_finish(h,r) (h)->finish(h,r) 50 51#define hash(h,r,b,n) hash_init(h),hash_add(h,b,n),hash_finish(h,r) 52 53#define crypt_setkey(c,k) (c)->set_key((c)->data,k) 54#define crypt_crypt(c,out,in) (c)->crypt((c)->date,out,in) 55 56struct apr_random_t { 57 apr_pool_t *apr_pool; 58 apr_crypto_hash_t *pool_hash; 59 unsigned int npools; 60 apr_random_pool_t *pools; 61 unsigned int next_pool; 62 unsigned int generation; 63 apr_size_t rehash_size; 64 apr_size_t reseed_size; 65 apr_crypto_hash_t *key_hash; 66#define K_size(g) ((g)->key_hash->size) 67 apr_crypto_hash_t *prng_hash; 68#define B_size(g) ((g)->prng_hash->size) 69 70 unsigned char *H; 71 unsigned char *H_waiting; 72#define H_size(g) (B_size(g)+K_size(g)) 73#define H_current(g) (((g)->insecure_started && !(g)->secure_started) \ 74 ? (g)->H_waiting : (g)->H) 75 76 unsigned char *randomness; 77 apr_size_t random_bytes; 78 unsigned int g_for_insecure; 79 unsigned int g_for_secure; 80 unsigned int secure_base; 81 unsigned int insecure_started:1; 82 unsigned int secure_started:1; 83 84 apr_random_t *next; 85}; 86 87static apr_random_t *all_random; 88 89static apr_status_t random_cleanup(void *data) 90{ 91 apr_random_t *remove_this = data, 92 *cur = all_random, 93 **prev_ptr = &all_random; 94 while (cur) { 95 if (cur == remove_this) { 96 *prev_ptr = cur->next; 97 break; 98 } 99 prev_ptr = &cur->next; 100 cur = cur->next; 101 } 102 return APR_SUCCESS; 103} 104 105 106APR_DECLARE(void) apr_random_init(apr_random_t *g,apr_pool_t *p, 107 apr_crypto_hash_t *pool_hash, 108 apr_crypto_hash_t *key_hash, 109 apr_crypto_hash_t *prng_hash) 110{ 111 unsigned int n; 112 113 g->apr_pool = p; 114 115 g->pool_hash = pool_hash; 116 g->key_hash = key_hash; 117 g->prng_hash = prng_hash; 118 119 g->npools = APR_RANDOM_DEFAULT_POOLS; 120 g->pools = apr_palloc(p,g->npools*sizeof *g->pools); 121 for (n = 0; n < g->npools; ++n) { 122 g->pools[n].bytes = g->pools[n].pool_size = 0; 123 g->pools[n].pool = NULL; 124 } 125 g->next_pool = 0; 126 127 g->generation = 0; 128 129 g->rehash_size = APR_RANDOM_DEFAULT_REHASH_SIZE; 130 /* Ensure that the rehash size is twice the size of the pool hasher */ 131 g->rehash_size = ((g->rehash_size+2*g->pool_hash->size-1)/g->pool_hash->size 132 /2)*g->pool_hash->size*2; 133 g->reseed_size = APR_RANDOM_DEFAULT_RESEED_SIZE; 134 135 g->H = apr_pcalloc(p,H_size(g)); 136 g->H_waiting = apr_pcalloc(p,H_size(g)); 137 138 g->randomness = apr_palloc(p,B_size(g)); 139 g->random_bytes = 0; 140 141 g->g_for_insecure = APR_RANDOM_DEFAULT_G_FOR_INSECURE; 142 g->secure_base = 0; 143 g->g_for_secure = APR_RANDOM_DEFAULT_G_FOR_SECURE; 144 g->secure_started = g->insecure_started = 0; 145 146 g->next = all_random; 147 all_random = g; 148 apr_pool_cleanup_register(p, g, random_cleanup, apr_pool_cleanup_null); 149} 150 151static void mix_pid(apr_random_t *g,unsigned char *H,pid_t pid) 152{ 153 hash_init(g->key_hash); 154 hash_add(g->key_hash,H,H_size(g)); 155 hash_add(g->key_hash,&pid,sizeof pid); 156 hash_finish(g->key_hash,H); 157} 158 159static void mixer(apr_random_t *g,pid_t pid) 160{ 161 unsigned char *H = H_current(g); 162 163 /* mix the PID into the current H */ 164 mix_pid(g,H,pid); 165 /* if we are in waiting, then also mix into main H */ 166 if (H != g->H) 167 mix_pid(g,g->H,pid); 168 /* change order of pool mixing for good measure - note that going 169 backwards is much better than going forwards */ 170 --g->generation; 171 /* blow away any lingering randomness */ 172 g->random_bytes = 0; 173} 174 175APR_DECLARE(void) apr_random_after_fork(apr_proc_t *proc) 176{ 177 apr_random_t *r; 178 179 for (r = all_random; r; r = r->next) 180 /* 181 * XXX Note: the pid does not provide sufficient entropy to 182 * actually call this secure. See Ben's paper referenced at 183 * the top of this file. 184 */ 185 mixer(r,proc->pid); 186} 187 188APR_DECLARE(apr_random_t *) apr_random_standard_new(apr_pool_t *p) 189{ 190 apr_random_t *r = apr_palloc(p,sizeof *r); 191 192 apr_random_init(r,p,apr_crypto_sha256_new(p),apr_crypto_sha256_new(p), 193 apr_crypto_sha256_new(p)); 194 return r; 195} 196 197static void rekey(apr_random_t *g) 198{ 199 unsigned int n; 200 unsigned char *H = H_current(g); 201 202 hash_init(g->key_hash); 203 hash_add(g->key_hash,H,H_size(g)); 204 for (n = 0 ; n < g->npools && (n == 0 || g->generation&(1 << (n-1))) 205 ; ++n) { 206 hash_add(g->key_hash,g->pools[n].pool,g->pools[n].bytes); 207 g->pools[n].bytes = 0; 208 } 209 hash_finish(g->key_hash,H+B_size(g)); 210 211 ++g->generation; 212 if (!g->insecure_started && g->generation > g->g_for_insecure) { 213 g->insecure_started = 1; 214 if (!g->secure_started) { 215 memcpy(g->H_waiting,g->H,H_size(g)); 216 g->secure_base = g->generation; 217 } 218 } 219 220 if (!g->secure_started && g->generation > g->secure_base+g->g_for_secure) { 221 g->secure_started = 1; 222 memcpy(g->H,g->H_waiting,H_size(g)); 223 } 224} 225 226APR_DECLARE(void) apr_random_add_entropy(apr_random_t *g,const void *entropy_, 227 apr_size_t bytes) 228{ 229 unsigned int n; 230 const unsigned char *entropy = entropy_; 231 232 for (n = 0; n < bytes; ++n) { 233 apr_random_pool_t *p = &g->pools[g->next_pool]; 234 235 if (++g->next_pool == g->npools) 236 g->next_pool = 0; 237 238 if (p->pool_size < p->bytes+1) { 239 unsigned char *np = apr_palloc(g->apr_pool,(p->bytes+1)*2); 240 241 memcpy(np,p->pool,p->bytes); 242 p->pool = np; 243 p->pool_size = (p->bytes+1)*2; 244 } 245 p->pool[p->bytes++] = entropy[n]; 246 247 if (p->bytes == g->rehash_size) { 248 apr_size_t r; 249 250 for (r = 0; r < p->bytes/2; r+=g->pool_hash->size) 251 hash(g->pool_hash,p->pool+r,p->pool+r*2,g->pool_hash->size*2); 252 p->bytes/=2; 253 } 254 assert(p->bytes < g->rehash_size); 255 } 256 257 if (g->pools[0].bytes >= g->reseed_size) 258 rekey(g); 259} 260 261/* This will give g->B_size bytes of randomness */ 262static void apr_random_block(apr_random_t *g,unsigned char *random) 263{ 264 /* FIXME: in principle, these are different hashes */ 265 hash(g->prng_hash,g->H,g->H,H_size(g)); 266 hash(g->prng_hash,random,g->H,B_size(g)); 267} 268 269static void apr_random_bytes(apr_random_t *g,unsigned char *random, 270 apr_size_t bytes) 271{ 272 apr_size_t n; 273 274 for (n = 0; n < bytes; ) { 275 apr_size_t l; 276 277 if (g->random_bytes == 0) { 278 apr_random_block(g,g->randomness); 279 g->random_bytes = B_size(g); 280 } 281 l = min(bytes-n,g->random_bytes); 282 memcpy(&random[n],g->randomness+B_size(g)-g->random_bytes,l); 283 g->random_bytes-=l; 284 n+=l; 285 } 286} 287 288APR_DECLARE(apr_status_t) apr_random_secure_bytes(apr_random_t *g, 289 void *random, 290 apr_size_t bytes) 291{ 292 if (!g->secure_started) 293 return APR_ENOTENOUGHENTROPY; 294 apr_random_bytes(g,random,bytes); 295 return APR_SUCCESS; 296} 297 298APR_DECLARE(apr_status_t) apr_random_insecure_bytes(apr_random_t *g, 299 void *random, 300 apr_size_t bytes) 301{ 302 if (!g->insecure_started) 303 return APR_ENOTENOUGHENTROPY; 304 apr_random_bytes(g,random,bytes); 305 return APR_SUCCESS; 306} 307 308APR_DECLARE(void) apr_random_barrier(apr_random_t *g) 309{ 310 g->secure_started = 0; 311 g->secure_base = g->generation; 312} 313 314APR_DECLARE(apr_status_t) apr_random_secure_ready(apr_random_t *r) 315{ 316 if (!r->secure_started) 317 return APR_ENOTENOUGHENTROPY; 318 return APR_SUCCESS; 319} 320 321APR_DECLARE(apr_status_t) apr_random_insecure_ready(apr_random_t *r) 322{ 323 if (!r->insecure_started) 324 return APR_ENOTENOUGHENTROPY; 325 return APR_SUCCESS; 326} 327