--- /dev/null
+/* -*-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 -------------------------------------------------*/
projects / u / mdw / catacomb / commitdiff