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

   1 /* -*-c-*-
   2  *
   3  * Secure random number generator
   4  *
   5  * (c) 1999 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 /*----- Notes on the random number generator ------------------------------*
  29  *
  30  * The algorithm is one of the author's own devising.  It may therefore be
  31  * worth a certain amount of skepticism.  However, I've thought about this
  32  * method for over a year before actually considering it worth implementing.
  33  * With a little bit of luck, it should have received some peer review by the
  34  * time this code is actually properly released, and it'll be worth a bit
  35  * more confidence.  My earlier generator was very similar in structure to
  36  * the Linux /dev/random device.  This generator is intended to address
  37  * concerns I expressed about the Linux generator in a Usenet article to
  38  * sci.crypt.
  39  *
  40  * The generator is divided into two parts: an input pool and an output
  41  * buffer.  New random data is placed into the pool in the way described
  42  * below, which is shamelessly stolen from the Linux /dev/random generator.
  43  * The only interaction that the pool has on the output buffer is through the
  44  * keyed `gating' operation, which mixes up and redistributes all of the
  45  * generator's state in an irreversible manner.  Random bytes, when
  46  * requested, are extracted from the output buffer in a linear fashion.
  47  *
  48  * The input pool is best seen as being eight shift registers in parallel.
  49  * Data is added to the pool one octet at a time.  Each bit of a new octet is
  50  * added to a different shift register, by adding it (mod 2) with other bits
  51  * according to the coefficients of a primitive polynomial.  Each new byte is
  52  * rotated before being added into the pool, in a half-hearted attempt to
  53  * protect against biases in the input data (e.g., top bits being clear on
  54  * ASCII text).
  55  *
  56  * The gating operation takes a keyed hash of the entire generator state,
  57  * uses it as the key for a symmetric cipher, and encrypts the state.  The
  58  * key is then discarded.  The result is that every ouptut bit of the
  59  * operation depends in a complex way on every input bit, but the operation
  60  * cannot be reversed.
  61  *
  62  * As an added wrinkle, 160 bits of the output buffer are never actually
  63  * output.  They are used in the gating operation only, as an extra item that
  64  * an adversary has to guess before predicting generator output.
  65  */
  66
  67 #ifndef CATACOMB_RAND_H
  68 #define CATACOMB_RAND_H
  69
  70 #ifdef __cplusplus
  71   extern "C" {
  72 #endif
  73
  74 /*----- Header files ------------------------------------------------------*/
  75
  76 #include <stddef.h>
  77
  78 #ifndef CATACOMB_GRAND_H
  79 #  include "grand.h"
  80 #endif
  81
  82 #ifndef CATACOMB_RMD160_HMAC_H
  83 #  include "rmd160-hmac.h"
  84 #endif
  85
  86 /*----- Magic numbers -----------------------------------------------------*/
  87
  88 #define RAND_POOLSZ 128                 /* Input pool size in bytes */
  89 #define RAND_BUFSZ 512                  /* Output buffer size in bytes */
  90 #define RAND_SECSZ 20                   /* Secret octets in output buffer */
  91
  92 #define RAND_IBITS (RAND_POOLSZ * 8)
  93 #define RAND_OBITS (RAND_BUFSZ * 8)
  94
  95 /*----- Data structures ---------------------------------------------------*/
  96
  97 /* --- A random number generator pool --- */
  98
  99 typedef struct rand_pool {
 100   octet pool[RAND_POOLSZ];              /* Actual contents of the pool */
 101   unsigned i;                           /* Current index into pool */
 102   unsigned irot;                        /* Current rotation applied */
 103   unsigned ibits;                       /* Number of good bits in pool */
 104   octet buf[RAND_BUFSZ];                /* Random octet output buffer */
 105   unsigned o;                           /* Current index into buffer */
 106   unsigned obits;                       /* Number of good bits in buffer */
 107   rmd160_mackey k;                      /* Secret key for this pool */
 108   const struct rand_source *s;          /* System-specific noise source */
 109 } rand_pool;
 110
 111 #define RAND_GLOBAL ((rand_pool *)0)    /* The global randomness pool */
 112
 113 /* --- A noise source --- */
 114
 115 typedef struct rand_source {
 116   void (*getnoise)(rand_pool */*r*/);   /* Acquire more noise */
 117   int (*timer)(rand_pool */*r*/);       /* Get noise from current time */
 118 } rand_source;
 119
 120 /*----- Functions provided ------------------------------------------------*/
 121
 122 /* --- @rand_init@ --- *
 123  *
 124  * Arguments:   @rand_pool *r@ = pointer to a randomness pool
 125  *
 126  * Returns:     ---
 127  *
 128  * Use:         Initializes a randomness pool.  The pool doesn't start out
 129  *              very random: that's your job to sort out.
 130  */
 131
 132 extern void rand_init(rand_pool */*r*/);
 133
 134 /* --- @rand_noisesrc@ --- *
 135  *
 136  * Arguments:   @rand_pool *r@ = pointer to a randomness pool
 137  *              @const rand_source *s@ = pointer to source definition
 138  *
 139  * Returns:     ---
 140  *
 141  * Use:         Sets a noise source for a randomness pool.  When the pool's
 142  *              estimate of good random bits falls to zero, the @getnoise@
 143  *              function is called, passing the pool handle as an argument.
 144  *              It is expected to increase the number of good bits by at
 145  *              least one, because it'll be called over and over again until
 146  *              there are enough bits to satisfy the caller.  The @timer@
 147  *              function is called frequently throughout the generator's
 148  *              operation.
 149  */
 150
 151 extern void rand_noisesrc(rand_pool */*r*/, const rand_source */*s*/);
 152
 153 /* --- @rand_seed@ --- *
 154  *
 155  * Arguments:   @rand_pool *r@ = pointer to a randomness pool
 156  *              @unsigned bits@ = number of bits to ensure
 157  *
 158  * Returns:     ---
 159  *
 160  * Use:         Ensures that there are at least @bits@ good bits of entropy
 161  *              in the pool.  It is recommended that you call this after
 162  *              initializing a new pool.  Requesting @bits > RAND_IBITS@ is
 163  *              doomed to failure (and is an error).
 164  */
 165
 166 extern void rand_seed(rand_pool */*r*/, unsigned /*bits*/);
 167
 168 /* --- @rand_key@ --- *
 169  *
 170  * Arguments:   @rand_pool *r@ = pointer to a randomness pool
 171  *              @const void *k@ = pointer to key data
 172  *              @size_t sz@ = size of key data
 173  *
 174  * Returns:     ---
 175  *
 176  * Use:         Sets the secret key for a randomness pool.  The key is used
 177  *              when mixing in new random bits.
 178  */
 179
 180 extern void rand_key(rand_pool */*r*/, const void */*k*/, size_t /*sz*/);
 181
 182 /* --- @rand_add@ --- *
 183  *
 184  * Arguments:   @rand_pool *r@ = pointer to a randomness pool
 185  *              @const void *p@ = pointer a buffer of data to add
 186  *              @size_t sz@ = size of the data buffer
 187  *              @unsigned goodbits@ = number of good bits estimated in buffer
 188  *
 189  * Returns:     ---
 190  *
 191  * Use:         Mixes the data in the buffer with the contents of the
 192  *              pool.  The estimate of the number of good bits is added to
 193  *              the pool's own count.  The mixing operation is not
 194  *              cryptographically strong.  However, data in the input pool
 195  *              isn't output directly, only through the one-way gating
 196  *              operation, so that shouldn't matter.
 197  */
 198
 199 extern void rand_add(rand_pool */*r*/,
 200                      const void */*p*/, size_t /*sz*/,
 201                      unsigned /*goodbits*/);
 202
 203 /* --- @rand_goodbits@ --- *
 204  *
 205  * Arguments:   @rand_pool *r@ = pointer to a randomness pool
 206  *
 207  * Returns:     Estimate of the number of good bits remaining in the pool.
 208  */
 209
 210 extern unsigned rand_goodbits(rand_pool */*r*/);
 211
 212 /* --- @rand_gate@ --- *
 213  *
 214  * Arguments:   @rand_pool *r@ = pointer to a randomness pool
 215  *
 216  * Returns:     ---
 217  *
 218  * Use:         Mixes up the entire state of the generator in a nonreversible
 219  *              way.
 220  */
 221
 222 extern void rand_gate(rand_pool */*r*/);
 223
 224 /* --- @rand_stretch@ --- *
 225  *
 226  * Arguments:   @rand_pool *r@ = pointer to a randomness pool
 227  *
 228  * Returns:     ---
 229  *
 230  * Use:         Stretches the contents of the output buffer by transforming
 231  *              it in a nonreversible way.  This doesn't add any entropy
 232  *              worth speaking about, but it works well enough when the
 233  *              caller doesn't care about that sort of thing.
 234  */
 235
 236 extern void rand_stretch(rand_pool */*r*/);
 237
 238 /* --- @rand_get@ --- *
 239  *
 240  * Arguments:   @rand_pool *r@ = pointer to a randomness pool
 241  *              @void *p@ = pointer to output buffer
 242  *              @size_t sz@ = size of output buffer
 243  *
 244  * Returns:     ---
 245  *
 246  * Use:         Gets random data from the pool.  The pool's contents can't be
 247  *              determined from the output of this function; nor can the
 248  *              output data be determined from a knowledge of the data input
 249  *              to the pool without also having knowledge of the secret key.
 250  *              The good bits counter is decremented, although no special
 251  *              action is taken if it reaches zero.
 252  */
 253
 254 extern void rand_get(rand_pool */*r*/, void */*p*/, size_t /*sz*/);
 255
 256 /* --- @rand_getgood@ --- *
 257  *
 258  * Arguments:   @rand_pool *r@ = pointer to a randomness pool
 259  *              @void *p@ = pointer to output buffer
 260  *              @size_t sz@ = size of output buffer
 261  *
 262  * Returns:     ---
 263  *
 264  * Use:         Gets random data from the pool.  The pool's contents can't be
 265  *              determined from the output of this function; nor can the
 266  *              output data be determined from a knowledge of the data input
 267  *              to the pool wihtout also having knowledge of the secret key.
 268  *              If a noise source is attached to the pool in question, it is
 269  *              called to replenish the supply of good bits in the pool;
 270  *              otherwise this call is equivalent to @rand_get@.
 271  */
 272
 273 extern void rand_getgood(rand_pool */*r*/, void */*p*/, size_t /*sz*/);
 274
 275 /*----- Generic random number generator interface -------------------------*/
 276
 277 /* --- Miscellaneous operations --- */
 278
 279 enum {
 280   RAND_GATE = GRAND_SPECIFIC('R'),      /* No args */
 281   RAND_STRETCH,                         /* No args */
 282   RAND_KEY,                             /* @const void *k, size_t sz@ */
 283   RAND_NOISESRC,                        /* @const rand_source *s@ */
 284   RAND_SEED,                            /* @unsigned bits@ */
 285   RAND_TIMER,                           /* No args */
 286   RAND_GOODBITS,                        /* No args */
 287   RAND_ADD                              /* @const void *p, size_t sz,@
 288                                          * @unsigned goodbits */
 289 };
 290
 291 /* --- Default random number generator --- */
 292
 293 #ifdef RAND__HACKS
 294   extern struct rand__gctx rand_global;
 295 #else
 296   extern grand rand_global;
 297 #endif
 298
 299 /* --- @rand_create@ --- *
 300  *
 301  * Arguments:   ---
 302  *
 303  * Returns:     Pointer to a generic generator.
 304  *
 305  * Use:         Constructs a generic generator interface over a Catacomb
 306  *              entropy pool generator.
 307  */
 308
 309 extern grand *rand_create(void);
 310
 311 /*----- That's all, folks -------------------------------------------------*/
 312
 313 #ifdef __cplusplus
 314   }
 315 #endif
 316
 317 #endif