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,
  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 TIMER(r) do {                                                   \
  83   if ((r)->s && (r)->s->timer)                                          \
  84     (r)->s->timer(r);                                                   \
  85 } while (0)
  86
  87 /*----- Main code ---------------------------------------------------------*/
  88
  89 /* --- @rand_init@ --- *
  90  *
  91  * Arguments:   @rand_pool *r@ = pointer to a randomness pool
  92  *
  93  * Returns:     ---
  94  *
  95  * Use:         Initializes a randomness pool.  The pool doesn't start out
  96  *              very random: that's your job to sort out.  A good suggestion
  97  *              would be to attach an appropriate noise source and call
  98  *              @rand_seed@.
  99  */
 100
 101 void rand_init(rand_pool *r)
 102 {
 103   RAND_RESOLVE(r);
 104   memset(r->pool, 0, sizeof(r->pool));
 105   memset(r->buf, 0, sizeof(r->buf));
 106   r->i = 0;
 107   r->irot = 0;
 108   r->ibits = r->obits = 0;
 109   r->o = RAND_SECSZ;
 110   r->s = &noise_source;
 111   rand_key(r, 0, 0);
 112   rand_gate(r);
 113 }
 114
 115 /* --- @rand_noisesrc@ --- *
 116  *
 117  * Arguments:   @rand_pool *r@ = pointer to a randomness pool
 118  *              @const rand_source *s@ = pointer to source definition
 119  *
 120  * Returns:     ---
 121  *
 122  * Use:         Sets a noise source for a randomness pool.  When the pool's
 123  *              estimate of good random bits falls to zero, the @getnoise@
 124  *              function is called, passing the pool handle as an argument.
 125  *              It is expected to increase the number of good bits by at
 126  *              least one, because it'll be called over and over again until
 127  *              there are enough bits to satisfy the caller.  The @timer@
 128  *              function is called frequently throughout the generator's
 129  *              operation.
 130  */
 131
 132 void rand_noisesrc(rand_pool *r, const rand_source *s)
 133 {
 134   RAND_RESOLVE(r);
 135   r->s = s;
 136 }
 137
 138 /* --- @rand_seed@ --- *
 139  *
 140  * Arguments:   @rand_pool *r@ = pointer to a randomness pool
 141  *              @unsigned bits@ = number of bits to ensure
 142  *
 143  * Returns:     ---
 144  *
 145  * Use:         Ensures that there are at least @bits@ good bits of entropy
 146  *              in the pool.  It is recommended that you call this after
 147  *              initializing a new pool.  Requesting @bits > RAND_IBITS@ is
 148  *              doomed to failure (and is an error).
 149  */
 150
 151 void rand_seed(rand_pool *r, unsigned bits)
 152 {
 153   RAND_RESOLVE(r);
 154
 155   assert(((void)"bits pointlessly large in rand_seed", bits <= RAND_IBITS));
 156   assert(((void)"no noise source in rand_seed", r->s));
 157
 158   while (r->ibits < bits)
 159     r->s->getnoise(r);
 160   rand_gate(r);
 161 }
 162
 163 /* --- @rand_key@ --- *
 164  *
 165  * Arguments:   @rand_pool *r@ = pointer to a randomness pool
 166  *              @const void *k@ = pointer to key data
 167  *              @size_t sz@ = size of key data
 168  *
 169  * Returns:     ---
 170  *
 171  * Use:         Sets the secret key for a randomness pool.  The key is used
 172  *              when mixing in new random bits.
 173  */
 174
 175 void rand_key(rand_pool *r, const void *k, size_t sz)
 176 {
 177   HASH_CTX hc;
 178   octet h[HASH_SZ];
 179   static const char label[] = "Catacomb random pool key";
 180
 181   RAND_RESOLVE(r);
 182
 183   assert(HASH_SZ >= RAND_KEYSZ);
 184   HASH_INIT(&hc);
 185   HASH(&hc, label, sizeof(label));
 186   if (sz) HASH(&hc, k, sz);
 187   HASH_DONE(&hc, h);
 188   memcpy(r->k.k, h, RAND_KEYSZ);
 189 }
 190
 191 /* --- @rand_add@ --- *
 192  *
 193  * Arguments:   @rand_pool *r@ = pointer to a randomness pool
 194  *              @const void *p@ = pointer a buffer of data to add
 195  *              @size_t sz@ = size of the data buffer
 196  *              @unsigned goodbits@ = number of good bits estimated in buffer
 197  *
 198  * Returns:     ---
 199  *
 200  * Use:         Mixes the data in the buffer with the contents of the
 201  *              pool.  The estimate of the number of good bits is added to
 202  *              the pool's own count.  The mixing operation is not
 203  *              cryptographically strong.  However, data in the input pool
 204  *              isn't output directly, only through the one-way gating
 205  *              operation, so that shouldn't matter.
 206  */
 207
 208 void rand_add(rand_pool *r, const void *p, size_t sz, unsigned goodbits)
 209 {
 210   const octet *c = p;
 211   int i, rot;
 212
 213 #if RAND_POOLSZ != 128
 214 #  error Polynomial in rand_add is out of date.  Fix it.
 215 #endif
 216
 217   RAND_RESOLVE(r);
 218
 219   i = r->i; rot = r->irot;
 220
 221   while (sz) {
 222     octet o = *c++;
 223     r->pool[i] ^= (ROL8(o, rot) ^
 224                    r->pool[(i + 1) % RAND_POOLSZ] ^
 225                    r->pool[(i + 2) % RAND_POOLSZ] ^
 226                    r->pool[(i + 7) % RAND_POOLSZ]);
 227     rot = (rot + 5) & 7;
 228     i++; if (i >= RAND_POOLSZ) i -= RAND_POOLSZ;
 229     sz--;
 230   }
 231
 232   r->i = i;
 233   r->irot = rot;
 234   r->ibits += goodbits;
 235   if (r->ibits > RAND_IBITS)
 236     r->ibits = RAND_IBITS;
 237 }
 238
 239 /* --- @rand_goodbits@ --- *
 240  *
 241  * Arguments:   @rand_pool *r@ = pointer to a randomness pool
 242  *
 243  * Returns:     Estimate of the number of good bits remaining in the pool.
 244  */
 245
 246 unsigned rand_goodbits(rand_pool *r)
 247 {
 248   RAND_RESOLVE(r);
 249   return (r->ibits + r->obits);
 250 }
 251
 252 /* --- @rand_gate@ --- *
 253  *
 254  * Arguments:   @rand_pool *r@ = pointer to a randomness pool
 255  *
 256  * Returns:     ---
 257  *
 258  * Use:         Mixes up the entire state of the generator in a nonreversible
 259  *              way.
 260  */
 261
 262 void rand_gate(rand_pool *r)
 263 {
 264   octet h[HASH_SZ];
 265   HASH_CTX hc;
 266   CIPHER_CTX cc;
 267
 268   RAND_RESOLVE(r);
 269   TIMER(r);
 270
 271   /* --- Hash up all the data in the pool --- */
 272
 273   HASH_INIT(&hc);
 274   HASH(&hc, r->pool, RAND_POOLSZ);
 275   HASH(&hc, r->buf, RAND_BUFSZ);
 276   HASH_DONE(&hc, h);
 277   BURN(hc);
 278
 279   /* --- Now mangle all of the data based on the hash --- */
 280
 281   assert(CIPHER_KEYSZ <= HASH_SZ);
 282   CIPHER_INIT(&cc, h, CIPHER_KEYSZ, 0);
 283   CIPHER_ENCRYPT(&cc, r->pool, r->pool, RAND_POOLSZ);
 284   CIPHER_ENCRYPT(&cc, r->buf, r->buf, RAND_BUFSZ);
 285   BURN(cc);
 286
 287   /* --- Reset the various state variables --- */
 288
 289   r->o = RAND_SECSZ;
 290   r->obits += r->ibits;
 291   if (r->obits > RAND_OBITS) {
 292     r->ibits = r->obits - r->ibits;
 293     r->obits = RAND_OBITS;
 294   } else
 295     r->ibits = 0;
 296   TIMER(r);
 297 }
 298
 299 /* --- @rand_stretch@ --- *
 300  *
 301  * Arguments:   @rand_pool *r@ = pointer to a randomness pool
 302  *
 303  * Returns:     ---
 304  *
 305  * Use:         Stretches the contents of the output buffer by transforming
 306  *              it in a nonreversible way.  This doesn't add any entropy
 307  *              worth speaking about, but it works well enough when the
 308  *              caller doesn't care about that sort of thing.
 309  */
 310
 311 void rand_stretch(rand_pool *r)
 312 {
 313   octet h[HASH_SZ];
 314   HASH_CTX hc;
 315   CIPHER_CTX cc;
 316
 317   RAND_RESOLVE(r);
 318   TIMER(r);
 319
 320   /* --- Hash up all the data in the buffer --- */
 321
 322   HASH_INIT(&hc);
 323   HASH(&hc, r->pool, RAND_POOLSZ);
 324   HASH(&hc, r->buf, RAND_BUFSZ);
 325   HASH_DONE(&hc, h);
 326   BURN(hc);
 327
 328   /* --- Now mangle the buffer based on the hash --- */
 329
 330   assert(CIPHER_KEYSZ <= HASH_SZ);
 331   CIPHER_INIT(&cc, h, CIPHER_KEYSZ, 0);
 332   CIPHER_ENCRYPT(&cc, r->buf, r->buf, RAND_BUFSZ);
 333   BURN(cc);
 334
 335   /* --- Reset the various state variables --- */
 336
 337   r->o = RAND_SECSZ;
 338   TIMER(r);
 339 }
 340
 341 /* --- @rand_get@ --- *
 342  *
 343  * Arguments:   @rand_pool *r@ = pointer to a randomness pool
 344  *              @void *p@ = pointer to output buffer
 345  *              @size_t sz@ = size of output buffer
 346  *
 347  * Returns:     ---
 348  *
 349  * Use:         Gets random data from the pool.  The pool's contents can't be
 350  *              determined from the output of this function; nor can the
 351  *              output data be determined from a knowledge of the data input
 352  *              to the pool wihtout also having knowledge of the secret key.
 353  *              The good bits counter is decremented, although no special
 354  *              action is taken if it reaches zero.
 355  */
 356
 357 void rand_get(rand_pool *r, void *p, size_t sz)
 358 {
 359   octet *o = p;
 360
 361   RAND_RESOLVE(r);
 362   TIMER(r);
 363
 364   if (!sz)
 365     return;
 366   for (;;) {
 367     if (r->o + sz <= RAND_BUFSZ) {
 368       memcpy(o, r->buf + r->o, sz);
 369       r->o += sz;
 370       break;
 371     } else {
 372       size_t chunk = RAND_BUFSZ - r->o;
 373       if (chunk) {
 374         memcpy(o, r->buf + r->o, chunk);
 375         sz -= chunk;
 376         o += chunk;
 377       }
 378       rand_stretch(r);
 379     }
 380   }
 381
 382   if (r->obits > sz * 8)
 383     r->obits -= sz * 8;
 384   else
 385     r->obits = 0;
 386 }
 387
 388 /* --- @rand_getgood@ --- *
 389  *
 390  * Arguments:   @rand_pool *r@ = pointer to a randomness pool
 391  *              @void *p@ = pointer to output buffer
 392  *              @size_t sz@ = size of output buffer
 393  *
 394  * Returns:     ---
 395  *
 396  * Use:         Gets random data from the pool, ensuring that there are
 397  *              enough good bits.  This interface isn't recommended: it makes
 398  *              the generator slow, and doesn't provide much more security
 399  *              than @rand_get@, assuming you've previously done a
 400  *              @rand_seed@.
 401  */
 402
 403 void rand_getgood(rand_pool *r, void *p, size_t sz)
 404 {
 405   octet *o = p;
 406
 407   RAND_RESOLVE(r);
 408
 409   if (!sz)
 410     return;
 411   if (!r->s || !r->s->getnoise) {
 412     rand_get(r, p, sz);
 413     return;
 414   }
 415   TIMER(r);
 416
 417   while (sz) {
 418     size_t chunk = sz;
 419
 420     if (chunk * 8 > r->obits) {
 421       if (chunk * 8 > r->ibits + r->obits)
 422         do r->s->getnoise(r); while (r->ibits + r->obits < 256);
 423       rand_gate(r);
 424       if (chunk * 8 > r->obits)
 425         chunk = r->obits / 8;
 426     }
 427
 428     if (chunk + r->o > RAND_BUFSZ)
 429       chunk = RAND_BUFSZ - r->o;
 430
 431     memcpy(o, r->buf + r->o, chunk);
 432     r->o += chunk;
 433     r->obits -= chunk * 8;
 434     o += chunk;
 435     sz -= chunk;
 436   }
 437 }
 438
 439 /*----- Generic random number generator interface -------------------------*/
 440
 441 static void gdestroy(grand *r)
 442 {
 443   gctx *g = (gctx *)r;
 444   if (g != &rand_global) {
 445     BURN(*g);
 446     S_DESTROY(g);
 447   }
 448 }
 449
 450 static int gmisc(grand *r, unsigned op, ...)
 451 {
 452   gctx *g = (gctx *)r;
 453   va_list ap;
 454   int rc = 0;
 455   va_start(ap, op);
 456
 457   switch (op) {
 458     case GRAND_CHECK:
 459       switch (va_arg(ap, unsigned)) {
 460         case GRAND_CHECK:
 461         case GRAND_SEEDINT:
 462         case GRAND_SEEDUINT32:
 463         case GRAND_SEEDBLOCK:
 464         case GRAND_SEEDRAND:
 465         case RAND_GATE:
 466         case RAND_STRETCH:
 467         case RAND_KEY:
 468         case RAND_NOISESRC:
 469         case RAND_SEED:
 470         case RAND_TIMER:
 471         case RAND_GOODBITS:
 472         case RAND_ADD:
 473           rc = 1;
 474           break;
 475         default:
 476           rc = 0;
 477           break;
 478       }
 479       break;
 480     case GRAND_SEEDINT: {
 481       unsigned u = va_arg(ap, unsigned);
 482       rand_add(&g->p, &u, sizeof(u), sizeof(u));
 483     } break;
 484     case GRAND_SEEDUINT32: {
 485       uint32 i = va_arg(ap, uint32);
 486       rand_add(&g->p, &i, sizeof(i), 4);
 487     } break;
 488     case GRAND_SEEDBLOCK: {
 489       const void *p = va_arg(ap, const void *);
 490       size_t sz = va_arg(ap, size_t);
 491       rand_add(&g->p, p, sz, sz);
 492     } break;
 493     case GRAND_SEEDRAND: {
 494       grand *rr = va_arg(ap, grand *);
 495       octet buf[16];
 496       rr->ops->fill(rr, buf, sizeof(buf));
 497       rand_add(&g->p, buf, sizeof(buf), 8);
 498     } break;
 499     case RAND_GATE:
 500       rand_gate(&g->p);
 501       break;
 502     case RAND_STRETCH:
 503       rand_stretch(&g->p);
 504       break;
 505     case RAND_KEY: {
 506       const void *k = va_arg(ap, const void *);
 507       size_t sz = va_arg(ap, size_t);
 508       rand_key(&g->p, k, sz);
 509     } break;
 510     case RAND_NOISESRC:
 511       rand_noisesrc(&g->p, va_arg(ap, const rand_source *));
 512       break;
 513     case RAND_SEED:
 514       rand_seed(&g->p, va_arg(ap, unsigned));
 515       break;
 516     case RAND_TIMER:
 517       TIMER(&g->p);
 518       break;
 519     case RAND_GOODBITS:
 520       rc = rand_goodbits(&g->p);
 521       break;
 522     case RAND_ADD: {
 523       const void *p = va_arg(ap, const void *);
 524       size_t sz = va_arg(ap, size_t);
 525       unsigned goodbits = va_arg(ap, unsigned);
 526       rand_add(&g->p, p, sz, goodbits);
 527     } break;
 528     default:
 529       GRAND_BADOP;
 530       break;
 531   }
 532
 533   va_end(ap);
 534   return (rc);
 535 }
 536
 537 static octet gbyte(grand *r)
 538 {
 539   gctx *g = (gctx *)r;
 540   octet o;
 541   rand_getgood(&g->p, &o, 1);
 542   return (o);
 543 }
 544
 545 static uint32 gword(grand *r)
 546 {
 547   gctx *g = (gctx *)r;
 548   octet b[4];
 549   rand_getgood(&g->p, &b, sizeof(b));
 550   return (LOAD32(b));
 551 }
 552
 553 static void gfill(grand *r, void *p, size_t sz)
 554 {
 555   gctx *g = (gctx *)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_defaultrange, gfill
 564 };
 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 -------------------------------------------------*/