(mkphrase): New program for generating random passphrases with measured

[u/mdw/catacomb] / mkphrase.c

/* -*-c-*-
 *
 * $Id: mkphrase.c,v 1.1 2000/08/06 10:50:55 mdw Exp $
 *
 * Generate passphrases from word lists
 *
 * (c) 2000 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.
 */

/*----- Revision history --------------------------------------------------* 
 *
 * $Log: mkphrase.c,v $
 * Revision 1.1  2000/08/06 10:50:55  mdw
 * (mkphrase): New program for generating random passphrases with measured
 * strength.
 *
 */

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

#include "config.h"

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

#include <mLib/alloc.h>
#include <mLib/bits.h>
#include <mLib/darray.h>
#include <mLib/dstr.h>
#include <mLib/mdwopt.h>
#include <mLib/quis.h>
#include <mLib/report.h>
#include <mLib/sym.h>

#include "grand.h"
#include "noise.h"
#include "rand.h"

/*----- Global state ------------------------------------------------------*/

static unsigned min = 0, max = 256;	/* Word length bounds */
static unsigned bits = 128;		/* Minimum acceptable entropy */
static unsigned count = 1;		/* How many passphrases to make */

static const char wchars[] = "abcdefghijklmnopqrstuvwxyz'";

typedef struct ppgen_ops {
  const char *name;			/* Name of the generator */
  void *(*init)(void);			/* Initialize generator */
  void (*scan)(FILE */*fp*/, void */*p*/); /* Scan an input word list */
  void (*endscan)(void */*p*/);		/* Scanning phase completed */
  double (*gen)(dstr */*d*/, grand */*r*/, void */*p*/);
					/* Emit word and return entropy */
  void (*done)(void */*p*/);		/* Close down generator */
} ppgen_ops;

/*----- Word list ---------------------------------------------------------*/

#ifndef STRING_V
#  define STRING_V
   DA_DECL(string_v, char *);
#endif

typedef struct wlist {
  string_v sv;
  sym_table tab;
  char *buf;
  double logp;
} wlist;

static void *wordlist_init(void)
{
  wlist *w = xmalloc(sizeof(wlist));
  sym_create(&w->tab);
  w->logp = 0;
  return (w);
}

static void wordlist_scan(FILE *fp, void *p)
{
  wlist *w = p;
  dstr d = DSTR_INIT;
  unsigned f = 0;

  for (;;) {
    int ch = getc(fp);
    if (ch == EOF || isspace(ch)) {
      DPUTZ(&d);
      if (f && d.len >= min && d.len <= max)
	sym_find(&w->tab, d.buf, d.len + 1, sizeof(sym_base), 0);
      f = 0;
      DRESET(&d);
      if (ch == EOF)
	break;
      continue;
    }
    ch = tolower(ch);
    if (strchr(wchars, ch)) {
      DPUTC(&d, ch);
      f = 1;
    }
  }

  dstr_destroy(&d);
}

static void wordlist_endscan(void *p)
{
  wlist *w = p;
  size_t buflen = 0;
  sym_iter i;
  sym_base *b;
  char *q;

  for (sym_mkiter(&i, &w->tab); (b = sym_next(&i)) != 0; )
    buflen += b->len;
  w->buf = xmalloc(buflen);
  q = w->buf;
  DA_CREATE(&w->sv);
  for (sym_mkiter(&i, &w->tab); (b = sym_next(&i)) != 0; ) {
    memcpy(q, SYM_NAME(b), b->len);
    DA_PUSH(&w->sv, q);
    q += b->len;
  }
  sym_destroy(&w->tab);
  w->logp = log(DA_LEN(&w->sv))/log(2);
}

static double wordlist_gen(dstr *d, grand *r, void *p)
{
  wlist *w = p;
  uint32 i = r->ops->range(r, DA_LEN(&w->sv));
  DPUTS(d, DA(&w->sv)[i]);
  return (w->logp);
}

static void wordlist_done(void *p)
{
  wlist *w = p;
  xfree(w->buf);
  DA_DESTROY(&w->sv);
  xfree(w);
}

