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