1251875Speter/* Licensed to the Apache Software Foundation (ASF) under one or more 2251875Speter * contributor license agreements. See the NOTICE file distributed with 3251875Speter * this work for additional information regarding copyright ownership. 4251875Speter * The ASF licenses this file to You under the Apache License, Version 2.0 5251875Speter * (the "License"); you may not use this file except in compliance with 6251875Speter * the License. You may obtain a copy of the License at 7251875Speter * 8251875Speter * http://www.apache.org/licenses/LICENSE-2.0 9251875Speter * 10251875Speter * Unless required by applicable law or agreed to in writing, software 11251875Speter * distributed under the License is distributed on an "AS IS" BASIS, 12251875Speter * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13251875Speter * See the License for the specific language governing permissions and 14251875Speter * limitations under the License. 15251875Speter */ 16251875Speter/* 17251875Speter * See the paper "On Randomness" by Ben Laurie for an explanation of this PRNG. 18251875Speter * http://www.apache-ssl.org/randomness.pdf 19251875Speter * XXX: Is there a formal proof of this PRNG? Couldn't we use the more popular 20251875Speter * Mersenne Twister PRNG (and BSD licensed)? 21251875Speter */ 22251875Speter 23251875Speter#include "apr.h" 24251875Speter#include "apr_pools.h" 25251875Speter#include "apr_random.h" 26251875Speter#include "apr_thread_proc.h" 27251875Speter#include <assert.h> 28251875Speter 29251875Speter#ifdef min 30251875Speter#undef min 31251875Speter#endif 32251875Speter#define min(a,b) ((a) < (b) ? (a) : (b)) 33251875Speter 34251875Speter#define APR_RANDOM_DEFAULT_POOLS 32 35251875Speter#define APR_RANDOM_DEFAULT_REHASH_SIZE 1024 36251875Speter#define APR_RANDOM_DEFAULT_RESEED_SIZE 32 37251875Speter#define APR_RANDOM_DEFAULT_HASH_SECRET_SIZE 32 38251875Speter#define APR_RANDOM_DEFAULT_G_FOR_INSECURE 32 39251875Speter#define APR_RANDOM_DEFAULT_G_FOR_SECURE 320 40251875Speter 41251875Spetertypedef struct apr_random_pool_t { 42251875Speter unsigned char *pool; 43251875Speter unsigned int bytes; 44251875Speter unsigned int pool_size; 45251875Speter} apr_random_pool_t; 46251875Speter 47251875Speter#define hash_init(h) (h)->init(h) 48251875Speter#define hash_add(h,b,n) (h)->add(h,b,n) 49251875Speter#define hash_finish(h,r) (h)->finish(h,r) 50251875Speter 51251875Speter#define hash(h,r,b,n) hash_init(h),hash_add(h,b,n),hash_finish(h,r) 52251875Speter 53251875Speter#define crypt_setkey(c,k) (c)->set_key((c)->data,k) 54251875Speter#define crypt_crypt(c,out,in) (c)->crypt((c)->date,out,in) 55251875Speter 56251875Speterstruct apr_random_t { 57251875Speter apr_pool_t *apr_pool; 58251875Speter apr_crypto_hash_t *pool_hash; 59251875Speter unsigned int npools; 60251875Speter apr_random_pool_t *pools; 61251875Speter unsigned int next_pool; 62251875Speter unsigned int generation; 63251875Speter apr_size_t rehash_size; 64251875Speter apr_size_t reseed_size; 65251875Speter apr_crypto_hash_t *key_hash; 66251875Speter#define K_size(g) ((g)->key_hash->size) 67251875Speter apr_crypto_hash_t *prng_hash; 68251875Speter#define B_size(g) ((g)->prng_hash->size) 69251875Speter 70251875Speter unsigned char *H; 71251875Speter unsigned char *H_waiting; 72251875Speter#define H_size(g) (B_size(g)+K_size(g)) 73251875Speter#define H_current(g) (((g)->insecure_started && !(g)->secure_started) \ 74251875Speter ? (g)->H_waiting : (g)->H) 75251875Speter 76251875Speter unsigned char *randomness; 77251875Speter apr_size_t random_bytes; 78251875Speter unsigned int g_for_insecure; 79251875Speter unsigned int g_for_secure; 80251875Speter unsigned int secure_base; 81251875Speter unsigned int insecure_started:1; 82251875Speter unsigned int secure_started:1; 83251875Speter 84251875Speter apr_random_t *next; 85251875Speter}; 86251875Speter 87251875Speterstatic apr_random_t *all_random; 88251875Speter 89251875Speterstatic apr_status_t random_cleanup(void *data) 90251875Speter{ 91251875Speter apr_random_t *remove_this = data, 92251875Speter *cur = all_random, 93251875Speter **prev_ptr = &all_random; 94251875Speter while (cur) { 95251875Speter if (cur == remove_this) { 96251875Speter *prev_ptr = cur->next; 97251875Speter break; 98251875Speter } 99251875Speter prev_ptr = &cur->next; 100251875Speter cur = cur->next; 101251875Speter } 102251875Speter return APR_SUCCESS; 103251875Speter} 104251875Speter 105251875Speter 106251875SpeterAPR_DECLARE(void) apr_random_init(apr_random_t *g,apr_pool_t *p, 107251875Speter apr_crypto_hash_t *pool_hash, 108251875Speter apr_crypto_hash_t *key_hash, 109251875Speter apr_crypto_hash_t *prng_hash) 110251875Speter{ 111251875Speter unsigned int n; 112251875Speter 113251875Speter g->apr_pool = p; 114251875Speter 115251875Speter g->pool_hash = pool_hash; 116251875Speter g->key_hash = key_hash; 117251875Speter g->prng_hash = prng_hash; 118251875Speter 119251875Speter g->npools = APR_RANDOM_DEFAULT_POOLS; 120251875Speter g->pools = apr_palloc(p,g->npools*sizeof *g->pools); 121251875Speter for (n = 0; n < g->npools; ++n) { 122251875Speter g->pools[n].bytes = g->pools[n].pool_size = 0; 123251875Speter g->pools[n].pool = NULL; 124251875Speter } 125251875Speter g->next_pool = 0; 126251875Speter 127251875Speter g->generation = 0; 128251875Speter 129251875Speter g->rehash_size = APR_RANDOM_DEFAULT_REHASH_SIZE; 130251875Speter /* Ensure that the rehash size is twice the size of the pool hasher */ 131251875Speter g->rehash_size = ((g->rehash_size+2*g->pool_hash->size-1)/g->pool_hash->size 132251875Speter /2)*g->pool_hash->size*2; 133251875Speter g->reseed_size = APR_RANDOM_DEFAULT_RESEED_SIZE; 134251875Speter 135251875Speter g->H = apr_pcalloc(p,H_size(g)); 136251875Speter g->H_waiting = apr_pcalloc(p,H_size(g)); 137251875Speter 138251875Speter g->randomness = apr_palloc(p,B_size(g)); 139251875Speter g->random_bytes = 0; 140251875Speter 141251875Speter g->g_for_insecure = APR_RANDOM_DEFAULT_G_FOR_INSECURE; 142251875Speter g->secure_base = 0; 143251875Speter g->g_for_secure = APR_RANDOM_DEFAULT_G_FOR_SECURE; 144251875Speter g->secure_started = g->insecure_started = 0; 145251875Speter 146251875Speter g->next = all_random; 147251875Speter all_random = g; 148251875Speter apr_pool_cleanup_register(p, g, random_cleanup, apr_pool_cleanup_null); 149251875Speter} 150251875Speter 151251875Speterstatic void mix_pid(apr_random_t *g,unsigned char *H,pid_t pid) 152251875Speter{ 153251875Speter hash_init(g->key_hash); 154251875Speter hash_add(g->key_hash,H,H_size(g)); 155251875Speter hash_add(g->key_hash,&pid,sizeof pid); 156251875Speter hash_finish(g->key_hash,H); 157251875Speter} 158251875Speter 159251875Speterstatic void mixer(apr_random_t *g,pid_t pid) 160251875Speter{ 161251875Speter unsigned char *H = H_current(g); 162251875Speter 163251875Speter /* mix the PID into the current H */ 164251875Speter mix_pid(g,H,pid); 165251875Speter /* if we are in waiting, then also mix into main H */ 166251875Speter if (H != g->H) 167251875Speter mix_pid(g,g->H,pid); 168251875Speter /* change order of pool mixing for good measure - note that going 169251875Speter backwards is much better than going forwards */ 170251875Speter --g->generation; 171251875Speter /* blow away any lingering randomness */ 172251875Speter g->random_bytes = 0; 173251875Speter} 174251875Speter 175251875SpeterAPR_DECLARE(void) apr_random_after_fork(apr_proc_t *proc) 176251875Speter{ 177251875Speter apr_random_t *r; 178251875Speter 179251875Speter for (r = all_random; r; r = r->next) 180251875Speter /* 181251875Speter * XXX Note: the pid does not provide sufficient entropy to 182251875Speter * actually call this secure. See Ben's paper referenced at 183251875Speter * the top of this file. 184251875Speter */ 185251875Speter mixer(r,proc->pid); 186251875Speter} 187251875Speter 188251875SpeterAPR_DECLARE(apr_random_t *) apr_random_standard_new(apr_pool_t *p) 189251875Speter{ 190251875Speter apr_random_t *r = apr_palloc(p,sizeof *r); 191251875Speter 192251875Speter apr_random_init(r,p,apr_crypto_sha256_new(p),apr_crypto_sha256_new(p), 193251875Speter apr_crypto_sha256_new(p)); 194251875Speter return r; 195251875Speter} 196251875Speter 197251875Speterstatic void rekey(apr_random_t *g) 198251875Speter{ 199251875Speter unsigned int n; 200251875Speter unsigned char *H = H_current(g); 201251875Speter 202251875Speter hash_init(g->key_hash); 203251875Speter hash_add(g->key_hash,H,H_size(g)); 204251875Speter for (n = 0 ; n < g->npools && (n == 0 || g->generation&(1 << (n-1))) 205251875Speter ; ++n) { 206251875Speter hash_add(g->key_hash,g->pools[n].pool,g->pools[n].bytes); 207251875Speter g->pools[n].bytes = 0; 208251875Speter } 209251875Speter hash_finish(g->key_hash,H+B_size(g)); 210251875Speter 211251875Speter ++g->generation; 212251875Speter if (!g->insecure_started && g->generation > g->g_for_insecure) { 213251875Speter g->insecure_started = 1; 214251875Speter if (!g->secure_started) { 215251875Speter memcpy(g->H_waiting,g->H,H_size(g)); 216251875Speter g->secure_base = g->generation; 217251875Speter } 218251875Speter } 219251875Speter 220251875Speter if (!g->secure_started && g->generation > g->secure_base+g->g_for_secure) { 221251875Speter g->secure_started = 1; 222251875Speter memcpy(g->H,g->H_waiting,H_size(g)); 223251875Speter } 224251875Speter} 225251875Speter 226251875SpeterAPR_DECLARE(void) apr_random_add_entropy(apr_random_t *g,const void *entropy_, 227251875Speter apr_size_t bytes) 228251875Speter{ 229251875Speter unsigned int n; 230251875Speter const unsigned char *entropy = entropy_; 231251875Speter 232251875Speter for (n = 0; n < bytes; ++n) { 233251875Speter apr_random_pool_t *p = &g->pools[g->next_pool]; 234251875Speter 235251875Speter if (++g->next_pool == g->npools) 236251875Speter g->next_pool = 0; 237251875Speter 238251875Speter if (p->pool_size < p->bytes+1) { 239251875Speter unsigned char *np = apr_palloc(g->apr_pool,(p->bytes+1)*2); 240251875Speter 241251875Speter memcpy(np,p->pool,p->bytes); 242251875Speter p->pool = np; 243251875Speter p->pool_size = (p->bytes+1)*2; 244251875Speter } 245251875Speter p->pool[p->bytes++] = entropy[n]; 246251875Speter 247251875Speter if (p->bytes == g->rehash_size) { 248251875Speter apr_size_t r; 249251875Speter 250251875Speter for (r = 0; r < p->bytes/2; r+=g->pool_hash->size) 251251875Speter hash(g->pool_hash,p->pool+r,p->pool+r*2,g->pool_hash->size*2); 252251875Speter p->bytes/=2; 253251875Speter } 254251875Speter assert(p->bytes < g->rehash_size); 255251875Speter } 256251875Speter 257251875Speter if (g->pools[0].bytes >= g->reseed_size) 258251875Speter rekey(g); 259251875Speter} 260251875Speter 261251875Speter/* This will give g->B_size bytes of randomness */ 262251875Speterstatic void apr_random_block(apr_random_t *g,unsigned char *random) 263251875Speter{ 264251875Speter /* FIXME: in principle, these are different hashes */ 265251875Speter hash(g->prng_hash,g->H,g->H,H_size(g)); 266251875Speter hash(g->prng_hash,random,g->H,B_size(g)); 267251875Speter} 268251875Speter 269251875Speterstatic void apr_random_bytes(apr_random_t *g,unsigned char *random, 270251875Speter apr_size_t bytes) 271251875Speter{ 272251875Speter apr_size_t n; 273251875Speter 274251875Speter for (n = 0; n < bytes; ) { 275251875Speter apr_size_t l; 276251875Speter 277251875Speter if (g->random_bytes == 0) { 278251875Speter apr_random_block(g,g->randomness); 279251875Speter g->random_bytes = B_size(g); 280251875Speter } 281251875Speter l = min(bytes-n,g->random_bytes); 282251875Speter memcpy(&random[n],g->randomness+B_size(g)-g->random_bytes,l); 283251875Speter g->random_bytes-=l; 284251875Speter n+=l; 285251875Speter } 286251875Speter} 287251875Speter 288251875SpeterAPR_DECLARE(apr_status_t) apr_random_secure_bytes(apr_random_t *g, 289251875Speter void *random, 290251875Speter apr_size_t bytes) 291251875Speter{ 292251875Speter if (!g->secure_started) 293251875Speter return APR_ENOTENOUGHENTROPY; 294251875Speter apr_random_bytes(g,random,bytes); 295251875Speter return APR_SUCCESS; 296251875Speter} 297251875Speter 298251875SpeterAPR_DECLARE(apr_status_t) apr_random_insecure_bytes(apr_random_t *g, 299251875Speter void *random, 300251875Speter apr_size_t bytes) 301251875Speter{ 302251875Speter if (!g->insecure_started) 303251875Speter return APR_ENOTENOUGHENTROPY; 304251875Speter apr_random_bytes(g,random,bytes); 305251875Speter return APR_SUCCESS; 306251875Speter} 307251875Speter 308251875SpeterAPR_DECLARE(void) apr_random_barrier(apr_random_t *g) 309251875Speter{ 310251875Speter g->secure_started = 0; 311251875Speter g->secure_base = g->generation; 312251875Speter} 313251875Speter 314251875SpeterAPR_DECLARE(apr_status_t) apr_random_secure_ready(apr_random_t *r) 315251875Speter{ 316251875Speter if (!r->secure_started) 317251875Speter return APR_ENOTENOUGHENTROPY; 318251875Speter return APR_SUCCESS; 319251875Speter} 320251875Speter 321251875SpeterAPR_DECLARE(apr_status_t) apr_random_insecure_ready(apr_random_t *r) 322251875Speter{ 323251875Speter if (!r->insecure_started) 324251875Speter return APR_ENOTENOUGHENTROPY; 325251875Speter return APR_SUCCESS; 326251875Speter} 327