--- /dev/null
+/* -*-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
projects / u / mdw / catacomb / blobdiff