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 32                   /* Secret octets in output buffer */
  91 #define RAND_KEYSZ 32                   /* Recommended random key size */
  92
  93 #define RAND_IBITS (RAND_POOLSZ * 8)
  94 #define RAND_OBITS (RAND_BUFSZ * 8)
  95
  96 /*----- Data structures ---------------------------------------------------*/
  97
  98 /* --- A random number generator pool --- */
  99
 100 typedef struct rand_pool {
 101   octet pool[RAND_POOLSZ];              /* Actual contents of the pool */
 102   unsigned gen;                         /* Generation number */
 103   unsigned short i;                     /* Current index into pool */
 104   unsigned short irot;                  /* Current rotation applied */
 105   unsigned ibits;                       /* Number of good bits in pool */
 106   octet buf[RAND_BUFSZ];                /* Random octet output buffer */
 107   unsigned o;                           /* Current index into buffer */
 108   unsigned obits;                       /* Number of good bits in buffer */
 109   union { octet k[RAND_KEYSZ]; rmd160_mackey _; } k; /* Key for the pool */
 110   const struct rand_source *s;          /* System-specific noise source */
 111 } rand_pool;
 112
 113 #define RAND_GLOBAL ((rand_pool *)0)    /* The global randomness pool */
 114
 115 /* --- A noise source --- */
 116
 117 typedef struct rand_source {
 118   void (*getnoise)(rand_pool */*r*/);   /* Acquire more noise */
 119   int (*timer)(rand_pool */*r*/);       /* Get noise from current time */
 120 } rand_source;
 121
 122 /*----- Functions provided ------------------------------------------------*/
 123
 124 /* --- @rand_init@ --- *
 125  *
 126  * Arguments:   @rand_pool *r@ = pointer to a randomness pool
 127  *
 128  * Returns:     ---
 129  *
 130  * Use:         Initializes a randomness pool.  The pool doesn't start out
 131  *              very random: that's your job to sort out.
 132  */
 133
 134 extern void rand_init(rand_pool */*r*/);
 135
 136 /* --- @rand_generation@ --- *
 137  *
 138  * Arguments:   ---
 139  *
 140  * Returns:     A nonzero generation number.
 141  *
 142  * Use:         Returns a generation number for the current process.  Each
 143  *              pool has its own number.  If this matches the process number
 144  *              then all is well.  If it doesn't match, then the pool needs
 145  *              to be cleaned before its next use.
 146  */
 147
 148 extern unsigned rand_generation(void);
 149
 150 /* --- @rand_noisesrc@ --- *
 151  *
 152  * Arguments:   @rand_pool *r@ = pointer to a randomness pool
 153  *              @const rand_source *s@ = pointer to source definition
 154  *
 155  * Returns:     ---
 156  *
 157  * Use:         Sets a noise source for a randomness pool.  When the pool's
 158  *              estimate of good random bits falls to zero, the @getnoise@
 159  *              function is called, passing the pool handle as an argument.
 160  *              It is expected to increase the number of good bits by at
 161  *              least one, because it'll be called over and over again until
 162  *              there are enough bits to satisfy the caller.  The @timer@
 163  *              function is called frequently throughout the generator's
 164  *              operation.
 165  */
 166
 167 extern void rand_noisesrc(rand_pool */*r*/, const rand_source */*s*/);
 168
 169 /* --- @rand_seed@ --- *
 170  *
 171  * Arguments:   @rand_pool *r@ = pointer to a randomness pool
 172  *              @unsigned bits@ = number of bits to ensure
 173  *
 174  * Returns:     ---
 175  *
 176  * Use:         Ensures that there are at least @bits@ good bits of entropy
 177  *              in the pool.  It is recommended that you call this after
 178  *              initializing a new pool.  Requesting @bits > RAND_IBITS@ is
 179  *              doomed to failure (and is an error).
 180  */
 181
 182 extern void rand_seed(rand_pool */*r*/, unsigned /*bits*/);
 183
 184 /* --- @rand_key@ --- *
 185  *
 186  * Arguments:   @rand_pool *r@ = pointer to a randomness pool
 187  *              @const void *k@ = pointer to key data
 188  *              @size_t sz@ = size of key data
 189  *
 190  * Returns:     ---
 191  *
 192  * Use:         Sets the secret key for a randomness pool.  The key is used
 193  *              when mixing in new random bits.
 194  */
 195
 196 extern void rand_key(rand_pool */*r*/, const void */*k*/, size_t /*sz*/);
 197
 198 /* --- @rand_quick@ --- *
 199  *
 200  * Arguments:   @rand_pool *r@ = pointer to a randomness pool
 201  *
 202  * Returns:     Zero on success; @-1@ on failure.
 203  *
 204  * Use          Attempts to use some machine-specific `quick' source of
 205  *              entropy to top up @r@.  This may not do anything at all on
 206  *              many systems.
 207  */
 208
 209 extern int rand_quick(rand_pool */*r*/);
 210
 211 /* --- @rand_add@ --- *
 212  *
 213  * Arguments:   @rand_pool *r@ = pointer to a randomness pool
 214  *              @const void *p@ = pointer a buffer of data to add
 215  *              @size_t sz@ = size of the data buffer
 216  *              @unsigned goodbits@ = number of good bits estimated in buffer
 217  *
 218  * Returns:     ---
 219  *
 220  * Use:         Mixes the data in the buffer with the contents of the
 221  *              pool.  The estimate of the number of good bits is added to
 222  *              the pool's own count.  The mixing operation is not
 223  *              cryptographically strong.  However, data in the input pool
 224  *              isn't output directly, only through the one-way gating
 225  *              operation, so that shouldn't matter.
 226  */
 227
 228 extern void rand_add(rand_pool */*r*/,
 229                      const void */*p*/, size_t /*sz*/,
 230                      unsigned /*goodbits*/);
 231
 232 /* --- @rand_goodbits@ --- *
 233  *
 234  * Arguments:   @rand_pool *r@ = pointer to a randomness pool
 235  *
 236  * Returns:     Estimate of the number of good bits remaining in the pool.
 237  */
 238
 239 extern unsigned rand_goodbits(rand_pool */*r*/);
 240
 241 /* --- @rand_gate@ --- *
 242  *
 243  * Arguments:   @rand_pool *r@ = pointer to a randomness pool
 244  *
 245  * Returns:     ---
 246  *
 247  * Use:         Mixes up the entire state of the generator in a nonreversible
 248  *              way.
 249  */
 250
 251 extern void rand_gate(rand_pool */*r*/);
 252
 253 /* --- @rand_stretch@ --- *
 254  *
 255  * Arguments:   @rand_pool *r@ = pointer to a randomness pool
 256  *
 257  * Returns:     ---
 258  *
 259  * Use:         Stretches the contents of the output buffer by transforming
 260  *              it in a nonreversible way.  This doesn't add any entropy
 261  *              worth speaking about, but it works well enough when the
 262  *              caller doesn't care about that sort of thing.
 263  */
 264
 265 extern void rand_stretch(rand_pool */*r*/);
 266
 267 /* --- @rand_get@ --- *
 268  *
 269  * Arguments:   @rand_pool *r@ = pointer to a randomness pool
 270  *              @void *p@ = pointer to output buffer
 271  *              @size_t sz@ = size of output buffer
 272  *
 273  * Returns:     ---
 274  *
 275  * Use:         Gets random data from the pool.  The pool's contents can't be
 276  *              determined from the output of this function; nor can the
 277  *              output data be determined from a knowledge of the data input
 278  *              to the pool without also having knowledge of the secret key.
 279  *              The good bits counter is decremented, although no special
 280  *              action is taken if it reaches zero.
 281  */
 282
 283 extern void rand_get(rand_pool */*r*/, void */*p*/, size_t /*sz*/);
 284
 285 /* --- @rand_getgood@ --- *
 286  *
 287  * Arguments:   @rand_pool *r@ = pointer to a randomness pool
 288  *              @void *p@ = pointer to output buffer
 289  *              @size_t sz@ = size of output buffer
 290  *
 291  * Returns:     ---
 292  *
 293  * Use:         Gets random data from the pool.  The pool's contents can't be
 294  *              determined from the output of this function; nor can the
 295  *              output data be determined from a knowledge of the data input
 296  *              to the pool wihtout also having knowledge of the secret key.
 297  *              If a noise source is attached to the pool in question, it is
 298  *              called to replenish the supply of good bits in the pool;
 299  *              otherwise this call is equivalent to @rand_get@.
 300  */
 301
 302 extern void rand_getgood(rand_pool */*r*/, void */*p*/, size_t /*sz*/);
 303
 304 /*----- Generic random number generator interface -------------------------*/
 305
 306 /* --- Miscellaneous operations --- */
 307
 308 enum {
 309   RAND_GATE = GRAND_SPECIFIC('R'),      /* No args */
 310   RAND_STRETCH,                         /* No args */
 311   RAND_KEY,                             /* @const void *k, size_t sz@ */
 312   RAND_NOISESRC,                        /* @const rand_source *s@ */
 313   RAND_SEED,                            /* @unsigned bits@ */
 314   RAND_TIMER,                           /* No args */
 315   RAND_GOODBITS,                        /* No args */
 316   RAND_ADD                              /* @const void *p, size_t sz,@
 317                                          * @unsigned goodbits */
 318 };
 319
 320 /* --- Default random number generator --- */
 321
 322 #ifdef RAND__HACKS
 323   extern struct rand__gctx rand_global;
 324 #else
 325   extern grand rand_global;
 326 #endif
 327
 328 /* --- @rand_create@ --- *
 329  *
 330  * Arguments:   ---
 331  *
 332  * Returns:     Pointer to a generic generator.
 333  *
 334  * Use:         Constructs a generic generator interface over a Catacomb
 335  *              entropy pool generator.
 336  */
 337
 338 extern grand *rand_create(void);
 339
 340 /*----- That's all, folks -------------------------------------------------*/
 341
 342 #ifdef __cplusplus
 343   }
 344 #endif
 345
 346 #endif