math/mpreduce.h: Missing include files.

[u/mdw/catacomb] / rand / rand.h

/* -*-c-*-
 *
 * Secure random number generator
 *
 * (c) 1999 Straylight/Edgeware
 */

/*----- Licensing notice --------------------------------------------------*
 *
 * This file is part of Catacomb.
 *
 * Catacomb is free software; you can redistribute it and/or modify
 * it under the terms of the GNU Library General Public License as
 * published by the Free Software Foundation; either version 2 of the
 * License, or (at your option) any later version.
 *
 * Catacomb is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU Library General Public License for more details.
 *
 * You should have received a copy of the GNU Library General Public
 * License along with Catacomb; if not, write to the Free
 * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
 * MA 02111-1307, USA.
 */

/*----- Notes on the random number generator ------------------------------*
 *
 * The algorithm is one of the author's own devising.  It may therefore be
 * worth a certain amount of skepticism.  However, I've thought about this
 * method for over a year before actually considering it worth implementing.
 * With a little bit of luck, it should have received some peer review by the
 * time this code is actually properly released, and it'll be worth a bit
 * more confidence.  My earlier generator was very similar in structure to
 * the Linux /dev/random device.  This generator is intended to address
 * concerns I expressed about the Linux generator in a Usenet article to
 * sci.crypt.
 *
 * The generator is divided into two parts: an input pool and an output
 * buffer.  New random data is placed into the pool in the way described
 * below, which is shamelessly stolen from the Linux /dev/random generator.
 * The only interaction that the pool has on the output buffer is through the
 * keyed `gating' operation, which mixes up and redistributes all of the
 * generator's state in an irreversible manner.  Random bytes, when
 * requested, are extracted from the output buffer in a linear fashion.
 *
 * The input pool is best seen as being eight shift registers in parallel.
 * Data is added to the pool one octet at a time.  Each bit of a new octet is
 * added to a different shift register, by adding it (mod 2) with other bits
 * according to the coefficients of a primitive polynomial.  Each new byte is
 * rotated before being added into the pool, in a half-hearted attempt to
 * protect against biases in the input data (e.g., top bits being clear on
 * ASCII text).
 *
 * The gating operation takes a keyed hash of the entire generator state,
 * uses it as the key for a symmetric cipher, and encrypts the state.  The
 * key is then discarded.  The result is that every ouptut bit of the
 * operation depends in a complex way on every input bit, but the operation
 * cannot be reversed.
 *
 * As an added wrinkle, 160 bits of the output buffer are never actually
 * output.  They are used in the gating operation only, as an extra item that
 * an adversary has to guess before predicting generator output.
 */

#ifndef CATACOMB_RAND_H
#define CATACOMB_RAND_H

