d03ab969 |
1 | /* -*-c-*- |
2 | * |
838a6a51 |
3 | * $Id$ |
d03ab969 |
4 | * |
5 | * Secure random number generator |
6 | * |
7 | * (c) 1998 Straylight/Edgeware |
8 | */ |
9 | |
45c0fd36 |
10 | /*----- Licensing notice --------------------------------------------------* |
d03ab969 |
11 | * |
12 | * This file is part of Catacomb. |
13 | * |
14 | * Catacomb is free software; you can redistribute it and/or modify |
15 | * it under the terms of the GNU Library General Public License as |
16 | * published by the Free Software Foundation; either version 2 of the |
17 | * License, or (at your option) any later version. |
45c0fd36 |
18 | * |
d03ab969 |
19 | * Catacomb is distributed in the hope that it will be useful, |
20 | * but WITHOUT ANY WARRANTY; without even the implied warranty of |
21 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
22 | * GNU Library General Public License for more details. |
45c0fd36 |
23 | * |
d03ab969 |
24 | * You should have received a copy of the GNU Library General Public |
25 | * License along with Catacomb; if not, write to the Free |
26 | * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, |
27 | * MA 02111-1307, USA. |
28 | */ |
29 | |
d03ab969 |
30 | /*----- Header files ------------------------------------------------------*/ |
31 | |
aacbc1c6 |
32 | #include <stdarg.h> |
d03ab969 |
33 | #include <stdio.h> |
34 | #include <string.h> |
35 | |
36 | #include <mLib/bits.h> |
aacbc1c6 |
37 | #include <mLib/sub.h> |
d03ab969 |
38 | |
ac2fd5cd |
39 | #include "arena.h" |
d03ab969 |
40 | #include "blowfish-cbc.h" |
41 | #include "paranoia.h" |
42 | #include "rand.h" |
43 | #include "rmd160.h" |
44 | #include "rmd160-hmac.h" |
45 | |
46 | /*----- Static variables --------------------------------------------------*/ |
47 | |
aacbc1c6 |
48 | static const grand_ops gops; |
49 | |
50 | typedef struct gctx { |
51 | grand r; |
52 | rand_pool p; |
53 | } gctx; |
54 | |
ac2fd5cd |
55 | static gctx *pool = 0; /* Default random pool */ |
d03ab969 |
56 | |
57 | /*----- Macros ------------------------------------------------------------*/ |
58 | |
59 | #define RAND_RESOLVE(r) do { \ |
ac2fd5cd |
60 | if ((r) == RAND_GLOBAL) { \ |
61 | if (!pool) \ |
62 | pool = (gctx *)rand_create(); \ |
63 | (r) = &pool->p; \ |
64 | } \ |
d03ab969 |
65 | } while (0) |
66 | |
67 | #define TIMER(r) do { \ |
68 | if ((r)->s && (r)->s->timer) \ |
69 | (r)->s->timer(r); \ |
70 | } while (0) |
71 | |
72 | /*----- Main code ---------------------------------------------------------*/ |
73 | |
74 | /* --- @rand_init@ --- * |
75 | * |
76 | * Arguments: @rand_pool *r@ = pointer to a randomness pool |
77 | * |
78 | * Returns: --- |
79 | * |
80 | * Use: Initializes a randomness pool. The pool doesn't start out |
ac2fd5cd |
81 | * very random: that's your job to sort out. A good suggestion |
82 | * would be to attach an appropriate noise source and call |
83 | * @rand_seed@. |
d03ab969 |
84 | */ |
85 | |
86 | void rand_init(rand_pool *r) |
87 | { |
88 | RAND_RESOLVE(r); |
89 | memset(r->pool, 0, sizeof(r->pool)); |
90 | memset(r->buf, 0, sizeof(r->buf)); |
91 | r->i = 0; |
92 | r->irot = 0; |
93 | r->ibits = r->obits = 0; |
94 | r->o = RAND_SECSZ; |
95 | r->s = 0; |
aacbc1c6 |
96 | rmd160_hmacinit(&r->k, 0, 0); |
d03ab969 |
97 | rand_gate(r); |
98 | } |
99 | |
100 | /* --- @rand_noisesrc@ --- * |
101 | * |
102 | * Arguments: @rand_pool *r@ = pointer to a randomness pool |
103 | * @const rand_source *s@ = pointer to source definition |
104 | * |
105 | * Returns: --- |
106 | * |
107 | * Use: Sets a noise source for a randomness pool. When the pool's |
108 | * estimate of good random bits falls to zero, the @getnoise@ |
109 | * function is called, passing the pool handle as an argument. |
110 | * It is expected to increase the number of good bits by at |
111 | * least one, because it'll be called over and over again until |
112 | * there are enough bits to satisfy the caller. The @timer@ |
113 | * function is called frequently throughout the generator's |
114 | * operation. |
115 | */ |
116 | |
117 | void rand_noisesrc(rand_pool *r, const rand_source *s) |
118 | { |
119 | RAND_RESOLVE(r); |
120 | r->s = s; |
121 | } |
122 | |
ac2fd5cd |
123 | /* --- @rand_seed@ --- * |
124 | * |
125 | * Arguments: @rand_pool *r@ = pointer to a randomness pool |
126 | * @unsigned bits@ = number of bits to ensure |
127 | * |
128 | * Returns: --- |
129 | * |
130 | * Use: Ensures that there are at least @bits@ good bits of entropy |
131 | * in the pool. It is recommended that you call this after |
132 | * initializing a new pool. Requesting @bits > RAND_IBITS@ is |
133 | * doomed to failure (and is an error). |
134 | */ |
135 | |
136 | void rand_seed(rand_pool *r, unsigned bits) |
137 | { |
138 | RAND_RESOLVE(r); |
139 | |
140 | assert(((void)"bits pointlessly large in rand_seed", bits <= RAND_IBITS)); |
141 | assert(((void)"no noise source in rand_seed", r->s)); |
142 | |
143 | while (r->ibits < bits) |
144 | r->s->getnoise(r); |
145 | rand_gate(r); |
146 | } |
147 | |
d03ab969 |
148 | /* --- @rand_key@ --- * |
149 | * |
150 | * Arguments: @rand_pool *r@ = pointer to a randomness pool |
151 | * @const void *k@ = pointer to key data |
152 | * @size_t sz@ = size of key data |
153 | * |
154 | * Returns: --- |
155 | * |
156 | * Use: Sets the secret key for a randomness pool. The key is used |
157 | * when mixing in new random bits. |
158 | */ |
159 | |
160 | void rand_key(rand_pool *r, const void *k, size_t sz) |
161 | { |
162 | RAND_RESOLVE(r); |
aacbc1c6 |
163 | rmd160_hmacinit(&r->k, k, sz); |
d03ab969 |
164 | } |
165 | |
166 | /* --- @rand_add@ --- * |
167 | * |
168 | * Arguments: @rand_pool *r@ = pointer to a randomness pool |
169 | * @const void *p@ = pointer a buffer of data to add |
170 | * @size_t sz@ = size of the data buffer |
171 | * @unsigned goodbits@ = number of good bits estimated in buffer |
172 | * |
173 | * Returns: --- |
174 | * |
175 | * Use: Mixes the data in the buffer with the contents of the |
176 | * pool. The estimate of the number of good bits is added to |
177 | * the pool's own count. The mixing operation is not |
178 | * cryptographically strong. However, data in the input pool |
179 | * isn't output directly, only through the one-way gating |
180 | * operation, so that shouldn't matter. |
181 | */ |
182 | |
183 | void rand_add(rand_pool *r, const void *p, size_t sz, unsigned goodbits) |
184 | { |
185 | const octet *c = p; |
ba044e65 |
186 | int i, rot; |
d03ab969 |
187 | |
ba044e65 |
188 | #if RAND_POOLSZ != 128 |
d03ab969 |
189 | # error Polynomial in rand_add is out of date. Fix it. |
190 | #endif |
191 | |
192 | RAND_RESOLVE(r); |
193 | |
ba044e65 |
194 | i = r->i; rot = r->irot; |
d03ab969 |
195 | |
196 | while (sz) { |
197 | octet o = *c++; |
ba044e65 |
198 | r->pool[i] ^= (ROL8(o, rot) ^ |
199 | r->pool[(i + 1) % RAND_POOLSZ] ^ |
200 | r->pool[(i + 2) % RAND_POOLSZ] ^ |
201 | r->pool[(i + 7) % RAND_POOLSZ]); |
d03ab969 |
202 | rot = (rot + 5) & 7; |
203 | i++; if (i >= RAND_POOLSZ) i -= RAND_POOLSZ; |
d03ab969 |
204 | sz--; |
205 | } |
206 | |
207 | r->i = i; |
208 | r->irot = rot; |
209 | r->ibits += goodbits; |
210 | if (r->ibits > RAND_IBITS) |
211 | r->ibits = RAND_IBITS; |
212 | } |
213 | |
214 | /* --- @rand_goodbits@ --- * |
215 | * |
45c0fd36 |
216 | * Arguments: @rand_pool *r@ = pointer to a randomness pool |
d03ab969 |
217 | * |
45c0fd36 |
218 | * Returns: Estimate of the number of good bits remaining in the pool. |
d03ab969 |
219 | */ |
220 | |
221 | unsigned rand_goodbits(rand_pool *r) |
222 | { |
223 | RAND_RESOLVE(r); |
224 | return (r->ibits + r->obits); |
225 | } |
226 | |
227 | /* --- @rand_gate@ --- * |
228 | * |
229 | * Arguments: @rand_pool *r@ = pointer to a randomness pool |
230 | * |
231 | * Returns: --- |
232 | * |
233 | * Use: Mixes up the entire state of the generator in a nonreversible |
234 | * way. |
235 | */ |
236 | |
237 | void rand_gate(rand_pool *r) |
238 | { |
239 | octet mac[RMD160_HASHSZ]; |
240 | |
241 | RAND_RESOLVE(r); |
242 | TIMER(r); |
243 | |
244 | /* --- Hash up all the data in the pool --- */ |
245 | |
246 | { |
247 | rmd160_macctx mc; |
248 | |
249 | rmd160_macinit(&mc, &r->k); |
aacbc1c6 |
250 | rmd160_machash(&mc, r->pool, sizeof(r->pool)); |
251 | rmd160_machash(&mc, r->buf, sizeof(r->buf)); |
d03ab969 |
252 | rmd160_macdone(&mc, mac); |
253 | BURN(mc); |
254 | } |
255 | |
256 | /* --- Now mangle all of the data based on the hash --- */ |
257 | |
258 | { |
259 | blowfish_cbcctx bc; |
260 | |
261 | blowfish_cbcinit(&bc, mac, sizeof(mac), 0); |
262 | blowfish_cbcencrypt(&bc, r->pool, r->pool, sizeof(r->pool)); |
263 | blowfish_cbcencrypt(&bc, r->buf, r->buf, sizeof(r->buf)); |
264 | BURN(bc); |
265 | } |
266 | |
267 | /* --- Reset the various state variables --- */ |
268 | |
269 | r->o = RAND_SECSZ; |
270 | r->obits += r->ibits; |
271 | if (r->obits > RAND_OBITS) { |
272 | r->ibits = r->obits - r->ibits; |
273 | r->obits = RAND_OBITS; |
274 | } else |
275 | r->ibits = 0; |
276 | TIMER(r); |
277 | } |
278 | |
279 | /* --- @rand_stretch@ --- * |
280 | * |
281 | * Arguments: @rand_pool *r@ = pointer to a randomness pool |
282 | * |
283 | * Returns: --- |
284 | * |
285 | * Use: Stretches the contents of the output buffer by transforming |
286 | * it in a nonreversible way. This doesn't add any entropy |
287 | * worth speaking about, but it works well enough when the |
288 | * caller doesn't care about that sort of thing. |
289 | */ |
290 | |
291 | void rand_stretch(rand_pool *r) |
292 | { |
293 | octet mac[RMD160_HASHSZ]; |
294 | |
295 | RAND_RESOLVE(r); |
296 | TIMER(r); |
297 | |
298 | /* --- Hash up all the data in the buffer --- */ |
299 | |
300 | { |
301 | rmd160_macctx mc; |
302 | |
303 | rmd160_macinit(&mc, &r->k); |
aacbc1c6 |
304 | rmd160_machash(&mc, r->pool, sizeof(r->pool)); |
305 | rmd160_machash(&mc, r->buf, sizeof(r->buf)); |
d03ab969 |
306 | rmd160_macdone(&mc, mac); |
307 | BURN(mc); |
308 | } |
309 | |
310 | /* --- Now mangle the buffer based on that hash --- */ |
311 | |
312 | { |
313 | blowfish_cbcctx bc; |
314 | |
315 | blowfish_cbcinit(&bc, mac, sizeof(mac), 0); |
316 | blowfish_cbcencrypt(&bc, r->buf, r->buf, sizeof(r->buf)); |
317 | BURN(bc); |
318 | } |
319 | |
320 | /* --- Reset the various state variables --- */ |
321 | |
322 | r->o = RAND_SECSZ; |
323 | TIMER(r); |
324 | } |
325 | |
326 | /* --- @rand_get@ --- * |
327 | * |
328 | * Arguments: @rand_pool *r@ = pointer to a randomness pool |
329 | * @void *p@ = pointer to output buffer |
330 | * @size_t sz@ = size of output buffer |
331 | * |
332 | * Returns: --- |
333 | * |
334 | * Use: Gets random data from the pool. The pool's contents can't be |
335 | * determined from the output of this function; nor can the |
336 | * output data be determined from a knowledge of the data input |
337 | * to the pool wihtout also having knowledge of the secret key. |
338 | * The good bits counter is decremented, although no special |
339 | * action is taken if it reaches zero. |
340 | */ |
341 | |
342 | void rand_get(rand_pool *r, void *p, size_t sz) |
343 | { |
344 | octet *o = p; |
345 | |
346 | RAND_RESOLVE(r); |
347 | TIMER(r); |
348 | |
349 | if (!sz) |
350 | return; |
351 | for (;;) { |
352 | if (r->o + sz <= RAND_BUFSZ) { |
353 | memcpy(o, r->buf + r->o, sz); |
354 | r->o += sz; |
355 | break; |
356 | } else { |
357 | size_t chunk = RAND_BUFSZ - r->o; |
358 | if (chunk) { |
359 | memcpy(o, r->buf + r->o, chunk); |
360 | sz -= chunk; |
361 | o += chunk; |
362 | } |
363 | rand_stretch(r); |
364 | } |
365 | } |
366 | |
367 | if (r->obits > sz * 8) |
368 | r->obits -= sz * 8; |
369 | else |
370 | r->obits = 0; |
371 | } |
372 | |
373 | /* --- @rand_getgood@ --- * |
374 | * |
375 | * Arguments: @rand_pool *r@ = pointer to a randomness pool |
376 | * @void *p@ = pointer to output buffer |
377 | * @size_t sz@ = size of output buffer |
378 | * |
379 | * Returns: --- |
380 | * |
ac2fd5cd |
381 | * Use: Gets random data from the pool, ensuring that there are |
382 | * enough good bits. This interface isn't recommended: it makes |
383 | * the generator slow, and doesn't provide much more security |
384 | * than @rand_get@, assuming you've previously done a |
385 | * @rand_seed@. |
d03ab969 |
386 | */ |
387 | |
388 | void rand_getgood(rand_pool *r, void *p, size_t sz) |
389 | { |
390 | octet *o = p; |
391 | |
392 | RAND_RESOLVE(r); |
393 | |
394 | if (!sz) |
395 | return; |
396 | if (!r->s || !r->s->getnoise) { |
397 | rand_get(r, p, sz); |
398 | return; |
399 | } |
400 | TIMER(r); |
401 | |
402 | while (sz) { |
403 | size_t chunk = sz; |
404 | |
405 | if (chunk * 8 > r->obits) { |
406 | if (chunk * 8 > r->ibits + r->obits) |
b056b793 |
407 | do r->s->getnoise(r); while (r->ibits + r->obits < 256); |
d03ab969 |
408 | rand_gate(r); |
409 | if (chunk * 8 > r->obits) |
410 | chunk = r->obits / 8; |
411 | } |
412 | |
413 | if (chunk + r->o > RAND_BUFSZ) |
414 | chunk = RAND_BUFSZ - r->o; |
415 | |
416 | memcpy(o, r->buf + r->o, chunk); |
aacbc1c6 |
417 | r->o += chunk; |
d03ab969 |
418 | r->obits -= chunk * 8; |
419 | o += chunk; |
420 | sz -= chunk; |
421 | } |
422 | } |
423 | |
aacbc1c6 |
424 | /*----- Generic random number generator interface -------------------------*/ |
425 | |
ac2fd5cd |
426 | #define GRESOLVE(g, r) do { \ |
427 | if (r != &rand_global) \ |
428 | g = (gctx *)r; \ |
429 | else { \ |
430 | if (!pool) \ |
431 | pool = (gctx *)rand_create(); \ |
432 | g = pool; \ |
433 | } \ |
434 | } while (0) |
435 | |
aacbc1c6 |
436 | static void gdestroy(grand *r) |
437 | { |
ac2fd5cd |
438 | gctx *g; |
439 | GRESOLVE(g, r); |
440 | if (g != pool) { |
441 | BURN(*g); |
442 | S_DESTROY(g); |
443 | } |
aacbc1c6 |
444 | } |
445 | |
446 | static int gmisc(grand *r, unsigned op, ...) |
447 | { |
ac2fd5cd |
448 | gctx *g; |
aacbc1c6 |
449 | va_list ap; |
450 | int rc = 0; |
451 | va_start(ap, op); |
452 | |
ac2fd5cd |
453 | GRESOLVE(g, r); |
aacbc1c6 |
454 | switch (op) { |
455 | case GRAND_CHECK: |
456 | switch (va_arg(ap, unsigned)) { |
457 | case GRAND_CHECK: |
458 | case GRAND_SEEDINT: |
459 | case GRAND_SEEDUINT32: |
460 | case GRAND_SEEDBLOCK: |
b056b793 |
461 | case GRAND_SEEDRAND: |
aacbc1c6 |
462 | case RAND_GATE: |
463 | case RAND_STRETCH: |
464 | case RAND_KEY: |
465 | case RAND_NOISESRC: |
ac2fd5cd |
466 | case RAND_SEED: |
838a6a51 |
467 | case RAND_TIMER: |
468 | case RAND_GOODBITS: |
990dafb1 |
469 | case RAND_ADD: |
aacbc1c6 |
470 | rc = 1; |
471 | break; |
472 | default: |
473 | rc = 0; |
474 | break; |
475 | } |
476 | break; |
477 | case GRAND_SEEDINT: { |
478 | unsigned u = va_arg(ap, unsigned); |
479 | rand_add(&g->p, &u, sizeof(u), sizeof(u)); |
480 | } break; |
481 | case GRAND_SEEDUINT32: { |
482 | uint32 i = va_arg(ap, uint32); |
483 | rand_add(&g->p, &i, sizeof(i), 4); |
484 | } break; |
485 | case GRAND_SEEDBLOCK: { |
486 | const void *p = va_arg(ap, const void *); |
487 | size_t sz = va_arg(ap, size_t); |
488 | rand_add(&g->p, p, sz, sz); |
489 | } break; |
b056b793 |
490 | case GRAND_SEEDRAND: { |
491 | grand *rr = va_arg(ap, grand *); |
492 | octet buf[16]; |
493 | rr->ops->fill(rr, buf, sizeof(buf)); |
494 | rand_add(&g->p, buf, sizeof(buf), 8); |
495 | } break; |
aacbc1c6 |
496 | case RAND_GATE: |
497 | rand_gate(&g->p); |
498 | break; |
499 | case RAND_STRETCH: |
500 | rand_stretch(&g->p); |
501 | break; |
502 | case RAND_KEY: { |
503 | const void *k = va_arg(ap, const void *); |
504 | size_t sz = va_arg(ap, size_t); |
505 | rand_key(&g->p, k, sz); |
506 | } break; |
507 | case RAND_NOISESRC: |
508 | rand_noisesrc(&g->p, va_arg(ap, const rand_source *)); |
509 | break; |
ac2fd5cd |
510 | case RAND_SEED: |
511 | rand_seed(&g->p, va_arg(ap, unsigned)); |
512 | break; |
838a6a51 |
513 | case RAND_TIMER: |
514 | TIMER(&g->p); |
515 | break; |
516 | case RAND_GOODBITS: |
517 | rc = rand_goodbits(&g->p); |
518 | break; |
990dafb1 |
519 | case RAND_ADD: { |
520 | const void *p = va_arg(ap, const void *); |
521 | size_t sz = va_arg(ap, size_t); |
522 | unsigned goodbits = va_arg(ap, unsigned); |
523 | rand_add(&g->p, p, sz, goodbits); |
524 | } break; |
aacbc1c6 |
525 | default: |
526 | GRAND_BADOP; |
527 | break; |
528 | } |
529 | |
530 | va_end(ap); |
531 | return (rc); |
532 | } |
533 | |
534 | static octet gbyte(grand *r) |
535 | { |
ac2fd5cd |
536 | gctx *g; |
aacbc1c6 |
537 | octet o; |
ac2fd5cd |
538 | GRESOLVE(g, r); |
aacbc1c6 |
539 | rand_getgood(&g->p, &o, 1); |
540 | return (o); |
541 | } |
542 | |
543 | static uint32 gword(grand *r) |
544 | { |
ac2fd5cd |
545 | gctx *g; |
aacbc1c6 |
546 | octet b[4]; |
ac2fd5cd |
547 | GRESOLVE(g, r); |
aacbc1c6 |
548 | rand_getgood(&g->p, &b, sizeof(b)); |
549 | return (LOAD32(b)); |
550 | } |
551 | |
552 | static void gfill(grand *r, void *p, size_t sz) |
553 | { |
ac2fd5cd |
554 | gctx *g; |
555 | GRESOLVE(g, r); |
556 | rand_get(&g->p, p, sz); |
aacbc1c6 |
557 | } |
558 | |
559 | static const grand_ops gops = { |
560 | "rand", |
ac2fd5cd |
561 | GRAND_CRYPTO, 0, |
aacbc1c6 |
562 | gmisc, gdestroy, |
563 | gword, gbyte, gword, grand_range, gfill |
564 | }; |
565 | |
566 | grand rand_global = { &gops }; |
567 | |
568 | /* --- @rand_create@ --- * |
569 | * |
570 | * Arguments: --- |
571 | * |
572 | * Returns: Pointer to a generic generator. |
573 | * |
574 | * Use: Constructs a generic generator interface over a Catacomb |
575 | * entropy pool generator. |
576 | */ |
577 | |
578 | grand *rand_create(void) |
579 | { |
ac2fd5cd |
580 | gctx *g = S_CREATE(gctx); |
aacbc1c6 |
581 | g->r.ops = &gops; |
582 | rand_init(&g->p); |
583 | return (&g->r); |
584 | } |
585 | |
d03ab969 |
586 | /*----- That's all, folks -------------------------------------------------*/ |