1 /*
2  * This software is Copyright (c) 2018 magnum
3  * and is hereby released to the general public under the following terms:
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted.
6  */
7 
8 /*
9  * TODO:
10  * - Profile with Callgrind
11  * - Assure hybrid support (mask or external)
12  * - Reject other hybrid modes?
13  * - Try inlining utf32_to_enc
14  * - Are we still using an unnecessary step of indexing?
15  *
16  * IDEAS:
17  * - Store charset in target encoding for quicker conversion, even for
18  *   UTF-8 (we can store it in uint32_t)! Beware of endianness.
19  *
20  * RELATED:
21  * - Unicode ranges charsets. Generator? Standalone? --subsets-file=FILE?
22  * - Add global options --skip-odd-lengths and --skip-even-lengths (also
23  *   affecting mask mode and inc, possibly some external modes)
24  */
25 #include "os.h"
26 
27 #include <stdio.h>
28 #include <string.h>
29 #include <stdlib.h>
30 #include <stdint.h>
31 #include <ctype.h>
32 
33 #include "arch.h"
34 #include "int128.h"
35 #include "john.h"
36 #include "loader.h"
37 #include "cracker.h"
38 #include "options.h"
39 #include "config.h"
40 #include "logger.h"
41 #include "status.h"
42 #include "signals.h"
43 #include "recovery.h"
44 #include "mask.h"
45 #include "unicode.h"
46 #include "unicode_range.h"
47 
48 #define SUBSET_DEBUG 1
49 
50 #define MAX_SUBSET_SIZE 16
51 #define MAX_CAND_LENGTH PLAINTEXT_BUFFER_SIZE
52 #define DEFAULT_MAX_LEN 16
53 
54 #if JTR_HAVE_INT128
55 typedef uint128_t uint_big;
56 #define UINT_BIG_MAX UINT128_MAX
57 #else
58 typedef uint64_t uint_big;
59 #define UINT_BIG_MAX UINT64_MAX
60 #endif
61 
62 int subsets_cur_len;
63 
64 static char *charset;
65 static UTF32 subset[MAX_CAND_LENGTH + 1];
66 static int done_len[MAX_SUBSET_SIZE + 1];
67 static int rec_done_len[MAX_SUBSET_SIZE + 1];
68 static int charset_idx[MAX_CAND_LENGTH];
69 static int rec_charset_idx[MAX_CAND_LENGTH];
70 static int maxdiff;
71 static int maxlength;
72 static int rec_num_comb, num_comb;
73 static int rec_word_len, word_len;
74 static int rec_set, set;
75 static int state_restored;
76 static int rec_cur_len;
77 static int quick_conversion;
78 static uint64_t rec_num_done[MAX_CAND_LENGTH + 1];
79 static uint64_t num_done[MAX_CAND_LENGTH + 1];
80 static uint64_t keyspace;
81 
get_progress(void)82 static double get_progress(void)
83 {
84 	emms();
85 
86 	if (!keyspace)
87 		return -1;
88 
89 	if (subsets_cur_len > maxlength)
90 		return 100;
91 
92 	return 100.0 * num_done[subsets_cur_len] / keyspace;
93 }
94 
fix_state(void)95 static void fix_state(void)
96 {
97 	int i;
98 
99 	rec_set = set;
100 	rec_num_comb = num_comb;
101 	rec_word_len = word_len;
102 	for (i = 0; i <= maxdiff; i++)
103 		rec_done_len[i] = done_len[i];
104 	for (i = 0; i < rec_num_comb; i++)
105 		rec_charset_idx[i] = charset_idx[i];
106 	rec_cur_len = subsets_cur_len;
107 	for (i = 0; i <= maxlength; i++)
108 		rec_num_done[i] = num_done[i];
109 }
110 
save_state(FILE * file)111 static void save_state(FILE *file)
112 {
113 	int i;
114 
115 	fprintf(file, "%d\n", rec_set);
116 	fprintf(file, "%d\n", rec_num_comb);
117 	fprintf(file, "%d\n", rec_word_len);
118 	for (i = 0; i <= maxdiff; i++)
119 		fprintf(file, "%d\n", rec_done_len[i]);
120 	for (i = 0; i < rec_num_comb; i++)
121 		fprintf(file, "%d\n", rec_charset_idx[i]);
122 	fprintf(file, "%d\n", rec_cur_len);
123 	for (i = 0; i <= maxlength; i++)
124 		fprintf(file, "%"PRIu64"\n", rec_num_done[i]);
125 	//fprintf(file, "%s\n", charset); /* In case we can get it from conf */
126 }
127 
restore_state(FILE * file)128 static int restore_state(FILE *file)
129 {
130 	int i, d;
131 	uint64_t q;
132 
133 	if (fscanf(file, "%d\n", &d) == 1)
134 		set = d;
135 	else
136 		return 1;
137 
138 	if (fscanf(file, "%d\n", &d) == 1)
139 		num_comb = d;
140 	else
141 		return 1;
142 
143 	if (fscanf(file, "%d\n", &d) == 1)
144 		word_len = d;
145 	else
146 		return 1;
147 
148 	for (i = 0; i <= maxdiff; i++)
149 		if (fscanf(file, "%d\n", &d) == 1)
150 			done_len[i] = d;
151 		else
152 			return 1;
153 
154 	for (i = 0; i < num_comb; i++)
155 		if (fscanf(file, "%d\n", &d) == 1)
156 			charset_idx[i] = d;
157 		else
158 			return 1;
159 
160 	if (fscanf(file, "%d\n", &d) == 1)
161 		subsets_cur_len = d;
162 	else
163 		return 1;
164 
165 	for (i = 0; i <= maxlength; i++)
166 		if (fscanf(file, "%"PRIu64"\n", &q) == 1)
167 			num_done[i] = q;
168 		else
169 			return 1;
170 
171 	/* In case we can get it from conf */
172 	//if (fscanf(file, "%s\n", &charset) != 1)
173 	//	return 1;
174 
175 	state_restored = 1;
176 
177 	return 0;
178 }
179 
180 /* uint128_t max. eg. 2^127, 3^80, 4^63, 5^55, 6^49, 7^45 */
181 /* uint64_t            2^63, 3^40, 4^31, 5^27, 6^24, 7^22 */
powi(uint32_t b,uint32_t p)182 static uint_big powi(uint32_t b, uint32_t p)
183 {
184 	uint_big res = 1;
185 	uint32_t orig = p;
186 
187 	if (b == 0)
188 		return 0;
189 
190 	while (p--) {
191 		uint_big temp = res * b;
192 
193 		if (temp < res)
194 #if SUBSET_DEBUG
195 			error_msg("%s(%u, %u) overflow\n", __FUNCTION__, b, orig);
196 #else
197 			return UINT_BIG_MAX
198 #endif
199 		res = temp;
200 	}
201 
202 	return res;
203 }
204 
205 /* Max 34! for uint128_t or 20! for uint64_t*/
fac(uint32_t n)206 static uint_big fac(uint32_t n)
207 {
208 	uint_big res = n;
209 	uint32_t orig = n;
210 
211 	if (n == 0)
212 		return 1;
213 
214 	while (--n) {
215 		uint_big temp = res * n;
216 
217 		if (temp < res)
218 #if SUBSET_DEBUG
219 			error_msg("%s(%u) overflow\n", __FUNCTION__, orig);
220 #else
221 			return UINT_BIG_MAX
222 #endif
223 		res = temp;
224 	}
225 
226 	return res;
227 }
228 
229 /* Drop dupes in string, in place. */
remove_dupes(UTF32 * string)230 static void remove_dupes(UTF32 *string)
231 {
232 	UTF32 *s = string, *d = string;
233 
234 	while (*s) {
235 		UTF32 c = *s, *p = s;
236 
237 		while (p > string) {
238 			if (*--p == c) {
239 				c = 0;
240 				break;
241 			}
242 		}
243 		if (c)
244 			*d++ = *s++;
245 		else
246 			s++;
247 	}
248 	*d = 0;
249 }
250 
251 /* Parse \U+HHHH and \U+HHHHH notation to characters, in place. */
parse_unicode(char * string)252 static void parse_unicode(char *string)
253 {
254 	static int warned;
255 	unsigned char *s = (unsigned char*)string;
256 	unsigned char *d = s;
257 
258 	if (!string || !*string)
259 		return;
260 
261 	while (*s)
262 		if (*s == '\\' && s[1] != 'U') {
263 			*d++ = *s++;
264 			*d++ = *s++;
265 		} else if (*s == '\\' && s[1] == 'U' && s[2] == '+' &&
266 		           atoi16[s[3]] != 0x7f && atoi16[s[4]] != 0x7f &&
267 		           atoi16[s[5]] != 0x7f && atoi16[s[6]] != 0x7f &&
268 		           atoi16[s[7]] != 0x7f) {
269 			UTF32 wc[2];
270 			UTF8 conv[8];
271 			char *c = (char*)conv;
272 
273 			wc[0] = (atoi16[s[3]] << 16) + (atoi16[s[4]] << 12) +
274 				(atoi16[s[5]] << 8) + (atoi16[s[6]] << 4) + atoi16[s[7]];
275 			wc[1] = 0;
276 			if (!wc[0] && !warned++ && john_main_process)
277 				fprintf(stderr,
278 				        "Warning: \\U+00000 in mask terminates the string\n");
279 			if (wc[0] == '\\')
280 				*d++ = '\\';
281 
282 			utf32_to_enc(conv, sizeof(conv), wc);
283 
284 			while (*c)
285 				*d++ = *c++;
286 			s += 8;
287 		} else if (*s == '\\' && s[1] == 'U' && s[2] == '+' &&
288 		           atoi16[s[3]] != 0x7f && atoi16[s[4]] != 0x7f &&
289 		           atoi16[s[5]] != 0x7f && atoi16[s[6]] != 0x7f) {
290 			UTF32 wc[2];
291 			UTF8 conv[8];
292 			char *c = (char*)conv;
293 
294 			wc[0] = (atoi16[s[3]] << 12) + (atoi16[s[4]] << 8) +
295 				(atoi16[s[5]] << 4) + atoi16[s[6]];
296 			wc[1] = 0;
297 			if (!wc[0] && !warned++ && john_main_process)
298 				fprintf(stderr,
299 				        "Warning: \\U+0000 in mask terminates the string\n");
300 			if (wc[0] == '\\')
301 				*d++ = '\\';
302 
303 			utf32_to_enc(conv, sizeof(conv), wc);
304 
305 			while (*c)
306 				*d++ = *c++;
307 			s += 7;
308 		} else
309 			*d++ = *s++;
310 
311 	*d = 0;
312 }
313 
314 /*
315  * How many unique sets of size k can you make from full set of size n?
316  * No repeats, order does not matter.
317  * numsets(3, 2) == 3, eg. abc --> ab ac cb (not aa or ba etc.)
318  *
319  * This is known as "n choose k":   n! / (k!(n - k)!)
320  *
321  * fac() would overflow so here's a recursing function that does the
322  * job nicely at O(k).
323  *
324  * if r > 0, this is size of required part of set
325  */
numsets(uint64_t n,uint64_t k,uint32_t r)326 static uint64_t numsets(uint64_t n, uint64_t k, uint32_t r)
327 {
328 	if (r)
329 		return numsets(n, k, 0) - numsets(n - r, k, 0);
330 	if (k == 0)
331 		return 1;
332 	else if (k == 1)
333 		return n;
334 	else
335 		return (n * numsets(n - 1, k - 1, 0)) / k;
336 }
337 
338 /*
339  * How many unique words of length len can you make from all subsets of
340  * size k from a full set with size n? k is <= len.
341  * Repeats are allowed, order does matter, all of the subset must be
342  * represented.
343  *
344  * numwords(2, 3, 2) = 6  "abc" --> ab ac ba bc ca cb (not aa, bb or cc)
345  *
346  * if r > 0, this is size of required part of set
347  */
numwords(uint32_t k,uint32_t n,uint32_t len,uint32_t r)348 static uint64_t numwords(uint32_t k, uint32_t n, uint32_t len, uint32_t r)
349 {
350 	if (r)
351 		return numwords(k, n, len, 0) - numwords(k, n - r, len, 0);
352 	if (k == 1)
353 		return n;
354 	else if (n == len && k == n)
355 		return fac(n);
356 	else if (k == len)
357 		return fac(k) * numsets(n, k, 0);
358 	else {
359 		uint64_t res, i;
360 
361 		res = powi(k, len);
362 		i = 0;
363 		do {
364 			i++;
365 			res -= numsets(k, i, 0) * powi(k - i, len);
366 			if (i == k)
367 				break;
368 			i++;
369 			res += numsets(k, i, 0) * powi(k - i, len);
370 		} while (i < k);
371 
372 		return res * numsets(n, k, 0);
373 	}
374 }
375 
submit(UTF32 * subset)376 static int submit(UTF32 *subset)
377 {
378 	UTF8 out[4 * MAX_CAND_LENGTH];
379 	int i;
380 
381 	/* Set current word */
382 	if (quick_conversion) {
383 		/* Quick conversion (only ASCII or ISO-8859-1) */
384 		for (i = 0; i < word_len; i++)
385 			out[i] = subset[i];
386 		out[i] = 0;
387 	} else if (options.target_enc == UTF_8) {
388 		/* Nearly as quick conversion, from UTF-8-32[tm] to UTF-8 */
389 		subset[word_len] = 0;
390 		utf8_32_to_utf8(out, subset);
391 	} else {
392 		/* Slowest conversion, from real UTF-32 to sone legacy codepage */
393 		subset[word_len] = 0;
394 		utf32_to_enc(out, sizeof(out), subset);
395 	}
396 
397 	if (options.flags & FLG_MASK_CHK)
398 		return do_mask_crack((char*)out);
399 	else
400 		return crk_process_key((char*)out);
401 }
402 
swap(UTF32 * x,UTF32 * y)403 static void swap(UTF32 *x, UTF32 *y)
404 {
405 	int temp;
406 
407 	temp = *x;
408 	*x = *y;
409 	*y = temp;
410 }
411 
412 
permute(UTF32 * a,int i,int n)413 static int permute(UTF32 *a, int i, int n)
414 {
415 	int j;
416 
417 	if (i >= n - 1)
418 		return submit(a);
419 
420 	for (j = i; j < n; j++) {
421 		swap(&a[i], &a[j]);
422 		if (permute(a, i + 1, n))
423 			return 1;
424 		swap(&a[i], &a[j]);
425 	}
426 
427 	return 0;
428 }
429 
unique(UTF32 * a,int start,int index)430 static int unique(UTF32 *a, int start, int index)
431 {
432 	int i;
433 
434 	for (i = start; i < index; i++)
435 		if (a[i] == a[index])
436 			return 0;
437 	return 1;
438 }
439 
permute_dupe(UTF32 * a,int i,int n)440 static int permute_dupe(UTF32 *a, int i, int n)
441 {
442 	int j;
443 
444 	if (i >= n - 1)
445 		return submit(a);
446 
447 	for (j = i; j < n; j++) {
448 		if (unique(a, i, j)) {
449 			swap(&a[i], &a[j]);
450 			if (permute_dupe(a, i + 1, n))
451 				return 1;
452 			swap(&a[i], &a[j]);
453 		}
454 	}
455 
456 	return 0;
457 }
458 
expand(UTF32 * a,int setlen,int outlen,int base)459 static int expand(UTF32 *a, int setlen, int outlen, int base)
460 {
461 	int j;
462 
463 	if (setlen == outlen)
464 		return permute_dupe(a, 0, outlen);
465 
466 	for (j = base; j < num_comb; j++) {
467 		a[setlen] = a[j];
468 		if (expand(a, setlen + 1, outlen, j))
469 			return 1;
470 	}
471 
472 	return 0;
473 }
474 
do_subsets_crack(struct db_main * db,char * req_charset)475 int do_subsets_crack(struct db_main *db, char *req_charset)
476 {
477 	int i, cp_max = 127;
478 	int charcount;
479 	int fmt_case = (db->format->params.flags & FMT_CASE);
480 	char *default_set;
481 	UTF32 *charset_utf32;
482 	int required = options.subset_must;
483 	int min_comb = options.subset_min_diff;
484 
485 	maxlength = MIN(MAX_CAND_LENGTH, options.eff_maxlength);
486 
487 	if (!options.req_maxlength)
488 		maxlength = MIN(maxlength, DEFAULT_MAX_LEN);
489 
490 	if ((maxdiff = options.subset_max_diff) < 0)
491 		maxdiff += maxlength;
492 
493 	if (!min_comb && ((min_comb = cfg_get_int("Subsets", NULL, "MinDiff")) < 1))
494 		min_comb = 1;
495 
496 	if (!maxdiff && ((maxdiff = cfg_get_int("Subsets", NULL, "MaxDiff")) < 0))
497 		maxdiff = MAX_SUBSET_SIZE;
498 
499 	if (maxdiff < min_comb)
500 		maxdiff = min_comb;
501 
502 	num_comb = min_comb;
503 
504 	if (maxdiff > MAX_SUBSET_SIZE)
505 		maxdiff = MAX_SUBSET_SIZE;
506 
507 	done_len[0] = maxlength;
508 	for (i = 1; i <= maxdiff; i++)
509 		done_len[i] = MAX(MAX(i, options.eff_minlength), 1) - 1;
510 
511 	default_set = (char*)cfg_get_param("Subsets", NULL, "DefaultCharset");
512 	if (!req_charset)
513 		req_charset = default_set;
514 
515 	if (req_charset && *req_charset) {
516 		if (strlen(req_charset) == 1 && isdigit(req_charset[0])) {
517 			int cnum = atoi(req_charset);
518 			char pl[2] = { '0' + cnum, 0 };
519 			char *c = (char*)cfg_get_param("Subsets", NULL, pl);
520 
521 			if (c)
522 				req_charset = c;
523 		}
524 
525 		/* Parse \U+HHHH notation */
526 		parse_unicode(req_charset);
527 		charset = req_charset;
528 	} else if (fmt_case)
529 		charset = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ !\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~";
530 	else
531 		charset = "0123456789abcdefghijklmnopqrstuvwxyz !\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~";
532 
533 	charcount = strlen(charset);
534 
535 	/* Convert charset to UTF-32 */
536 	if (!strcasecmp(charset, "full-unicode")) {
537 		charset_utf32 = mem_alloc(0x22000 * sizeof(UTF32));
538 		charcount = full_unicode_charset(charset_utf32);
539 	}
540 	else if (options.input_enc == UTF_8) {
541 		if (!valid_utf8((UTF8*)charset)) {
542 			if (john_main_process)
543 				fprintf(stderr, "Error in Unicode conversion. "
544 				        "Ensure --input-encoding is correct\n");
545 			error();
546 		} else {
547 			int charsize = strlen8((UTF8*)charset) + 1;
548 
549 			charset_utf32 = mem_alloc(charsize * sizeof(UTF32));
550 			utf8_to_utf32(charset_utf32, charsize * sizeof(UTF32),
551 			              (UTF8*)charset, charcount);
552 		}
553 	}
554 	else {
555 		charset_utf32 = mem_alloc((charcount + 1) * sizeof(UTF32));
556 		enc_to_utf32(charset_utf32, (charcount + 1) * sizeof(UTF32),
557 		             (UTF8*)charset, charcount);
558 	}
559 
560 	/* Performance step: Use UTF-32-8 when applicable */
561 	if (options.target_enc == UTF_8)
562 		utf32_to_utf8_32(charset_utf32);
563 
564 	/* Silently drop dupes */
565 	remove_dupes(charset_utf32);
566 
567 	charcount = strlen32(charset_utf32);
568 
569 	if (required >= charcount) {
570 		if (john_main_process)
571 			fprintf(stderr, "Error, required part of charset must be smaller "
572 			        "than charset (1..%d out of %d)\n",
573 			        charcount - 1, charcount);
574 		error();
575 	}
576 
577 	if (options.target_enc == ASCII || options.target_enc == ISO_8859_1)
578 		cp_max = 255;
579 
580 	if (maxdiff > charcount)
581 		maxdiff = charcount;
582 
583 	if (maxdiff > maxlength)
584 		maxdiff = maxlength;
585 
586 	subsets_cur_len = word_len = MAX(num_comb, options.eff_minlength);
587 
588 	status_init(get_progress, 0);
589 	rec_restore_mode(restore_state);
590 	rec_init(db, save_state);
591 
592 	for (i = min_comb; i <= MIN(subsets_cur_len, maxdiff); i++)
593 		keyspace += numwords(i, charcount, subsets_cur_len, required);
594 
595 	log_event("Proceeding with \"subsets\" mode");
596 	log_event("- Charset: %s size %d", req_charset ? req_charset : charset,
597 	          charcount);
598 	log_event("- Lengths: %d-%d, max. subset size %d",
599 	          MAX(options.eff_minlength, 1), maxlength, maxdiff);
600 	if (required)
601 		log_event("- Required set: First %d of charset", required);
602 	if (rec_restored && john_main_process) {
603 		fprintf(stderr, "Proceeding with \"subsets\"%s%s",
604 		        req_charset ? ": " : "",
605 		        req_charset ? req_charset : "");
606 		if (options.flags & FLG_MASK_CHK)
607 			fprintf(stderr, ", hybrid mask:%s", options.eff_mask);
608 		if (options.rule_stack)
609 			fprintf(stderr, ", rules-stack:%s", options.rule_stack);
610 		if (options.req_minlength >= 0 || options.req_maxlength)
611 			fprintf(stderr, ", lengths: %d-%d",
612 			        options.eff_minlength + mask_add_len,
613 			        options.eff_maxlength + mask_add_len);
614 		fprintf(stderr, "\n");
615 	}
616 
617 	crk_init(db, fix_state, NULL);
618 
619 	/* Iterate over subset sizes and output lengths */
620 	while (num_comb <= maxdiff && word_len <= maxlength) {
621 		int target = MIN(num_comb, word_len);
622 		uint64_t num_sets = numsets(charcount, num_comb, required);
623 		uint64_t num_words = numwords(num_comb, charcount, word_len, required);
624 		int bail = 0;
625 
626 		log_event("- Subset size %d, word length %d (%"PRIu64" sets x %"PRIu64
627 		          " words), keyspace %"PRIu64, num_comb, word_len, num_sets,
628 		          num_words / num_sets, num_words);
629 
630 		if (!state_restored) {
631 			/* Initialize first subset */
632 			for (i = 0; i < num_comb; i++)
633 				charset_idx[num_comb - i - 1] = i;
634 		}
635 
636 		/* Iterate over subsets for this size */
637 		while (1) {
638 			int skip = 0;
639 
640 			if (state_restored)
641 				state_restored = 0;
642 			else
643 				set++;
644 
645 			if (options.node_count) {
646 				int for_node = set % options.node_count + 1;
647 				skip = for_node < options.node_min ||
648 					for_node > options.node_max;
649 			}
650 
651 			if (!skip) {
652 				/* Set current subset */
653 				quick_conversion = 1;
654 				for (i = 0; i < num_comb; i++) {
655 					if ((subset[i] = charset_utf32[charset_idx[i]]) > cp_max)
656 						quick_conversion = 0;
657 				}
658 
659 				/* Create all words for this subset and length */
660 				if (word_len > num_comb) {
661 					if (expand(subset, num_comb, word_len, 0)) {
662 						bail = 1;
663 						break;
664 					}
665 				} else {
666 					if (permute(subset, 0, word_len)) {
667 						bail = 1;
668 						break;
669 					}
670 				}
671 			}
672 
673 			num_done[word_len] += num_words / num_sets;
674 
675 			if (bail || num_comb == charcount)
676 				break;
677 
678 			/* Next subset of this size */
679 			i = 0;
680 			do {
681 				int b;
682 
683 				while (i < target && ++charset_idx[i] >= charcount)
684 					++i;
685 
686 				if (required && charset_idx[num_comb - 1] >= required)
687 					i = num_comb;
688 
689 				if (i >= num_comb)
690 					break;
691 
692 				b = i;
693 				while (--i >= 0)
694 				if ((charset_idx[i] = charset_idx[i + 1] + 1) >= charcount) {
695 					i = b + 1;
696 					break;
697 				}
698 			} while (i >= 0);
699 
700 			if (i >= num_comb)
701 				break;
702 		}
703 
704 		if (bail)
705 			break;
706 
707 		done_len[num_comb] = word_len;
708 
709 		for (i = min_comb; i <= maxdiff; i++)
710 			if (done_len[i] < word_len)
711 				break;
712 
713 		if (i > maxdiff) {
714 			log_event("- Length %d now fully exhausted", word_len);
715 			subsets_cur_len = word_len + 1;
716 			keyspace = 0;
717 			for (i = min_comb; i <= MIN(subsets_cur_len, maxdiff); i++)
718 				keyspace += numwords(i, charcount, subsets_cur_len, required);
719 			if (cfg_get_bool("Subsets", NULL, "LengthIterStatus", 1))
720 				event_pending = event_status = 1;
721 		}
722 
723 		/*
724 		 * Next length or next subset size, whichever has smaller keyspace.
725 		 * A larger subset size than next, of *same* length, can actually be
726 		 * smaller - but we never pick that.
727 		 */
728 		num_comb = min_comb;
729 		while (done_len[num_comb] == maxlength && num_comb < maxdiff)
730 			word_len = done_len[++num_comb];
731 
732 		/* Are we done yet? */
733 		if (++word_len > maxlength)
734 			break;
735 
736 		if (num_comb < maxdiff && done_len[num_comb + 1] + 1 < maxlength &&
737 		    numwords(num_comb + 1, charcount, done_len[num_comb + 1] + 1,
738 		             required) <
739 		    numwords(num_comb, charcount, word_len, required)) {
740 			num_comb++;
741 			word_len = done_len[num_comb] + 1;
742 		}
743 		else if (num_comb + 1 < maxdiff &&
744 		         done_len[num_comb + 2] + 1 < maxlength &&
745 		         numwords(num_comb + 2, charcount, done_len[num_comb + 2] + 1,
746 		                  required) <
747 		         numwords(num_comb, charcount, word_len, required)) {
748 			num_comb += 2;
749 			word_len = done_len[num_comb] + 1;
750 		}
751 	}
752 
753 	crk_done();
754 	rec_done(event_abort);
755 
756 	MEM_FREE(charset_utf32);
757 
758 	return 0;
759 }
760