From b55540f69066f9127c964af2097b7563ab69369c Mon Sep 17 00:00:00 2001 From: mdw Date: Sun, 6 Aug 2000 10:50:55 +0000 Subject: [PATCH] (mkphrase): New program for generating random passphrases with measured strength. --- Makefile.m4 | 9 +- mkphrase.c | 462 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 469 insertions(+), 2 deletions(-) create mode 100644 mkphrase.c diff --git a/Makefile.m4 b/Makefile.m4 index f6c3b33..42e4125 100644 --- a/Makefile.m4 +++ b/Makefile.m4 @@ -1,6 +1,6 @@ ## -*-makefile-*- ## -## $Id: Makefile.m4,v 1.39 2000/07/29 21:55:32 mdw Exp $ +## $Id: Makefile.m4,v 1.40 2000/08/06 10:50:55 mdw Exp $ ## ## Makefile for Catacomb ## @@ -29,6 +29,10 @@ ##----- Revision history ---------------------------------------------------- ## ## $Log: Makefile.m4,v $ +## Revision 1.40 2000/08/06 10:50:55 mdw +## (mkphrase): New program for generating random passphrases with measured +## strength. +## ## Revision 1.39 2000/07/29 21:55:32 mdw ## Make sure the pixie is installed setuid-root (workaround for an Automake ## bug). Install new manpages. @@ -296,7 +300,7 @@ $(libcatacomb_la_OBJECTS) dsig.o keyutil.o rspit.o: mptypes.h primetab.h ## --- Utility programs --- -bin_PROGRAMS = dsig key pixie rspit factorial hashsum +bin_PROGRAMS = dsig key pixie rspit factorial hashsum mkphrase bin_SCRIPTS = catacomb-config xpixie noinst_PROGRAMS = \ genprimes mptypes \ @@ -312,6 +316,7 @@ rspit_SOURCES = rspit.c factorial_SOURCES = factorial.c pixie_SOURCES = pixie.c pixie-common.c lmem.c arena.c pixie_LDADD = +mkphrase_SOURCES = mkphrase.c des_mktab_SOURCES = des-mktab.c des_mktab_LDADD = diff --git a/mkphrase.c b/mkphrase.c new file mode 100644 index 0000000..f315108 --- /dev/null +++ b/mkphrase.c @@ -0,0 +1,462 @@ +/* -*-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 +#include +#include +#include +#include +#include + +#include +#include +#include +#include +#include +#include +#include +#include + +#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 -------------------------------------------------*/ -- 2.11.0