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