[u/mdw/catacomb] / rand.c

/* -*-c-*-
 *
 * $Id: rand.c,v 1.2 1999/10/12 21:00:15 mdw Exp $
 *
 * Secure random number generator
 *
 * (c) 1998 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.
 */

/*----- Revision history --------------------------------------------------* 
 *
 * $Log: rand.c,v $
 * Revision 1.2  1999/10/12 21:00:15  mdw
 * Make pool and buffer sizes more sensible.
 *
 * Revision 1.1  1999/09/03 08:41:12  mdw
 * Initial import.
 *
 */

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

#include <stdio.h>
#include <string.h>

#include <mLib/bits.h>

#include "blowfish-cbc.h"
#include "paranoia.h"
#include "rand.h"
#include "rmd160.h"
#include "rmd160-hmac.h"

/*----- Static variables --------------------------------------------------*/

static rand_pool pool;		/* Default random pool */

/*----- Macros ------------------------------------------------------------*/

#define RAND_RESOLVE(r) do {						\
  if ((r) == RAND_GLOBAL)						\
    (r) = &pool;							\
} while (0)

#define TIMER(r) do {							\
  if ((r)->s && (r)->s->timer)						\
    (r)->s->timer(r);							\
} while (0)

/*----- Main code ---------------------------------------------------------*/

/* --- @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.
 */