static ppgen_ops wordlist_ops = {
  "wordlist",
  wordlist_init, wordlist_scan, wordlist_endscan, wordlist_gen, wordlist_done
};

/*----- Markov word model -------------------------------------------------*/

enum {
  C_START = 27,
  C_END,
  VECSZ
};

typedef struct node {
  uint32 count;
  uint32 p[VECSZ];
} node;

static void *markov_init(void)
{
  node (*model)[VECSZ][VECSZ][VECSZ] = xmalloc(sizeof(*model));
  unsigned i, j, k, l;
  
  for (i = 0; i < VECSZ; i++) {
    for (j = 0; j < VECSZ; j++) {
      for (k = 0; k < VECSZ; k++) {
	node *n = &(*model)[i][j][k];
	n->count = 0;
	for (l = 0; l < VECSZ; l++)
	  n->p[l] = 0;
      }
    }
  }

  return (model);
}

static void markov_scan(FILE *fp, void *p)
{
  node (*model)[VECSZ][VECSZ][VECSZ] = p;
  unsigned i = C_START, j = C_START, k = C_START, l = C_END;

  for (;;) {
    int ch = getc(fp);
    const char *q;
    node *n = &(*model)[i][j][k];

    if (ch == EOF || isspace(ch)) {
      if (l != C_END) {
	l = C_END;
	n->count++;
	n->p[l]++;
	i = j = k = C_START;
      }
      if (ch == EOF)
	break;
      continue;
    }

    if ((q = strchr(wchars, tolower(ch))) == 0)
      continue;
    l = q - wchars;
    n->count++;
    n->p[l]++;
    i = j; j = k; k = l;
  }
}

static double markov_gen(dstr *d, grand *r, void *p)
{
  node (*model)[VECSZ][VECSZ][VECSZ] = p;
  unsigned i = C_START, j = C_START, k = C_START, l;
  double logp = 0;
  double log2 = log(2);

  for (;;) {
    node *n = &(*model)[i][j][k];
    uint32 z = r->ops->range(r, n->count);
    for (l = 0; z >= n->p[l]; z -= n->p[l++])
      ;
    logp -= log((double)n->p[l]/(double)n->count)/log2;
    if (l == C_END)
      break;
    DPUTC(d, wchars[l]);
    i = j; j = k; k = l;
  }

  return (logp);
}

static void markov_done(void *p)
{
  node (*model)[VECSZ][VECSZ][VECSZ] = p;
  xfree(model);
}

static ppgen_ops markov_ops = {
  "markov",
  markov_init, markov_scan, 0, markov_gen, markov_done
};

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

static ppgen_ops *ppgentab[] = {
  &markov_ops,
  &wordlist_ops,
  0
};

static void version(FILE *fp)
{
  pquis(fp, "$, Catacomb version " VERSION "\n");
}

static void usage(FILE *fp)
{
  pquis(fp, "\
Usage: $ [-p] [-b bits] [-g gen] [-n count] [-r [min-]max] wordlist...\n\
");
}

static void help(FILE *fp)
{
  ppgen_ops **ops;
  version(fp);
  fputc('\n', fp);
  usage(fp);
  pquis(fp, "\n\
Generates random passphrases with the requested level of entropy.  Options\n\
supported are:\n\
\n\
-h, --help		Show this help text.\n\
-v, --version		Show the program's version number.\n\
-u, --usage		Show a terse usage summary.\n\
-b, --bits=BITS		Produce at least BITS bits of entropy.\n\
-g, --generator=GEN	Use passphrase generator GEN.\n\
-n, --count=COUNT	Generate COUNT passphrases.\n\
-p, --probability	Show -log_2 of probability for each phrase.\n\
-r, --range=[MIN-]MAX	Supply minimum and maximum word lengths.\n\
\n\
Generators currently available:");
  for (ops = ppgentab; *ops; ops++)
    fprintf(fp, " %s", (*ops)->name);
  fputc('\n', fp);
}

