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 minbits = 128, maxbits = UINT_MAX; /* 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 MIN[-MAX]] [-g GEN] [-n COUNT]\n\
 278 \t[-r [MIN-]MAX] WORDLIST...\n                    \
 279 ");
 280 }
 281
 282 static void help(FILE *fp)
 283 {
 284   ppgen_ops **ops;
 285   version(fp);
 286   fputc('\n', fp);
 287   usage(fp);
 288   pquis(fp, "\n\
 289 Generates random passphrases with the requested level of entropy.  Options\n\
 290 supported are:\n\
 291 \n\
 292 -h, --help              Show this help text.\n\
 293 -v, --version           Show the program's version number.\n\
 294 -u, --usage             Show a terse usage summary.\n\
 295 -b, --bits=MIN[-MAX]    Minimum and maximum bits of entropy.\n\
 296 -g, --generator=GEN     Use passphrase generator GEN.\n\
 297 -n, --count=COUNT       Generate COUNT passphrases.\n\
 298 -p, --probability       Show -log_2 of probability for each phrase.\n\
 299 -r, --range=[MIN-]MAX   Supply minimum and maximum word lengths.\n\
 300 \n\
 301 Generators currently available:");
 302   for (ops = ppgentab; *ops; ops++)
 303     fprintf(fp, " %s", (*ops)->name);
 304   fputc('\n', fp);
 305 }
 306
 307 int main(int argc, char *argv[])
 308 {
 309   ppgen_ops *ops = ppgentab[0];
 310   unsigned f = 0;
 311   void *ctx;
 312   dstr d = DSTR_INIT;
 313   dstr dd = DSTR_INIT;
 314   unsigned i;
 315
 316 #define f_bogus 1u
 317 #define f_showp 2u
 318
 319   ego(argv[0]);
 320   for (;;) {
 321     static struct option opts[] = {
 322       { "help",         0,              0,      'h' },
 323       { "version",      0,              0,      'v' },
 324       { "usage",        0,              0,      'u' },
 325       { "bits",         OPTF_ARGREQ,    0,      'b' },
 326       { "generator",    OPTF_ARGREQ,    0,      'g' },
 327       { "count",        OPTF_ARGREQ,    0,      'n' },
 328       { "probability",  0,              0,      'p' },
 329       { "range",        OPTF_ARGREQ,    0,      'r' },
 330       { 0,              0,              0,      0 }
 331     };
 332     int i = mdwopt(argc, argv, "hvu b:g:n:pr:", opts, 0, 0, 0);
 333
 334     if (i < 0)
 335       break;
 336     switch (i) {
 337       case 'h':
 338         help(stdout);
 339         exit(0);
 340       case 'v':
 341         version(stdout);
 342         exit(0);
 343       case 'u':
 344         usage(stdout);
 345         exit(0);
 346       case 'b': {
 347         char *p;
 348         minbits = strtoul(optarg, &p, 0);
 349         if (*p == '-')
 350           maxbits = strtoul(p + 1, &p, 0);
 351         else
 352           maxbits = UINT_MAX;
 353         if (*p || minbits > maxbits)
 354           die(EXIT_FAILURE, "bad entropy range `%s'", optarg);
 355       } break;
 356       case 'g': {
 357         ppgen_ops **p;
 358         size_t n = strlen(optarg);
 359         ops = 0;
 360         for (p = ppgentab; *p; p++) {
 361           if (strncmp(optarg, (*p)->name, n) == 0) {
 362             if (!(*p)->name[n]) {
 363               ops = *p;
 364               break;
 365             } else if (ops)
 366               die(EXIT_FAILURE, "ambiguous generator name `%s'", optarg);
 367             ops = *p;
 368           }
 369         }
 370         if (!ops)
 371           die(EXIT_FAILURE, "unknown generator name `%s'", optarg);
 372       } break;
 373       case 'n': {
 374         char *p;
 375         unsigned long n = strtoul(optarg, &p, 0);
 376         if (*p)
 377           die(EXIT_FAILURE, "bad integer `%s'", optarg);
 378         count = n;
 379       } break;
 380       case 'p':
 381         f |= f_showp;
 382         break;
 383       case 'r': {
 384         char *p;
 385         unsigned long n = min, nn = max;
 386         nn = strtoul(optarg, &p, 0);
 387         if (*p == '-') {
 388           n = nn;
 389           nn = strtoul(p + 1, &p, 0);
 390         }
 391         if (*p || min > max)
 392           die(EXIT_FAILURE, "bad range string `%s'", optarg);
 393         min = n; max = nn;
 394       } break;
 395       default:
 396         f |= f_bogus;
 397         break;
 398     }
 399   }
 400
 401   argc -= optind;
 402   argv += optind;
 403   if ((f & f_bogus) || !argc) {
 404     usage(stderr);
 405     exit(EXIT_FAILURE);
 406   }
 407
 408   rand_noisesrc(RAND_GLOBAL, &noise_source);
 409   rand_seed(RAND_GLOBAL, 160);
 410
 411   ctx = ops->init();
 412   while (*argv) {
 413     if (strcmp(*argv, "-") == 0)
 414       ops->scan(stdin, ctx);
 415     else {
 416       FILE *fp = fopen(*argv, "r");
 417       if (!fp) {
 418         die(EXIT_FAILURE, "error opening file `%s': %s",
 419             *argv, strerror(errno));
 420       }
 421       ops->scan(fp, ctx);
 422       fclose(fp);
 423     }
 424     argv++;
 425   }
 426   if (ops->endscan)
 427     ops->endscan(ctx);
 428
 429   for (i = 0; !count || i < count; ) {
 430     double logp = 0;
 431     DRESET(&d);
 432     while (logp < minbits) {
 433       double pp;
 434       DRESET(&dd);
 435       pp = ops->gen(&dd, &rand_global, ctx);
 436       if (!pp || dd.len < min || dd.len > max)
 437         continue;
 438       if (logp)
 439         DPUTC(&d, ' ');
 440       DPUTD(&d, &dd);
 441       logp += pp;
 442     }
 443     if (logp >= (double)maxbits + 1)
 444       continue;
 445     dstr_write(&d, stdout);
 446     if (f & f_showp)
 447       printf(" [%g]", logp);
 448     fputc('\n', stdout);
 449     i++;
 450   }
 451
 452   ops->done(ctx);
 453   dstr_destroy(&d);
 454   dstr_destroy(&dd);
 455   return (0);
 456 }
 457
 458 /*----- That's all, folks -------------------------------------------------*/