chiark - git - mdw - catacomb/blob - mkphrase.c

   1 /* -*-c-*-
   2  *
   3  * $Id$
   4  *
   5  * Generate passphrases from word lists
   6  *
   7  * (c) 2000 Straylight/Edgeware
   8  */
   9
  10 /*----- Licensing notice --------------------------------------------------*
  11  *
  12  * This file is part of Catacomb.
  13  *
  14  * Catacomb is free software; you can redistribute it and/or modify
  15  * it under the terms of the GNU Library General Public License as
  16  * published by the Free Software Foundation; either version 2 of the
  17  * License, or (at your option) any later version.
  18  *
  19  * Catacomb is distributed in the hope that it will be useful,
  20  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  21  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  22  * GNU Library General Public License for more details.
  23  *
  24  * You should have received a copy of the GNU Library General Public
  25  * License along with Catacomb; if not, write to the Free
  26  * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  27  * MA 02111-1307, USA.
  28  */
  29
  30 /*----- Header files ------------------------------------------------------*/
  31
  32 #include "config.h"
  33
  34 #include <ctype.h>
  35 #include <errno.h>
  36 #include <math.h>
  37 #include <stdio.h>
  38 #include <stdlib.h>
  39 #include <string.h>
  40
  41 #include <mLib/alloc.h>
  42 #include <mLib/bits.h>
  43 #include <mLib/darray.h>
  44 #include <mLib/dstr.h>
  45 #include <mLib/mdwopt.h>
  46 #include <mLib/quis.h>
  47 #include <mLib/report.h>
  48 #include <mLib/sym.h>
  49
  50 #include "grand.h"
  51 #include "noise.h"
  52 #include "rand.h"
  53
  54 /*----- Global state ------------------------------------------------------*/
  55
  56 static unsigned min = 0, max = 256;     /* Word length bounds */
  57 static unsigned bits = 128;             /* Minimum acceptable entropy */
  58 static unsigned count = 1;              /* How many passphrases to make */
  59
  60 static const char wchars[] = "abcdefghijklmnopqrstuvwxyz'";
  61
  62 typedef struct ppgen_ops {
  63   const char *name;                     /* Name of the generator */
  64   void *(*init)(void);                  /* Initialize generator */
  65   void (*scan)(FILE */*fp*/, void */*p*/); /* Scan an input word list */
  66   void (*endscan)(void */*p*/);         /* Scanning phase completed */
  67   double (*gen)(dstr */*d*/, grand */*r*/, void */*p*/);
  68                                         /* Emit word and return entropy */
  69   void (*done)(void */*p*/);            /* Close down generator */
  70 } ppgen_ops;
  71
  72 /*----- Word list ---------------------------------------------------------*/
  73
  74 #ifndef STRING_V
  75 #  define STRING_V
  76    DA_DECL(string_v, char *);
  77 #endif
  78
  79 typedef struct wlist {
  80   string_v sv;
  81   sym_table tab;
  82   char *buf;
  83   double logp;
  84 } wlist;
  85
  86 static void *wordlist_init(void)
  87 {
  88   wlist *w = xmalloc(sizeof(wlist));
  89   sym_create(&w->tab);
  90   w->logp = 0;
  91   return (w);
  92 }
  93
  94 static void wordlist_scan(FILE *fp, void *p)
  95 {
  96   wlist *w = p;
  97   dstr d = DSTR_INIT;
  98   unsigned f = 0;
  99
 100   for (;;) {
 101     int ch = getc(fp);
 102     if (ch == EOF || isspace(ch)) {
 103       DPUTZ(&d);
 104       if (f && d.len >= min && d.len <= max)
 105         sym_find(&w->tab, d.buf, d.len + 1, sizeof(sym_base), 0);
 106       f = 0;
 107       DRESET(&d);
 108       if (ch == EOF)
 109         break;
 110       continue;
 111     }
 112     ch = tolower(ch);
 113     if (strchr(wchars, ch)) {
 114       DPUTC(&d, ch);
 115       f = 1;
 116     }
 117   }
 118
 119   dstr_destroy(&d);
 120 }
 121
 122 static void wordlist_endscan(void *p)
 123 {
 124   wlist *w = p;
 125   size_t buflen = 0;
 126   sym_iter i;
 127   sym_base *b;
 128   char *q;
 129
 130   for (sym_mkiter(&i, &w->tab); (b = sym_next(&i)) != 0; )
 131     buflen += b->len;
 132   w->buf = xmalloc(buflen);
 133   q = w->buf;
 134   DA_CREATE(&w->sv);
 135   for (sym_mkiter(&i, &w->tab); (b = sym_next(&i)) != 0; ) {
 136     memcpy(q, SYM_NAME(b), b->len);
 137     DA_PUSH(&w->sv, q);
 138     q += b->len;
 139   }
 140   sym_destroy(&w->tab);
 141   w->logp = log(DA_LEN(&w->sv))/log(2);
 142 }
 143
 144 static double wordlist_gen(dstr *d, grand *r, void *p)
 145 {
 146   wlist *w = p;
 147   uint32 i = r->ops->range(r, DA_LEN(&w->sv));
 148   DPUTS(d, DA(&w->sv)[i]);
 149   return (w->logp);
 150 }
 151
 152 static void wordlist_done(void *p)
 153 {
 154   wlist *w = p;
 155   xfree(w->buf);
 156   DA_DESTROY(&w->sv);
 157   xfree(w);
 158 }
 159
 160 static ppgen_ops wordlist_ops = {
 161   "wordlist",
 162   wordlist_init, wordlist_scan, wordlist_endscan, wordlist_gen, wordlist_done
 163 };
 164
 165 /*----- Markov word model -------------------------------------------------*/
 166
 167 enum {
 168   C_START = 27,
 169   C_END,
 170   VECSZ
 171 };
 172
 173 typedef struct node {
 174   uint32 count;
 175   uint32 p[VECSZ];
 176 } node;
 177
 178 static void *markov_init(void)
 179 {
 180   node (*model)[VECSZ][VECSZ][VECSZ] = xmalloc(sizeof(*model));
 181   unsigned i, j, k, l;
 182
 183   for (i = 0; i < VECSZ; i++) {
 184     for (j = 0; j < VECSZ; j++) {
 185       for (k = 0; k < VECSZ; k++) {
 186         node *n = &(*model)[i][j][k];
 187         n->count = 0;
 188         for (l = 0; l < VECSZ; l++)
 189           n->p[l] = 0;
 190       }
 191     }
 192   }
 193
 194   return (model);
 195 }
 196
 197 static void markov_scan(FILE *fp, void *p)
 198 {
 199   node (*model)[VECSZ][VECSZ][VECSZ] = p;
 200   unsigned i = C_START, j = C_START, k = C_START, l = C_END;
 201
 202   for (;;) {
 203     int ch = getc(fp);
 204     const char *q;
 205     node *n = &(*model)[i][j][k];
 206
 207     if (ch == EOF || isspace(ch)) {
 208       if (l != C_END) {
 209         l = C_END;
 210         n->count++;
 211         n->p[l]++;
 212         i = j = k = C_START;
 213       }
 214       if (ch == EOF)
 215         break;
 216       continue;
 217     }
 218
 219     if ((q = strchr(wchars, tolower(ch))) == 0)
 220       continue;
 221     l = q - wchars;
 222     n->count++;
 223     n->p[l]++;
 224     i = j; j = k; k = l;
 225   }
 226 }
 227
 228 static double markov_gen(dstr *d, grand *r, void *p)
 229 {
 230   node (*model)[VECSZ][VECSZ][VECSZ] = p;
 231   unsigned i = C_START, j = C_START, k = C_START, l;
 232   double logp = 0;
 233   double log2 = log(2);
 234
 235   for (;;) {
 236     node *n = &(*model)[i][j][k];
 237     uint32 z = r->ops->range(r, n->count);
 238     for (l = 0; z >= n->p[l]; z -= n->p[l++])
 239       ;
 240     logp -= log((double)n->p[l]/(double)n->count)/log2;
 241     if (l == C_END)
 242       break;
 243     DPUTC(d, wchars[l]);
 244     i = j; j = k; k = l;
 245   }
 246
 247   return (logp);
 248 }
 249
 250 static void markov_done(void *p)
 251 {
 252   node (*model)[VECSZ][VECSZ][VECSZ] = p;
 253   xfree(model);
 254 }
 255
 256 static ppgen_ops markov_ops = {
 257   "markov",
 258   markov_init, markov_scan, 0, markov_gen, markov_done
 259 };
 260
 261 /*----- Main code ---------------------------------------------------------*/
 262
 263 static ppgen_ops *ppgentab[] = {
 264   &markov_ops,
 265   &wordlist_ops,
 266   0
 267 };
 268
 269 static void version(FILE *fp)
 270 {
 271   pquis(fp, "$, Catacomb version " VERSION "\n");
 272 }
 273
 274 static void usage(FILE *fp)
 275 {
 276   pquis(fp, "\
 277 Usage: $ [-p] [-b BITS] [-g GEN] [-n COUNT] [-r [MIN-]MAX] WORDLIST...\n\
 278 ");
 279 }
 280
 281 static void help(FILE *fp)
 282 {
 283   ppgen_ops **ops;
 284   version(fp);
 285   fputc('\n', fp);
 286   usage(fp);
 287   pquis(fp, "\n\
 288 Generates random passphrases with the requested level of entropy.  Options\n\
 289 supported are:\n\
 290 \n\
 291 -h, --help              Show this help text.\n\
 292 -v, --version           Show the program's version number.\n\
 293 -u, --usage             Show a terse usage summary.\n\
 294 -b, --bits=BITS         Produce at least BITS bits of entropy.\n\
 295 -g, --generator=GEN     Use passphrase generator GEN.\n\
 296 -n, --count=COUNT       Generate COUNT passphrases.\n\
 297 -p, --probability       Show -log_2 of probability for each phrase.\n\
 298 -r, --range=[MIN-]MAX   Supply minimum and maximum word lengths.\n\
 299 \n\
 300 Generators currently available:");
 301   for (ops = ppgentab; *ops; ops++)
 302     fprintf(fp, " %s", (*ops)->name);
 303   fputc('\n', fp);
 304 }
 305
 306 int main(int argc, char *argv[])
 307 {
 308   ppgen_ops *ops = ppgentab[0];
 309   unsigned f = 0;
 310   void *ctx;
 311   dstr d = DSTR_INIT;
 312   dstr dd = DSTR_INIT;
 313   unsigned i;
 314
 315 #define f_bogus 1u
 316 #define f_showp 2u
 317
 318   ego(argv[0]);
 319   for (;;) {
 320     static struct option opts[] = {
 321       { "help",         0,              0,      'h' },
 322       { "version",      0,              0,      'v' },
 323       { "usage",        0,              0,      'u' },
 324       { "bits",         OPTF_ARGREQ,    0,      'b' },
 325       { "generator",    OPTF_ARGREQ,    0,      'g' },
 326       { "count",        OPTF_ARGREQ,    0,      'n' },
 327       { "probability",  0,              0,      'p' },
 328       { "range",        OPTF_ARGREQ,    0,      'r' },
 329       { 0,              0,              0,      0 }
 330     };
 331     int i = mdwopt(argc, argv, "hvu b:g:n:pr:", opts, 0, 0, 0);
 332
 333     if (i < 0)
 334       break;
 335     switch (i) {
 336       case 'h':
 337         help(stdout);
 338         exit(0);
 339       case 'v':
 340         version(stdout);
 341         exit(0);
 342       case 'u':
 343         usage(stdout);
 344         exit(0);
 345       case 'b': {
 346         char *p;
 347         unsigned long n = strtoul(optarg, &p, 0);
 348         if (*p)
 349           die(EXIT_FAILURE, "bad integer `%s'", optarg);
 350         bits = n;
 351       } break;
 352       case 'g': {
 353         ppgen_ops **p;
 354         size_t n = strlen(optarg);
 355         ops = 0;
 356         for (p = ppgentab; *p; p++) {
 357           if (strncmp(optarg, (*p)->name, n) == 0) {
 358             if (!(*p)->name[n]) {
 359               ops = *p;
 360               break;
 361             } else if (ops)
 362               die(EXIT_FAILURE, "ambiguous generator name `%s'", optarg);
 363             ops = *p;
 364           }
 365         }
 366         if (!ops)
 367           die(EXIT_FAILURE, "unknown generator name `%s'", optarg);
 368       } break;
 369       case 'n': {
 370         char *p;
 371         unsigned long n = strtoul(optarg, &p, 0);
 372         if (*p)
 373           die(EXIT_FAILURE, "bad integer `%s'", optarg);
 374         count = n;
 375       } break;
 376       case 'p':
 377         f |= f_showp;
 378         break;
 379       case 'r': {
 380         char *p;
 381         unsigned long n = min, nn = max;
 382         nn = strtoul(optarg, &p, 0);
 383         if (*p == '-') {
 384           n = nn;
 385           nn = strtoul(p + 1, &p, 0);
 386         }
 387         if (*p)
 388           die(EXIT_FAILURE, "bad range string `%s'", optarg);
 389         min = n; max = nn;
 390       } break;
 391       default:
 392         f |= f_bogus;
 393         break;
 394     }
 395   }
 396
 397   argc -= optind;
 398   argv += optind;
 399   if ((f & f_bogus) || !argc) {
 400     usage(stderr);
 401     exit(EXIT_FAILURE);
 402   }
 403
 404   rand_noisesrc(RAND_GLOBAL, &noise_source);
 405   rand_seed(RAND_GLOBAL, 160);
 406
 407   ctx = ops->init();
 408   while (*argv) {
 409     if (strcmp(*argv, "-") == 0)
 410       ops->scan(stdin, ctx);
 411     else {
 412       FILE *fp = fopen(*argv, "r");
 413       if (!fp) {
 414         die(EXIT_FAILURE, "error opening file `%s': %s",
 415             *argv, strerror(errno));
 416       }
 417       ops->scan(fp, ctx);
 418       fclose(fp);
 419     }
 420     argv++;
 421   }
 422   if (ops->endscan)
 423     ops->endscan(ctx);
 424
 425   for (i = 0; !count || i < count; i++) {
 426     double logp = 0;
 427     DRESET(&d);
 428     while (logp < bits) {
 429       double pp;
 430       DRESET(&dd);
 431       pp = ops->gen(&dd, &rand_global, ctx);
 432       if (!pp || dd.len < min || dd.len > max)
 433         continue;
 434       if (logp)
 435         DPUTC(&d, ' ');
 436       DPUTD(&d, &dd);
 437       logp += pp;
 438     }
 439     dstr_write(&d, stdout);
 440     if (f & f_showp)
 441       printf(" [%g]", logp);
 442     fputc('\n', stdout);
 443   }
 444
 445   ops->done(ctx);
 446   dstr_destroy(&d);
 447   dstr_destroy(&dd);
 448   return (0);
 449 }
 450
 451 /*----- That's all, folks -------------------------------------------------*/