Line data Source code
1 : #include "passgen/generate.h"
2 :
3 : #include "passgen/assert.h"
4 : #include "passgen/container/hashmap.h"
5 : #include "passgen/container/stack.h"
6 : #include "passgen/markov.h"
7 : #include "passgen/pattern/group.h"
8 : #include "passgen/pattern/literal.h"
9 : #include "passgen/pattern/pattern.h"
10 : #include "passgen/pattern/range.h"
11 : #include "passgen/pattern/repeat.h"
12 : #include "passgen/pattern/segment.h"
13 : #include "passgen/pattern/segment_item.h"
14 : #include "passgen/pattern/set.h"
15 : #include "passgen/pattern/special.h"
16 : #include "passgen/util/utf8.h"
17 : #include "passgen/wordlist.h"
18 : #include "try.h"
19 :
20 : #include <string.h>
21 :
22 : typedef struct {
23 : passgen_env *env;
24 : size_t depth;
25 : double *entropy;
26 : void *data;
27 : passgen_generate_cb *func;
28 : } passgen_generate_context;
29 :
30 : // Emit a character
31 143 : static inline int emit(passgen_generate_context *context, uint32_t codepoint) {
32 143 : return context->func(context->data, codepoint);
33 : }
34 :
35 : // Recurse
36 89 : static inline int descend(passgen_generate_context *context) {
37 89 : if(!context->depth) {
38 3 : return 1;
39 : }
40 :
41 86 : context->depth -= 1;
42 86 : return 0;
43 : }
44 :
45 83 : static inline void ascend(passgen_generate_context *context) {
46 83 : context->depth += 1;
47 83 : }
48 :
49 : static size_t passgen_generate_repeat(
50 : passgen_generate_context *context,
51 : const passgen_pattern_repeat *repeat);
52 :
53 : static int passgen_generate_set(
54 : passgen_generate_context *context,
55 : const passgen_pattern_set *set);
56 :
57 : static int passgen_generate_literal(
58 : passgen_generate_context *context,
59 : const passgen_pattern_literal *character);
60 :
61 : static int passgen_generate_special_markov(
62 : passgen_generate_context *context,
63 : const passgen_pattern_special *special);
64 :
65 : static int passgen_generate_special_wordlist(
66 : passgen_generate_context *context,
67 : const passgen_pattern_special *special);
68 :
69 : static int passgen_generate_special(
70 : passgen_generate_context *context,
71 : const passgen_pattern_special *special);
72 :
73 : static int passgen_generate_group(
74 : passgen_generate_context *context,
75 : const passgen_pattern_group *group);
76 :
77 : static int passgen_generate_item(
78 : passgen_generate_context *context,
79 : const passgen_pattern_item *item);
80 :
81 : static int passgen_generate_segment(
82 : passgen_generate_context *context,
83 : const passgen_pattern_segment *segment);
84 :
85 : struct fillpos {
86 : uint32_t *buffer;
87 : size_t cur;
88 : size_t len;
89 : };
90 :
91 : struct fillpos_utf8 {
92 : uint8_t *buffer;
93 : size_t cur;
94 : size_t len;
95 : };
96 :
97 47 : static int passgen_generate_write_buffer(void *data, uint32_t codepoint) {
98 47 : struct fillpos *fillpos = data;
99 :
100 47 : if(fillpos->cur == fillpos->len) {
101 0 : return -1;
102 : }
103 :
104 47 : fillpos->buffer[fillpos->cur] = codepoint;
105 47 : fillpos->cur++;
106 :
107 47 : return 0;
108 : }
109 :
110 90 : static int passgen_generate_write_buffer_utf8(void *data, uint32_t codepoint) {
111 90 : struct fillpos_utf8 *fillpos = data;
112 :
113 90 : if(fillpos->cur == fillpos->len) {
114 0 : return -1;
115 : }
116 :
117 90 : if((fillpos->cur + 4) <= fillpos->len) {
118 90 : int bytes = passgen_utf8_encode_codepoint(
119 90 : (uint8_t *) &fillpos->buffer[fillpos->cur],
120 : codepoint);
121 :
122 90 : if(bytes < 0) {
123 : // error happened during encoding.
124 0 : return -1;
125 : }
126 :
127 90 : fillpos->cur += bytes;
128 : } else {
129 : char buffer[4];
130 : int bytes =
131 0 : passgen_utf8_encode_codepoint((uint8_t *) &buffer[0], codepoint);
132 :
133 0 : if(bytes < 0) {
134 : // error happened during encoding.
135 0 : return -1;
136 : }
137 :
138 0 : if(bytes <= (fillpos->len - fillpos->cur)) {
139 0 : memcpy(&fillpos->buffer[fillpos->cur], &buffer[0], bytes);
140 0 : fillpos->cur += bytes;
141 : } else {
142 : // error: encoded doesn't fit in buffer.
143 0 : return -1;
144 : }
145 : }
146 :
147 90 : return 0;
148 : }
149 :
150 : /// Write JSON-escaped UTF-8 to buffer.
151 : static int
152 0 : passgen_generate_write_buffer_json_utf8(void *data, uint32_t codepoint) {
153 0 : struct fillpos_utf8 *fillpos = data;
154 :
155 0 : if(fillpos->cur == fillpos->len) {
156 0 : return -1;
157 : }
158 :
159 0 : unsigned char buffer[4] = {'\\', 0};
160 0 : size_t bytes = 2;
161 0 : switch(codepoint) {
162 0 : case '"':
163 0 : buffer[1] = '"';
164 0 : break;
165 0 : case '\\':
166 0 : buffer[1] = '\\';
167 0 : break;
168 0 : case '\b':
169 0 : buffer[1] = 'b';
170 0 : break;
171 0 : case '\f':
172 0 : buffer[1] = 'f';
173 0 : break;
174 0 : case '\r':
175 0 : buffer[1] = 'r';
176 0 : break;
177 0 : case '\n':
178 0 : buffer[1] = 'n';
179 0 : break;
180 0 : case '\t':
181 0 : buffer[1] = 't';
182 0 : break;
183 0 : default:
184 0 : bytes = passgen_utf8_encode_codepoint(
185 : (uint8_t *) &buffer[0],
186 : codepoint);
187 : }
188 :
189 : // check that no error happened.
190 0 : if(!bytes) {
191 0 : return -1;
192 : }
193 :
194 : // make sure it fits.
195 0 : if(bytes <= (fillpos->len - fillpos->cur)) {
196 0 : memcpy(&fillpos->buffer[fillpos->cur], &buffer[0], bytes);
197 0 : fillpos->cur += bytes;
198 : } else {
199 0 : return -1;
200 : }
201 :
202 0 : return 0;
203 : }
204 :
205 28 : size_t passgen_generate_fill_unicode(
206 : const passgen_pattern *pattern,
207 : passgen_env *env,
208 : double *entropy,
209 : uint32_t *buffer,
210 : size_t len) {
211 28 : struct fillpos fillpos = {
212 : .buffer = buffer,
213 : .len = len,
214 : .cur = 0,
215 : };
216 :
217 28 : int ret = passgen_generate(
218 : pattern,
219 : env,
220 : entropy,
221 : &fillpos,
222 : passgen_generate_write_buffer);
223 :
224 28 : if(ret != 0) {
225 0 : return 0;
226 : }
227 :
228 28 : return fillpos.cur;
229 : }
230 :
231 31 : size_t passgen_generate_fill_utf8(
232 : const passgen_pattern *pattern,
233 : passgen_env *env,
234 : double *entropy,
235 : uint8_t *buffer,
236 : size_t len) {
237 31 : struct fillpos_utf8 fillpos = {
238 : .buffer = buffer,
239 : .len = len,
240 : .cur = 0,
241 : };
242 :
243 31 : int ret = passgen_generate(
244 : pattern,
245 : env,
246 : entropy,
247 : &fillpos,
248 : passgen_generate_write_buffer_utf8);
249 :
250 31 : if(ret != 0) {
251 0 : return 0;
252 : }
253 :
254 31 : return fillpos.cur;
255 : }
256 :
257 0 : size_t passgen_generate_fill_json_utf8(
258 : const passgen_pattern *pattern,
259 : passgen_env *env,
260 : double *entropy,
261 : uint8_t *buffer,
262 : size_t len) {
263 0 : struct fillpos_utf8 fillpos = {
264 : .buffer = buffer,
265 : .len = len,
266 : .cur = 0,
267 : };
268 :
269 0 : int ret = passgen_generate(
270 : pattern,
271 : env,
272 : entropy,
273 : &fillpos,
274 : passgen_generate_write_buffer_json_utf8);
275 :
276 0 : if(ret != 0) {
277 0 : return 0;
278 : }
279 :
280 0 : return fillpos.cur;
281 : }
282 :
283 84 : static size_t passgen_generate_repeat(
284 : passgen_generate_context *context,
285 : const passgen_pattern_repeat *repeat) {
286 84 : size_t difference = repeat->max - repeat->min;
287 :
288 : // if there is no difference to pick, just return here
289 84 : if(0 == difference) {
290 78 : return repeat->min;
291 : }
292 :
293 : // get random number to choose from the range
294 : size_t choice =
295 6 : passgen_random_u64_max(context->env->random, difference + 1);
296 :
297 : // keep track of entropy
298 6 : if(context->entropy) {
299 4 : *context->entropy *= difference + 1;
300 : }
301 :
302 6 : return repeat->min + choice;
303 : }
304 :
305 26 : static int passgen_generate_set(
306 : passgen_generate_context *context,
307 : const passgen_pattern_set *set) {
308 : // if this set is empty, we're done.
309 26 : if(set->items.len == 0) {
310 0 : return 0;
311 : }
312 :
313 : // compute number of possible codepoints
314 26 : size_t possible = set->choices_list[set->items.len - 1];
315 26 : passgen_assert(possible != 0);
316 26 : size_t choice = passgen_random_u64_max(context->env->random, possible);
317 :
318 : // keep track of entropy
319 26 : if(context->entropy) {
320 14 : *context->entropy *= possible;
321 : }
322 :
323 : // locate choice in list of choices.
324 : // TODO: binary search.
325 : size_t num;
326 46 : for(num = 0; num < set->items.len; num++) {
327 46 : if(choice < set->choices_list[num]) {
328 26 : break;
329 : }
330 : }
331 :
332 26 : passgen_assert(num != set->items.len);
333 :
334 : /* adjust choice to be relative offset */
335 26 : if(num) {
336 12 : choice -= set->choices_list[num - 1];
337 : }
338 :
339 26 : passgen_pattern_range *range = passgen_stack_get(&set->items, num);
340 :
341 26 : return emit(context, range->start + choice);
342 : }
343 :
344 50 : static int passgen_generate_literal(
345 : passgen_generate_context *context,
346 : const passgen_pattern_literal *literal) {
347 50 : passgen_assert(literal->count > 0);
348 50 : passgen_assert(literal->count < 8);
349 :
350 167 : for(size_t i = 0; i < literal->count; i++) {
351 117 : try(emit(context, literal->codepoints[i]));
352 : }
353 :
354 50 : return 0;
355 : }
356 :
357 0 : static int passgen_generate_special_markov(
358 : passgen_generate_context *context,
359 : const passgen_pattern_special *special) {
360 : passgen_hashmap_entry *entry =
361 0 : passgen_hashmap_lookup(&context->env->wordlists, special->parameters);
362 0 : if(!entry) {
363 0 : return -1;
364 : }
365 0 : passgen_wordlist *wordlist = entry->value;
366 0 : if(!wordlist->parsed) {
367 0 : passgen_wordlist_parse(wordlist);
368 : }
369 0 : if(!wordlist->parsed_markov) {
370 0 : passgen_wordlist_parse_markov(wordlist);
371 : }
372 0 : passgen_markov *markov = &wordlist->markov;
373 : uint32_t word[128];
374 0 : size_t pos = markov->level;
375 0 : memset(word, 0, pos * sizeof(uint32_t));
376 0 : double *entropy = context->entropy ? &*context->entropy : NULL;
377 : do {
378 0 : word[pos] = passgen_markov_generate(
379 : markov,
380 0 : &word[pos - markov->level],
381 0 : context->env->random,
382 : entropy);
383 0 : pos++;
384 0 : } while(word[pos - 1]);
385 :
386 0 : pos = markov->level;
387 0 : while(word[pos]) {
388 0 : try(emit(context, word[pos]));
389 0 : pos++;
390 : }
391 :
392 0 : return 0;
393 : }
394 :
395 0 : static int passgen_generate_special_wordlist(
396 : passgen_generate_context *context,
397 : const passgen_pattern_special *special) {
398 : passgen_hashmap_entry *entry =
399 0 : passgen_hashmap_lookup(&context->env->wordlists, special->parameters);
400 0 : if(!entry) {
401 0 : return -1;
402 : }
403 0 : passgen_wordlist *wordlist = entry->value;
404 0 : if(!wordlist->parsed) {
405 0 : passgen_wordlist_parse(wordlist);
406 : }
407 :
408 : // pick word at random
409 0 : const unsigned char *word = passgen_wordlist_random(wordlist, context->env->random);
410 :
411 : // UTF8-decode word and write codepoints
412 : // TODO: handle longer words
413 0 : size_t word_len = strlen(word);
414 0 : const char *word_pos = &word;
415 : uint32_t codepoints[128];
416 0 : uint32_t *codepoints_pos = &codepoints[0];
417 0 : try(passgen_utf8_decode(&codepoints_pos, 128, NULL, word_pos, word_len));
418 0 : for(int i = 0; &codepoints[i] < codepoints_pos; i++) {
419 0 : try(emit(context, codepoints[i]));
420 : }
421 :
422 0 : if(context->entropy) {
423 0 : *context->entropy *= passgen_wordlist_count(wordlist);
424 : }
425 :
426 0 : return 0;
427 : }
428 :
429 0 : static int passgen_generate_special_preset(
430 : passgen_generate_context *context,
431 : const passgen_pattern_special *special) {
432 : (void) special;
433 : // TODO: implement
434 0 : return 0;
435 : }
436 :
437 0 : static int passgen_generate_special(
438 : passgen_generate_context *context,
439 : const passgen_pattern_special *special) {
440 0 : switch(special->kind) {
441 0 : case PASSGEN_PATTERN_SPECIAL_MARKOV:
442 0 : return passgen_generate_special_markov(context, special);
443 0 : case PASSGEN_PATTERN_SPECIAL_WORDLIST:
444 0 : return passgen_generate_special_wordlist(context, special);
445 0 : case PASSGEN_PATTERN_SPECIAL_PRESET:
446 0 : return passgen_generate_special_preset(context, special);
447 0 : default:
448 0 : return 1;
449 : }
450 : return 0;
451 : }
452 :
453 85 : static int passgen_generate_item(
454 : passgen_generate_context *context,
455 : const passgen_pattern_item *item) {
456 : // if it is a maybe (has a question mark following it), decide first if we
457 : // want to emit it or not.
458 85 : if(item->maybe) {
459 6 : if(!passgen_random_bool(context->env->random)) {
460 1 : return 0;
461 : }
462 : }
463 :
464 : // compute random number of repetitions
465 84 : size_t reps = passgen_generate_repeat(context, &item->repeat);
466 :
467 182 : for(size_t i = 0; i < reps; i++) {
468 101 : switch(item->kind) {
469 26 : case PASSGEN_PATTERN_SET:
470 26 : try(passgen_generate_set(context, &item->data.set));
471 26 : break;
472 50 : case PASSGEN_PATTERN_LITERAL:
473 50 : try(passgen_generate_literal(context, &item->data.literal));
474 50 : break;
475 0 : case PASSGEN_PATTERN_SPECIAL:
476 0 : try(passgen_generate_special(context, &item->data.special));
477 0 : break;
478 25 : case PASSGEN_PATTERN_GROUP:
479 25 : try(passgen_generate_group(context, &item->data.group));
480 22 : break;
481 0 : default:
482 0 : passgen_assert(false);
483 0 : break;
484 : }
485 : }
486 :
487 : // unreachable
488 81 : return 0;
489 : }
490 :
491 86 : static int passgen_generate_segment(
492 : passgen_generate_context *context,
493 : const passgen_pattern_segment *segment) {
494 168 : for(size_t i = 0; i < segment->items.len; i++) {
495 85 : passgen_pattern_item *item = passgen_stack_get(&segment->items, i);
496 :
497 85 : try(passgen_generate_item(context, item));
498 : }
499 :
500 83 : return 0;
501 : }
502 :
503 89 : static int passgen_generate_group(
504 : passgen_generate_context *context,
505 : const passgen_pattern_group *group) {
506 : // descend in depth
507 89 : try(descend(context));
508 :
509 86 : if(group->multiplier_sum == 0) {
510 0 : return 1;
511 : }
512 :
513 : // choose random segment from segments
514 : size_t choice =
515 86 : passgen_random_u64_max(context->env->random, group->multiplier_sum);
516 86 : size_t segment_index = 0;
517 : passgen_pattern_segment *segment =
518 86 : passgen_stack_get(&group->segments, segment_index);
519 :
520 100 : while(choice >= segment->multiplier) {
521 14 : choice -= segment->multiplier;
522 14 : segment_index += 1;
523 14 : segment = passgen_stack_get(&group->segments, segment_index);
524 : }
525 :
526 : // keep track of entropy
527 86 : if(context->entropy) {
528 44 : *context->entropy *= group->multiplier_sum;
529 44 : *context->entropy /= segment->multiplier;
530 : }
531 :
532 86 : try(passgen_generate_segment(context, segment));
533 :
534 83 : ascend(context);
535 :
536 83 : return 0;
537 : }
538 :
539 64 : int passgen_generate(
540 : const passgen_pattern *pattern,
541 : passgen_env *env,
542 : double *entropy,
543 : void *data,
544 : passgen_generate_cb *func) {
545 : // when entropy collection is request (by passing a non-NULL pointer),
546 : // initialize it.
547 64 : if(entropy) {
548 31 : *entropy = 1.0;
549 : }
550 :
551 64 : passgen_generate_context context = {
552 : .env = env,
553 64 : .depth = env->depth_limit,
554 : .func = func,
555 : .data = data,
556 : .entropy = entropy,
557 : };
558 :
559 64 : return passgen_generate_group(&context, &pattern->group);
560 : }
|
