Mix the noise from the key timings with some other environmental noise

[become] / src / keygen.c

/* -*-c-*-
 *
 * $Id: keygen.c,v 1.3 1997/09/17 15:29:28 mdw Exp $
 *
 * Key generation
 *
 * (c) 1997 EBI
 */

/*----- Licensing 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: keygen.c,v $
 * Revision 1.3  1997/09/17 15:29:28  mdw
 * Mix the noise from the key timings with some other environmental noise
 * (obtained from `noise_acquire') for a little bit more randomness.
 *
 * Revision 1.2  1997/08/04 10:24:23  mdw
 * Sources placed under CVS control.
 *
 * Revision 1.1  1997/07/21  13:47:48  mdw
 * Initial revision
 *
 */

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

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

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

/* --- Unix headers --- */

#include <sys/types.h>
#include <sys/time.h>
#include <fcntl.h>

#include <termios.h>
#include <unistd.h>

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

#include "config.h"
#include "mdwopt.h"
#include "noise.h"
#include "rand.h"
#include "tx.h"
#include "utils.h"

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

static struct termios kg__raw, kg__old;	/* Terminal settings */
static int kg__tty;			/* File handle for the terminal */
static FILE *kg__ttyfp;			/* Stream pointer for terminal */
static unsigned int kg__flags;		/* Various interesting flags */

enum {
  kgFlag__cbreak = 1			/* Terminal is in cbreak mode */
};

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

/* --- @kg__cbreak@ --- *
 *
 * Arguments:	---
 *
 * Returns:	---
 *
 * Use:		Makes the terminal return characters as soon as they're
 *		asked for.
 */

void kg__cbreak(void)
{
  /* --- Don't do this if I don't have to --- */

  if (kg__flags & kgFlag__cbreak)
    return;

  /* --- Fetch the old attributes, and remember them --- */

  if (tcgetattr(kg__tty, &kg__old))
    die("couldn't read terminal attributes: %s", strerror(errno));
  memcpy(&kg__raw, &kg__old, sizeof(kg__raw));

  /* --- Now modify them for raw mode --- */

  kg__raw.c_lflag &= ~(ICANON | ECHO);
  kg__raw.c_cc[VTIME] = 0;
  kg__raw.c_cc[VMIN] = 1;

  /* --- Remember the new state, and away we go --- */

  kg__flags |= kgFlag__cbreak;
  if (tcsetattr(kg__tty, TCSAFLUSH, &kg__raw))
    die("couldn't set terminal attributes: %s", strerror(errno));
}

/* --- @kg__crepair@ --- *
 *
 * Arguments:	---
 *
 * Returns:	---
 *
 * Use:		Unbreaks a cbroken tty.  Obvious, innit?
 */

static void kg__crepair(void)
{
  /* --- Don't do this if I don't have to --- */

  if (~kg__flags & kgFlag__cbreak)
    return;

  /* --- Reset the old attributes --- */

  tcsetattr(kg__tty, TCSAFLUSH, &kg__old);
  kg__flags &= ~kgFlag__cbreak;
}

/* --- @kg__signal@ --- *
 *
 * Arguments:	@int sig@ = signal number
 *
 * Returns:	---
 *
 * Use:		Tidies up if I get a signal.
 */

static void kg__signal(int sig)
{
  kg__crepair();
  signal(sig, SIG_DFL);
  raise(sig);
}

/* --- @kgFmt__binary@ --- *
 *
 * Arguments:	@unsigned char *k@ = pointer to key buffer
 *		@size_t bits@ = number of bits to write
 *		@FILE *fp@ = stream to write on
 *
 * Returns:	---
 *
 * Use:		Writes bits on a stream.
 */

static void kgFmt__binary(unsigned char *k, size_t bits, FILE *fp)
{
  fwrite(k, 1, bits / 8, fp);
}

