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