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

   1 /* -*-c-*-
   2  *
   3  * Generate passphrases from word lists
   4  *
   5  * (c) 2000 Straylight/Edgeware
   6  */
   7
   8 /*----- Licensing notice --------------------------------------------------*
   9  *
  10  * This file is part of Catacomb.
  11  *
  12  * Catacomb is free software; you can redistribute it and/or modify
  13  * it under the terms of the GNU Library General Public License as
  14  * published by the Free Software Foundation; either version 2 of the
  15  * License, or (at your option) any later version.
  16  *
  17  * Catacomb is distributed in the hope that it will be useful,
  18  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  19  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  20  * GNU Library General Public License for more details.
  21  *
  22  * You should have received a copy of the GNU Library General Public
  23  * License along with Catacomb; if not, write to the Free
  24  * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  25  * MA 02111-1307, USA.
  26  */
  27
  28 /*----- Header files ------------------------------------------------------*/
  29
  30 #include "config.h"
  31
  32 #include <ctype.h>
  33 #include <errno.h>
  34 #include <math.h>
  35 #include <stdio.h>
  36 #include <stdlib.h>
  37 #include <string.h>
  38
  39 #include <mLib/alloc.h>
  40 #include <mLib/bits.h>
  41 #include <mLib/darray.h>
  42 #include <mLib/dstr.h>
  43 #include <mLib/mdwopt.h>
  44 #include <mLib/quis.h>
  45 #include <mLib/report.h>
  46 #include <mLib/sym.h>
  47
  48 #include "grand.h"
  49 #include "noise.h"
  50 #include "rand.h"
  51
  52 /*----- Global state ------------------------------------------------------*/
  53
  54 static unsigned min = 0, max = 256;     /* Word length bounds */
  55 static unsigned minbits = 128, maxbits = UINT_MAX; /* Acceptable entropy */
  56 static unsigned count = 1;              /* How many passphrases to make */
  57
  58 static const char
  59   all_wchars[] = "'abcdefghijklmnopqrstuvwxyz",
  60   *wchars = all_wchars;
  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       { "no-apostrophe", 0,             0,      'A' },
 326       { "bits",         OPTF_ARGREQ,    0,      'b' },
 327       { "generator",    OPTF_ARGREQ,    0,      'g' },
 328       { "count",        OPTF_ARGREQ,    0,      'n' },
 329       { "probability",  0,              0,      'p' },
 330       { "range",        OPTF_ARGREQ,    0,      'r' },
 331       { 0,              0,              0,      0 }
 332     };
 333     int i = mdwopt(argc, argv, "hvu Ab:g:n:pr:", opts, 0, 0, 0);
 334
 335     if (i < 0)
 336       break;
 337     switch (i) {
 338       case 'h':
 339         help(stdout);
 340         exit(0);
 341       case 'v':
 342         version(stdout);
 343         exit(0);
 344       case 'u':
 345         usage(stdout);
 346         exit(0);
 347       case 'A':
 348         wchars = all_wchars + 1;
 349         break;
 350       case 'b': {
 351         char *p;
 352         minbits = strtoul(optarg, &p, 0);
 353         if (*p == '-')
 354           maxbits = strtoul(p + 1, &p, 0);
 355         else
 356           maxbits = UINT_MAX;
 357         if (*p || minbits > maxbits)
 358           die(EXIT_FAILURE, "bad entropy range `%s'", optarg);
 359       } break;
 360       case 'g': {
 361         ppgen_ops **p;
 362         size_t n = strlen(optarg);
 363         ops = 0;
 364         for (p = ppgentab; *p; p++) {
 365           if (strncmp(optarg, (*p)->name, n) == 0) {
 366             if (!(*p)->name[n]) {
 367               ops = *p;
 368               break;
 369             } else if (ops)
 370               die(EXIT_FAILURE, "ambiguous generator name `%s'", optarg);
 371             ops = *p;
 372           }
 373         }
 374         if (!ops)
 375           die(EXIT_FAILURE, "unknown generator name `%s'", optarg);
 376       } break;
 377       case 'n': {
 378         char *p;
 379         unsigned long n = strtoul(optarg, &p, 0);
 380         if (*p)
 381           die(EXIT_FAILURE, "bad integer `%s'", optarg);
 382         count = n;
 383       } break;
 384       case 'p':
 385         f |= f_showp;
 386         break;
 387       case 'r': {
 388         char *p;
 389         unsigned long n = min, nn = max;
 390         nn = strtoul(optarg, &p, 0);
 391         if (*p == '-') {
 392           n = nn;
 393           nn = strtoul(p + 1, &p, 0);
 394         }
 395         if (*p || min > max)
 396           die(EXIT_FAILURE, "bad range string `%s'", optarg);
 397         min = n; max = nn;
 398       } break;
 399       default:
 400         f |= f_bogus;
 401         break;
 402     }
 403   }
 404
 405   argc -= optind;
 406   argv += optind;
 407   if ((f & f_bogus) || !argc) {
 408     usage(stderr);
 409     exit(EXIT_FAILURE);
 410   }
 411
 412   rand_noisesrc(RAND_GLOBAL, &noise_source);
 413   rand_seed(RAND_GLOBAL, 160);
 414
 415   ctx = ops->init();
 416   while (*argv) {
 417     if (strcmp(*argv, "-") == 0)
 418       ops->scan(stdin, ctx);
 419     else {
 420       FILE *fp = fopen(*argv, "r");
 421       if (!fp) {
 422         die(EXIT_FAILURE, "error opening file `%s': %s",
 423             *argv, strerror(errno));
 424       }
 425       ops->scan(fp, ctx);
 426       fclose(fp);
 427     }
 428     argv++;
 429   }
 430   if (ops->endscan)
 431     ops->endscan(ctx);
 432
 433   for (i = 0; !count || i < count; ) {
 434     double logp = 0;
 435     DRESET(&d);
 436     while (logp < minbits) {
 437       double pp;
 438       DRESET(&dd);
 439       pp = ops->gen(&dd, &rand_global, ctx);
 440       if (!pp || dd.len < min || dd.len > max)
 441         continue;
 442       if (logp)
 443         DPUTC(&d, ' ');
 444       DPUTD(&d, &dd);
 445       logp += pp;
 446     }
 447     if (logp >= (double)maxbits + 1)
 448       continue;
 449     dstr_write(&d, stdout);
 450     if (f & f_showp)
 451       printf(" [%g]", logp);
 452     fputc('\n', stdout);
 453     i++;
 454   }
 455
 456   ops->done(ctx);
 457   dstr_destroy(&d);
 458   dstr_destroy(&dd);
 459   return (0);
 460 }
 461
 462 /*----- That's all, folks -------------------------------------------------*/