/* --- @kgFmt__base64@ --- *
 *
 * Arguments:	@unsigned char *k@ = pointer to key buffer
 *		@size_t bits@ = number of bits to write
 *		@FILE *fp@ = stream to write on
 *
 * Returns:	---
 *
 * Use:		Writes bits on a stream in an encoded way.
 */

static void kgFmt__base64(unsigned char *k, size_t bits, FILE *fp)
{
  static const char xlt[64] = { "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
				"abcdefghijklmnopqrstuvwxyz"
				"0123456789+/" };
  unsigned long b;
  int ll = 0;

  while (bits > 24) {
    b = ((k[0] & 0xffu) << 16) | ((k[1] & 0xffu) << 8) | (k[2] & 0xffu);
    k += 3;
    bits -= 24;
    putc(xlt[(b >> 18) & 0x3fu], fp);
    putc(xlt[(b >> 12) & 0x3fu], fp);
    putc(xlt[(b >>  6) & 0x3fu], fp);
    putc(xlt[(b >>  0) & 0x3fu], fp);
    if ((ll += 4) > 70) {
      putc('\n', fp);
      ll = 0;
    }
  }

  b = 0;
  switch (bits) {
    case 24:
      b = *k++ & 0xffu;
    case 16:
      b = (b << 8) | (*k++ & 0xffu);
    case 8:
      b = (b << 8) | (*k++ & 0xffu);
  }
  b <<= (24 - bits);
  putc(xlt[(b >> 18) & 0x3fu], fp);
  putc(xlt[(b >> 12) & 0x3fu], fp);
  switch (bits) {
    case 24:
      putc(xlt[(b >>  6) & 0x3fu], fp);
      putc(xlt[(b >>  0) & 0x3fu], fp);
      break;
    case 16:
      putc(xlt[(b >>  6) & 0x3fu], fp);
      putc('=', fp);
      break;
    case 8:
      fputs("==", fp);
      break;
  }

  putc('\n', fp);
}

/* --- @kg__gen@ --- *
 *
 * Arguments:	@unsigned char *ui@ = pointer to array to fill in
 *		@size_t sz@ = number of bits to generate
 *
 * Returns:	---
 *
 * Use:		Uses key timings to generate random numbers.  Maybe.
 */

