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

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