3 * $Id: rand.h,v 1.8 2001/02/03 16:07:33 mdw Exp $
5 * Secure random number generator
7 * (c) 1999 Straylight/Edgeware
10 /*----- Licensing notice --------------------------------------------------*
12 * This file is part of Catacomb.
14 * Catacomb is free software; you can redistribute it and/or modify
15 * it under the terms of the GNU Library General Public License as
16 * published by the Free Software Foundation; either version 2 of the
17 * License, or (at your option) any later version.
19 * Catacomb is distributed in the hope that it will be useful,
20 * but WITHOUT ANY WARRANTY; without even the implied warranty of
21 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
22 * GNU Library General Public License for more details.
24 * You should have received a copy of the GNU Library General Public
25 * License along with Catacomb; if not, write to the Free
26 * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
30 /*----- Revision history --------------------------------------------------*
33 * Revision 1.8 2001/02/03 16:07:33 mdw
34 * Give generic random objects separate namespaces for their supported misc
37 * Revision 1.7 2000/10/08 12:07:18 mdw
38 * Remove spurious comma in enum.
40 * Revision 1.6 2000/06/17 11:53:38 mdw
41 * Deprecate `rand_getgood'. Provide a new interface to ensure that a pool
44 * Revision 1.5 1999/12/13 15:34:15 mdw
47 * Revision 1.4 1999/12/10 23:29:48 mdw
48 * Change header file guard names.
50 * Revision 1.3 1999/10/15 21:04:30 mdw
51 * Increase output buffer a bit for performance.
53 * Revision 1.2 1999/10/12 21:00:15 mdw
54 * Make pool and buffer sizes more sensible.
56 * Revision 1.1 1999/09/03 08:41:12 mdw
61 /*----- Notes on the random number generator ------------------------------*
63 * The algorithm is one of the author's own devising. It may therefore be
64 * worth a certain amount of skepticism. However, I've thought about this
65 * method for over a year before actually considering it worth implementing.
66 * With a little bit of luck, it should have received some peer review by the
67 * time this code is actually properly released, and it'll be worth a bit
68 * more confidence. My earlier generator was very similar in structure to
69 * the Linux /dev/random device. This generator is intended to address
70 * concerns I expressed about the Linux generator in a Usenet article to
73 * The generator is divided into two parts: an input pool and an output
74 * buffer. New random data is placed into the pool in the way described
75 * below, which is shamelessly stolen from the Linux /dev/random generator.
76 * The only interaction that the pool has on the output buffer is through the
77 * keyed `gating' operation, which mixes up and redistributes all of the
78 * generator's state in an irreversible manner. Random bytes, when
79 * requested, are extracted from the output buffer in a linear fashion.
81 * The input pool is best seen as being eight shift registers in parallel.
82 * Data is added to the pool one octet at a time. Each bit of a new octet is
83 * added to a different shift register, by adding it (mod 2) with other bits
84 * according to the coefficients of a primitive polynomial. Each new byte is
85 * rotated before being added into the pool, in a half-hearted attempt to
86 * protect against biases in the input data (e.g., top bits being clear on
89 * The gating operation takes a keyed hash of the entire generator state,
90 * uses it as the key for a symmetric cipher, and encrypts the state. The
91 * key is then discarded. The result is that every ouptut bit of the
92 * operation depends in a complex way on every input bit, but the operation
95 * As an added wrinkle, 160 bits of the output buffer are never actually
96 * output. They are used in the gating operation only, as an extra item that
97 * an adversary has to guess before predicting generator output.
100 #ifndef CATACOMB_RAND_H
101 #define CATACOMB_RAND_H
107 /*----- Header files ------------------------------------------------------*/
111 #ifndef CATACOMB_GRAND_H
115 #ifndef CATACOMB_RMD160_HMAC_H
116 # include "rmd160-hmac.h"
119 /*----- Magic numbers -----------------------------------------------------*/
121 #define RAND_POOLSZ 128 /* Input pool size in bytes */
122 #define RAND_BUFSZ 512 /* Output buffer size in bytes */
123 #define RAND_SECSZ 20 /* Secret octets in output buffer */
125 #define RAND_IBITS (RAND_POOLSZ * 8)
126 #define RAND_OBITS (RAND_BUFSZ * 8)
128 /*----- Data structures ---------------------------------------------------*/
130 /* --- A random number generator pool --- */
132 typedef struct rand_pool
{
133 octet pool
[RAND_POOLSZ
]; /* Actual contents of the pool */
134 unsigned i
; /* Current index into pool */
135 unsigned irot
; /* Current rotation applied */
136 unsigned ibits
; /* Number of good bits in pool */
137 octet buf
[RAND_BUFSZ
]; /* Random octet output buffer */
138 unsigned o
; /* Current index into buffer */
139 unsigned obits
; /* Number of good bits in buffer */
140 rmd160_mackey k
; /* Secret key for this pool */
141 const struct rand_source
*s
; /* System-specific noise source */
144 #define RAND_GLOBAL ((rand_pool *)0) /* The global randomness pool */
146 /* --- A noise source --- */
148 typedef struct rand_source
{
149 void (*getnoise
)(rand_pool */
*r*/
); /* Acquire more noise */
150 int (*timer
)(rand_pool */
*r*/
); /* Get noise from current time */
153 /*----- Functions provided ------------------------------------------------*/
155 /* --- @rand_init@ --- *
157 * Arguments: @rand_pool *r@ = pointer to a randomness pool
161 * Use: Initializes a randomness pool. The pool doesn't start out
162 * very random: that's your job to sort out.
165 extern void rand_init(rand_pool */
*r*/
);
167 /* --- @rand_noisesrc@ --- *
169 * Arguments: @rand_pool *r@ = pointer to a randomness pool
170 * @const rand_source *s@ = pointer to source definition
174 * Use: Sets a noise source for a randomness pool. When the pool's
175 * estimate of good random bits falls to zero, the @getnoise@
176 * function is called, passing the pool handle as an argument.
177 * It is expected to increase the number of good bits by at
178 * least one, because it'll be called over and over again until
179 * there are enough bits to satisfy the caller. The @timer@
180 * function is called frequently throughout the generator's
184 extern void rand_noisesrc(rand_pool */
*r*/
, const rand_source */
*s*/
);
186 /* --- @rand_seed@ --- *
188 * Arguments: @rand_pool *r@ = pointer to a randomness pool
189 * @unsigned bits@ = number of bits to ensure
193 * Use: Ensures that there are at least @bits@ good bits of entropy
194 * in the pool. It is recommended that you call this after
195 * initializing a new pool. Requesting @bits > RAND_IBITS@ is
196 * doomed to failure (and is an error).
199 extern void rand_seed(rand_pool */
*r*/
, unsigned /*bits*/);
201 /* --- @rand_key@ --- *
203 * Arguments: @rand_pool *r@ = pointer to a randomness pool
204 * @const void *k@ = pointer to key data
205 * @size_t sz@ = size of key data
209 * Use: Sets the secret key for a randomness pool. The key is used
210 * when mixing in new random bits.
213 extern void rand_key(rand_pool */
*r*/
, const void */
*k*/
, size_t /*sz*/);
215 /* --- @rand_add@ --- *
217 * Arguments: @rand_pool *r@ = pointer to a randomness pool
218 * @const void *p@ = pointer a buffer of data to add
219 * @size_t sz@ = size of the data buffer
220 * @unsigned goodbits@ = number of good bits estimated in buffer
224 * Use: Mixes the data in the buffer with the contents of the
225 * pool. The estimate of the number of good bits is added to
226 * the pool's own count. The mixing operation is not
227 * cryptographically strong. However, data in the input pool
228 * isn't output directly, only through the one-way gating
229 * operation, so that shouldn't matter.
232 extern void rand_add(rand_pool */
*r*/
,
233 const void */
*p*/
, size_t /*sz*/,
234 unsigned /*goodbits*/);
236 /* --- @rand_goodbits@ --- *
238 * Arguments: @rand_pool *r@ = pointer to a randomness pool
240 * Returns: Estimate of the number of good bits remaining in the pool.
243 extern unsigned rand_goodbits(rand_pool */
*r*/
);
245 /* --- @rand_gate@ --- *
247 * Arguments: @rand_pool *r@ = pointer to a randomness pool
251 * Use: Mixes up the entire state of the generator in a nonreversible
255 extern void rand_gate(rand_pool */
*r*/
);
257 /* --- @rand_stretch@ --- *
259 * Arguments: @rand_pool *r@ = pointer to a randomness pool
263 * Use: Stretches the contents of the output buffer by transforming
264 * it in a nonreversible way. This doesn't add any entropy
265 * worth speaking about, but it works well enough when the
266 * caller doesn't care about that sort of thing.
269 extern void rand_stretch(rand_pool */
*r*/
);
271 /* --- @rand_get@ --- *
273 * Arguments: @rand_pool *r@ = pointer to a randomness pool
274 * @void *p@ = pointer to output buffer
275 * @size_t sz@ = size of output buffer
279 * Use: Gets random data from the pool. The pool's contents can't be
280 * determined from the output of this function; nor can the
281 * output data be determined from a knowledge of the data input
282 * to the pool without also having knowledge of the secret key.
283 * The good bits counter is decremented, although no special
284 * action is taken if it reaches zero.
287 extern void rand_get(rand_pool */
*r*/
, void */
*p*/
, size_t /*sz*/);
289 /* --- @rand_getgood@ --- *
291 * Arguments: @rand_pool *r@ = pointer to a randomness pool
292 * @void *p@ = pointer to output buffer
293 * @size_t sz@ = size of output buffer
297 * Use: Gets random data from the pool. The pool's contents can't be
298 * determined from the output of this function; nor can the
299 * output data be determined from a knowledge of the data input
300 * to the pool wihtout also having knowledge of the secret key.
301 * If a noise source is attached to the pool in question, it is
302 * called to replenish the supply of good bits in the pool;
303 * otherwise this call is equivalent to @rand_get@.
306 extern void rand_getgood(rand_pool */
*r*/
, void */
*p*/
, size_t /*sz*/);
308 /*----- Generic random number generator interface -------------------------*/
310 /* --- Miscellaneous operations --- */
313 RAND_GATE
= GRAND_SPECIFIC('R'), /* No args */
314 RAND_STRETCH
, /* No args */
315 RAND_KEY
, /* @const void *k, size_t sz@ */
316 RAND_NOISESRC
, /* @const rand_source *s@ */
317 RAND_SEED
/* @unsigned bits@ */
320 /* --- Default random number generator --- */
322 extern grand rand_global
;
324 /* --- @rand_create@ --- *
328 * Returns: Pointer to a generic generator.
330 * Use: Constructs a generic generator interface over a Catacomb
331 * entropy pool generator.
334 extern grand
*rand_create(void);
336 /*----- That's all, folks -------------------------------------------------*/