/src/httpd/srclib/apr/random/unix/apr_random.c
Line | Count | Source (jump to first uncovered line) |
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 | 0 | #define min(a,b) ((a) < (b) ? (a) : (b)) |
33 | | |
34 | 0 | #define APR_RANDOM_DEFAULT_POOLS 32 |
35 | 0 | #define APR_RANDOM_DEFAULT_REHASH_SIZE 1024 |
36 | 0 | #define APR_RANDOM_DEFAULT_RESEED_SIZE 32 |
37 | | #define APR_RANDOM_DEFAULT_HASH_SECRET_SIZE 32 |
38 | 0 | #define APR_RANDOM_DEFAULT_G_FOR_INSECURE 32 |
39 | 0 | #define APR_RANDOM_DEFAULT_G_FOR_SECURE 320 |
40 | | |
41 | | typedef 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 | 0 | #define hash_init(h) (h)->init(h) |
48 | 0 | #define hash_add(h,b,n) (h)->add(h,b,n) |
49 | 0 | #define hash_finish(h,r) (h)->finish(h,r) |
50 | | |
51 | 0 | #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 | | |
56 | | struct 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 | 0 | #define K_size(g) ((g)->key_hash->size) |
67 | | apr_crypto_hash_t *prng_hash; |
68 | 0 | #define B_size(g) ((g)->prng_hash->size) |
69 | | |
70 | | unsigned char *H; |
71 | | unsigned char *H_waiting; |
72 | 0 | #define H_size(g) (B_size(g)+K_size(g)) |
73 | 0 | #define H_current(g) (((g)->insecure_started && !(g)->secure_started) \ |
74 | 0 | ? (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 | | |
87 | | static apr_random_t *all_random; |
88 | | |
89 | | static apr_status_t random_cleanup(void *data) |
90 | 0 | { |
91 | 0 | apr_random_t *remove_this = data, |
92 | 0 | *cur = all_random, |
93 | 0 | **prev_ptr = &all_random; |
94 | 0 | while (cur) { |
95 | 0 | if (cur == remove_this) { |
96 | 0 | *prev_ptr = cur->next; |
97 | 0 | break; |
98 | 0 | } |
99 | 0 | prev_ptr = &cur->next; |
100 | 0 | cur = cur->next; |
101 | 0 | } |
102 | 0 | return APR_SUCCESS; |
103 | 0 | } |
104 | | |
105 | | |
106 | | APR_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 | 0 | { |
111 | 0 | unsigned int n; |
112 | |
|
113 | 0 | g->apr_pool = p; |
114 | |
|
115 | 0 | g->pool_hash = pool_hash; |
116 | 0 | g->key_hash = key_hash; |
117 | 0 | g->prng_hash = prng_hash; |
118 | |
|
119 | 0 | g->npools = APR_RANDOM_DEFAULT_POOLS; |
120 | 0 | g->pools = apr_palloc(p,g->npools*sizeof *g->pools); |
121 | 0 | for (n = 0; n < g->npools; ++n) { |
122 | 0 | g->pools[n].bytes = g->pools[n].pool_size = 0; |
123 | 0 | g->pools[n].pool = NULL; |
124 | 0 | } |
125 | 0 | g->next_pool = 0; |
126 | |
|
127 | 0 | g->generation = 0; |
128 | |
|
129 | 0 | g->rehash_size = APR_RANDOM_DEFAULT_REHASH_SIZE; |
130 | | /* Ensure that the rehash size is twice the size of the pool hasher */ |
131 | 0 | g->rehash_size = ((g->rehash_size+2*g->pool_hash->size-1)/g->pool_hash->size |
132 | 0 | /2)*g->pool_hash->size*2; |
133 | 0 | g->reseed_size = APR_RANDOM_DEFAULT_RESEED_SIZE; |
134 | |
|
135 | 0 | g->H = apr_pcalloc(p,H_size(g)); |
136 | 0 | g->H_waiting = apr_pcalloc(p,H_size(g)); |
137 | |
|
138 | 0 | g->randomness = apr_palloc(p,B_size(g)); |
139 | 0 | g->random_bytes = 0; |
140 | |
|
141 | 0 | g->g_for_insecure = APR_RANDOM_DEFAULT_G_FOR_INSECURE; |
142 | 0 | g->secure_base = 0; |
143 | 0 | g->g_for_secure = APR_RANDOM_DEFAULT_G_FOR_SECURE; |
144 | 0 | g->secure_started = g->insecure_started = 0; |
145 | |
|
146 | 0 | g->next = all_random; |
147 | 0 | all_random = g; |
148 | 0 | apr_pool_cleanup_register(p, g, random_cleanup, apr_pool_cleanup_null); |
149 | 0 | } |
150 | | |
151 | | static void mix_pid(apr_random_t *g,unsigned char *H,pid_t pid) |
152 | 0 | { |
153 | 0 | hash_init(g->key_hash); |
154 | 0 | hash_add(g->key_hash,H,H_size(g)); |
155 | 0 | hash_add(g->key_hash,&pid,sizeof pid); |
156 | 0 | hash_finish(g->key_hash,H); |
157 | 0 | } |
158 | | |
159 | | static void mixer(apr_random_t *g,pid_t pid) |
160 | 0 | { |
161 | 0 | unsigned char *H = H_current(g); |
162 | | |
163 | | /* mix the PID into the current H */ |
164 | 0 | mix_pid(g,H,pid); |
165 | | /* if we are in waiting, then also mix into main H */ |
166 | 0 | if (H != g->H) |
167 | 0 | 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 | 0 | --g->generation; |
171 | | /* blow away any lingering randomness */ |
172 | 0 | g->random_bytes = 0; |
173 | 0 | } |
174 | | |
175 | | APR_DECLARE(void) apr_random_after_fork(apr_proc_t *proc) |
176 | 0 | { |
177 | 0 | apr_random_t *r; |
178 | |
|
179 | 0 | 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 | 0 | mixer(r,proc->pid); |
186 | 0 | } |
187 | | |
188 | | APR_DECLARE(apr_random_t *) apr_random_standard_new(apr_pool_t *p) |
189 | 0 | { |
190 | 0 | apr_random_t *r = apr_palloc(p,sizeof *r); |
191 | |
|
192 | 0 | apr_random_init(r,p,apr_crypto_sha256_new(p),apr_crypto_sha256_new(p), |
193 | 0 | apr_crypto_sha256_new(p)); |
194 | 0 | return r; |
195 | 0 | } |
196 | | |
197 | | static void rekey(apr_random_t *g) |
198 | 0 | { |
199 | 0 | unsigned int n; |
200 | 0 | unsigned char *H = H_current(g); |
201 | |
|
202 | 0 | hash_init(g->key_hash); |
203 | 0 | hash_add(g->key_hash,H,H_size(g)); |
204 | 0 | for (n = 0 ; n < g->npools && (n == 0 || g->generation&(1 << (n-1))) |
205 | 0 | ; ++n) { |
206 | 0 | hash_add(g->key_hash,g->pools[n].pool,g->pools[n].bytes); |
207 | 0 | g->pools[n].bytes = 0; |
208 | 0 | } |
209 | 0 | hash_finish(g->key_hash,H+B_size(g)); |
210 | |
|
211 | 0 | ++g->generation; |
212 | 0 | if (!g->insecure_started && g->generation > g->g_for_insecure) { |
213 | 0 | g->insecure_started = 1; |
214 | 0 | if (!g->secure_started) { |
215 | 0 | memcpy(g->H_waiting,g->H,H_size(g)); |
216 | 0 | g->secure_base = g->generation; |
217 | 0 | } |
218 | 0 | } |
219 | |
|
220 | 0 | if (!g->secure_started && g->generation > g->secure_base+g->g_for_secure) { |
221 | 0 | g->secure_started = 1; |
222 | 0 | memcpy(g->H,g->H_waiting,H_size(g)); |
223 | 0 | } |
224 | 0 | } |
225 | | |
226 | | APR_DECLARE(void) apr_random_add_entropy(apr_random_t *g,const void *entropy_, |
227 | | apr_size_t bytes) |
228 | 0 | { |
229 | 0 | unsigned int n; |
230 | 0 | const unsigned char *entropy = entropy_; |
231 | |
|
232 | 0 | for (n = 0; n < bytes; ++n) { |
233 | 0 | apr_random_pool_t *p = &g->pools[g->next_pool]; |
234 | |
|
235 | 0 | if (++g->next_pool == g->npools) |
236 | 0 | g->next_pool = 0; |
237 | |
|
238 | 0 | if (p->pool_size < p->bytes+1) { |
239 | 0 | unsigned char *np = apr_palloc(g->apr_pool,(p->bytes+1)*2); |
240 | |
|
241 | 0 | if (p->pool) memcpy(np,p->pool,p->bytes); |
242 | 0 | p->pool = np; |
243 | 0 | p->pool_size = (p->bytes+1)*2; |
244 | 0 | } |
245 | 0 | p->pool[p->bytes++] = entropy[n]; |
246 | |
|
247 | 0 | if (p->bytes == g->rehash_size) { |
248 | 0 | apr_size_t r; |
249 | |
|
250 | 0 | for (r = 0; r < p->bytes/2; r+=g->pool_hash->size) |
251 | 0 | hash(g->pool_hash,p->pool+r,p->pool+r*2,g->pool_hash->size*2); |
252 | 0 | p->bytes/=2; |
253 | 0 | } |
254 | 0 | assert(p->bytes < g->rehash_size); |
255 | 0 | } |
256 | | |
257 | 0 | if (g->pools[0].bytes >= g->reseed_size) |
258 | 0 | rekey(g); |
259 | 0 | } |
260 | | |
261 | | /* This will give g->B_size bytes of randomness */ |
262 | | static void apr_random_block(apr_random_t *g,unsigned char *random) |
263 | 0 | { |
264 | | /* FIXME: in principle, these are different hashes */ |
265 | 0 | hash(g->prng_hash,g->H,g->H,H_size(g)); |
266 | 0 | hash(g->prng_hash,random,g->H,B_size(g)); |
267 | 0 | } |
268 | | |
269 | | static void apr_random_bytes(apr_random_t *g,unsigned char *random, |
270 | | apr_size_t bytes) |
271 | 0 | { |
272 | 0 | apr_size_t n; |
273 | |
|
274 | 0 | for (n = 0; n < bytes; ) { |
275 | 0 | apr_size_t l; |
276 | |
|
277 | 0 | if (g->random_bytes == 0) { |
278 | 0 | apr_random_block(g,g->randomness); |
279 | 0 | g->random_bytes = B_size(g); |
280 | 0 | } |
281 | 0 | l = min(bytes-n,g->random_bytes); |
282 | 0 | memcpy(&random[n],g->randomness+B_size(g)-g->random_bytes,l); |
283 | 0 | g->random_bytes-=l; |
284 | 0 | n+=l; |
285 | 0 | } |
286 | 0 | } |
287 | | |
288 | | APR_DECLARE(apr_status_t) apr_random_secure_bytes(apr_random_t *g, |
289 | | void *random, |
290 | | apr_size_t bytes) |
291 | 0 | { |
292 | 0 | if (!g->secure_started) |
293 | 0 | return APR_ENOTENOUGHENTROPY; |
294 | 0 | apr_random_bytes(g,random,bytes); |
295 | 0 | return APR_SUCCESS; |
296 | 0 | } |
297 | | |
298 | | APR_DECLARE(apr_status_t) apr_random_insecure_bytes(apr_random_t *g, |
299 | | void *random, |
300 | | apr_size_t bytes) |
301 | 0 | { |
302 | 0 | if (!g->insecure_started) |
303 | 0 | return APR_ENOTENOUGHENTROPY; |
304 | 0 | apr_random_bytes(g,random,bytes); |
305 | 0 | return APR_SUCCESS; |
306 | 0 | } |
307 | | |
308 | | APR_DECLARE(void) apr_random_barrier(apr_random_t *g) |
309 | 0 | { |
310 | 0 | g->secure_started = 0; |
311 | 0 | g->secure_base = g->generation; |
312 | 0 | } |
313 | | |
314 | | APR_DECLARE(apr_status_t) apr_random_secure_ready(apr_random_t *r) |
315 | 0 | { |
316 | 0 | if (!r->secure_started) |
317 | 0 | return APR_ENOTENOUGHENTROPY; |
318 | 0 | return APR_SUCCESS; |
319 | 0 | } |
320 | | |
321 | | APR_DECLARE(apr_status_t) apr_random_insecure_ready(apr_random_t *r) |
322 | 0 | { |
323 | 0 | if (!r->insecure_started) |
324 | 0 | return APR_ENOTENOUGHENTROPY; |
325 | 0 | return APR_SUCCESS; |
326 | 0 | } |