1 /* eschalot - generates vanity .onion names using brute-force hashing.
2 * A fork of shallot, which was a fork of onionhash. */
3
4 /*
5 * Copyright (c) 2013 Unperson Hiro <blacksunhq56imku.onion>
6 * Copyright (c) 2007 Orum <hangman5naigg7rr.onion>
7 * Copyright (c) 2006 Cowboy Bebop <torlandypjxiligx.onion>
8 *
9 * Permission to use, copy, modify, and distribute this software for any
10 * purpose with or without fee is hereby granted, provided that the above
11 * copyright notice and this permission notice appear in all copies.
12 *
13 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
14 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
15 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
16 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
17 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
18 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
19 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
20 */
21
22 /* Lets agree on 100 characters line limit, tab is 8 spaces long, second level ident is 4 spaces. */
23 /* ---------- This wide ------------------------------------------------------------------------- */
24
25 #ifdef __APPLE__
26 #include <libkern/OSByteOrder.h>
27
28 #define htobe16(x) OSSwapHostToBigInt16(x)
29 #define htole16(x) OSSwapHostToLittleInt16(x)
30 #define be16toh(x) OSSwapBigToHostInt16(x)
31 #define le16toh(x) OSSwapLittleToHostInt16(x)
32
33 #define htobe32(x) OSSwapHostToBigInt32(x)
34 #define htole32(x) OSSwapHostToLittleInt32(x)
35 #define be32toh(x) OSSwapBigToHostInt32(x)
36 #define le32toh(x) OSSwapLittleToHostInt32(x)
37
38 #define htobe64(x) OSSwapHostToBigInt64(x)
39 #define htole64(x) OSSwapHostToLittleInt64(x)
40 #define be64toh(x) OSSwapBigToHostInt64(x)
41 #define le64toh(x) OSSwapLittleToHostInt64(x)
42 #endif /* __APPLE__ */
43
44 #if defined(__linux__) || defined(__CYGWIN__)
45 # define _GNU_SOURCE
46 # include <endian.h>
47 #endif
48
49 #ifdef __FreeBSD__
50 # include <sys/endian.h>
51 #endif
52
53 #include <sys/types.h>
54
55 #include <ctype.h>
56 #include <getopt.h>
57 #include <inttypes.h>
58 #include <pthread.h>
59 #include <regex.h>
60 #include <stdarg.h>
61 #include <stdio.h>
62 #include <stdlib.h>
63 #include <string.h>
64 #include <unistd.h>
65
66 #include <openssl/bn.h>
67 #include <openssl/pem.h>
68 #include <openssl/rsa.h>
69 #include <openssl/sha.h>
70 #define OPENSSL_VERSION_1_1 0x10100000L
71 #define OPENSSL_VERSION_0_9_0_8 0x0090800FL
72
73 /* Define NEED_HTOBE32 if htobe32() is not available on your platform. */
74 /* #define NEED_HTOBE32 */
75 #if BYTE_ORDER == LITTLE_ENDIAN
76 # ifdef NEED_HTOBE32
77 # define HTOBE32(x) (((uint32_t)(x) & 0xffu) << 24 | \
78 ((uint32_t)(x) & 0xff00u) << 8 | \
79 ((uint32_t)(x) & 0xff0000u) >> 8 | \
80 ((uint32_t)(x) & 0xff000000u) >> 24)
81 # else
82 # define HTOBE32(x) htobe32(x)
83 # endif
84 #else
85 # define HTOBE32(x) (x)
86 #endif
87
88 /* Define NEED_STRNLEN if strnlen() is not available on your platform. */
89 /* #define NEED_STRNLEN */
90 #ifdef NEED_STRNLEN
91 static size_t strnlen(const char *, size_t);
92 size_t
strnlen(const char * s,size_t ml)93 strnlen(const char *s, size_t ml)
94 {
95 unsigned int i;
96 for (i = 0; *(s + i) != '\0' && i < ml; i++)
97 ;
98 return i;
99 }
100 #endif
101
102
103 #define VERSION "1.2.0"
104 #define SHA_REL_CTX_LEN 10 * sizeof(SHA_LONG) /* 40 bytes */
105 #define RSA_KEYS_BITLEN 1024 /* RSA key length to use */
106 #define SIZE_OF_E 4 /* Limit public exponent to 4 bytes */
107 #define RSA_E_START 0xFFFFFFu + 2 /* Min e */
108 #define RSA_E_LIMIT 0x7FFFFFFFu /* Max e */
109 #define ONION_LENP1 17 /* Onion name length plus 1 */
110 #define MAX_THREADS 100 /* Maximum number of threads */
111 #define MAX_WORDS 0xFFFFFFFFu /* Maximum words to read from file */
112 #define BASE32_ALPHABET "abcdefghijklmnopqrstuvwxyz234567"
113
114 extern char *__progname;
115
116 /* Error and debug functions */
117 static void usage(void);
118 static void error(char *, ...);
119 static void verbose(char *, ...);
120 static void normal(char *, ...);
121 static void (*msg)(char *, ...);
122 /* User IO functions */
123 static void setoptions(int, char *[]);
124 static void readfile(void);
125 static void printresult(RSA *, uint8_t *, uint8_t *);
126 /* Math and search functions */
127 static _Bool fsearch(uint8_t *, uint8_t *);
128 static _Bool psearch(uint8_t *, uint8_t *);
129 static _Bool rsearch(uint8_t *, uint8_t *);
130 static _Bool (*search)(uint8_t *, uint8_t *);
131 static _Bool validkey(RSA *);
132 static signed int compare(const void *, const void *);
133 static void base32_enc(uint8_t *, uint8_t *);
134 static void base32_dec(uint8_t *, uint8_t *);
135 static void onion_enc(uint8_t *, RSA *);
136 static void zerobits(uint16_t * ind, uint64_t * word,
137 uint8_t * buffer, unsigned int length);
138 /* Main thread routine */
139 static void *worker(void *);
140
141 /* Global variables */
142 /* TODO: perhaps getting rid of so many globals is in order... */
143 _Bool done, cflag, fflag, nflag, pflag, rflag, vflag;
144 unsigned int minlen, maxlen, threads, prefixlen, wordcount;
145 char fn[FILENAME_MAX + 1], prefix[ONION_LENP1];
146 regex_t *regex;
147
148 pthread_mutex_t printresult_lock;
149
150 struct {
151 unsigned int count;
152 uint64_t *branch;
153 } tree[65536] = { {0, NULL} };
154
155 int
main(int argc,char * argv[])156 main(int argc, char *argv[])
157 {
158 pthread_t babies[MAX_THREADS];
159 uint64_t count[MAX_THREADS];
160 unsigned int i, j, dupcount = 0;
161
162 pthread_mutex_init(&printresult_lock, NULL);
163
164 /* Initialize global flags */
165 wordcount = done = cflag = fflag = nflag = pflag = rflag = vflag = 0;
166 minlen = 8;
167 maxlen = 16;
168 threads = 1;
169 msg = normal; /* Default: non-verbose */
170 search = NULL; /* No default search, has to be specified */
171
172 setoptions(argc, argv);
173
174 if (fflag) {
175 readfile();
176 msg("Sorting the word hashes and removing duplicates.\n");
177 wordcount = 0;
178 for (i = 0; i < 65536; i++) {
179 dupcount = 0;
180 qsort(tree[i].branch, tree[i].count, sizeof(tree[i].branch[0]), &compare);
181 for (j = 1; j < tree[i].count ; j++) {
182 if (tree[i].branch[j] == tree[i].branch[j - 1]) {
183 tree[i].branch[j - 1] = 0xFFFFFFFFFFFFFFFFu;
184 dupcount++;
185 }
186 }
187
188 if (dupcount > 0) {
189 qsort(tree[i].branch, tree[i].count, sizeof(tree[i].branch[0]),
190 &compare);
191 tree[i].count -= dupcount;
192 }
193 wordcount += tree[i].count;
194 }
195 msg("Final word count: %d.\n", wordcount);
196 }
197
198 /* Start our threads */
199 for (i = 1; i <= threads; i++) {
200 count[i] = 0;
201 if (pthread_create(&babies[i], NULL, worker, (void *)&count[i]) != 0)
202 error("Failed to start thread!\n");
203 msg("Thread #%d started.\n", i);
204 }
205
206 /* Monitor performance
207 * TODO: redo this whole thing, add estimate time for keys */
208 if (vflag) {
209 uint64_t loops;
210 time_t elapsed, start = time(NULL);
211 unsigned int delay = 5;
212
213 msg("Running, collecting performance data...\n");
214 for(;;) {
215 sleep(delay *= 2);
216 if (done)
217 return 0;
218
219 /* Collect our thread's counters */
220 loops = 0;
221 i = threads;
222 do {
223 loops += count[i];
224 } while (--i);
225
226 /* On a really slow machine the initial delay might not be
227 * enough to generate the first RSA key, so give it more time. */
228 if (loops == 0)
229 continue;
230
231 elapsed = time(NULL) - start;
232
233 /* Bug here somewhere - with pcc compiler only. */
234 /* TODO: Fix. */
235 msg("Total hashes: %" PRIu64
236 ", running time: %d seconds, hashes per second: %" PRIu64 "\n",
237 loops, elapsed, (uint64_t)(loops / elapsed));
238 }
239 }
240 /* Wait for all the threads to exit */
241 for (i = 1; i <= threads; i++)
242 pthread_join(babies[i], NULL);
243 exit(0);
244 }
245
246 /* Main hashing thread */
247 void *
worker(void * arg)248 worker(void *arg)
249 {
250 SHA_CTX hash, copy;
251 RSA *rsa = NULL;
252 uint8_t *tmp, *der,
253 buf[SHA_DIGEST_LENGTH],
254 onion[ONION_LENP1],
255 onionfinal[ONION_LENP1];
256 signed int derlen;
257 uint64_t *counter;
258 /* Public exponent and the "big-endian" version of it */
259 unsigned int e, e_be;
260 BIGNUM *big_e = BN_new();
261 BN_set_word(big_e, (unsigned long) RSA_E_START);
262
263 counter = (uint64_t *)arg;
264
265 while (!done) {
266 /* Generate a new RSA key every time e reaches RSA_E_LIMIT */
267 #if OPENSSL_VERSION_NUMBER >= OPENSSL_VERSION_0_9_0_8
268 rsa = RSA_new();
269 if (!RSA_generate_key_ex(rsa, RSA_KEYS_BITLEN, big_e, NULL))
270 error("RSA Key Generation failed!\n");
271 #else
272 rsa = RSA_generate_key(RSA_KEYS_BITLEN, RSA_E_START,
273 NULL, NULL);
274 if (!rsa)
275 error("RSA Key Generation failed!\n");
276 #endif
277
278 /* Too chatty - disable. */
279 /* msg("Generated a new RSA key pair.\n"); */
280
281 /* Encode RSA key in X.690 DER format */
282 if((derlen = i2d_RSAPublicKey(rsa, NULL)) < 0)
283 error("DER encoding failed!\n");
284 if ((der = tmp = (uint8_t *)malloc(derlen)) == NULL)
285 error("malloc(derlen) failed!\n");
286 if (i2d_RSAPublicKey(rsa, &tmp) != derlen)
287 error("DER encoding failed!\n");
288
289 /* Prepare the hash context */
290 SHA1_Init(&hash);
291 SHA1_Update(&hash, der, derlen - SIZE_OF_E);
292 free(der);
293 e = RSA_E_START - 2; /* public exponent */
294 BN_set_word(big_e, (unsigned long) e);
295
296 /* Main loop */
297 while ((e < RSA_E_LIMIT) && !done) {
298 e += 2;
299 /* Convert e to big-endian format. */
300 e_be = HTOBE32(e);
301 /* Copy the relevant parts of already set up context. */
302 memcpy(©, &hash, SHA_REL_CTX_LEN); /* 40 bytes */
303 copy.num = hash.num;
304 /* Compute SHA1 digest (the real bottleneck) */
305 SHA1_Update(©, &e_be, SIZE_OF_E);
306 SHA1_Final(buf, ©);
307 (*counter)++;
308 /* This is fairly fast, but can be faster if inlined. */
309 base32_enc(onion, buf);
310
311 /* The search speed varies based on the mode we are in.
312 * Regex's performance depends on the expression used.
313 * Fixed prefix is as fast as memcmp(3).
314 * Wordlist performance depends on (mostly):
315 * number of "lengths" to search for (-l from-to);
316 * number of unique words loaded from file.
317 *
318 * Inlining everything and optimizing for one mode and
319 * fixed word length improved the performance somewhat
320 * when I tried it, but it's not worth it. */
321 if (search(buf, onion)) {
322 /* Found a possible key,
323 * from here on down performance is not critical. */
324 #if OPENSSL_VERSION_NUMBER >= OPENSSL_VERSION_1_1
325 BIGNUM *new_e;
326 new_e = BN_bin2bn((uint8_t *)&e_be, SIZE_OF_E, NULL);
327 if (new_e == NULL)
328 error("Failed to convert e to BIGNUM!\n");
329 if(!RSA_set0_key(rsa, NULL, new_e, NULL))
330 error("Failed to set e in RSA key!\n");
331 #else
332 if (!BN_bin2bn((uint8_t *)&e_be, SIZE_OF_E, rsa->e))
333 error("Failed to set e in RSA key!\n");
334 #endif
335 if (!validkey(rsa))
336 error("A bad key was found!\n");
337 if (pflag)
338 onion[prefixlen] = '\0';
339
340 onion_enc(onionfinal, rsa);
341
342 /* Every so often the onion found matches
343 * whatever we were looking for, but the final
344 * generated onion is garbage. I suspect a CPU
345 * or RAM overheating, but it could be a subtle
346 * bug somewhere. Hard to pin-point. According
347 * to the reports I've seen, shallot has had a
348 * similar problem.
349 *
350 * Happens most often in a wordlist search mode,
351 * but I think I have seen it in a regex mode
352 * as well. Does not seem to happen in a fixed
353 * prefix mode.
354 *
355 * Adding this check to avoid producing garbage
356 * results and to alleviate the problem a bit. */
357 if (strncmp((char *)onion, (char *)onionfinal,
358 (!rflag ? strnlen((char *)onion, ONION_LENP1) : 16))) {
359 msg("\nWARNING! Error detected! CPU/RAM overheating?\n");
360 msg("Found %s, but finalized to %s.\n",
361 (char *)onion, (char *)onionfinal);
362 msg("Suspending this thread for 30 seconds.\n");
363 sleep(30);
364 msg("Generating new RSA key.\n\n");
365 break;
366 } else {
367 pthread_mutex_lock(&printresult_lock);
368 printresult(rsa, onion, onionfinal);
369
370 pthread_mutex_unlock(&printresult_lock);
371 }
372
373 if (!cflag)
374 done = 1; /* Notify other threads. */
375 break;
376 }
377 }
378 RSA_free(rsa);
379 }
380 return 0;
381 }
382
383 /* Read words from file */
384 void
readfile(void)385 readfile(void)
386 {
387 FILE *file;
388 uint8_t w[ONION_LENP1] = { 0 }, buf[10];
389 uint8_t len, j;
390 uint16_t ind;
391 signed int c;
392 uint64_t wrd;
393 _Bool inword;
394
395 if ((file = fopen(fn,"r")) == NULL)
396 error("Failed to open %s!\n", fn);
397 msg("Reading words from %s, please wait...\n", fn);
398
399 /* We have to inspect each character individually anyway,
400 * so lets just use fgetc here and let the OS buffer stuff. */
401 j = 0;
402 while ((c = fgetc(file)) != EOF) {
403 c = tolower(c);
404 inword = 0;
405 /* Only load words with digits if the -n option was used. */
406 if ((c >= 'a' && c <= 'z') || (nflag && c >= '2' && c <= '7')) {
407 w[j++] = c;
408 inword = 1;
409 }
410
411 if ((!inword && j > 0) || j > 16) {
412 /* We clip the words longer than 16 characters here. */
413 w[j] = '\0';
414 j = 0;
415 /* Only pick the words of the length we need. */
416 len = strnlen((char *)w, ONION_LENP1);
417 if (len >= minlen && len <= maxlen && wordcount < MAX_WORDS) {
418 base32_dec(buf, w);
419 memset(w, 0, sizeof(w));
420 zerobits(&ind, &wrd, buf, len);
421
422 if ((tree[ind].branch = (uint64_t *)realloc(tree[ind].branch,
423 sizeof(uint64_t) * (tree[ind].count + 1))) == NULL)
424 error("realloc() failed!\n");
425
426 tree[ind].branch[tree[ind].count] = wrd;
427 tree[ind].count++;
428 wordcount++;
429 }
430 }
431 }
432 fclose(file);
433
434 if (wordcount == 0 )
435 error("Could not find any valid words in %s!\n", fn);
436 else
437 msg("Loaded %d words.\n", wordcount);
438 }
439
440 /* Check if the RSA key is ok (PKCS#1 v2.1). */
441 _Bool
validkey(RSA * rsa)442 validkey(RSA *rsa)
443 {
444 BN_CTX *ctx = BN_CTX_new();
445 BN_CTX_start(ctx);
446 BIGNUM *p1 = BN_CTX_get(ctx), /* p - 1 */
447 *q1 = BN_CTX_get(ctx), /* q - 1 */
448 *gcd = BN_CTX_get(ctx), /* GCD(p - 1, q - 1) */
449 *lambda = BN_CTX_get(ctx), /* LCM(p - 1, q - 1) */
450 *tmp = BN_CTX_get(ctx); /* temporary storage */
451 #if OPENSSL_VERSION_NUMBER >= OPENSSL_VERSION_1_1
452 BIGNUM const *n = BN_CTX_get(ctx),
453 *e = BN_CTX_get(ctx),
454 *d = BN_CTX_get(ctx);
455 BIGNUM const *p = BN_CTX_get(ctx),
456 *q = BN_CTX_get(ctx);
457 BIGNUM const *dmp1 = BN_CTX_get(ctx),
458 *dmq1 = BN_CTX_get(ctx),
459 *iqmp = BN_CTX_get(ctx);
460
461 RSA_get0_key(rsa, &n, &e, &d);
462 if (n == NULL || e == NULL || d == NULL)
463 error("RSA_get0_key() failed!\n");
464
465 RSA_get0_factors(rsa, &p, &q);
466 if (p == NULL || q == NULL)
467 error("RSA_get0_factors() failed!\n");
468
469 RSA_get0_crt_params(rsa, &dmp1, &dmq1, &iqmp);
470 if (dmp1 == NULL || dmq1 == NULL || iqmp == NULL)
471 error("RSA_get0_crt_params() failed!\n");
472
473 BN_sub(p1, p, BN_value_one()); /* p - 1 */
474 BN_sub(q1, q, BN_value_one()); /* q - 1 */
475 #else
476 BN_sub(p1, rsa->p, BN_value_one()); /* p - 1 */
477 BN_sub(q1, rsa->q, BN_value_one()); /* q - 1 */
478 #endif
479 BN_gcd(gcd, p1, q1, ctx); /* gcd(p - 1, q - 1) */
480
481 BN_div(tmp, NULL, p1, gcd, ctx);
482 BN_mul(lambda, q1, tmp, ctx); /* lambda(n) */
483
484 /* Check if e is coprime to lambda(n). */
485 #if OPENSSL_VERSION_NUMBER >= OPENSSL_VERSION_1_1
486 BN_gcd(tmp, lambda, e, ctx);
487 #else
488 BN_gcd(tmp, lambda, rsa->e, ctx);
489 #endif
490 if (!BN_is_one(tmp)) {
491 verbose("WARNING: Key check failed - e is coprime to lambda!\n");
492 return 0;
493 }
494
495 /* Check if public exponent e is less than n - 1. */
496 /* Subtract n from e to avoid checking BN_is_zero. */
497 #if OPENSSL_VERSION_NUMBER >= OPENSSL_VERSION_1_1
498 BN_sub(tmp, n, BN_value_one());
499 if (BN_cmp(e, tmp) >= 0) {
500 verbose("WARNING: Key check failed - e is less than (n - 1)!\n");
501 return 0;
502 }
503 #else
504 BN_sub(tmp, rsa->n, BN_value_one());
505 if (BN_cmp(rsa->e, tmp) >= 0) {
506 verbose("WARNING: Key check failed - e is less than (n - 1)!\n");
507 return 0;
508 }
509 #endif
510
511 #if OPENSSL_VERSION_NUMBER >= OPENSSL_VERSION_1_1
512 BIGNUM *new_d = BN_new(),
513 *new_dmp1 = BN_new(),
514 *new_dmq1 = BN_new(),
515 *new_iqmp = BN_new();
516
517 BN_mod_inverse(new_d, e, lambda, ctx); /* d */
518 BN_mod(new_dmp1, new_d, p1, ctx); /* d mod(p - 1) */
519 BN_mod(new_dmq1, new_d, q1, ctx); /* d mod(q - 1) */
520 BN_mod_inverse(new_iqmp, q, p, ctx); /* q ^ -1 mod p */
521
522 if (!RSA_set0_key(rsa, NULL, NULL, new_d))
523 error("RSA_set0_key() failed!\n");
524
525 if (!RSA_set0_crt_params(rsa, new_dmp1, new_dmq1, new_iqmp))
526 error("RSA_set0_crt_params() failed!\n");
527 #else
528 BN_mod_inverse(rsa->d, rsa->e, lambda, ctx); /* d */
529 BN_mod(rsa->dmp1, rsa->d, p1, ctx); /* d mod(p - 1) */
530 BN_mod(rsa->dmq1, rsa->d, q1, ctx); /* d mod(q - 1) */
531 BN_mod_inverse(rsa->iqmp, rsa->q, rsa->p, ctx); /* q ^ -1 mod p */
532 #endif
533 BN_CTX_end(ctx);
534 BN_CTX_free(ctx);
535
536 /* In theory this should never be true,
537 * unless the guy before me made a mistake ;). */
538 if (RSA_check_key(rsa) != 1) {
539 verbose("WARNING: OpenSSL's RSA_check_key(rsa) failed!\n");
540 return 0;
541 }
542 return 1;
543 }
544
545 /* Base32 encode 10 byte long 'src' into 16 character long 'dst' */
546 /* Experimental, unroll everything. So far, it seems to be the fastest of the
547 * algorithms that I've tried. TODO: review and decide if it's final.*/
548 void
base32_enc(uint8_t * dst,uint8_t * src)549 base32_enc (uint8_t *dst, uint8_t *src)
550 {
551 dst[ 0] = BASE32_ALPHABET[ (src[0] >> 3) ];
552 dst[ 1] = BASE32_ALPHABET[((src[0] << 2) | (src[1] >> 6)) & 31];
553 dst[ 2] = BASE32_ALPHABET[ (src[1] >> 1) & 31];
554 dst[ 3] = BASE32_ALPHABET[((src[1] << 4) | (src[2] >> 4)) & 31];
555 dst[ 4] = BASE32_ALPHABET[((src[2] << 1) | (src[3] >> 7)) & 31];
556 dst[ 5] = BASE32_ALPHABET[ (src[3] >> 2) & 31];
557 dst[ 6] = BASE32_ALPHABET[((src[3] << 3) | (src[4] >> 5)) & 31];
558 dst[ 7] = BASE32_ALPHABET[ src[4] & 31];
559
560 dst[ 8] = BASE32_ALPHABET[ (src[5] >> 3) ];
561 dst[ 9] = BASE32_ALPHABET[((src[5] << 2) | (src[6] >> 6)) & 31];
562 dst[10] = BASE32_ALPHABET[ (src[6] >> 1) & 31];
563 dst[11] = BASE32_ALPHABET[((src[6] << 4) | (src[7] >> 4)) & 31];
564 dst[12] = BASE32_ALPHABET[((src[7] << 1) | (src[8] >> 7)) & 31];
565 dst[13] = BASE32_ALPHABET[ (src[8] >> 2) & 31];
566 dst[14] = BASE32_ALPHABET[((src[8] << 3) | (src[9] >> 5)) & 31];
567 dst[15] = BASE32_ALPHABET[ src[9] & 31];
568
569 dst[16] = '\0';
570 }
571
572 /* Decode base32 16 character long 'src' into 10 byte long 'dst'. */
573 /* TODO: Revisit and review, would like to shrink it down a bit.
574 * However, it has to stay endian-safe and be fast. */
575 void
base32_dec(uint8_t * dst,uint8_t * src)576 base32_dec (uint8_t *dst, uint8_t *src)
577 {
578 uint8_t tmp[ONION_LENP1];
579 unsigned int i;
580
581 for (i = 0; i < 16; i++) {
582 if (src[i] >= 'a' && src[i] <= 'z') {
583 tmp[i] = src[i] - 'a';
584 } else {
585 if (src[i] >= '2' && src[i] <= '7')
586 tmp[i] = src[i] - '1' + ('z' - 'a');
587 else {
588 /* Bad character detected.
589 * This should not happen, but just in case
590 * we will replace it with 'z' character. */
591 tmp[i] = 26;
592 }
593 }
594 }
595 dst[0] = (tmp[ 0] << 3) | (tmp[1] >> 2);
596 dst[1] = (tmp[ 1] << 6) | (tmp[2] << 1) | (tmp[3] >> 4);
597 dst[2] = (tmp[ 3] << 4) | (tmp[4] >> 1);
598 dst[3] = (tmp[ 4] << 7) | (tmp[5] << 2) | (tmp[6] >> 3);
599 dst[4] = (tmp[ 6] << 5) | tmp[7];
600 dst[5] = (tmp[ 8] << 3) | (tmp[9] >> 2);
601 dst[6] = (tmp[ 9] << 6) | (tmp[10] << 1) | (tmp[11] >> 4);
602 dst[7] = (tmp[11] << 4) | (tmp[12] >> 1);
603 dst[8] = (tmp[12] << 7) | (tmp[13] << 2) | (tmp[14] >> 3);
604 dst[9] = (tmp[14] << 5) | tmp[15];
605 }
606
607 /* Print found .onion name and PEM formatted RSA key. */
608 void
printresult(RSA * rsa,uint8_t * target,uint8_t * actual)609 printresult(RSA *rsa, uint8_t *target, uint8_t *actual)
610 {
611 uint8_t *dst;
612 BUF_MEM *buf;
613 BIO *b;
614
615 b = BIO_new(BIO_s_mem());
616
617 PEM_write_bio_RSAPrivateKey(b, rsa, NULL, NULL, 0, NULL, NULL);
618 BIO_get_mem_ptr(b, &buf);
619 (void)BIO_set_close(b, BIO_NOCLOSE);
620 BIO_free(b);
621
622 if ((dst = (uint8_t *)malloc(buf->length + 1)) == NULL)
623 error("malloc(buf->length + 1) failed!\n");
624 memcpy(dst, buf->data, buf->length);
625
626 dst[buf->length] = '\0';
627
628 msg("Found a key for %s (%d) - %s.onion\n",
629 target, strnlen((char *)target, ONION_LENP1), actual);
630 printf("----------------------------------------------------------------\n");
631 printf("%s.onion\n", actual);
632 printf("%s\n", dst);
633 fflush(stdout);
634
635 BUF_MEM_free(buf);
636 free(dst);
637
638 if (cflag == 0) {
639 exit(0);
640 }
641 }
642
643 /* Generate .onion name from the RSA key. */
644 /* (using the same method as the official TOR client) */
645 void
onion_enc(uint8_t * onion,RSA * rsa)646 onion_enc(uint8_t *onion, RSA *rsa)
647 {
648 uint8_t *bufa, *bufb, digest[SHA_DIGEST_LENGTH];
649 signed int derlen;
650
651 if((derlen = i2d_RSAPublicKey(rsa, NULL)) < 0)
652 error("DER encoding failed!\n");
653
654 if ((bufa = bufb = (uint8_t *)malloc(derlen)) == NULL)
655 error("malloc(derlen) failed!\n");
656
657 if (i2d_RSAPublicKey(rsa, &bufb) != derlen)
658 error("DER encoding failed!\n");
659
660 SHA1(bufa, derlen, digest);
661 free(bufa);
662 base32_enc(onion, digest);
663 }
664
665 /* Compare function for qsort(3). */
666 signed int
compare(const void * a,const void * b)667 compare (const void *a, const void *b)
668 {
669 if (*((const uint64_t*)a) > *((const uint64_t*)b))
670 return 1;
671 if (*((const uint64_t*)a) < *((const uint64_t*)b))
672 return -1;
673 return 0;
674 }
675
676 /* Wordlist mode search. */
677 _Bool
fsearch(uint8_t * buf,uint8_t * onion)678 fsearch(uint8_t *buf, uint8_t *onion)
679 {
680 unsigned int i;
681 uint16_t ind;
682 uint64_t wrd;
683
684 if (!nflag)
685 for (i = 0; i < minlen; i++)
686 if (onion[i] < 'a')
687 return 0;
688
689 for (i = minlen; i <= maxlen; i++) {
690 if (!nflag && onion[i - 1] < 'a')
691 return 0;
692
693 zerobits(&ind, &wrd, buf, i);
694
695 if (tree[ind].branch != NULL &&
696 bsearch(&wrd, tree[ind].branch, tree[ind].count,
697 sizeof(tree[ind].branch[0]), &compare)) {
698 onion[i] = '\0';
699 return 1;
700 }
701 }
702 return 0;
703 }
704
705 /* Regex mode search. */
706 _Bool
rsearch(uint8_t * buf,uint8_t * onion)707 rsearch(__attribute__((unused)) uint8_t *buf, uint8_t *onion)
708 {
709 return !regexec(regex, (char *)onion, 0, 0, 0);
710 }
711
712 /* Fixed prefix mode search. */
713 _Bool
psearch(uint8_t * buf,uint8_t * onion)714 psearch(__attribute__((unused)) uint8_t *buf, uint8_t *onion)
715 {
716 return !memcmp(onion, prefix, prefixlen);
717 }
718
719 /* Zero unused bits, split 10 byte 'buffer' into 2 byte 'ind' and 8 byte 'word'. */
720 /* TODO: currently doing '1' fill instead of zeroes - decide if it's final. */
721 void
zerobits(uint16_t * ind,uint64_t * word,uint8_t * buffer,unsigned int length)722 zerobits(uint16_t * ind, uint64_t * word, uint8_t * buffer, unsigned int length)
723 {
724 uint8_t bufcopy[10];
725 unsigned int usedbytes, usedbits;
726
727 memcpy(bufcopy, buffer, 10);
728 usedbytes = length * 5 / 8;
729 usedbits = length * 5 % 8;
730
731 if (usedbits) {
732 /* Lets try '1' fill instead of zeroes.. */
733 /* bufcopy[usedbytes] &= (0xFFu << (8 - usedbits)); */
734 bufcopy[usedbytes] |= (0xFFu >> usedbits);
735 usedbytes++;
736 }
737
738 if (usedbytes < 10) {
739 /* Lets try '1' fill instead of zeroes.. */
740 /* memset(&bufcopy[usedbytes], 0, 10 - usedbytes); */
741 memset(&bufcopy[usedbytes], 0xFFu, 10 - usedbytes);
742 }
743
744 memcpy(ind, &bufcopy[0], 2);
745 memcpy(word, &bufcopy[2], 8);
746 }
747
748 /* Read arguments and set global variables. */
749 void
setoptions(int argc,char * argv[])750 setoptions(int argc, char *argv[])
751 {
752 int ch;
753
754 while ((ch = getopt(argc, argv, "cnvt:l:f:p:r:")) != -1)
755 switch (ch) {
756 case 'c':
757 cflag = 1;
758 break;
759 case 'n':
760 nflag = 1;
761 break;
762 case 'v':
763 vflag = 1;
764 msg = verbose;
765 break;
766 case 't':
767 threads = strtoul(optarg, NULL, 0);
768 if (threads < 1)
769 usage();
770 if (threads > MAX_THREADS)
771 threads = MAX_THREADS;
772 break;
773 case 'l':
774 minlen = strtoul(optarg, NULL, 0);
775 if (minlen < 8 || minlen > 16 || !strchr(optarg, '-'))
776 usage();
777 maxlen = strtoul(strchr(optarg, '-') + 1, NULL, 0);
778 if (maxlen < 8 || maxlen > 16 || minlen > maxlen)
779 usage();
780 break;
781 case 'f':
782 fflag = 1;
783 strncpy(fn, optarg, FILENAME_MAX);
784 search = fsearch;
785 break;
786 case 'p':
787 pflag = 1;
788 strncpy(prefix, optarg, ONION_LENP1);
789 minlen = maxlen = prefixlen = strnlen(prefix, ONION_LENP1);
790 if (prefixlen > 16 || prefixlen < 1)
791 usage();
792 for (unsigned int i = 0; i < prefixlen; i++) {
793 prefix[i] = tolower(prefix[i]);
794 if (!isalpha(prefix[i]) && (!nflag || !isdigit(prefix[i]) ||
795 prefix[i] < '2' || prefix[i] > '7'))
796 usage();
797 }
798 search = psearch;
799 break;
800 case 'r':
801 rflag = 1;
802 minlen = 1;
803 maxlen = 16;
804 if ((regex = (regex_t *)malloc(sizeof(regex_t))) == NULL)
805 error("malloc(sizeof(regex_t)) failed!\n");;
806
807 /* Do not use ICASE - too slow. */
808 if (regcomp(regex, optarg, REG_EXTENDED | REG_NOSUB))
809 error("Failed to compile regex expression!\n");
810 search = rsearch;
811 break;
812 default:
813 usage();
814 /* NOTREACHED */
815 }
816
817 if (fflag + rflag + pflag != 1)
818 usage();
819
820 msg("Verbose, ");
821 cflag ? msg("continuous, ") : msg("single result, ");
822 nflag ? msg("digits ok, ") : msg("no digits, ");
823 msg("%d threads, prefixes %d-%d characters long.\n",
824 threads, minlen, maxlen);
825 }
826
827 /* Print usage information and exit. */
828 void
usage(void)829 usage(void)
830 {
831 fprintf(stderr,
832 "Version: %s\n"
833 "\n"
834 "usage:\n"
835 "%s [-c] [-v] [-t count] ([-n] [-l min-max] -f filename) | (-r regex) | (-p prefix)\n"
836 " -v : verbose mode - print extra information to STDERR\n"
837 " -c : continue searching after the hash is found\n"
838 " -t count : number of threads to spawn default is one)\n"
839 " -l min-max : look for prefixes that are from 'min' to 'max' characters long\n"
840 " -n : Allow digits to be part of the prefix (affects wordlist mode only)\n"
841 " -f filename: name of the text file with a list of prefixes\n"
842 " -p prefix : single prefix to look for (1-16 characters long)\n"
843 " -r regex : search for a POSIX-style regular expression\n"
844 "\n"
845 "Examples:\n"
846 " %s -cvt4 -l8-12 -f wordlist.txt >> results.txt\n"
847 " %s -v -r '^test|^exam'\n"
848 " %s -ct5 -p test\n\n",
849 VERSION, __progname, __progname, __progname, __progname);
850
851 fprintf(stderr,
852 " base32 alphabet allows letters [a-z] and digits [2-7]\n"
853 " Regex pattern examples:\n"
854 " xxx must contain 'xxx'\n"
855 " ^foo must begin with 'foo'\n"
856 " bar$ must end with 'bar'\n"
857 " b[aoeiu]r must have a vowel between 'b' and 'r'\n"
858 " '^ab|^cd' must begin with 'ab' or 'cd'\n"
859 " [a-z]{16} must contain letters only, no digits\n"
860 " ^dusk.*dawn$ must begin with 'dusk' and end with 'dawn'\n"
861 " [a-z2-7]{16} any name - will succeed after one iteration\n");
862
863 exit(1);
864 }
865
866 /* Spam STDERR with diagnostic messages... */
867 void
verbose(char * message,...)868 verbose(char *message, ...)
869 {
870 va_list ap;
871
872 va_start(ap, message);
873 vfprintf(stderr, message, ap);
874 va_end(ap);
875 fflush(stderr);
876 }
877
878 /* ...or be a very quiet thinker. */
879 void
normal(char * unused,...)880 normal(__attribute__((unused)) char *unused, ...)
881 {
882 }
883
884 /* Print error message and exit. */
885 /* (Not all Linuxes implement the err/errx functions properly.) */
886 void
error(char * message,...)887 error(char *message, ...)
888 {
889 va_list ap;
890
891 va_start(ap, message);
892 fprintf(stderr, "ERROR: ");
893 vfprintf(stderr, message, ap);
894 va_end(ap);
895 exit(1);
896 }
897
898