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 "paranoia.h"
  39
  40 #define RAND__HACKS
  41 #include "rand.h"
  42
  43 #include "noise.h"
  44
  45 #include "twofish-counter.h"
  46 #include "sha256.h"
  47
  48 #define CIPHER_CTX twofish_counterctx
  49 #define CIPHER_INIT twofish_counterinit
  50 #define CIPHER_ENCRYPT twofish_counterencrypt
  51 #define CIPHER_IVSZ TWOFISH_BLKSZ
  52 #define CIPHER_KEYSZ TWOFISH_KEYSZ
  53
  54 #define HASH_CTX sha256_ctx
  55 #define HASH_INIT sha256_init
  56 #define HASH sha256_hash
  57 #define HASH_DONE sha256_done
  58 #define HASH_SZ SHA256_HASHSZ
  59
  60 /*----- Static variables --------------------------------------------------*/
  61
  62 static const grand_ops gops;
  63
  64 typedef struct rand__gctx {
  65   grand r;
  66   rand_pool p;
  67 } gctx;
  68
  69 gctx rand_global = {
  70   { &gops },
  71   { { 0 }, 0, 0, 0, 0,
  72     { 0 }, RAND_SECSZ, 0,
  73     { "Catacomb global random byte pool" },
  74     &noise_source }
  75 };
  76
  77 /*----- Macros ------------------------------------------------------------*/
  78
  79 #define RAND_RESOLVE(r)                                                 \
  80   do { if ((r) == RAND_GLOBAL) r = &rand_global.p; } while (0)
  81
  82 #define GENCHECK(r) do {                                                \
  83   unsigned gen = rand_generation();                                     \
  84   if (r->gen != gen) { r->gen = gen; rand_gate(r); }                    \
  85 } while (0)
  86
  87 #define TIMER(r) do {                                                   \
  88   if ((r)->s && (r)->s->timer)                                          \
  89     (r)->s->timer(r);                                                   \
  90 } while (0)
  91
  92 /*----- Main code ---------------------------------------------------------*/
  93
  94 /* --- @rand_init@ --- *
  95  *
  96  * Arguments:   @rand_pool *r@ = pointer to a randomness pool
  97  *
  98  * Returns:     ---
  99  *
 100  * Use:         Initializes a randomness pool.  The pool doesn't start out
 101  *              very random: that's your job to sort out.  A good suggestion
 102  *              would be to attach an appropriate noise source and call
 103  *              @rand_seed@.
 104  */
 105
 106 void rand_init(rand_pool *r)
 107 {
 108   RAND_RESOLVE(r);
 109   memset(r->pool, 0, sizeof(r->pool));
 110   memset(r->buf, 0, sizeof(r->buf));
 111   r->gen = rand_generation();
 112   r->i = 0;
 113   r->irot = 0;
 114   r->ibits = r->obits = 0;
 115   r->o = RAND_SECSZ;
 116   r->s = &noise_source;
 117   rand_key(r, 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   HASH_CTX hc;
 184   octet h[HASH_SZ];
 185   static const char label[] = "Catacomb random pool key";
 186
 187   RAND_RESOLVE(r);
 188
 189   assert(HASH_SZ >= RAND_KEYSZ);
 190   HASH_INIT(&hc);
 191   HASH(&hc, label, sizeof(label));
 192   if (sz) HASH(&hc, k, sz);
 193   HASH_DONE(&hc, h);
 194   memcpy(r->k.k, h, RAND_KEYSZ);
 195 }
 196
 197 /* --- @rand_add@ --- *
 198  *
 199  * Arguments:   @rand_pool *r@ = pointer to a randomness pool
 200  *              @const void *p@ = pointer a buffer of data to add
 201  *              @size_t sz@ = size of the data buffer
 202  *              @unsigned goodbits@ = number of good bits estimated in buffer
 203  *
 204  * Returns:     ---
 205  *
 206  * Use:         Mixes the data in the buffer with the contents of the
 207  *              pool.  The estimate of the number of good bits is added to
 208  *              the pool's own count.  The mixing operation is not
 209  *              cryptographically strong.  However, data in the input pool
 210  *              isn't output directly, only through the one-way gating
 211  *              operation, so that shouldn't matter.
 212  */
 213
 214 void rand_add(rand_pool *r, const void *p, size_t sz, unsigned goodbits)
 215 {
 216   const octet *c = p;
 217   int i, rot;
 218
 219 #if RAND_POOLSZ != 128
 220 #  error Polynomial in rand_add is out of date.  Fix it.
 221 #endif
 222
 223   RAND_RESOLVE(r);
 224
 225   i = r->i; rot = r->irot;
 226
 227   while (sz) {
 228     octet o = *c++;
 229     r->pool[i] ^= (ROL8(o, rot) ^
 230                    r->pool[(i + 1) % RAND_POOLSZ] ^
 231                    r->pool[(i + 2) % RAND_POOLSZ] ^
 232                    r->pool[(i + 7) % RAND_POOLSZ]);
 233     rot = (rot + 5) & 7;
 234     i++; if (i >= RAND_POOLSZ) i -= RAND_POOLSZ;
 235     sz--;
 236   }
 237
 238   r->i = i;
 239   r->irot = rot;
 240   r->ibits += goodbits;
 241   if (r->ibits > RAND_IBITS)
 242     r->ibits = RAND_IBITS;
 243 }
 244
 245 /* --- @rand_goodbits@ --- *
 246  *
 247  * Arguments:   @rand_pool *r@ = pointer to a randomness pool
 248  *
 249  * Returns:     Estimate of the number of good bits remaining in the pool.
 250  */
 251
 252 unsigned rand_goodbits(rand_pool *r)
 253 {
 254   RAND_RESOLVE(r);
 255   return (r->ibits + r->obits);
 256 }
 257
 258 /* --- @rand_gate@ --- *
 259  *
 260  * Arguments:   @rand_pool *r@ = pointer to a randomness pool
 261  *
 262  * Returns:     ---
 263  *
 264  * Use:         Mixes up the entire state of the generator in a nonreversible
 265  *              way.
 266  */
 267
 268 void rand_gate(rand_pool *r)
 269 {
 270   octet h[HASH_SZ], g[4];
 271   HASH_CTX hc;
 272   CIPHER_CTX cc;
 273
 274   RAND_RESOLVE(r);
 275   TIMER(r);
 276
 277   /* --- Hash up all the data in the pool --- */
 278
 279   HASH_INIT(&hc);
 280   STORE32(g, r->gen); HASH(&hc, g, sizeof(g));
 281   HASH(&hc, r->pool, RAND_POOLSZ);
 282   HASH(&hc, r->buf, RAND_BUFSZ);
 283   HASH_DONE(&hc, h);
 284   BURN(hc);
 285
 286   /* --- Now mangle all of the data based on the hash --- */
 287
 288   assert(CIPHER_KEYSZ <= HASH_SZ);
 289   CIPHER_INIT(&cc, h, CIPHER_KEYSZ, 0);
 290   CIPHER_ENCRYPT(&cc, r->pool, r->pool, RAND_POOLSZ);
 291   CIPHER_ENCRYPT(&cc, r->buf, r->buf, RAND_BUFSZ);
 292   BURN(cc);
 293
 294   /* --- Reset the various state variables --- */
 295
 296   r->o = RAND_SECSZ;
 297   r->obits += r->ibits;
 298   if (r->obits > RAND_OBITS) {
 299     r->ibits = r->obits - r->ibits;
 300     r->obits = RAND_OBITS;
 301   } else
 302     r->ibits = 0;
 303   TIMER(r);
 304 }
 305
 306 /* --- @rand_stretch@ --- *
 307  *
 308  * Arguments:   @rand_pool *r@ = pointer to a randomness pool
 309  *
 310  * Returns:     ---
 311  *
 312  * Use:         Stretches the contents of the output buffer by transforming
 313  *              it in a nonreversible way.  This doesn't add any entropy
 314  *              worth speaking about, but it works well enough when the
 315  *              caller doesn't care about that sort of thing.
 316  */
 317
 318 void rand_stretch(rand_pool *r)
 319 {
 320   octet h[HASH_SZ], g[4];
 321   HASH_CTX hc;
 322   CIPHER_CTX cc;
 323
 324   RAND_RESOLVE(r);
 325   TIMER(r);
 326
 327   /* --- Hash up all the data in the buffer --- */
 328
 329   HASH_INIT(&hc);
 330   STORE32(g, r->gen); HASH(&hc, g, sizeof(g));
 331   HASH(&hc, r->pool, RAND_POOLSZ);
 332   HASH(&hc, r->buf, RAND_BUFSZ);
 333   HASH_DONE(&hc, h);
 334   BURN(hc);
 335
 336   /* --- Now mangle the buffer based on the hash --- */
 337
 338   assert(CIPHER_KEYSZ <= HASH_SZ);
 339   CIPHER_INIT(&cc, h, CIPHER_KEYSZ, 0);
 340   CIPHER_ENCRYPT(&cc, r->buf, r->buf, RAND_BUFSZ);
 341   BURN(cc);
 342
 343   /* --- Reset the various state variables --- */
 344
 345   r->o = RAND_SECSZ;
 346   TIMER(r);
 347 }
 348
 349 /* --- @rand_get@ --- *
 350  *
 351  * Arguments:   @rand_pool *r@ = pointer to a randomness pool
 352  *              @void *p@ = pointer to output buffer
 353  *              @size_t sz@ = size of output buffer
 354  *
 355  * Returns:     ---
 356  *
 357  * Use:         Gets random data from the pool.  The pool's contents can't be
 358  *              determined from the output of this function; nor can the
 359  *              output data be determined from a knowledge of the data input
 360  *              to the pool wihtout also having knowledge of the secret key.
 361  *              The good bits counter is decremented, although no special
 362  *              action is taken if it reaches zero.
 363  */
 364
 365 void rand_get(rand_pool *r, void *p, size_t sz)
 366 {
 367   octet *o = p;
 368
 369   RAND_RESOLVE(r);
 370   GENCHECK(r);
 371   TIMER(r);
 372
 373   if (!sz)
 374     return;
 375   for (;;) {
 376     if (r->o + sz <= RAND_BUFSZ) {
 377       memcpy(o, r->buf + r->o, sz);
 378       r->o += sz;
 379       break;
 380     } else {
 381       size_t chunk = RAND_BUFSZ - r->o;
 382       if (chunk) {
 383         memcpy(o, r->buf + r->o, chunk);
 384         sz -= chunk;
 385         o += chunk;
 386       }
 387       rand_stretch(r);
 388     }
 389   }
 390
 391   if (r->obits > sz * 8)
 392     r->obits -= sz * 8;
 393   else
 394     r->obits = 0;
 395 }
 396
 397 /* --- @rand_getgood@ --- *
 398  *
 399  * Arguments:   @rand_pool *r@ = pointer to a randomness pool
 400  *              @void *p@ = pointer to output buffer
 401  *              @size_t sz@ = size of output buffer
 402  *
 403  * Returns:     ---
 404  *
 405  * Use:         Gets random data from the pool, ensuring that there are
 406  *              enough good bits.  This interface isn't recommended: it makes
 407  *              the generator slow, and doesn't provide much more security
 408  *              than @rand_get@, assuming you've previously done a
 409  *              @rand_seed@.
 410  */
 411
 412 void rand_getgood(rand_pool *r, void *p, size_t sz)
 413 {
 414   octet *o = p;
 415
 416   RAND_RESOLVE(r);
 417
 418   if (!sz)
 419     return;
 420   if (!r->s || !r->s->getnoise) {
 421     rand_get(r, p, sz);
 422     return;
 423   }
 424   GENCHECK(r);
 425   TIMER(r);
 426
 427   while (sz) {
 428     size_t chunk = sz;
 429
 430     if (chunk * 8 > r->obits) {
 431       if (chunk * 8 > r->ibits + r->obits)
 432         do r->s->getnoise(r); while (r->ibits + r->obits < 256);
 433       rand_gate(r);
 434       if (chunk * 8 > r->obits)
 435         chunk = r->obits / 8;
 436     }
 437
 438     if (chunk + r->o > RAND_BUFSZ)
 439       chunk = RAND_BUFSZ - r->o;
 440
 441     memcpy(o, r->buf + r->o, chunk);
 442     r->o += chunk;
 443     r->obits -= chunk * 8;
 444     o += chunk;
 445     sz -= chunk;
 446   }
 447 }
 448
 449 /*----- Generic random number generator interface -------------------------*/
 450
 451 static void gdestroy(grand *r)
 452 {
 453   gctx *g = (gctx *)r;
 454   if (g != &rand_global) {
 455     BURN(*g);
 456     S_DESTROY(g);
 457   }
 458 }
 459
 460 static int gmisc(grand *r, unsigned op, ...)
 461 {
 462   gctx *g = (gctx *)r;
 463   va_list ap;
 464   int rc = 0;
 465   va_start(ap, op);
 466
 467   switch (op) {
 468     case GRAND_CHECK:
 469       switch (va_arg(ap, unsigned)) {
 470         case GRAND_CHECK:
 471         case GRAND_SEEDINT:
 472         case GRAND_SEEDUINT32:
 473         case GRAND_SEEDBLOCK:
 474         case GRAND_SEEDRAND:
 475         case RAND_GATE:
 476         case RAND_STRETCH:
 477         case RAND_KEY:
 478         case RAND_NOISESRC:
 479         case RAND_SEED:
 480         case RAND_TIMER:
 481         case RAND_GOODBITS:
 482         case RAND_ADD:
 483           rc = 1;
 484           break;
 485         default:
 486           rc = 0;
 487           break;
 488       }
 489       break;
 490     case GRAND_SEEDINT: {
 491       unsigned u = va_arg(ap, unsigned);
 492       rand_add(&g->p, &u, sizeof(u), sizeof(u));
 493     } break;
 494     case GRAND_SEEDUINT32: {
 495       uint32 i = va_arg(ap, uint32);
 496       rand_add(&g->p, &i, sizeof(i), 4);
 497     } break;
 498     case GRAND_SEEDBLOCK: {
 499       const void *p = va_arg(ap, const void *);
 500       size_t sz = va_arg(ap, size_t);
 501       rand_add(&g->p, p, sz, sz);
 502     } break;
 503     case GRAND_SEEDRAND: {
 504       grand *rr = va_arg(ap, grand *);
 505       octet buf[16];
 506       rr->ops->fill(rr, buf, sizeof(buf));
 507       rand_add(&g->p, buf, sizeof(buf), 8);
 508     } break;
 509     case RAND_GATE:
 510       rand_gate(&g->p);
 511       break;
 512     case RAND_STRETCH:
 513       rand_stretch(&g->p);
 514       break;
 515     case RAND_KEY: {
 516       const void *k = va_arg(ap, const void *);
 517       size_t sz = va_arg(ap, size_t);
 518       rand_key(&g->p, k, sz);
 519     } break;
 520     case RAND_NOISESRC:
 521       rand_noisesrc(&g->p, va_arg(ap, const rand_source *));
 522       break;
 523     case RAND_SEED:
 524       rand_seed(&g->p, va_arg(ap, unsigned));
 525       break;
 526     case RAND_TIMER:
 527       TIMER(&g->p);
 528       break;
 529     case RAND_GOODBITS:
 530       rc = rand_goodbits(&g->p);
 531       break;
 532     case RAND_ADD: {
 533       const void *p = va_arg(ap, const void *);
 534       size_t sz = va_arg(ap, size_t);
 535       unsigned goodbits = va_arg(ap, unsigned);
 536       rand_add(&g->p, p, sz, goodbits);
 537     } break;
 538     default:
 539       GRAND_BADOP;
 540       break;
 541   }
 542
 543   va_end(ap);
 544   return (rc);
 545 }
 546
 547 static octet gbyte(grand *r)
 548 {
 549   gctx *g = (gctx *)r;
 550   octet o;
 551   rand_getgood(&g->p, &o, 1);
 552   return (o);
 553 }
 554
 555 static uint32 gword(grand *r)
 556 {
 557   gctx *g = (gctx *)r;
 558   octet b[4];
 559   rand_getgood(&g->p, &b, sizeof(b));
 560   return (LOAD32(b));
 561 }
 562
 563 static void gfill(grand *r, void *p, size_t sz)
 564 {
 565   gctx *g = (gctx *)r;
 566   rand_get(&g->p, p, sz);
 567 }
 568
 569 static const grand_ops gops = {
 570   "rand",
 571   GRAND_CRYPTO, 0,
 572   gmisc, gdestroy,
 573   gword, gbyte, gword, grand_defaultrange, gfill
 574 };
 575
 576 /* --- @rand_create@ --- *
 577  *
 578  * Arguments:   ---
 579  *
 580  * Returns:     Pointer to a generic generator.
 581  *
 582  * Use:         Constructs a generic generator interface over a Catacomb
 583  *              entropy pool generator.
 584  */
 585
 586 grand *rand_create(void)
 587 {
 588   gctx *g = S_CREATE(gctx);
 589   g->r.ops = &gops;
 590   rand_init(&g->p);
 591   return (&g->r);
 592 }
 593
 594 /*----- That's all, folks -------------------------------------------------*/