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

   1 /* -*-c-*-
   2  *
   3  * $Id$
   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 /*----- Header files ------------------------------------------------------*/
  31
  32 #include <stdarg.h>
  33 #include <stdio.h>
  34 #include <string.h>
  35
  36 #include <mLib/bits.h>
  37 #include <mLib/sub.h>
  38
  39 #include "arena.h"
  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
  48 static const grand_ops gops;
  49
  50 typedef struct gctx {
  51   grand r;
  52   rand_pool p;
  53 } gctx;
  54
  55 static gctx *pool = 0;                  /* Default random pool */
  56
  57 /*----- Macros ------------------------------------------------------------*/
  58
  59 #define RAND_RESOLVE(r) do {                                            \
  60   if ((r) == RAND_GLOBAL) {                                             \
  61     if (!pool)                                                          \
  62       pool = (gctx *)rand_create();                                     \
  63     (r) = &pool->p;                                                     \
  64   }                                                                     \
  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
  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@.
  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;
  96   rmd160_hmacinit(&r->k, 0, 0);
  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
 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
 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);
 163   rmd160_hmacinit(&r->k, k, sz);
 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;
 186   int i, rot;
 187
 188 #if RAND_POOLSZ != 128
 189 #  error Polynomial in rand_add is out of date.  Fix it.
 190 #endif
 191
 192   RAND_RESOLVE(r);
 193
 194   i = r->i; rot = r->irot;
 195
 196   while (sz) {
 197     octet o = *c++;
 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]);
 202     rot = (rot + 5) & 7;
 203     i++; if (i >= RAND_POOLSZ) i -= RAND_POOLSZ;
 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  *
 216  * Arguments:   @rand_pool *r@ = pointer to a randomness pool
 217  *
 218  * Returns:     Estimate of the number of good bits remaining in the pool.
 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);
 250     rmd160_machash(&mc, r->pool, sizeof(r->pool));
 251     rmd160_machash(&mc, r->buf, sizeof(r->buf));
 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);
 304     rmd160_machash(&mc, r->pool, sizeof(r->pool));
 305     rmd160_machash(&mc, r->buf, sizeof(r->buf));
 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  *
 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@.
 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)
 407         do r->s->getnoise(r); while (r->ibits + r->obits < 256);
 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);
 417     r->o += chunk;
 418     r->obits -= chunk * 8;
 419     o += chunk;
 420     sz -= chunk;
 421   }
 422 }
 423
 424 /*----- Generic random number generator interface -------------------------*/
 425
 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
 436 static void gdestroy(grand *r)
 437 {
 438   gctx *g;
 439   GRESOLVE(g, r);
 440   if (g != pool) {
 441     BURN(*g);
 442     S_DESTROY(g);
 443   }
 444 }
 445
 446 static int gmisc(grand *r, unsigned op, ...)
 447 {
 448   gctx *g;
 449   va_list ap;
 450   int rc = 0;
 451   va_start(ap, op);
 452
 453   GRESOLVE(g, r);
 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:
 461         case GRAND_SEEDRAND:
 462         case RAND_GATE:
 463         case RAND_STRETCH:
 464         case RAND_KEY:
 465         case RAND_NOISESRC:
 466         case RAND_SEED:
 467         case RAND_TIMER:
 468         case RAND_GOODBITS:
 469         case RAND_ADD:
 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;
 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;
 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;
 510     case RAND_SEED:
 511       rand_seed(&g->p, va_arg(ap, unsigned));
 512       break;
 513     case RAND_TIMER:
 514       TIMER(&g->p);
 515       break;
 516     case RAND_GOODBITS:
 517       rc = rand_goodbits(&g->p);
 518       break;
 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;
 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 {
 536   gctx *g;
 537   octet o;
 538   GRESOLVE(g, r);
 539   rand_getgood(&g->p, &o, 1);
 540   return (o);
 541 }
 542
 543 static uint32 gword(grand *r)
 544 {
 545   gctx *g;
 546   octet b[4];
 547   GRESOLVE(g, r);
 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 {
 554   gctx *g;
 555   GRESOLVE(g, r);
 556   rand_get(&g->p, p, sz);
 557 }
 558
 559 static const grand_ops gops = {
 560   "rand",
 561   GRAND_CRYPTO, 0,
 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 {
 580   gctx *g = S_CREATE(gctx);
 581   g->r.ops = &gops;
 582   rand_init(&g->p);
 583   return (&g->r);
 584 }
 585
 586 /*----- That's all, folks -------------------------------------------------*/