rand/rand.c (rand_gate): Evolve r->ibits in a more sensible manner.

[catacomb] / rand / rand.c

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

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

#include "config.h"

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

#include <mLib/bits.h>
#include <mLib/sub.h>

#include "arena.h"
#include "dispatch.h"
#include "paranoia.h"

#define RAND__HACKS
#include "rand.h"

#include "noise.h"

#include "twofish-counter.h"
#include "sha256.h"

#define CIPHER_CTX twofish_counterctx
#define CIPHER_INIT twofish_counterinit
#define CIPHER_ENCRYPT twofish_counterencrypt
#define CIPHER_IVSZ TWOFISH_BLKSZ
#define CIPHER_KEYSZ TWOFISH_KEYSZ

#define HASH_CTX sha256_ctx
#define HASH_INIT sha256_init
#define HASH sha256_hash
#define HASH_DONE sha256_done
#define HASH_SZ SHA256_HASHSZ

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

static const grand_ops gops;

typedef struct rand__gctx {
  grand r;
  rand_pool p;
} gctx;

gctx rand_global = {
  { &gops },
  { { 0 }, 0, 0, 0, 0,
    { 0 }, RAND_SECSZ, 0,
    { "Catacomb global random byte pool" },
    &noise_source }
};

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

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

#define GENCHECK(r) do {						\
  unsigned gen = rand_generation();					\
  if (r->gen != gen) { r->gen = gen; rand_gate(r); }			\
} while (0)

static int quick(rand_pool *);
#define QUICK(r) do {							\
  quick(r);								\
  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.  A good suggestion
 *		would be to attach an appropriate noise source and call
 *		@rand_seed@.
 */