static void kg__gen(unsigned char *ui, size_t sz)
{
  int bits = 32 < sz ? 32 : sz;
  size_t wsz = (sz + 31u) & ~31u;
  unsigned long last, ldiff = 0;
  unsigned long a = 0;
  unsigned long fact = 1000000 / CLOCKS_PER_SEC;

  fprintf(kg__ttyfp,
"I need to get %lu random bits; I'll do this by timing your keypresses.\n"
"Please type some arbitrary text until I say `done'.\n",
	  (unsigned long)sz);

  {
    struct timeval tv;
    gettimeofday(&tv, 0);
    last = tv.tv_usec / fact + tv.tv_sec * fact;
  }

  while (sz) {
    int useful;
    uint_32 orr, xor;

    /* --- Print current status --- */

    fprintf(kg__ttyfp, "\r%5lu...", (unsigned long)sz);
    fflush(kg__ttyfp);

    /* --- Read the next character --- */

    {
      char buff[16];
      if (read(kg__tty, buff, sizeof(buff)) < 0)
	die("couldn't read from terminal: %s", strerror(errno));
    }

    /* --- Fiddle with times --- *
     *
     * Read the time now.  Turn it into 32 bits of useful information, and
     * find the difference between that and the previous time.  Compare this
     * with the difference between the previous pair of keypresses.
     */

    {
      struct timeval tv;
      uint_32 n, nd;

      gettimeofday(&tv, 0);
      n = tv.tv_usec / fact + tv.tv_sec * fact;
      if (!ldiff) {
	ldiff = n - last;
	last = n;
	continue;
      }
      nd = n - last;
      orr = nd | ldiff;
      xor = nd ^ ldiff;
      D( printf("\nlast = %08lx, next = %08lx, ldiff = %08lx, nd = %08lx\n",
		(unsigned long)last, (unsigned long)n,
		(unsigned long)ldiff, (unsigned long)nd);
	 printf("xor = %08lx\n", (unsigned long)xor); )
      ldiff = nd;
      last = n;
    }

    /* --- Find the useful bits in this value --- *
     *
     * Find the least significant set bit in @bowl@ and chop it off.  Then
     * find the most significant set bit and chop that off two.  The rest is
     * probably interesting.
     */

    {
      unsigned long i;

      if (!orr || !xor)
	continue; /* erk! */

      useful = 30;

      i = 0x80000000ul;
      if (xor & i) {
	while (i && (xor & i) != 0) {
	  i >>= 1;
	  useful--;
	}
      } else {
	while (i && (xor & i) == 0) {
	  i >>= 1;
	  useful--;
	}
      }
      xor &= ~-i;

      while ((orr & 1) == 0) {
	useful--;
	orr >>= 1;
	xor >>= 1;
      }
      xor >>= 1;

      if (useful < 1)
	continue;
    }

    /* --- Now add the bits in the mixing bowl to my stash --- *
     *
     * There are two cases:
     *
     * 1. I have more bits than will fit into the accumulator.  Then I must
     *    put as many bits into the accumulator as will fit, store the
     *    accumulator, and remove the spent bits.
     *
     * 2. I have too few bits to fit in the accumulator.  Then shift them
     *    in and return.
     */

    while (sz && useful) {

      D( printf("got %i bits, need %i/%i: %8lx\n",
		useful, bits, sz, (unsigned long)xor); )

      if (useful >= bits) {

	D( printf("shifted acc = %08lx\n"
		  "   new bits = %08lx\n"
		  "     result = %08lx\n",
		  (unsigned long)(a << bits),
		  (unsigned long)(xor >> (useful - bits)),
		  (unsigned long)((a << bits) | (xor >> (useful - bits)))); )

	a = (a << bits) | (xor >> (useful - bits));

	sz -= bits;
	wsz -= bits;
	useful -= bits;

	if (sz == 0) {
	  a <<= wsz;
	  bits = 32 - wsz;
	} else
	  bits = 32;

	while (bits > 0) {
	  D( printf("writing %02x\n", (a >> 24) & 0xffu); )
	  *ui++ = (a >> 24) & 0xffu;
	  a <<= 8;
	  bits -= 8;
	}
	a = 0;

	bits = 32 < sz ? 32 : sz;

      } else {

	D( printf("shifted acc = %08lx\n"
		  "   new bits = %08lx\n"
		  "     result = %08lx\n",
		  (unsigned long)(a << useful),
		  (unsigned long)(xor),
		  (unsigned long)((a << useful) | (xor))); )
	a = (a << useful) | xor;
	bits -= useful;
	sz -= useful;
	wsz -= useful;
	useful = 0;
      }
    }
  }

  fputs("\rDone!         \n", kg__ttyfp);
  putc('\a', kg__ttyfp); fflush(kg__ttyfp);
  sleep(1);
}

/* --- @main@ --- *
 *
 * Arguments:	@int argc@ = number of arguments
 *		@char *argv[]@ = array of arguments
 *
 * Returns:	Zero if it worked, nonzero if it didn't.
 *
 * Use:		Generates random numbers from the keyboard.
 */

