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