void rand_init(rand_pool *r)
{
  RAND_RESOLVE(r);
  memset(r->pool, 0, sizeof(r->pool));
  memset(r->buf, 0, sizeof(r->buf));
  r->gen = rand_generation();
  r->i = 0;
  r->irot = 0;
  r->ibits = r->obits = 0;
  r->o = RAND_SECSZ;
  r->s = &noise_source;
  rand_key(r, 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_quick@ --- *
 *
 * Arguments:	@rand_pool *r@ = pointer to a randomness pool
 *
 * Returns:	Zero on success; @-1@ on failure.
 *
 * Use		Attempts to use some machine-specific `quick' source of
 *		entropy to top up @r@.  This may not do anything at all on
 *		many systems.
 */

CPU_DISPATCH(static, return, int, quick, (rand_pool *r), (r),
	     pick_quick, trivial_quick);

static int trivial_quick(rand_pool *r) { return (-1); }

#if __GNUC__ && (CPUFAM_X86 || CPUFAM_AMD64)
static int rdrand_quick(rand_pool *r)
{
  unsigned long rr;
  int i = 16;

  __asm__ ("0: rdrand %0; jc 9f; dec %1; jnz 0b; 9:"
	   : "=r" (rr), "=r" (i) : "1" (i) : "cc");
  if (!i) return (-1);
  rand_add(r, &rr, sizeof(rr), 8*sizeof(rr));
  return (0);
}
#endif

static quick__functype *pick_quick(void)
{
#if __GNUC__ && (CPUFAM_X86 || CPUFAM_AMD64)
  DISPATCH_PICK_COND(rand_quick, rdrand_quick,
		     cpu_feature_p(CPUFEAT_X86_RDRAND));
#endif
  DISPATCH_PICK_FALLBACK(rand_quick, trivial_quick);
}

int rand_quick(rand_pool *r) { RAND_RESOLVE(r); return (quick(r)); }

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

void rand_seed(rand_pool *r, unsigned bits)
{
  RAND_RESOLVE(r);

  assert(((void)"bits pointlessly large in rand_seed", bits <= RAND_IBITS));
  assert(((void)"no noise source in rand_seed", r->s));

  while (r->ibits < bits)
    r->s->getnoise(r);
  rand_gate(r);
}

/* --- @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)
{
  HASH_CTX hc;
  octet h[HASH_SZ];
  static const char label[] = "Catacomb random pool key";

  RAND_RESOLVE(r);

  assert(HASH_SZ >= RAND_KEYSZ);
  HASH_INIT(&hc);
  HASH(&hc, label, sizeof(label));
  if (sz) HASH(&hc, k, sz);
  HASH_DONE(&hc, h);
  memcpy(r->k.k, h, RAND_KEYSZ);
}

/* --- @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 h[HASH_SZ], g[4];
  HASH_CTX hc;
  CIPHER_CTX cc;

  RAND_RESOLVE(r);
  QUICK(r);

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

  HASH_INIT(&hc);
  STORE32(g, r->gen); HASH(&hc, g, sizeof(g));
  HASH(&hc, r->k.k, RAND_KEYSZ);
  HASH(&hc, r->pool, RAND_POOLSZ);
  HASH(&hc, r->buf, RAND_BUFSZ);
  HASH_DONE(&hc, h);
  BURN(hc);

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

  assert(CIPHER_KEYSZ <= HASH_SZ);
  CIPHER_INIT(&cc, h, CIPHER_KEYSZ, 0);
  CIPHER_ENCRYPT(&cc, r->pool, r->pool, RAND_POOLSZ);
  CIPHER_ENCRYPT(&cc, r->buf, r->buf, RAND_BUFSZ);
  BURN(cc);

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

  r->o = RAND_SECSZ;
  r->obits += r->ibits;
  if (r->obits > RAND_OBITS) {
    r->ibits = r->obits - RAND_OBITS;
    r->obits = RAND_OBITS;
  } else
    r->ibits = 0;
  QUICK(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 h[HASH_SZ], g[4];
  HASH_CTX hc;
  CIPHER_CTX cc;

  RAND_RESOLVE(r);
  QUICK(r);

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

  HASH_INIT(&hc);
  STORE32(g, r->gen); HASH(&hc, g, sizeof(g));
  HASH(&hc, r->k.k, RAND_KEYSZ);
  HASH(&hc, r->pool, RAND_POOLSZ);
  HASH(&hc, r->buf, RAND_BUFSZ);
  HASH_DONE(&hc, h);
  BURN(hc);

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

  assert(CIPHER_KEYSZ <= HASH_SZ);
  CIPHER_INIT(&cc, h, CIPHER_KEYSZ, 0);
  CIPHER_ENCRYPT(&cc, r->buf, r->buf, RAND_BUFSZ);
  BURN(cc);

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

  r->o = RAND_SECSZ;
  QUICK(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);
  GENCHECK(r);
  QUICK(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, ensuring that there are
 *		enough good bits.  This interface isn't recommended: it makes
 *		the generator slow, and doesn't provide much more security
 *		than @rand_get@, assuming you've previously done a
 *		@rand_seed@.
 */

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;
  }
  GENCHECK(r);
  QUICK(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 < 256);
      rand_gate(r);
      if (chunk * 8 > r->obits)
	chunk = r->obits / 8;
    }

    if (chunk + r->o <= RAND_BUFSZ) {
      memcpy(o, r->buf + r->o, chunk);
      r->o += chunk;
    } else {
      chunk = RAND_BUFSZ - r->o;
      memcpy(o, r->buf + r->o, chunk);
      rand_stretch(r);
    }

    r->obits -= chunk * 8;
    o += chunk;
    sz -= chunk;
  }
}

/*----- Generic random number generator interface -------------------------*/

static void gdestroy(grand *r)
{
  gctx *g = (gctx *)r;
  if (g != &rand_global) {
    BURN(*g);
    S_DESTROY(g);
  }
}

static int gmisc(grand *r, unsigned op, ...)
{
  gctx *g = (gctx *)r;
  va_list ap;
  int rc = 0;
  va_start(ap, op);

  switch (op) {
    case GRAND_CHECK:
      switch (va_arg(ap, unsigned)) {
	case GRAND_CHECK:
	case GRAND_SEEDINT:
	case GRAND_SEEDUINT32:
	case GRAND_SEEDBLOCK:
	case GRAND_SEEDRAND:
	case RAND_GATE:
	case RAND_STRETCH:
	case RAND_KEY:
	case RAND_NOISESRC:
	case RAND_SEED:
	case RAND_TIMER:
	case RAND_GOODBITS:
	case RAND_ADD:
	  rc = 1;
	  break;
	default:
	  rc = 0;
	  break;
      }
      break;
    case GRAND_SEEDINT: {
      unsigned u = va_arg(ap, unsigned);
      rand_add(&g->p, &u, sizeof(u), sizeof(u));
    } break;
    case GRAND_SEEDUINT32: {
      uint32 i = va_arg(ap, uint32);
      rand_add(&g->p, &i, sizeof(i), 4);
    } break;
    case GRAND_SEEDBLOCK: {
      const void *p = va_arg(ap, const void *);
      size_t sz = va_arg(ap, size_t);
      rand_add(&g->p, p, sz, sz);
    } break;
    case GRAND_SEEDRAND: {
      grand *rr = va_arg(ap, grand *);
      octet buf[16];
      rr->ops->fill(rr, buf, sizeof(buf));
      rand_add(&g->p, buf, sizeof(buf), 8);
    } break;
    case RAND_GATE:
      rand_gate(&g->p);
      break;
    case RAND_STRETCH:
      rand_stretch(&g->p);
      break;
    case RAND_KEY: {
      const void *k = va_arg(ap, const void *);
      size_t sz = va_arg(ap, size_t);
      rand_key(&g->p, k, sz);
    } break;
    case RAND_NOISESRC:
      rand_noisesrc(&g->p, va_arg(ap, const rand_source *));
      break;
    case RAND_SEED:
      rand_seed(&g->p, va_arg(ap, unsigned));
      break;
    case RAND_TIMER:
      QUICK(&g->p);
      break;
    case RAND_GOODBITS:
      rc = rand_goodbits(&g->p);
      break;
    case RAND_ADD: {
      const void *p = va_arg(ap, const void *);
      size_t sz = va_arg(ap, size_t);
      unsigned goodbits = va_arg(ap, unsigned);
      rand_add(&g->p, p, sz, goodbits);
    } break;
    default:
      GRAND_BADOP;
      break;
  }

  va_end(ap);
  return (rc);
}

static octet gbyte(grand *r)
{
  gctx *g = (gctx *)r;
  octet o;
  rand_getgood(&g->p, &o, 1);
  return (o);
}

static uint32 gword(grand *r)
{
  gctx *g = (gctx *)r;
  octet b[4];
  rand_getgood(&g->p, &b, sizeof(b));
  return (LOAD32(b));
}

static void gfill(grand *r, void *p, size_t sz)
{
  gctx *g = (gctx *)r;
  rand_get(&g->p, p, sz);
}

static const grand_ops gops = {
  "rand",
  GRAND_CRYPTO, 0,
  gmisc, gdestroy,
  gword, gbyte, gword, grand_defaultrange, gfill
};

/* --- @rand_create@ --- *
 *
 * Arguments:	---
 *
 * Returns:	Pointer to a generic generator.
 *
 * Use:		Constructs a generic generator interface over a Catacomb
 *		entropy pool generator.
 */

grand *rand_create(void)
{
  gctx *g = S_CREATE(gctx);
  g->r.ops = &gops;
  rand_init(&g->p);
  return (&g->r);
}

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