#ifdef __cplusplus
  extern "C" {
#endif

/*----- Header files ------------------------------------------------------*/

#include <stddef.h>

#ifndef CATACOMB_GRAND_H
#  include "grand.h"
#endif

#ifndef CATACOMB_RMD160_HMAC_H
#  include "rmd160-hmac.h"
#endif

/*----- Magic numbers -----------------------------------------------------*/

#define RAND_POOLSZ 128                 /* Input pool size in bytes */
#define RAND_BUFSZ 512                  /* Output buffer size in bytes */
#define RAND_SECSZ 20                   /* Secret octets in output buffer */

#define RAND_IBITS (RAND_POOLSZ * 8)
#define RAND_OBITS (RAND_BUFSZ * 8)

/*----- Data structures ---------------------------------------------------*/

/* --- A random number generator pool --- */

typedef struct rand_pool {
  octet pool[RAND_POOLSZ];              /* Actual contents of the pool */
  unsigned i;                           /* Current index into pool */
  unsigned irot;                        /* Current rotation applied */
  unsigned ibits;                       /* Number of good bits in pool */
  octet buf[RAND_BUFSZ];                /* Random octet output buffer */
  unsigned o;                           /* Current index into buffer */
  unsigned obits;                       /* Number of good bits in buffer */
  rmd160_mackey k;                      /* Secret key for this pool */
  const struct rand_source *s;          /* System-specific noise source */
} rand_pool;

#define RAND_GLOBAL ((rand_pool *)0)    /* The global randomness pool */

/* --- A noise source --- */

typedef struct rand_source {
  void (*getnoise)(rand_pool */*r*/);   /* Acquire more noise */
  int (*timer)(rand_pool */*r*/);       /* Get noise from current time */
} rand_source;

/*----- Functions provided ------------------------------------------------*/

/* --- @rand_init@ --- *
 *
 * Arguments:   @rand_pool *r@ = pointer to a randomness pool
 *
 * Returns:     ---
 *
 * Use:         Initializes a randomness pool.  The pool doesn't start out
 *              very random: that's your job to sort out.
 */

extern void rand_init(rand_pool */*r*/);

/* --- @rand_noisesrc@ --- *
 *
 * Arguments:   @rand_pool *r@ = pointer to a randomness pool
 *              @const rand_source *s@ = pointer to source definition
 *
 * Returns:     ---
 *
 * Use:         Sets a noise source for a randomness pool.  When the pool's
 *              estimate of good random bits falls to zero, the @getnoise@
 *              function is called, passing the pool handle as an argument.
 *              It is expected to increase the number of good bits by at
 *              least one, because it'll be called over and over again until
 *              there are enough bits to satisfy the caller.  The @timer@
 *              function is called frequently throughout the generator's
 *              operation.
 */

extern void rand_noisesrc(rand_pool */*r*/, const rand_source */*s*/);

/* --- @rand_seed@ --- *
 *
 * Arguments:   @rand_pool *r@ = pointer to a randomness pool
 *              @unsigned bits@ = number of bits to ensure
 *
 * Returns:     ---
 *
 * Use:         Ensures that there are at least @bits@ good bits of entropy
 *              in the pool.  It is recommended that you call this after
 *              initializing a new pool.  Requesting @bits > RAND_IBITS@ is
 *              doomed to failure (and is an error).
 */

extern void rand_seed(rand_pool */*r*/, unsigned /*bits*/);

/* --- @rand_key@ --- *
 *
 * Arguments:   @rand_pool *r@ = pointer to a randomness pool
 *              @const void *k@ = pointer to key data
 *              @size_t sz@ = size of key data
 *
 * Returns:     ---
 *
 * Use:         Sets the secret key for a randomness pool.  The key is used
 *              when mixing in new random bits.
 */

extern void rand_key(rand_pool */*r*/, const void */*k*/, size_t /*sz*/);

/* --- @rand_add@ --- *
 *
 * Arguments:   @rand_pool *r@ = pointer to a randomness pool
 *              @const void *p@ = pointer a buffer of data to add
 *              @size_t sz@ = size of the data buffer
 *              @unsigned goodbits@ = number of good bits estimated in buffer
 *
 * Returns:     ---
 *
 * Use:         Mixes the data in the buffer with the contents of the
 *              pool.  The estimate of the number of good bits is added to
 *              the pool's own count.  The mixing operation is not
 *              cryptographically strong.  However, data in the input pool
 *              isn't output directly, only through the one-way gating
 *              operation, so that shouldn't matter.
 */

extern void rand_add(rand_pool */*r*/,
                     const void */*p*/, size_t /*sz*/,
                     unsigned /*goodbits*/);

/* --- @rand_goodbits@ --- *
 *
 * Arguments:   @rand_pool *r@ = pointer to a randomness pool
 *
 * Returns:     Estimate of the number of good bits remaining in the pool.
 */

extern unsigned rand_goodbits(rand_pool */*r*/);

/* --- @rand_gate@ --- *
 *
 * Arguments:   @rand_pool *r@ = pointer to a randomness pool
 *
 * Returns:     ---
 *
 * Use:         Mixes up the entire state of the generator in a nonreversible
 *              way.
 */

extern void rand_gate(rand_pool */*r*/);

/* --- @rand_stretch@ --- *
 *
 * Arguments:   @rand_pool *r@ = pointer to a randomness pool
 *
 * Returns:     ---
 *
 * Use:         Stretches the contents of the output buffer by transforming
 *              it in a nonreversible way.  This doesn't add any entropy
 *              worth speaking about, but it works well enough when the
 *              caller doesn't care about that sort of thing.
 */

extern void rand_stretch(rand_pool */*r*/);

/* --- @rand_get@ --- *
 *
 * Arguments:   @rand_pool *r@ = pointer to a randomness pool
 *              @void *p@ = pointer to output buffer
 *              @size_t sz@ = size of output buffer
 *
 * Returns:     ---
 *
 * Use:         Gets random data from the pool.  The pool's contents can't be
 *              determined from the output of this function; nor can the
 *              output data be determined from a knowledge of the data input
 *              to the pool without also having knowledge of the secret key.
 *              The good bits counter is decremented, although no special
 *              action is taken if it reaches zero.
 */

extern void rand_get(rand_pool */*r*/, void */*p*/, size_t /*sz*/);

/* --- @rand_getgood@ --- *
 *
 * Arguments:   @rand_pool *r@ = pointer to a randomness pool
 *              @void *p@ = pointer to output buffer
 *              @size_t sz@ = size of output buffer
 *
 * Returns:     ---
 *
 * Use:         Gets random data from the pool.  The pool's contents can't be
 *              determined from the output of this function; nor can the
 *              output data be determined from a knowledge of the data input
 *              to the pool wihtout also having knowledge of the secret key.
 *              If a noise source is attached to the pool in question, it is
 *              called to replenish the supply of good bits in the pool;
 *              otherwise this call is equivalent to @rand_get@.
 */

extern void rand_getgood(rand_pool */*r*/, void */*p*/, size_t /*sz*/);

/*----- Generic random number generator interface -------------------------*/

/* --- Miscellaneous operations --- */

enum {
  RAND_GATE = GRAND_SPECIFIC('R'),      /* No args */
  RAND_STRETCH,                         /* No args */
  RAND_KEY,                             /* @const void *k, size_t sz@ */
  RAND_NOISESRC,                        /* @const rand_source *s@ */
  RAND_SEED,                            /* @unsigned bits@ */
  RAND_TIMER,                           /* No args */
  RAND_GOODBITS,                        /* No args */
  RAND_ADD                              /* @const void *p, size_t sz,@
                                         * @unsigned goodbits */
};

/* --- Default random number generator --- */

extern grand rand_global;

/* --- @rand_create@ --- *
 *
 * Arguments:   ---
 *
 * Returns:     Pointer to a generic generator.
 *
 * Use:         Constructs a generic generator interface over a Catacomb
 *              entropy pool generator.
 */

extern grand *rand_create(void);

/*----- That's all, folks -------------------------------------------------*/

#ifdef __cplusplus
  }
#endif

#endif