3 * $Id: mkphrase.c,v 1.3 2003/01/24 20:16:04 mdw Exp $
5 * Generate passphrases from word lists
7 * (c) 2000 Straylight/Edgeware
10 /*----- Licensing notice --------------------------------------------------*
12 * This file is part of Catacomb.
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.
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.
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,
30 /*----- Revision history --------------------------------------------------*
32 * $Log: mkphrase.c,v $
33 * Revision 1.3 2003/01/24 20:16:04 mdw
34 * Fix stupidity in reading wordlists from stdin. (Thanks to James
37 * Revision 1.2 2000/12/06 20:33:27 mdw
38 * Make flags be macros rather than enumerations, to ensure that they're
41 * Revision 1.1 2000/08/06 10:50:55 mdw
42 * (mkphrase): New program for generating random passphrases with measured
47 /*----- Header files ------------------------------------------------------*/
58 #include <mLib/alloc.h>
59 #include <mLib/bits.h>
60 #include <mLib/darray.h>
61 #include <mLib/dstr.h>
62 #include <mLib/mdwopt.h>
63 #include <mLib/quis.h>
64 #include <mLib/report.h>
71 /*----- Global state ------------------------------------------------------*/
73 static unsigned min
= 0, max
= 256; /* Word length bounds */
74 static unsigned bits
= 128; /* Minimum acceptable entropy */
75 static unsigned count
= 1; /* How many passphrases to make */
77 static const char wchars
[] = "abcdefghijklmnopqrstuvwxyz'";
79 typedef struct ppgen_ops
{
80 const char *name
; /* Name of the generator */
81 void *(*init
)(void); /* Initialize generator */
82 void (*scan
)(FILE */
*fp*/
, void */
*p*/
); /* Scan an input word list */
83 void (*endscan
)(void */
*p*/
); /* Scanning phase completed */
84 double (*gen
)(dstr */
*d*/
, grand */
*r*/
, void */
*p*/
);
85 /* Emit word and return entropy */
86 void (*done
)(void */
*p*/
); /* Close down generator */
89 /*----- Word list ---------------------------------------------------------*/
93 DA_DECL(string_v
, char *);
96 typedef struct wlist
{
103 static void *wordlist_init(void)
105 wlist
*w
= xmalloc(sizeof(wlist
));
111 static void wordlist_scan(FILE *fp
, void *p
)
119 if (ch
== EOF
|| isspace(ch
)) {
121 if (f
&& d
.len
>= min
&& d
.len
<= max
)
122 sym_find(&w
->tab
, d
.buf
, d
.len
+ 1, sizeof(sym_base
), 0);
130 if (strchr(wchars
, ch
)) {
139 static void wordlist_endscan(void *p
)
147 for (sym_mkiter(&i
, &w
->tab
); (b
= sym_next(&i
)) != 0; )
149 w
->buf
= xmalloc(buflen
);
152 for (sym_mkiter(&i
, &w
->tab
); (b
= sym_next(&i
)) != 0; ) {
153 memcpy(q
, SYM_NAME(b
), b
->len
);
157 sym_destroy(&w
->tab
);
158 w
->logp
= log(DA_LEN(&w
->sv
))/log(2);
161 static double wordlist_gen(dstr
*d
, grand
*r
, void *p
)
164 uint32 i
= r
->ops
->range(r
, DA_LEN(&w
->sv
));
165 DPUTS(d
, DA(&w
->sv
)[i
]);
169 static void wordlist_done(void *p
)
177 static ppgen_ops wordlist_ops
= {
179 wordlist_init
, wordlist_scan
, wordlist_endscan
, wordlist_gen
, wordlist_done
182 /*----- Markov word model -------------------------------------------------*/
190 typedef struct node
{
195 static void *markov_init(void)
197 node (*model
)[VECSZ
][VECSZ
][VECSZ
] = xmalloc(sizeof(*model
));
200 for (i
= 0; i
< VECSZ
; i
++) {
201 for (j
= 0; j
< VECSZ
; j
++) {
202 for (k
= 0; k
< VECSZ
; k
++) {
203 node
*n
= &(*model
)[i
][j
][k
];
205 for (l
= 0; l
< VECSZ
; l
++)
214 static void markov_scan(FILE *fp
, void *p
)
216 node (*model
)[VECSZ
][VECSZ
][VECSZ
] = p
;
217 unsigned i
= C_START
, j
= C_START
, k
= C_START
, l
= C_END
;
222 node
*n
= &(*model
)[i
][j
][k
];
224 if (ch
== EOF
|| isspace(ch
)) {
236 if ((q
= strchr(wchars
, tolower(ch
))) == 0)
245 static double markov_gen(dstr
*d
, grand
*r
, void *p
)
247 node (*model
)[VECSZ
][VECSZ
][VECSZ
] = p
;
248 unsigned i
= C_START
, j
= C_START
, k
= C_START
, l
;
250 double log2
= log(2);
253 node
*n
= &(*model
)[i
][j
][k
];
254 uint32 z
= r
->ops
->range(r
, n
->count
);
255 for (l
= 0; z
>= n
->p
[l
]; z
-= n
->p
[l
++])
257 logp
-= log((double)n
->p
[l
]/(double)n
->count
)/log2
;
267 static void markov_done(void *p
)
269 node (*model
)[VECSZ
][VECSZ
][VECSZ
] = p
;
273 static ppgen_ops markov_ops
= {
275 markov_init
, markov_scan
, 0, markov_gen
, markov_done
278 /*----- Main code ---------------------------------------------------------*/
280 static ppgen_ops
*ppgentab
[] = {
286 static void version(FILE *fp
)
288 pquis(fp
, "$, Catacomb version " VERSION
"\n");
291 static void usage(FILE *fp
)
294 Usage: $ [-p] [-b bits] [-g gen] [-n count] [-r [min-]max] wordlist...\n\
298 static void help(FILE *fp
)
305 Generates random passphrases with the requested level of entropy. Options\n\
308 -h, --help Show this help text.\n\
309 -v, --version Show the program's version number.\n\
310 -u, --usage Show a terse usage summary.\n\
311 -b, --bits=BITS Produce at least BITS bits of entropy.\n\
312 -g, --generator=GEN Use passphrase generator GEN.\n\
313 -n, --count=COUNT Generate COUNT passphrases.\n\
314 -p, --probability Show -log_2 of probability for each phrase.\n\
315 -r, --range=[MIN-]MAX Supply minimum and maximum word lengths.\n\
317 Generators currently available:");
318 for (ops
= ppgentab
; *ops
; ops
++)
319 fprintf(fp
, " %s", (*ops
)->name
);
323 int main(int argc
, char *argv
[])
325 ppgen_ops
*ops
= ppgentab
[0];
337 static struct option opts
[] = {
338 { "help", 0, 0, 'h' },
339 { "version", 0, 0, 'v' },
340 { "usage", 0, 0, 'u' },
341 { "bits", OPTF_ARGREQ
, 0, 'b' },
342 { "generator", OPTF_ARGREQ
, 0, 'g' },
343 { "count", OPTF_ARGREQ
, 0, 'n' },
344 { "probability", 0, 0, 'p' },
345 { "range", OPTF_ARGREQ
, 0, 'r' },
348 int i
= mdwopt(argc
, argv
, "hvu b:g:n:pr:", opts
, 0, 0, 0);
364 unsigned long n
= strtoul(optarg
, &p
, 0);
366 die(EXIT_FAILURE
, "bad integer `%s'", optarg
);
371 size_t n
= strlen(optarg
);
373 for (p
= ppgentab
; *p
; p
++) {
374 if (strncmp(optarg
, (*p
)->name
, n
) == 0) {
375 if (!(*p
)->name
[n
]) {
379 die(EXIT_FAILURE
, "ambiguous generator name `%s'", optarg
);
384 die(EXIT_FAILURE
, "unknown generator name `%s'", optarg
);
388 unsigned long n
= strtoul(optarg
, &p
, 0);
390 die(EXIT_FAILURE
, "bad integer `%s'", optarg
);
398 unsigned long n
= min
, nn
= max
;
399 nn
= strtoul(optarg
, &p
, 0);
402 nn
= strtoul(p
+ 1, &p
, 0);
405 die(EXIT_FAILURE
, "bad range string `%s'", optarg
);
416 if ((f
& f_bogus
) || !argc
) {
421 rand_noisesrc(RAND_GLOBAL
, &noise_source
);
422 rand_seed(RAND_GLOBAL
, 160);
426 if (strcmp(*argv
, "-") == 0)
427 ops
->scan(stdin
, ctx
);
429 FILE *fp
= fopen(*argv
, "r");
431 die(EXIT_FAILURE
, "error opening file `%s': %s",
432 *argv
, strerror(errno
));
442 for (i
= 0; !count
|| i
< count
; i
++) {
445 while (logp
< bits
) {
448 pp
= ops
->gen(&dd
, &rand_global
, ctx
);
449 if (!pp
|| dd
.len
< min
|| dd
.len
> max
)
456 dstr_write(&d
, stdout
);
458 printf(" [%g]", logp
);
468 /*----- That's all, folks -------------------------------------------------*/