int main(int argc, char *argv[])
{
  ppgen_ops *ops = ppgentab[0];
  unsigned f = 0;
  void *ctx;
  dstr d = DSTR_INIT;
  dstr dd = DSTR_INIT;
  unsigned i;

  enum {
    f_bogus = 1,
    f_showp = 2
  };

  ego(argv[0]);
  for (;;) {
    static struct option opts[] = {
      { "help",		0,		0,	'h' },
      { "version",	0,		0,	'v' },
      { "usage",	0,		0,	'u' },
      { "bits",		OPTF_ARGREQ,	0,	'b' },
      { "generator",	OPTF_ARGREQ,	0,	'g' },
      { "count",	OPTF_ARGREQ,	0,	'n' },
      { "probability",	0,		0,	'p' },
      { "range",	OPTF_ARGREQ,	0,	'r' },
      { 0,		0,		0,	0 }
    };
    int i = mdwopt(argc, argv, "hvu b:g:n:pr:", opts, 0, 0, 0);

    if (i < 0)
      break;
    switch (i) {
      case 'h':
	help(stdout);
	exit(0);
      case 'v':
	version(stdout);
	exit(0);
      case 'u':
	usage(stdout);
	exit(0);
      case 'b': {
	char *p;
	unsigned long n = strtoul(optarg, &p, 0);
	if (*p)
	  die(EXIT_FAILURE, "bad integer `%s'", optarg);
	bits = n;
      } break;
      case 'g': {
	ppgen_ops **p;
	size_t n = strlen(optarg);
	ops = 0;
	for (p = ppgentab; *p; p++) {
	  if (strncmp(optarg, (*p)->name, n) == 0) {
	    if (!(*p)->name[n]) {
	      ops = *p;
	      break;
	    } else if (ops)
	      die(EXIT_FAILURE, "ambiguous generator name `%s'", optarg);
	    ops = *p;
	  }
	}
	if (!ops)
	  die(EXIT_FAILURE, "unknown generator name `%s'", optarg);
      } break;
      case 'n': {
	char *p;
	unsigned long n = strtoul(optarg, &p, 0);
	if (*p)
	  die(EXIT_FAILURE, "bad integer `%s'", optarg);
	count = n;
      } break;
      case 'p':
	f |= f_showp;
	break;
      case 'r': {
	char *p;
	unsigned long n = min, nn = max;
	nn = strtoul(optarg, &p, 0);
	if (*p == '-') {
	  n = nn;
	  nn = strtoul(p + 1, &p, 0);
	}
	if (*p)
	  die(EXIT_FAILURE, "bad range string `%s'", optarg);
	min = n; max = nn;
      } break;
      default:
	f |= f_bogus;
	break;
    }
  }

  argc -= optind;
  argv += optind;
  if ((f & f_bogus) || !argc) {
    usage(stderr);
    exit(EXIT_FAILURE);
  }

  rand_noisesrc(RAND_GLOBAL, &noise_source);
  rand_seed(RAND_GLOBAL, 160);

  ctx = ops->init();
  while (*argv) {
    if (strcmp(*argv, "-") == 0)
      ops->scan(ctx, stdin);
    else {
      FILE *fp = fopen(*argv, "r");
      if (!fp) {
	die(EXIT_FAILURE, "error opening file `%s': %s",
	    *argv, strerror(errno));
      }
      ops->scan(fp, ctx);
      fclose(fp);
    }
    argv++;
  }
  if (ops->endscan)
    ops->endscan(ctx);

  for (i = 0; !count || i < count; i++) {
    double logp = 0;
    DRESET(&d);
    while (logp < bits) {
      double pp;
      DRESET(&dd);
      pp = ops->gen(&dd, &rand_global, ctx);
      if (!pp || dd.len < min || dd.len > max)
	continue;
      if (logp)
	DPUTC(&d, ' ');
      DPUTD(&d, &dd);
      logp += pp;
    }
    dstr_write(&d, stdout);
    if (f & f_showp)
      printf(" [%g]", logp);
    fputc('\n', stdout);
  }

  ops->done(ctx);
  dstr_destroy(&d);
  dstr_destroy(&dd);
  return (0);
}

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