Fix copyright date.

[become] / src / rand.c

/* -*-c-*-
 *
 * $Id: rand.c,v 1.3 1998/01/12 16:46:23 mdw Exp $
 *
 * Random number generation
 *
 * (c) 1998 EBI
 */

/*----- Licencing notice --------------------------------------------------*
 *
 * This file is part of Become.
 *
 * Become is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * Become 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 General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with `become'; 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.3  1998/01/12 16:46:23  mdw
 * Fix copyright date.
 *
 * Revision 1.2  1997/08/07 09:47:07  mdw
 * Fix address of the FSF.
 *
 * Revision 1.1  1997/08/07 09:46:05  mdw
 * New source file added to maintain a randomness pool.
 *
 */

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

/* --- ANSI headers --- */

#include <ctype.h>
#include <errno.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

/* --- Local headers --- */

#include "become.h"
#include "config.h"
#include "icrypt.h"
#include "md5.h"
#include "rand.h"
#include "tx.h"
#include "utils.h"

/*----- Magic numbers -----------------------------------------------------*/

#define rand__seedBits 512		/* Number of random seed bits */

/*----- Persistant state --------------------------------------------------*/

static unsigned char rand__pool[rand__seedBits / 8]; /* Entropy pool */
static size_t rand__i = 0;		/* Index into entropy pool */
static size_t rand__r = 0;		/* Rotation to apply to next byte */

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

/* --- @rand_read@ --- *
 *
 * Arguments:	@FILE *fp@ = pointer to file to read from
 *
 * Returns:	---
 *
 * Use:		Reads a random number seed from the stream.
 */

void rand_read(FILE *fp)
{
  tx_getBits(rand__pool, rand__seedBits, fp);
  rand__i = 0;
  rand__r = 0;
  T( traceblk(TRACE_RAND, "rand: loaded randomness pool",
	      rand__pool, sizeof(rand__pool)); )
}

/* --- @rand_write@ --- *
 *
 * Arguments:	@FILE *fp@ = pointer to file to write on
 *
 * Returns:	---
 *
 * Use:		Writes a random number seed back to the stream.
 */

void rand_write(FILE *fp)
{
  rand_churn();
  tx_putBits(rand__pool, rand__seedBits, fp);
}

/* --- @rand_clear@ --- *
 *
 * Arguments:	---
 *
 * Returns:	---
 *
 * Use:		Clears the random number pool.
 */

void rand_clear(void)
{
  memset(rand__pool, 0, sizeof(rand__pool));
  T( trace(TRACE_RAND, "rand: cleared randomness pool"); )
  rand__i = 0;
  rand__r = 0;
}

/* --- @rand_encrypt@ --- *
 *
 * Arguments:	@icrypt_job *j@ = pointer to an encryption job to apply
 *
 * Returns:	---
 *
 * Use:		Encrypts the randomness pool with a given key.  This should
 *		be done before use, in case the pool gets compromised.
 */

void rand_encrypt(icrypt_job *j)
{
  icrypt_encrypt(j, rand__pool, rand__pool, sizeof(rand__pool));
  rand__i = 0;
  rand__r = 0;
  T( traceblk(TRACE_RAND, "encrypted randomness pool",
	      rand__pool, sizeof(rand__pool)); )
}  

/* --- @rand_add@ --- *
 *
 * Arguments:	@const void *p@ = pointer to some data
 *		@size_t sz@ = size of the data in bytes
 *
 * Returns:	---
 *
 * Use:		Adds entropy to the pool.
 */

