Bad bug makes all previous testing worthless.

[storin] / dsarand.c

/* -*-c-*-
 *
 * $Id: dsarand.c,v 1.1 2000/05/21 11:28:30 mdw Exp $
 *
 * Random number generator for DSA
 *
 * (c) 1999 Straylight/Edgeware
 * (c) 2000 Mark Wooding
 */

/*----- Licensing notice --------------------------------------------------* 
 *
 * Copyright (c) 2000 Mark Wooding
 * All rights reserved.
 * 
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met:
 * 
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 
 * 2, Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 
 * 3. The name of the authors may not be used to endorse or promote
 *    products derived from this software without specific prior written
 *    permission.
 * 
 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED
 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN
 * NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
 * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 * 
 * Instead of accepting the above terms, you may redistribute and/or modify
 * this software under the terms of either the GNU General Public License,
 * or the GNU Library General Public License, published by the Free
 * Software Foundation; either version 2 of the License, or (at your
 * option) any later version.
 */

/*----- Revision history --------------------------------------------------* 
 *
 * $Log: dsarand.c,v $
 * Revision 1.1  2000/05/21 11:28:30  mdw
 * Initial check-in.
 *
 * --- Past lives (Catacomb) --- *
 *
 * Revision 1.1  1999/12/22 15:53:12  mdw
 * Random number generator for finding DSA parameters.
 *
 */

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

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

#include "bits.h"
#include "dsarand.h"
#include "sha.h"

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

/* --- @STEP@ --- *
 *
 * Arguments:	@dsarand *d@ = pointer to context
 *
 * Use:		Increments the buffer by one, interpreting it as a big-endian
 *		integer.  Carries outside the integer are discarded.
 */

#define STEP(d) do {							\
  dsarand *_d = (d);							\
  octet *_p = _d->p;							\
  octet *_q = _p + _d->sz;						\
  unsigned _c = 1;							\
  while (_c && _q > _p) {						\
    _c += *--_q;							\
    *_q = U8(_c);							\
    _c >>= 8;								\
  }									\
} while (0)

/* --- @dsarand_init@ --- *
 *
 * Arguments:	@dsarand *d@ = pointer to context
 *		@const void *p@ = pointer to seed buffer
 *		@size_t sz@ = size of the buffer
 *
 * Returns:	---
 *
 * Use:		Initializes a DSA random number generator.
 */

void dsarand_init(dsarand *d, const void *p, size_t sz)
{
  if ((d->p = malloc(sz)) == 0) {
    fputs("Out of memory in dsarand_init!\n", stderr);
    exit(EXIT_FAILURE);
  }
  d->sz = sz;
  d->passes = 1;
  if (p)
    memcpy(d->p, p, sz);
}

/* --- @dsarand_reseed@ --- *
 *
 * Arguments:	@dsarand *d@ = pointer to context
 *		@const void *p@ = pointer to seed buffer
 *		@size_t sz@ = size of the buffer
 *
 * Returns:	---
 *
 * Use:		Initializes a DSA random number generator.
 */

void dsarand_reseed(dsarand *d, const void *p, size_t sz)
{
  free(d->p);
  if ((d->p = malloc(sz)) != 0) {
    fputs("Out of memory in dsarand_init!\n", stderr);
    exit(EXIT_FAILURE);
  }
  d->sz = sz;
  d->passes = 1;
  if (p)
    memcpy(d->p, p, sz);
}

/* --- @dsarand_destroy@ --- *
 *
 * Arguments:	@dsarand *d@ = pointer to context
 *
 * Returns:	---
 *
 * Use:		Disposes of a DSA random number generation context.
 */

void dsarand_destroy(dsarand *d)
{
  free(d->p);
}

/* --- @dsarand_fill@ --- *
 *
 * Arguments:	@dsarand *d@ = pointer to context
 *		@void *p@ = pointer to output buffer
 *		@size_t sz@ = size of output buffer
 *
 * Returns:	---
 *
 * Use:		Fills an output buffer with pseudorandom data.
 *
 *		Let %$p$% be the numerical value of the input buffer, and let
 *		%$b$% be the number of bytes required.  Let
 *		%$z = \lceil b / 20 \rceil$% be the number of SHA outputs
 *		required.  Then the output of pass %$n$% is
 *
 *		  %$P_n = \sum_{0 \le i < z} 2^{160i} SHA(p + nz + i)$%
 *							%${} \bmod 2^{8b}$%
 *
 *		and the actual result in the output buffer is the XOR of all
 *		of the output passes.
 *
 *		The DSA procedure for choosing @q@ involves two passes with
 *		%$z = 1$%; the procedure for choosing @p@ involves one pass
 *		with larger %$z$%.  This generalization of the DSA generation
 *		procedure is my own invention but it seems relatively sound.
 */

void dsarand_fill(dsarand *d, void *p, size_t sz)
{
  octet *q = p;
  unsigned n = d->passes;

  /* --- Write out the first pass --- *
   *
   * This can write directly to the output buffer, so it's done differently
   * from the latter passes.
   */

  {
    size_t o = sz;

    while (o) {
      sha_ctx h;

      /* --- Hash the input buffer --- */

      sha_init(&h);
      sha_hash(&h, d->p, d->sz);

      /* --- If enough space, extract the hash output directly --- */

      if (o >= SHA_HASHSZ) {
	o -= SHA_HASHSZ;
	sha_done(&h, q + o);
      }

      /* --- Otherwise take the hash result out of line and copy it --- */

      else {
	octet hash[SHA_HASHSZ];
	sha_done(&h, hash);
	memcpy(q, hash + (SHA_HASHSZ - o), o);
	o = 0;
      }

      /* --- Step the input buffer --- */

      STEP(d);
    }

    /* --- Another pass has been done --- */

    n--;
  }

  /* --- Write out subsequent passes --- *
   *
   * The hash output has to be done offline, so this is slightly easier.
   */

  while (n) {
    size_t o = sz;

    while (o) {
      sha_ctx h;
      octet hash[SHA_HASHSZ];
      size_t n;
      octet *pp, *qq;

      /* --- Hash the input buffer --- */

      sha_init(&h);
      sha_hash(&h, d->p, d->sz);
      sha_done(&h, hash);

      /* --- Work out how much output is wanted --- */

      n = SHA_HASHSZ;
      if (n > o)
	n = o;
      o -= n;

      /* --- XOR the data out --- */

      for (pp = hash + (SHA_HASHSZ - n), qq = q + o;
	   pp < hash + SHA_HASHSZ; pp++, qq++)
	*qq ^= *pp;

      /* --- Step the input buffer --- */

      STEP(d);
    }

    /* --- Another pass is done --- */

    n--;
  }
}

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