void rand_init(rand_pool *r)
{
  RAND_RESOLVE(r);
  memset(r->pool, 0, sizeof(r->pool));
  memset(r->buf, 0, sizeof(r->buf));
  r->i = 0;
  r->irot = 0;
  r->ibits = r->obits = 0;
  r->o = RAND_SECSZ;
  r->s = 0;
  rmd160_hmac(&r->k, 0, 0);
  rand_gate(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.
 */

void rand_noisesrc(rand_pool *r, const rand_source *s)
{
  RAND_RESOLVE(r);
  r->s = s;
}

/* --- @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.
 */

void rand_key(rand_pool *r, const void *k, size_t sz)
{
  RAND_RESOLVE(r);
  rmd160_hmac(&r->k, k, 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.
 */

void rand_add(rand_pool *r, const void *p, size_t sz, unsigned goodbits)
{
  const octet *c = p;
  int i, rot;

#if RAND_POOLSZ != 128
#  error Polynomial in rand_add is out of date.  Fix it.
#endif

  RAND_RESOLVE(r);

  i = r->i; rot = r->irot;

  while (sz) {
    octet o = *c++;
    r->pool[i] ^= (ROL8(o, rot) ^
		   r->pool[(i + 1) % RAND_POOLSZ] ^
		   r->pool[(i + 2) % RAND_POOLSZ] ^
		   r->pool[(i + 7) % RAND_POOLSZ]);
    rot = (rot + 5) & 7;
    i++; if (i >= RAND_POOLSZ) i -= RAND_POOLSZ;
    sz--;
  }

  r->i = i;
  r->irot = rot;
  r->ibits += goodbits;
  if (r->ibits > RAND_IBITS)
    r->ibits = RAND_IBITS;
}

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

unsigned rand_goodbits(rand_pool *r)
{
  RAND_RESOLVE(r);
  return (r->ibits + r->obits);
}

/* --- @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.
 */

void rand_gate(rand_pool *r)
{
  octet mac[RMD160_HASHSZ];

  RAND_RESOLVE(r);
  TIMER(r);

  /* --- Hash up all the data in the pool --- */

  {
    rmd160_macctx mc;

    rmd160_macinit(&mc, &r->k);
    rmd160_mac(&mc, r->pool, sizeof(r->pool));
    rmd160_mac(&mc, r->buf, sizeof(r->buf));
    rmd160_macdone(&mc, mac);
    BURN(mc);
  }

  /* --- Now mangle all of the data based on the hash --- */

  {
    blowfish_cbcctx bc;

    blowfish_cbcinit(&bc, mac, sizeof(mac), 0);
    blowfish_cbcencrypt(&bc, r->pool, r->pool, sizeof(r->pool));
    blowfish_cbcencrypt(&bc, r->buf, r->buf, sizeof(r->buf));
    BURN(bc);
  }

  /* --- Reset the various state variables --- */

  r->o = RAND_SECSZ;
  r->obits += r->ibits;
  if (r->obits > RAND_OBITS) {
    r->ibits = r->obits - r->ibits;
    r->obits = RAND_OBITS;
  } else
    r->ibits = 0;
  TIMER(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.
 */

void rand_stretch(rand_pool *r)
{
  octet mac[RMD160_HASHSZ];

  RAND_RESOLVE(r);
  TIMER(r);

  /* --- Hash up all the data in the buffer --- */

  {
    rmd160_macctx mc;

    rmd160_macinit(&mc, &r->k);
    rmd160_mac(&mc, r->pool, sizeof(r->pool));
    rmd160_mac(&mc, r->buf, sizeof(r->buf));
    rmd160_macdone(&mc, mac);
    BURN(mc);
  }

  /* --- Now mangle the buffer based on that hash --- */

  {
    blowfish_cbcctx bc;

    blowfish_cbcinit(&bc, mac, sizeof(mac), 0);
    blowfish_cbcencrypt(&bc, r->buf, r->buf, sizeof(r->buf));
    BURN(bc);
  }

  /* --- Reset the various state variables --- */

  r->o = RAND_SECSZ;
  TIMER(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 wihtout also having knowledge of the secret key.
 *		The good bits counter is decremented, although no special
 *		action is taken if it reaches zero.
 */

void rand_get(rand_pool *r, void *p, size_t sz)
{
  octet *o = p;

  RAND_RESOLVE(r);
  TIMER(r);

  if (!sz)
    return;
  for (;;) {
    if (r->o + sz <= RAND_BUFSZ) {
      memcpy(o, r->buf + r->o, sz);
      r->o += sz;
      break;
    } else {
      size_t chunk = RAND_BUFSZ - r->o;
      if (chunk) {
	memcpy(o, r->buf + r->o, chunk);
	sz -= chunk;
	o += chunk;
      }
      rand_stretch(r);
    }
  }

  if (r->obits > sz * 8)
    r->obits -= sz * 8;
  else
    r->obits = 0;
}

/* --- @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@.
 */

void rand_getgood(rand_pool *r, void *p, size_t sz)
{
  octet *o = p;

  RAND_RESOLVE(r);

  if (!sz)
    return;
  if (!r->s || !r->s->getnoise) {
    rand_get(r, p, sz);
    return;
  }
  TIMER(r);

  while (sz) {
    size_t chunk = sz;

    if (chunk * 8 > r->obits) {
      if (chunk * 8 > r->ibits + r->obits)
	do r->s->getnoise(r); while (r->ibits + r->obits < 128);
      rand_gate(r);
      if (chunk * 8 > r->obits)
	chunk = r->obits / 8;
    }

    if (chunk + r->o > RAND_BUFSZ)
      chunk = RAND_BUFSZ - r->o;

    memcpy(o, r->buf + r->o, chunk);
    r->obits -= chunk * 8;
    o += chunk;
    sz -= chunk;
  }
}

/*----- That's all, folks -------------------------------------------------*/
Commit	Line	Data
d03ab969	1	/* --c--
d03ab969	2	*
ba044e65	3	* $Id: rand.c,v 1.2 1999/10/12 21:00:15 mdw Exp $
d03ab969	4	*
	5	* Secure random number generator
	6	*
	7	* (c) 1998 Straylight/Edgeware
	8	*/
	9
	10	/----- Licensing notice --------------------------------------------------
	11	*
	12	* This file is part of Catacomb.
	13	*
	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.
	18	*
	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.
	23	*
	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,
	27	* MA 02111-1307, USA.
	28	*/
	29
	30	/----- Revision history --------------------------------------------------
	31	*
	32	* $Log: rand.c,v $
ba044e65	33	* Revision 1.2 1999/10/12 21:00:15 mdw
	34	* Make pool and buffer sizes more sensible.
	35	*
d03ab969	36	* Revision 1.1 1999/09/03 08:41:12 mdw
	37	* Initial import.
	38	*
	39	*/
	40
	41	/----- Header files ------------------------------------------------------/
	42
	43	#include <stdio.h>
	44	#include <string.h>
	45
	46	#include <mLib/bits.h>
	47
	48	#include "blowfish-cbc.h"
	49	#include "paranoia.h"
	50	#include "rand.h"
	51	#include "rmd160.h"
	52	#include "rmd160-hmac.h"
	53
	54	/----- Static variables --------------------------------------------------/
	55
	56	static rand_pool pool; /* Default random pool */
	57
	58	/----- Macros ------------------------------------------------------------/
	59
	60	#define RAND_RESOLVE(r) do { \
	61	if ((r) == RAND_GLOBAL) \
	62	(r) = &pool; \
	63	} while (0)
	64
	65	#define TIMER(r) do { \
	66	if ((r)->s && (r)->s->timer) \
	67	(r)->s->timer(r); \
	68	} while (0)
	69
	70	/----- Main code ---------------------------------------------------------/
	71
	72	/* --- @rand_init@ --- *
	73	*
	74	* Arguments: @rand_pool *r@ = pointer to a randomness pool
	75	*
	76	* Returns: ---
	77	*
	78	* Use: Initializes a randomness pool. The pool doesn't start out
	79	* very random: that's your job to sort out.
	80	*/
	81
	82	void rand_init(rand_pool *r)
	83	{
	84	RAND_RESOLVE(r);
	85	memset(r->pool, 0, sizeof(r->pool));
	86	memset(r->buf, 0, sizeof(r->buf));
	87	r->i = 0;
	88	r->irot = 0;
	89	r->ibits = r->obits = 0;
	90	r->o = RAND_SECSZ;
	91	r->s = 0;
	92	rmd160_hmac(&r->k, 0, 0);
	93	rand_gate(r);
	94	}
	95
	96	/* --- @rand_noisesrc@ --- *
	97	*
	98	* Arguments: @rand_pool *r@ = pointer to a randomness pool
	99	* @const rand_source *s@ = pointer to source definition
100	*
101	* Returns: ---
102	*
103	* Use: Sets a noise source for a randomness pool. When the pool's
104	* estimate of good random bits falls to zero, the @getnoise@
105	* function is called, passing the pool handle as an argument.
106	* It is expected to increase the number of good bits by at
107	* least one, because it'll be called over and over again until
108	* there are enough bits to satisfy the caller. The @timer@
109	* function is called frequently throughout the generator's
110	* operation.
111	*/
112
113	void rand_noisesrc(rand_pool r, const rand_source s)
114	{
115	RAND_RESOLVE(r);
116	r->s = s;
117	}
118
119	/* --- @rand_key@ --- *
120	*
121	* Arguments: @rand_pool *r@ = pointer to a randomness pool
122	* @const void *k@ = pointer to key data
123	* @size_t sz@ = size of key data
124	*
125	* Returns: ---
126	*
127	* Use: Sets the secret key for a randomness pool. The key is used
128	* when mixing in new random bits.
129	*/
130
131	void rand_key(rand_pool r, const void k, size_t sz)
132	{
133	RAND_RESOLVE(r);
134	rmd160_hmac(&r->k, k, sz);
135	}
136
137	/* --- @rand_add@ --- *
138	*
139	* Arguments: @rand_pool *r@ = pointer to a randomness pool
140	* @const void *p@ = pointer a buffer of data to add
141	* @size_t sz@ = size of the data buffer
142	* @unsigned goodbits@ = number of good bits estimated in buffer
143	*
144	* Returns: ---
145	*
146	* Use: Mixes the data in the buffer with the contents of the
147	* pool. The estimate of the number of good bits is added to
148	* the pool's own count. The mixing operation is not
149	* cryptographically strong. However, data in the input pool
150	* isn't output directly, only through the one-way gating
151	* operation, so that shouldn't matter.
152	*/
153
154	void rand_add(rand_pool r, const void p, size_t sz, unsigned goodbits)
155	{
156	const octet *c = p;
ba044e65	157	int i, rot;
d03ab969	158
ba044e65	159	#if RAND_POOLSZ != 128
d03ab969	160	# error Polynomial in rand_add is out of date. Fix it.
	161	#endif
	162
	163	RAND_RESOLVE(r);
	164
ba044e65	165	i = r->i; rot = r->irot;
d03ab969	166
	167	while (sz) {
	168	octet o = *c++;
ba044e65	169	r->pool[i] ^= (ROL8(o, rot) ^
	170	r->pool[(i + 1) % RAND_POOLSZ] ^
	171	r->pool[(i + 2) % RAND_POOLSZ] ^
	172	r->pool[(i + 7) % RAND_POOLSZ]);
d03ab969	173	rot = (rot + 5) & 7;
d03ab969	174	i++; if (i >= RAND_POOLSZ) i -= RAND_POOLSZ;
d03ab969	175	sz--;
	176	}
	177
	178	r->i = i;
	179	r->irot = rot;
	180	r->ibits += goodbits;
	181	if (r->ibits > RAND_IBITS)
	182	r->ibits = RAND_IBITS;
	183	}
	184
	185	/* --- @rand_goodbits@ --- *
	186	*
	187	* Arguments: @rand_pool *r@ = pointer to a randomness pool
	188	*
	189	* Returns: Estimate of the number of good bits remaining in the pool.
	190	*/
	191
	192	unsigned rand_goodbits(rand_pool *r)
	193	{
	194	RAND_RESOLVE(r);
	195	return (r->ibits + r->obits);
	196	}
	197
	198	/* --- @rand_gate@ --- *
	199	*
	200	* Arguments: @rand_pool *r@ = pointer to a randomness pool
	201	*
	202	* Returns: ---
	203	*
	204	* Use: Mixes up the entire state of the generator in a nonreversible
	205	* way.
	206	*/
	207
	208	void rand_gate(rand_pool *r)
	209	{
	210	octet mac[RMD160_HASHSZ];
	211
	212	RAND_RESOLVE(r);
	213	TIMER(r);
	214
	215	/* --- Hash up all the data in the pool --- */
	216
	217	{
	218	rmd160_macctx mc;
	219
	220	rmd160_macinit(&mc, &r->k);
	221	rmd160_mac(&mc, r->pool, sizeof(r->pool));
	222	rmd160_mac(&mc, r->buf, sizeof(r->buf));
	223	rmd160_macdone(&mc, mac);
	224	BURN(mc);
	225	}
	226
	227	/* --- Now mangle all of the data based on the hash --- */
	228
	229	{
	230	blowfish_cbcctx bc;
	231
	232	blowfish_cbcinit(&bc, mac, sizeof(mac), 0);
	233	blowfish_cbcencrypt(&bc, r->pool, r->pool, sizeof(r->pool));
	234	blowfish_cbcencrypt(&bc, r->buf, r->buf, sizeof(r->buf));
	235	BURN(bc);
	236	}
	237
	238	/* --- Reset the various state variables --- */
239
240	r->o = RAND_SECSZ;
241	r->obits += r->ibits;
242	if (r->obits > RAND_OBITS) {
243	r->ibits = r->obits - r->ibits;
244	r->obits = RAND_OBITS;
245	} else
246	r->ibits = 0;
247	TIMER(r);
248	}
249
250	/* --- @rand_stretch@ --- *
251	*
252	* Arguments: @rand_pool *r@ = pointer to a randomness pool
253	*
254	* Returns: ---
255	*
256	* Use: Stretches the contents of the output buffer by transforming
257	* it in a nonreversible way. This doesn't add any entropy
258	* worth speaking about, but it works well enough when the
259	* caller doesn't care about that sort of thing.
260	*/
261
262	void rand_stretch(rand_pool *r)
263	{
264	octet mac[RMD160_HASHSZ];
265
266	RAND_RESOLVE(r);
267	TIMER(r);
268
269	/* --- Hash up all the data in the buffer --- */
270
271	{
272	rmd160_macctx mc;
273
274	rmd160_macinit(&mc, &r->k);
275	rmd160_mac(&mc, r->pool, sizeof(r->pool));
276	rmd160_mac(&mc, r->buf, sizeof(r->buf));
277	rmd160_macdone(&mc, mac);
278	BURN(mc);
279	}
280
281	/* --- Now mangle the buffer based on that hash --- */
282
283	{
284	blowfish_cbcctx bc;
285
286	blowfish_cbcinit(&bc, mac, sizeof(mac), 0);
287	blowfish_cbcencrypt(&bc, r->buf, r->buf, sizeof(r->buf));
288	BURN(bc);
289	}
290
291	/* --- Reset the various state variables --- */
292
293	r->o = RAND_SECSZ;
294	TIMER(r);
295	}
296
297	/* --- @rand_get@ --- *
298	*
299	* Arguments: @rand_pool *r@ = pointer to a randomness pool
300	* @void *p@ = pointer to output buffer
301	* @size_t sz@ = size of output buffer
302	*
303	* Returns: ---
304	*
305	* Use: Gets random data from the pool. The pool's contents can't be
306	* determined from the output of this function; nor can the
307	* output data be determined from a knowledge of the data input
308	* to the pool wihtout also having knowledge of the secret key.
309	* The good bits counter is decremented, although no special
310	* action is taken if it reaches zero.
311	*/
312
313	void rand_get(rand_pool r, void p, size_t sz)
314	{
315	octet *o = p;
316
317	RAND_RESOLVE(r);
318	TIMER(r);
319
320	if (!sz)
321	return;
322	for (;;) {
323	if (r->o + sz <= RAND_BUFSZ) {
324	memcpy(o, r->buf + r->o, sz);
325	r->o += sz;
326	break;
327	} else {
328	size_t chunk = RAND_BUFSZ - r->o;
329	if (chunk) {
330	memcpy(o, r->buf + r->o, chunk);
331	sz -= chunk;
332	o += chunk;
333	}
334	rand_stretch(r);
335	}
336	}
337
338	if (r->obits > sz * 8)
339	r->obits -= sz * 8;
340	else
341	r->obits = 0;
342	}
343
344	/* --- @rand_getgood@ --- *
345	*
346	* Arguments: @rand_pool *r@ = pointer to a randomness pool
347	* @void *p@ = pointer to output buffer
348	* @size_t sz@ = size of output buffer
349	*
350	* Returns: ---
351	*
352	* Use: Gets random data from the pool. The pool's contents can't be
353	* determined from the output of this function; nor can the
354	* output data be determined from a knowledge of the data input
355	* to the pool wihtout also having knowledge of the secret key.
356	* If a noise source is attached to the pool in question, it is
357	* called to replenish the supply of good bits in the pool;
358	* otherwise this call is equivalent to @rand_get@.
359	*/
360
361	void rand_getgood(rand_pool r, void p, size_t sz)
362	{
363	octet *o = p;
364
365	RAND_RESOLVE(r);
366
367	if (!sz)
368	return;
369	if (!r->s \|\| !r->s->getnoise) {
370	rand_get(r, p, sz);
371	return;
372	}
373	TIMER(r);
374
375	while (sz) {
376	size_t chunk = sz;
377
378	if (chunk * 8 > r->obits) {
379	if (chunk * 8 > r->ibits + r->obits)
380	do r->s->getnoise(r); while (r->ibits + r->obits < 128);
381	rand_gate(r);
382	if (chunk * 8 > r->obits)
383	chunk = r->obits / 8;
384	}
385
386	if (chunk + r->o > RAND_BUFSZ)
387	chunk = RAND_BUFSZ - r->o;
388
389	memcpy(o, r->buf + r->o, chunk);
390	r->obits -= chunk * 8;
391	o += chunk;
392	sz -= chunk;
393	}
394	}
395
396	/----- That's all, folks -------------------------------------------------/