void rand_add(const void *p, size_t sz)
{
  /* --- Method --- *
   *
   * Entropy is inserted byte-by-byte.  The method used is derived from
   * Linux's `drivers/char/random.c', which is in turn appears to be inspired
   * by SHA-1.
   *
   * Imagine the randomness pool as 8 parallel shift registers.  To insert
   * a byte into the pool, XOR it with bytes picked according to a primitive
   * polynomial mod 2, and rotate one place to the left.  (The rotation is
   * from SHA-1; it introduces some interaction between the registers.)
   */

  size_t i = rand__i;
  const unsigned char *cp = p;
  size_t mask = (rand__seedBits / 8) - 1;
  size_t r = rand__r;
  unsigned int x;

  /* --- Ensure the polynomial is valid --- *
   *
   * The current polynomal is %$x^{64} + x^4 + x^3 + x + 1$% (picked from
   * Schneier's excellent book).  If the pool size changes, though, I'll
   * need another polynomial.
   */

#if rand__seedBits / 8 != 64
#  error Change the polynomal in rand_add
#endif

  T( traceblk(TRACE_RAND, "rand: incoming entropy", p, sz); )

  /* --- Add values to the entropy pool --- */

  while (sz) {
    x = *cp++ & 0xffu;
    if (r)
      x = ((x << r) | (x >> (8 - r)));
    x ^= (rand__pool[i] ^
	  rand__pool[(i + 1) & mask] ^
	  rand__pool[(i + 3) & mask] ^
	  rand__pool[(i + 4) & mask]);
    rand__pool[i] = ((x << 1) | (x >> 7)) & 0xffu;
    sz--;
    i = (i + 1) & mask;
    r = (r + 3) & 7;
  }

  /* --- Update the global counters --- */

  rand__r = r;
  rand__i = i;

  T( traceblk(TRACE_RAND, "rand: added some entropy",
	      rand__pool, sizeof(rand__pool)); )
}

/* --- @rand_extract@ --- *
 *
 * Arguments:	@unsigned char *b@ = pointer to output buffer
 *		@size_t sz@ = number of bytes wanted
 *
 * Returns:	---
 *
 * Use:		Produces a number of random bytes.
 */

void rand_extract(unsigned char *b, size_t sz)
{
  /* --- Method --- *
   *
   * Hash the buffer with a secure hash (or, in this case, with MD5 and hope
   * for the best...).  If this gives us enough bytes, fill the output
   * buffer; otherwise copy the whole hash out.  The contribute the hash back
   * into the randomness pool with @rand_add@ to provide some feedback.
   *
   * The secure hash gives us good mixing over the whole of the randomness
   * pool, and attempts to ensure that an attacker receiving our random
   * numbers can't predict any numbers we don't actually give him.
   */

  size_t c;
  unsigned char mdbuf[MD5_HASHSIZE];
  md5 md;

  T( trace(TRACE_RAND, "rand: extracting entropy"); )

  while (sz) {
    c = (sz >= sizeof(mdbuf)) ? sizeof(mdbuf) : sz;
    md5_init(&md);
    md5_buffer(&md, rand__pool, sizeof(rand__pool));
    md5_final(&md, mdbuf);
    memcpy(b, mdbuf, c);
    rand_add(mdbuf, c);
    b += c; sz -= c;
  }
  burn(mdbuf); burn(md);

  T( trace(TRACE_RAND, "rand: finished extracting entropy"); )
}

/* --- @rand_churn@ --- *
 *
 * Arguments:	---
 *
 * Returns:	---
 *
 * Use:		Churns the randomness pool completely.  The pool is replaced
 *		by repeated MD5-ings of itself.
 */

void rand_churn(void)
{
  md5 md;
  unsigned char mdbuf[MD5_HASHSIZE];
  size_t sz = sizeof(rand__pool);
  size_t c;

  T( trace(TRACE_RAND, "rand: churning pool"); )

  rand__i = 0;
  rand__r = 0;

  while (sz) {
    c = (sz >= sizeof(mdbuf)) ? sizeof(mdbuf) : sz;
    md5_init(&md);
    md5_buffer(&md, rand__pool, sizeof(rand__pool));
    md5_final(&md, mdbuf);
    rand_add(mdbuf, c);
    sz -= c;
  }

  rand__i = 0;
  rand__r = 0;

  burn(mdbuf); burn(md);

  T( trace(TRACE_RAND, "rand: finished churning pool"); )
}

/*----- That's all, folks -------------------------------------------------*/