chiark - git - mdw - catacomb/blob - rand/rand.c

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