3 * Secure random number generator
5 * (c) 1999 Straylight/Edgeware
8 /*----- Licensing notice --------------------------------------------------*
10 * This file is part of Catacomb.
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.
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.
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,
28 /*----- Notes on the random number generator ------------------------------*
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
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.
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
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
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.
67 #ifndef CATACOMB_RAND_H
68 #define CATACOMB_RAND_H
74 /*----- Header files ------------------------------------------------------*/
78 #ifndef CATACOMB_GRAND_H
82 #ifndef CATACOMB_RMD160_HMAC_H
83 # include "rmd160-hmac.h"
86 /*----- Magic numbers -----------------------------------------------------*/
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 */
93 #define RAND_IBITS (RAND_POOLSZ * 8)
94 #define RAND_OBITS (RAND_BUFSZ * 8)
96 /*----- Data structures ---------------------------------------------------*/
98 /* --- A random number generator pool --- */
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 */
113 #define RAND_GLOBAL ((rand_pool *)0) /* The global randomness pool */
115 /* --- A noise source --- */
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 */
122 /*----- Functions provided ------------------------------------------------*/
124 /* --- @rand_init@ --- *
126 * Arguments: @rand_pool *r@ = pointer to a randomness pool
130 * Use: Initializes a randomness pool. The pool doesn't start out
131 * very random: that's your job to sort out.
134 extern void rand_init(rand_pool */*r*/);
136 /* --- @rand_generation@ --- *
140 * Returns: A nonzero generation number.
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.
148 extern unsigned rand_generation(void);
150 /* --- @rand_noisesrc@ --- *
152 * Arguments: @rand_pool *r@ = pointer to a randomness pool
153 * @const rand_source *s@ = pointer to source definition
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
167 extern void rand_noisesrc(rand_pool */*r*/, const rand_source */*s*/);
169 /* --- @rand_seed@ --- *
171 * Arguments: @rand_pool *r@ = pointer to a randomness pool
172 * @unsigned bits@ = number of bits to ensure
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).
182 extern void rand_seed(rand_pool */*r*/, unsigned /*bits*/);
184 /* --- @rand_key@ --- *
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
192 * Use: Sets the secret key for a randomness pool. The key is used
193 * when mixing in new random bits.
196 extern void rand_key(rand_pool */*r*/, const void */*k*/, size_t /*sz*/);
198 /* --- @rand_quick@ --- *
200 * Arguments: @rand_pool *r@ = pointer to a randomness pool
202 * Returns: Zero on success; @-1@ on failure.
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
209 extern int rand_quick(rand_pool */*r*/);
211 /* --- @rand_add@ --- *
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
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.
228 extern void rand_add(rand_pool */*r*/,
229 const void */*p*/, size_t /*sz*/,
230 unsigned /*goodbits*/);
232 /* --- @rand_goodbits@ --- *
234 * Arguments: @rand_pool *r@ = pointer to a randomness pool
236 * Returns: Estimate of the number of good bits remaining in the pool.
239 extern unsigned rand_goodbits(rand_pool */*r*/);
241 /* --- @rand_gate@ --- *
243 * Arguments: @rand_pool *r@ = pointer to a randomness pool
247 * Use: Mixes up the entire state of the generator in a nonreversible
251 extern void rand_gate(rand_pool */*r*/);
253 /* --- @rand_stretch@ --- *
255 * Arguments: @rand_pool *r@ = pointer to a randomness pool
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.
265 extern void rand_stretch(rand_pool */*r*/);
267 /* --- @rand_get@ --- *
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
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.
283 extern void rand_get(rand_pool */*r*/, void */*p*/, size_t /*sz*/);
285 /* --- @rand_getgood@ --- *
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
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@.
302 extern void rand_getgood(rand_pool */*r*/, void */*p*/, size_t /*sz*/);
304 /*----- Generic random number generator interface -------------------------*/
306 /* --- Miscellaneous operations --- */
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 */
320 /* --- Default random number generator --- */
323 extern struct rand__gctx rand_global;
325 extern grand rand_global;
328 /* --- @rand_create@ --- *
332 * Returns: Pointer to a generic generator.
334 * Use: Constructs a generic generator interface over a Catacomb
335 * entropy pool generator.
338 extern grand *rand_create(void);
340 /*----- That's all, folks -------------------------------------------------*/