int main(int argc, char *argv[])
{
  unsigned char *uip;
  size_t sz = 128;
  const char *file = 0;
  FILE *fp;

  /* --- Formats table --- */

  static struct {
    const char *name;
    void (*proc)(unsigned char *k, size_t bits, FILE *fp);
  } format[] = {
    { "tx",	tx_putBits },
    { "hex",	tx_putBits },
    { "binary",	kgFmt__binary },
    { "base64",	kgFmt__base64 },
    { 0, 0 }
  };

  void (*fmt)(unsigned char *, size_t, FILE *) = tx_putBits;

  /* --- Explain who I am --- */

  ego(argv[0]);

  /* --- Read arguments --- */

  for (;;) {
    static struct option opts[] = {
      { "help",		0,		0,	'h' },
      { "bits",		gFlag_argReq,	0,	'b' },
      { "output",	gFlag_argReq,	0,	'o' },
      { "format",	gFlag_argReq,	0,	'f' },
      { 0,		0,		0,	0 }
    };

    int i = mdwopt(argc, argv, "hb:o:f:", opts, 0, 0, 0);

    if (i < 0)
      break;
    switch (i) {
      case 'h':
	printf(""
"Usage: %s [--bits=BITS] [--output=FILE] [--format=FORMAT]\n"
"\n"
"Generates BITS (by default, 128) random bits by timing keypresses.  The\n"
"resulting number is written to FILE, or standard output in the given\n"
"format.  Formats currently supported are:\n"
"\n"
"tx, hex		Hexadecimal, with punctuating dashes.\n"
"binary		Raw binary.\n"
"base64		Base64-encoded binary; the result is printable ASCII.\n",
	       quis());
	exit(0);
	break;
      case 'b':
	sz = atoi(optarg);
	if (sz == 0)
	  die("bad number of bits (illegible or zero)");
	if (sz % 8)
	  die("can only generate a whole number of 8-bit bytes");
	break;
      case 'o':
	file = optarg;
	break;
      case 'f':
	fmt = 0;
	for (i = 0; format[i].name; i++) {
	  const char *p = format[i].name, *q = optarg;
	  for (;;) {
	    if (*q == 0)
	      break;
	    if (*p != *q)
	      break;
	    p++, q++;
	  }
	  if (!*q) {
	    if (fmt)
	      die("ambiguous format name: `%s'", optarg);
	    fmt = format[i].proc;
	  }
	}
	if (!fmt)
	  die("unknown format name: `%s'", optarg);
	break;
      case '?':
	exit(1);
	break;
    }
  }

  if (optind < argc) {
    fprintf(stderr, "Usage: %s [--bits=BITS] [--output=FILE]\n", quis());
    exit(1);
  }

  /* --- Allocate memory --- */

  uip = xmalloc(sz / 8);

  /* --- Open the terminal --- *
   *
   * I'd like to be able to @fprintf@ to the terminal, so use @fopen@.
   */

  if ((kg__ttyfp = fopen("/dev/tty", "r+")) == 0)
    die("couldn't open terminal: %s", strerror(errno));
  kg__tty = fileno(kg__ttyfp);

  /* --- Open the output file, if one is specified --- */

  if (file) {
    int fd;

    /* --- Open the file oddly --- *
     *
     * There's a good reason for this.  I want to be able to @fprintf@ (for
     * the benefit of @tx_putWords@ mainly) but I also want to ensure that
     * only the user has read permissions for the file.  So I'll use @open@
     * with an appropriate mode and then @fdopen@ the file descriptor to get
     * a stream.  Yuk.
     */

    if ((fd = open(file, O_WRONLY | O_CREAT | O_TRUNC, 0600)) < 0)
      die("couldn't open output file: %s", strerror(errno));
    if ((fp = fdopen(fd, "w")) == 0)
      die("couldn't attach stream to output file: %s", strerror(errno));
  } else
    fp = stdout;

  /* --- Tidy up nicely if I die --- */

  signal(SIGINT, kg__signal);
  signal(SIGTERM, kg__signal);
  atexit(kg__crepair);

  /* --- Put the terminal into cbreak, read the key, and restore --- */

  kg__cbreak();
  kg__gen(uip, sz);
  kg__crepair();

  /* --- Find some noise from the environment too --- */

  rand_clear();
  noise_acquire();
  rand_add(uip, sz / 8);
  rand_churn();
  rand_extract(uip, sz / 8);

  /* --- Now write the number and exit --- */

  D( fputs("*** ", fp); tx_putBits(uip, sz, stdout); )
  fmt(uip, sz, fp);
  if (file)
    fclose(fp);
  memset(uip, 0, sz / 8);		/* Burn temporary buffer */
  rand_clear();
  return (0);
}

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