Major update: make random number sources configurable. Generate

[become] / src / keygen.c

/* -*-c-*-
 *
 * $Id: keygen.c,v 1.4 1997/12/08 15:29:27 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.4  1997/12/08 15:29:27  mdw
 * Major update: make random number sources configurable.  Generate
 * warnings if there isn't enough randomness available.
 *
 * 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;
  size_t keybits = 0;
  unsigned f = 0;
  const char *file = 0;
  FILE *fp;

  enum {
    f_envNoise = 1,
    f_keyTimer = 2
  };

  /* --- 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]);

  f |= f_envNoise | f_keyTimer;

  /* --- 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' },
      { "key-times",    gFlag_negate|gFlag_argOpt,      0,      'k' },
      { "env-noise",    gFlag_negate,                   0,      'e' },
      { 0,              0,                              0,      0 }
    };

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

    if (i < 0)
      break;
    switch (i) {
      case 'h':
        printf(""
"Usage: %s [-h] [-|+ek] [-b BITS] [-o FILE] [-f FORMAT]\n"
"\n"
"Generates BITS (by default, 128) random bits.  The resulting number is\n"
"written to FILE, or standard output.\n\n"
"Randomness is taken from key-timings and environmental noise, although\n"
"you can disable either (or both) of these sources.\n\n"
"Options provided are:\n\n"
"-h, --help                     Display this help text\n"
"-b, --bits=BITS\t              Generate BITS random bits instead of 128\n"
"-o, --output=FILE              Write bits to FILE, not standard output\n"
"-f, --format=FORMAT            Write bits in FORMAT:\n"
"                                 tx, hex  Hexadecimal\n"
"                                 binary   Raw binary\n"
"                                 base64   Base64-encoded binary\n"
"-e, --[no-]env-noise           Do [not] read environmental noise\n"
"-k, --[no-]key-times[=BITS]    Do [not] read key timing information\n"
"                                 (only read BITS bits from key timings)\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 'e':
        f |= f_envNoise;
        break;
      case 'e' | gFlag_negated:
        f &= ~f_envNoise;
        break;
      case 'k':
        f |= f_keyTimer;
        if (optarg) {
          keybits = atoi(optarg);
          if (keybits == 0)
            die("bad number of bits (illegible or zero)");
          if (keybits % 8)
            die("bad number of bits (must be multiple of 8)");
        }
        else
          keybits = 0;
        break;
      case 'k' | gFlag_negated:
        f &= ~f_keyTimer;
        break;
      case '?':
        exit(1);
        break;
    }
  }

  /* --- Check the sanity of this request --- */

  {
    size_t bits = 0;

    if (f & f_keyTimer) {
      if (!keybits)
        keybits = sz;
      bits += keybits;
    }
    if (f & f_envNoise)
      bits += 384; /* Estimate */

    if (bits == 0)
      die("no randomness sources given");
    if (bits < sz)
      moan("warning: randomness may not be sufficiently high");
  } 

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

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

  {
    size_t buff = sz / 8;
    if (f & f_keyTimer && keybits > sz)
      buff = keybits / 8;
    uip = xmalloc(buff);
  }

  rand_clear();

  /* --- Fetch randomness from key timings --- */

  if (f & f_keyTimer) {

    /* --- 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);

    /* --- 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, keybits);
    kg__crepair();
    rand_add(uip, keybits / 8);
    rand_churn();
  }

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

  if (f & f_envNoise) {
    noise_acquire();
    rand_churn();
  }

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

  rand_extract(uip, sz / 8);
  D( fputs("*** ", fp); tx_putBits(uip, sz, stdout); )

  /* --- 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;

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

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