X-Git-Url: https://git.distorted.org.uk/u/mdw/catacomb/blobdiff_plain/ba6e6b64033b1f9de49feccb5c9cd438354481f7..0f00dc4c8eb47e67bc0f148c2dd109f73a451e0a:/rand/rand.h diff --git a/rand/rand.h b/rand/rand.h new file mode 100644 index 0000000..a024c0f --- /dev/null +++ b/rand/rand.h @@ -0,0 +1,313 @@ +/* -*-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 + +#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