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

   1 /* -*-c-*-
   2  *
   3  * $Id: rand.c,v 1.1 1999/09/03 08:41:12 mdw Exp $
   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 /*----- Revision history --------------------------------------------------*
  31  *
  32  * $Log: rand.c,v $
  33  * Revision 1.1  1999/09/03 08:41:12  mdw
  34  * Initial import.
  35  *
  36  */
  37
  38 /*----- Header files ------------------------------------------------------*/
  39
  40 #include <stdio.h>
  41 #include <string.h>
  42
  43 #include <mLib/bits.h>
  44
  45 #include "blowfish-cbc.h"
  46 #include "paranoia.h"
  47 #include "rand.h"
  48 #include "rmd160.h"
  49 #include "rmd160-hmac.h"
  50
  51 /*----- Static variables --------------------------------------------------*/
  52
  53 static rand_pool pool;          /* Default random pool */
  54
  55 /*----- Macros ------------------------------------------------------------*/
  56
  57 #define RAND_RESOLVE(r) do {                                            \
  58   if ((r) == RAND_GLOBAL)                                               \
  59     (r) = &pool;                                                        \
  60 } while (0)
  61
  62 #define TIMER(r) do {                                                   \
  63   if ((r)->s && (r)->s->timer)                                          \
  64     (r)->s->timer(r);                                                   \
  65 } while (0)
  66
  67 /*----- Main code ---------------------------------------------------------*/
  68
  69 /* --- @rand_init@ --- *
  70  *
  71  * Arguments:   @rand_pool *r@ = pointer to a randomness pool
  72  *
  73  * Returns:     ---
  74  *
  75  * Use:         Initializes a randomness pool.  The pool doesn't start out
  76  *              very random: that's your job to sort out.
  77  */
  78
  79 void rand_init(rand_pool *r)
  80 {
  81   RAND_RESOLVE(r);
  82   memset(r->pool, 0, sizeof(r->pool));
  83   memset(r->buf, 0, sizeof(r->buf));
  84   r->i = 0;
  85   r->irot = 0;
  86   r->ibits = r->obits = 0;
  87   r->o = RAND_SECSZ;
  88   r->s = 0;
  89   rmd160_hmac(&r->k, 0, 0);
  90   rand_gate(r);
  91 }
  92
  93 /* --- @rand_noisesrc@ --- *
  94  *
  95  * Arguments:   @rand_pool *r@ = pointer to a randomness pool
  96  *              @const rand_source *s@ = pointer to source definition
  97  *
  98  * Returns:     ---
  99  *
 100  * Use:         Sets a noise source for a randomness pool.  When the pool's
 101  *              estimate of good random bits falls to zero, the @getnoise@
 102  *              function is called, passing the pool handle as an argument.
 103  *              It is expected to increase the number of good bits by at
 104  *              least one, because it'll be called over and over again until
 105  *              there are enough bits to satisfy the caller.  The @timer@
 106  *              function is called frequently throughout the generator's
 107  *              operation.
 108  */
 109
 110 void rand_noisesrc(rand_pool *r, const rand_source *s)
 111 {
 112   RAND_RESOLVE(r);
 113   r->s = s;
 114 }
 115
 116 /* --- @rand_key@ --- *
 117  *
 118  * Arguments:   @rand_pool *r@ = pointer to a randomness pool
 119  *              @const void *k@ = pointer to key data
 120  *              @size_t sz@ = size of key data
 121  *
 122  * Returns:     ---
 123  *
 124  * Use:         Sets the secret key for a randomness pool.  The key is used
 125  *              when mixing in new random bits.
 126  */
 127
 128 void rand_key(rand_pool *r, const void *k, size_t sz)
 129 {
 130   RAND_RESOLVE(r);
 131   rmd160_hmac(&r->k, k, sz);
 132 }
 133
 134 /* --- @rand_add@ --- *
 135  *
 136  * Arguments:   @rand_pool *r@ = pointer to a randomness pool
 137  *              @const void *p@ = pointer a buffer of data to add
 138  *              @size_t sz@ = size of the data buffer
 139  *              @unsigned goodbits@ = number of good bits estimated in buffer
 140  *
 141  * Returns:     ---
 142  *
 143  * Use:         Mixes the data in the buffer with the contents of the
 144  *              pool.  The estimate of the number of good bits is added to
 145  *              the pool's own count.  The mixing operation is not
 146  *              cryptographically strong.  However, data in the input pool
 147  *              isn't output directly, only through the one-way gating
 148  *              operation, so that shouldn't matter.
 149  */
 150
 151 void rand_add(rand_pool *r, const void *p, size_t sz, unsigned goodbits)
 152 {
 153   const octet *c = p;
 154   int i, rot, mid;
 155
 156 #if RAND_POOLSZ != 1279
 157 #  error Polynomial in rand_add is out of date.  Fix it.
 158 #endif
 159
 160   RAND_RESOLVE(r);
 161
 162   i = r->i; rot = r->irot; mid = i + 418;
 163   if (mid >= RAND_POOLSZ) mid -= RAND_POOLSZ;
 164
 165   while (sz) {
 166     octet o = *c++;
 167     r->pool[i] ^= (ROL8(o, rot) ^ r->pool[mid]);
 168     rot = (rot + 5) & 7;
 169     i++; if (i >= RAND_POOLSZ) i -= RAND_POOLSZ;
 170     mid++; if (mid >= RAND_POOLSZ) mid -= RAND_POOLSZ;
 171     sz--;
 172   }
 173
 174   r->i = i;
 175   r->irot = rot;
 176   r->ibits += goodbits;
 177   if (r->ibits > RAND_IBITS)
 178     r->ibits = RAND_IBITS;
 179 }
 180
 181 /* --- @rand_goodbits@ --- *
 182  *
 183  * Arguments:   @rand_pool *r@ = pointer to a randomness pool
 184  *
 185  * Returns:     Estimate of the number of good bits remaining in the pool.
 186  */
 187
 188 unsigned rand_goodbits(rand_pool *r)
 189 {
 190   RAND_RESOLVE(r);
 191   return (r->ibits + r->obits);
 192 }
 193
 194 /* --- @rand_gate@ --- *
 195  *
 196  * Arguments:   @rand_pool *r@ = pointer to a randomness pool
 197  *
 198  * Returns:     ---
 199  *
 200  * Use:         Mixes up the entire state of the generator in a nonreversible
 201  *              way.
 202  */
 203
 204 void rand_gate(rand_pool *r)
 205 {
 206   octet mac[RMD160_HASHSZ];
 207
 208   RAND_RESOLVE(r);
 209   TIMER(r);
 210
 211   /* --- Hash up all the data in the pool --- */
 212
 213   {
 214     rmd160_macctx mc;
 215
 216     rmd160_macinit(&mc, &r->k);
 217     rmd160_mac(&mc, r->pool, sizeof(r->pool));
 218     rmd160_mac(&mc, r->buf, sizeof(r->buf));
 219     rmd160_macdone(&mc, mac);
 220     BURN(mc);
 221   }
 222
 223   /* --- Now mangle all of the data based on the hash --- */
 224
 225   {
 226     blowfish_cbcctx bc;
 227
 228     blowfish_cbcinit(&bc, mac, sizeof(mac), 0);
 229     blowfish_cbcencrypt(&bc, r->pool, r->pool, sizeof(r->pool));
 230     blowfish_cbcencrypt(&bc, r->buf, r->buf, sizeof(r->buf));
 231     BURN(bc);
 232   }
 233
 234   /* --- Reset the various state variables --- */
 235
 236   r->o = RAND_SECSZ;
 237   r->obits += r->ibits;
 238   if (r->obits > RAND_OBITS) {
 239     r->ibits = r->obits - r->ibits;
 240     r->obits = RAND_OBITS;
 241   } else
 242     r->ibits = 0;
 243   TIMER(r);
 244 }
 245
 246 /* --- @rand_stretch@ --- *
 247  *
 248  * Arguments:   @rand_pool *r@ = pointer to a randomness pool
 249  *
 250  * Returns:     ---
 251  *
 252  * Use:         Stretches the contents of the output buffer by transforming
 253  *              it in a nonreversible way.  This doesn't add any entropy
 254  *              worth speaking about, but it works well enough when the
 255  *              caller doesn't care about that sort of thing.
 256  */
 257
 258 void rand_stretch(rand_pool *r)
 259 {
 260   octet mac[RMD160_HASHSZ];
 261
 262   RAND_RESOLVE(r);
 263   TIMER(r);
 264
 265   /* --- Hash up all the data in the buffer --- */
 266
 267   {
 268     rmd160_macctx mc;
 269
 270     rmd160_macinit(&mc, &r->k);
 271     rmd160_mac(&mc, r->pool, sizeof(r->pool));
 272     rmd160_mac(&mc, r->buf, sizeof(r->buf));
 273     rmd160_macdone(&mc, mac);
 274     BURN(mc);
 275   }
 276
 277   /* --- Now mangle the buffer based on that hash --- */
 278
 279   {
 280     blowfish_cbcctx bc;
 281
 282     blowfish_cbcinit(&bc, mac, sizeof(mac), 0);
 283     blowfish_cbcencrypt(&bc, r->buf, r->buf, sizeof(r->buf));
 284     BURN(bc);
 285   }
 286
 287   /* --- Reset the various state variables --- */
 288
 289   r->o = RAND_SECSZ;
 290   TIMER(r);
 291 }
 292
 293 /* --- @rand_get@ --- *
 294  *
 295  * Arguments:   @rand_pool *r@ = pointer to a randomness pool
 296  *              @void *p@ = pointer to output buffer
 297  *              @size_t sz@ = size of output buffer
 298  *
 299  * Returns:     ---
 300  *
 301  * Use:         Gets random data from the pool.  The pool's contents can't be
 302  *              determined from the output of this function; nor can the
 303  *              output data be determined from a knowledge of the data input
 304  *              to the pool wihtout also having knowledge of the secret key.
 305  *              The good bits counter is decremented, although no special
 306  *              action is taken if it reaches zero.
 307  */
 308
 309 void rand_get(rand_pool *r, void *p, size_t sz)
 310 {
 311   octet *o = p;
 312
 313   RAND_RESOLVE(r);
 314   TIMER(r);
 315
 316   if (!sz)
 317     return;
 318   for (;;) {
 319     if (r->o + sz <= RAND_BUFSZ) {
 320       memcpy(o, r->buf + r->o, sz);
 321       r->o += sz;
 322       break;
 323     } else {
 324       size_t chunk = RAND_BUFSZ - r->o;
 325       if (chunk) {
 326         memcpy(o, r->buf + r->o, chunk);
 327         sz -= chunk;
 328         o += chunk;
 329       }
 330       rand_stretch(r);
 331     }
 332   }
 333
 334   if (r->obits > sz * 8)
 335     r->obits -= sz * 8;
 336   else
 337     r->obits = 0;
 338 }
 339
 340 /* --- @rand_getgood@ --- *
 341  *
 342  * Arguments:   @rand_pool *r@ = pointer to a randomness pool
 343  *              @void *p@ = pointer to output buffer
 344  *              @size_t sz@ = size of output buffer
 345  *
 346  * Returns:     ---
 347  *
 348  * Use:         Gets random data from the pool.  The pool's contents can't be
 349  *              determined from the output of this function; nor can the
 350  *              output data be determined from a knowledge of the data input
 351  *              to the pool wihtout also having knowledge of the secret key.
 352  *              If a noise source is attached to the pool in question, it is
 353  *              called to replenish the supply of good bits in the pool;
 354  *              otherwise this call is equivalent to @rand_get@.
 355  */
 356
 357 void rand_getgood(rand_pool *r, void *p, size_t sz)
 358 {
 359   octet *o = p;
 360
 361   RAND_RESOLVE(r);
 362
 363   if (!sz)
 364     return;
 365   if (!r->s || !r->s->getnoise) {
 366     rand_get(r, p, sz);
 367     return;
 368   }
 369   TIMER(r);
 370
 371   while (sz) {
 372     size_t chunk = sz;
 373
 374     if (chunk * 8 > r->obits) {
 375       if (chunk * 8 > r->ibits + r->obits)
 376         do r->s->getnoise(r); while (r->ibits + r->obits < 128);
 377       rand_gate(r);
 378       if (chunk * 8 > r->obits)
 379         chunk = r->obits / 8;
 380     }
 381
 382     if (chunk + r->o > RAND_BUFSZ)
 383       chunk = RAND_BUFSZ - r->o;
 384
 385     memcpy(o, r->buf + r->o, chunk);
 386     r->obits -= chunk * 8;
 387     o += chunk;
 388     sz -= chunk;
 389   }
 390 }
 391
 392 /*----- That's all, folks -------------------------------------------------*/