From 9303e4cbbf6a1160d6f1e55992ea370ab2122847 Mon Sep 17 00:00:00 2001 From: `Orum <> Date: Sat, 20 Mar 2010 17:34:11 -0400 Subject: [PATCH] shallot v0.0.3 from taswebqlseworuhc.onion. --- CHANGELOG | 7 +++++++ Makefile | 10 +++++----- README | 31 ++++++++++++++++------------- src/config.h | 0 src/defines.h | 14 ++++++------- src/error.c | 3 ++- src/linux.c | 25 +----------------------- src/linux.h | 24 ++++++++++++++++++++++- src/math.c | 34 ++++++++++++++++++++++++++++++++ src/math.h | 3 +++ src/print.c | 30 +++++++++++++++++++++------- src/shallot.c | 10 +++++++--- src/thread.c | 63 ++++++++++++++++++++++++++++++++--------------------------- src/thread.h | 2 +- 14 files changed, 163 insertions(+), 93 deletions(-) delete mode 100644 src/config.h diff --git a/CHANGELOG b/CHANGELOG index 8e02878..ac89421 100644 --- a/CHANGELOG +++ b/CHANGELOG @@ -1,3 +1,10 @@ +Changed from shallot-0.0.2 to shallot-0.0.3: + +* Fixed some memory leaks. +* More efficient use of memory. +* Added '-o' option to optimize prime size for SHA-1 hashing. + + Changed from shallot-0.0.1 to shallot-0.0.2: * Corrected some things in the README. diff --git a/Makefile b/Makefile index 41cb356..9e4b29c 100644 --- a/Makefile +++ b/Makefile @@ -3,18 +3,18 @@ all: gcc -O3 -Wall -I/usr/local/include -c src/math.c -o src/math.o gcc -O3 -Wall -I/usr/local/include -c src/error.c -o src/error.o - gcc -O3 -Wall -I/usr/local/include -c src/print.c -o src/print.o gcc -O3 -Wall -I/usr/local/include -c src/linux.c -o src/linux.o + gcc -O3 -Wall -I/usr/local/include -c src/print.c -o src/print.o gcc -O3 -Wall -I/usr/local/include -c src/thread.c -o src/thread.o gcc -O3 -Wall -I/usr/local/include -c src/shallot.c -o src/shallot.o - gcc -O3 -Wall -L/usr/local/lib -pthread -lm -lpthread -lssl -lcrypto -o shallot src/math.o src/error.o src/print.o src/linux.o src/thread.o src/shallot.o + gcc -O3 -Wall -L/usr/local/lib -pthread -lm -lpthread -lssl -lcrypto -o shallot src/math.o src/error.o src/linux.o src/print.o src/thread.o src/shallot.o debug: gcc -g -O3 -Wall -I/usr/local/include -c src/math.c -o src/math.o gcc -g -O3 -Wall -I/usr/local/include -c src/error.c -o src/error.o - gcc -g -O3 -Wall -I/usr/local/include -c src/print.c -o src/print.o gcc -g -O3 -Wall -I/usr/local/include -c src/linux.c -o src/linux.o + gcc -g -O3 -Wall -I/usr/local/include -c src/print.c -o src/print.o gcc -g -O3 -Wall -I/usr/local/include -c src/thread.c -o src/thread.o gcc -g -O3 -Wall -I/usr/local/include -c src/shallot.c -o src/shallot.o - gcc -g -O3 -Wall -L/usr/local/lib -pthread -lm -lpthread -lssl -lcrypto -o shallot src/math.o src/error.o src/print.o src/linux.o src/thread.o src/shallot.o + gcc -g -O3 -Wall -L/usr/local/lib -pthread -lm -lpthread -lssl -lcrypto -o shallot src/math.o src/error.o src/linux.o src/print.o src/thread.o src/shallot.o clean: - rm -f shallot src/math.o src/error.o src/print.o src/linux.o src/thread.o src/shallot.o + rm -f shallot src/math.o src/error.o src/linux.o src/print.o src/thread.o src/shallot.o diff --git a/README b/README index a4a920b..4b51524 100644 --- a/README +++ b/README @@ -1,5 +1,5 @@ --------------------------------------------------------------------- - shallot 0.0.2 + shallot 0.0.3 --------------------------------------------------------------------- CONTENT @@ -42,15 +42,16 @@ expression patterns. >> example: create private key for test*.onion: $ ./shallot -Usage: shallot [-dmpv] [-f ] [-t count] [-e limit] pattern +Usage: shallot [-dmopv] [-f ] [-t count] [-e limit] pattern -d : Daemonize (requires -f) - -m : Monitor mode (incompatible with -d/-v) + -m : Monitor mode (incompatible with -f/-v) + -o : Optimize RSA key size to improve SHA-1 hashing speed -p : Print 'pattern' help and exit (requires pattern) -v : Verbose mode (debugging) -f : Write output to -t count : Forces exactly count threads to be spawned -e limit : Manually define the limit for e -Version: 0.0.2 +Version: 0.0.3 $ ./shallot -p foo base32 alphabet allows letters [a-z] and digits [2-7] @@ -104,16 +105,16 @@ SHA1 hash, Torland would be in serious trouble. The speed of the worker() loop can be divided in: -+------------------------------------+ -| function(s) | CPU consumption | -|------------------+-----------------| -| Copy SHA-1 hash | 1.5% | -| Endian swap 'e' | 0.1% | -| Hash 'e' | 67.9% | -| B32-encode hash | 21.9% | -| Regex comparison | 8.6% | -+------------------------------------+ - *** This is approximate. YMMV *** ++-------------------------+ +| Function | CPU usage | +|-------------+-----------| +| Copy CTX | 1.5% | +| Endian swap | 0.1% | +| Hash | 67.9% | +| B32-encode | 21.9% | +| Regex eval | 8.6% | ++-------------------------+ + *** YMMV. *** On my 1.5GHz x86-machine, I get about 500k hashes/sec. +---------------------------------------------+ @@ -128,6 +129,8 @@ On my 1.5GHz x86-machine, I get about 500k hashes/sec. | 7 | 32^7 = 32g | 1 day | | 8 | 32^8 = 1t | 25 days | | 9 | 32^9 = 32t | 2.5 years | +. . . . +. . . . | 16 | 32^16 = 1y | too long | +---------------------------------------------+ diff --git a/src/config.h b/src/config.h deleted file mode 100644 index e69de29..0000000 diff --git a/src/defines.h b/src/defines.h index da0bb76..8f2bb0f 100644 --- a/src/defines.h +++ b/src/defines.h @@ -4,7 +4,7 @@ #include "config.h" // our ever-important version string -#define VERSION "0.0.2" +#define VERSION "0.0.3-alpha" // default values #define DEFAULT_THREADS 1 // not used on anything but unknown systems @@ -16,17 +16,15 @@ #define REGEX_COMP_LMAX 0x40 #define SHA1_DIGEST_LEN 20 #define RSA_KEYS_BITLEN 0x400 +#define RSA_OPTM_BITLEN 0x380 // remember to subtract the length of e (in bits) // be sure to keep these constants in sync if you change them! #define RSA_PK_EXPONENT 0x10001ull #define RSA_PK_E_LENGTH 3 #define RSA_EXP_DER_LEN 0x8C -#define RSA_REL_DER_LEN 0x89 // RSA_EXP_DER_LEN - RSA_PK_E_LENGTH - // TODO: will gcc optimize constants w/o this? -#define RSA_ADD_DER_OFF 0x02 // don't ask... -#define SHA_REL_CTX_LEN 40 // 10 * sizeof(SHA_LONG) - // TODO: will gcc optimize constants w/o this? +#define RSA_OPT_DER_LEN 0x77 +#define RSA_ADD_DER_OFF 2 // don't ask... +#define SHA_REL_CTX_LEN 10 * sizeof(SHA_LONG) -#define BASE32_NUM_BITS SHA1_DIGEST_LEN/2*8 #define BASE32_ONIONLEN SHA1_DIGEST_LEN/2*8/5+1 #define BASE32_ALPHABET "abcdefghijklmnopqrstuvwxyz234567" @@ -39,7 +37,7 @@ #define CPUINFO_PATH "/proc/cpuinfo" #define CPUINFO_PROC_STR "processor" #define CPUINFO_PROC_STR_LEN 9 // don't include trailing NULL - // constant sanity checking + // sanity checking for constants #if CPUINFO_BUF_SIZE < 0x100 #error CPUINFO_BUFFER_SIZE set too small. Please make it bigger. #elif CPUINFO_BUF_SIZE > 0x7FFF diff --git a/src/error.c b/src/error.c index f9f34c8..af64fbc 100644 --- a/src/error.c +++ b/src/error.c @@ -9,9 +9,10 @@ // help - how to use this stuff void usage(void) { - printf("Usage: shallot [-dmpv] [-f ] [-t count] [-e limit] pattern\n" + printf("Usage: shallot [-dmopv] [-f ] [-t count] [-e limit] pattern\n" " -d : Daemonize (requires -f)\n" " -m : Monitor mode (incompatible with -f/-v)\n" + " -o : Optimize RSA key size to improve SHA-1 hashing speed\n" " -p : Print 'pattern' help and exit (requires pattern)\n" " -v : Verbose mode (debugging)\n" " -f : Write output to \n" diff --git a/src/linux.c b/src/linux.c index bba9269..22d1ff8 100644 --- a/src/linux.c +++ b/src/linux.c @@ -2,32 +2,9 @@ #include "linux.h" -#if defined(LINUX_PORT) || defined(OSX) || defined(GENERIC) +#ifdef LINUX_PORT #include "defines.h" - -#if defined(OSX) || defined(GENERIC) -#include -#else -#include -#include -#endif - -// why must glibc suck? -#if BYTE_ORDER == BIG_ENDIAN -#warning Compiling for a BIG_ENDIAN system. -#define htobe64(x) (x) -#elif BYTE_ORDER == LITTLE_ENDIAN -#warning Compiling for a LITTLE_ENDIAN system. -uint64_t htobe64(uint64_t x) { - return ((uint64_t)htonl(x) << 32) | htonl(x >> 32); -} -#else - #error Sell your PDP. -#endif -#endif // defined(LINUX_PORT) || defined(OSX) - -#ifdef LINUX_PORT #include // Linux specific stuff (damn this is ugly code. blame linus.) diff --git a/src/linux.h b/src/linux.h index f646ae7..8d797da 100644 --- a/src/linux.h +++ b/src/linux.h @@ -4,12 +4,34 @@ #include "config.h" #if defined(LINUX_PORT) || defined(OSX) || defined(GENERIC) + #include -uint64_t htobe64(uint64_t x); + +#if defined(OSX) || defined(GENERIC) + #include +#else + #include + #include +#endif + +#if BYTE_ORDER == BIG_ENDIAN + #warning Compiling for a BIG_ENDIAN system. + #define htobe64(x) (x) + #define htobe16(x) (x) + +#elif BYTE_ORDER == LITTLE_ENDIAN + #warning Compiling for a LITTLE_ENDIAN system. + #define htobe64(x) (((uint64_t)htonl(x) << 32) | htonl(x >> 32)) + #define htobe16(x) htons(x) + +#else + #error Sell your PDP. #endif #ifdef LINUX_PORT uint8_t parse_cpuinfo(char *buf, uint16_t avail, uint16_t *used); #endif +#endif // defined(LINUX_PORT) || defined(OSX) || defined(GENERIC) + #endif diff --git a/src/math.c b/src/math.c index 9b58ba2..ffe163e 100644 --- a/src/math.c +++ b/src/math.c @@ -1,6 +1,7 @@ // custom math routines for shallot #include "math.h" +#include "defines.h" void int_pow(uint32_t base, uint8_t pwr, uint64_t *out) { // integer pow() *out = (uint64_t)base; @@ -19,6 +20,39 @@ uint8_t BN_lcm(BIGNUM *r, BIGNUM *a, BIGNUM *b, BIGNUM *gcd, BN_CTX *ctx) { return 1; } +// wraps RSA key generation, DER encoding, and initial SHA-1 hashing +RSA *easygen(uint16_t num, uint8_t len, uint8_t *der, uint8_t edl, + SHA_CTX *ctx) { + uint8_t der_len; + RSA *rsa; + + for(;;) { // ugly, I know, but better than using goto imho + rsa = RSA_generate_key(num, 3, NULL, NULL); + + if(!rsa) // if key generation fails (no [p]rng seed?) + return rsa; + + // encode RSA key in X.690 DER format + uint8_t *tmp = der; + der_len = i2d_RSAPublicKey(rsa, &tmp); + + if(der_len == edl - len + 1) + break; // encoded key was the correct size, keep going + + RSA_free(rsa); // encoded key was the wrong size, try again + } + + // adjust for the actual size of e + der[RSA_ADD_DER_OFF] += len - 1; + der[der_len - 2] += len - 1; + + // and prepare our hash context + SHA1_Init(ctx); + SHA1_Update(ctx, der, der_len - 1); + + return rsa; +} + uint8_t sane_key(RSA *rsa) { // checks sanity of a RSA key (PKCS#1 v2.1) uint8_t sane = 1; diff --git a/src/math.h b/src/math.h index fe83e05..6ad4af6 100644 --- a/src/math.h +++ b/src/math.h @@ -22,9 +22,12 @@ #include #include #include +#include void int_pow(uint32_t base, uint8_t pwr, uint64_t *out); uint8_t BN_lcm(BIGNUM *r, BIGNUM *a, BIGNUM *b, BIGNUM *gcd, BN_CTX *ctx); +RSA *easygen(uint16_t num, uint8_t len, uint8_t *der, uint8_t edl, + SHA_CTX *ctx); uint8_t sane_key(RSA *rsa); #endif diff --git a/src/print.c b/src/print.c index 85180fd..8411ca1 100644 --- a/src/print.c +++ b/src/print.c @@ -10,15 +10,31 @@ #include #include +// endian crap for htobe16() [only needed +// for base32_onion which should be moved] { +#include // OpenBSD needs this included before sys/endian.h + +#if defined(LINUX_PORT) || defined(OSX) || defined(GENERIC) + #include "linux.h" +#else + #include // OpenBSD needs this early on too + #include +#endif +// } + +// TODO: Move to math.c? void base32_onion(char *dst, unsigned char *src) { // base32 encode hash - uint16_t i, bit, v, u; - for(i = 0, bit = 0; bit < BASE32_NUM_BITS; ++i, bit += 5) { - v = ((uint8_t)src[bit/8]) << 8; - if(bit+5 < BASE32_NUM_BITS) v += (uint8_t)src[(bit/8)+1]; - u = (v >> (11-(bit%8))) & 0x1F; - dst[i] = BASE32_ALPHABET[u]; + uint8_t byte = 0, // dst location + offset = 0; // bit offset + for(; byte < BASE32_ONIONLEN; offset += 5) { + if(offset > 7) { + offset -= 8; + src++; + } + dst[byte++] = BASE32_ALPHABET[(htobe16(*(uint16_t*)src) >> (11-offset)) + & (uint16_t)0x001F]; } - dst[i] = '\0'; + dst[byte] = '\0'; } void print_onion(char *onion) { // pretty print hash diff --git a/src/shallot.c b/src/shallot.c index b9a8909..4fbf9b1 100644 --- a/src/shallot.c +++ b/src/shallot.c @@ -67,7 +67,7 @@ int main(int argc, char *argv[]) { // onions are fun, here we go usage(); // set up our initial values - uint8_t daemon = 0; + uint8_t daemon = 0, optimum = 0; uint32_t threads = 1, x = 1; char *file = 0; elim = DEFAULT_E_LIMIT; @@ -143,6 +143,10 @@ int main(int argc, char *argv[]) { // onions are fun, here we go monitor = 1; break; } + case 'o': { // prime optimization + optimum = 1; + break; + } case 'p': { // pattern help pattern(); break; @@ -273,7 +277,7 @@ int main(int argc, char *argv[]) { // onions are fun, here we go if(verbose) printf("Additional thread spawning (%u)...\n", x); - if(pthread_create(&thrd, NULL, worker, NULL)) + if(pthread_create(&thrd, NULL, worker, &optimum)) error(X_THREAD_CREATE); } @@ -288,7 +292,7 @@ int main(int argc, char *argv[]) { // onions are fun, here we go "Main thread (ID: 0x%X) entering loop...\n", (uint32_t)pthread_self()); - worker(NULL); // use main thread for brute forcing too + worker(&optimum); // use main thread for brute forcing too if(pthread_self() != lucky_thread) { // be safe and avoid EDEADLK if(verbose) diff --git a/src/thread.c b/src/thread.c index 25836bd..59a4206 100644 --- a/src/thread.c +++ b/src/thread.c @@ -24,14 +24,14 @@ #include #include -void *worker(void *unused) { // life cycle of a cracking pthread - uint16_t len; +void *worker(void *params) { // life cycle of a cracking pthread uint64_t e_be; // storage for our "big endian" version of e uint8_t buf[SHA1_DIGEST_LEN], - der[RSA_KEYS_BITLEN]; + der[RSA_EXP_DER_LEN + 1], // TODO: is the size of this right? + optimum = *(uint8_t*)params; char onion[BASE32_ONIONLEN]; SHA_CTX hash, copy; - RSA *rsa = 0; + RSA *rsa; if(verbose) printf("Thread entering loop... (ID: 0x%X)\n", (uint32_t)pthread_self()); @@ -42,22 +42,20 @@ void *worker(void *unused) { // life cycle of a cracking pthread if(verbose) printf("Generating new key... (ID: 0x%X)\n", (uint32_t)pthread_self()); - rsa = RSA_generate_key(RSA_KEYS_BITLEN, RSA_PK_EXPONENT, NULL, NULL); - if(!rsa) // if key generation fails (no prng seed?) - error(X_KEY_GEN_FAILS); + if(optimum) + rsa = easygen(RSA_OPTM_BITLEN - RSA_PK_E_LENGTH * 8, RSA_PK_E_LENGTH, + der, RSA_OPT_DER_LEN, &hash); + else + rsa = easygen(RSA_KEYS_BITLEN, RSA_PK_E_LENGTH, der, RSA_EXP_DER_LEN, + &hash); - uint8_t *tmp = der; - len = i2d_RSAPublicKey(rsa, &tmp); // convert RSA key to X.690 DER format - if(len != RSA_EXP_DER_LEN) // if we got an unexpected length... - continue; // ...try again + if(!rsa) // if key generation fails (no [p]rng seed?) + error(X_KEY_GEN_FAILS); uint8_t e_bytes = RSA_PK_E_LENGTH; // number of bytes e occupies - uint64_t e = RSA_PK_EXPONENT; // public exponent + uint64_t e = RSA_PK_EXPONENT; // public exponent uint64_t e_byte_thresh; - SHA1_Init(&hash); // TODO: move to a function (is that thread safe?) - SHA1_Update(&hash, der, RSA_REL_DER_LEN); - int_pow(2, e_bytes * 8, &e_byte_thresh); e_byte_thresh++; @@ -71,12 +69,12 @@ void *worker(void *unused) { // life cycle of a cracking pthread // convert e to big-endian format e_be = htobe64(e); - // compute SHA1 digest (majority of loop time spent here? time it!) + // compute SHA1 digest (majority of loop time spent here!) SHA1_Update(©, e_ptr, e_bytes); SHA1_Final(buf, ©); base32_onion(onion, buf); // base32 encode SHA1 digest - loop++; // keep track of our tries... + loop++; // keep track of our tries... if(!regexec(regex, onion, 0, 0, 0)) { // check for a match if(verbose) @@ -91,16 +89,16 @@ void *worker(void *unused) { // life cycle of a cracking pthread printf("\n"); // keep our printing pretty! if(!BN_bin2bn(e_ptr, e_bytes, rsa->e)) // store our e in the actual key - error(X_BIGNUM_FAILED); // and make sure it got there + error(X_BIGNUM_FAILED); // and make sure it got there - if(!sane_key(rsa)) // check our key + if(!sane_key(rsa)) // check our key error(X_YOURE_UNLUCKY); // bad key :( if(verbose) printf("Public exponent (e) is 0x%llX.\n", e); print_onion(onion); // print our domain - print_prkey(rsa); // and more importantly the key + print_prkey(rsa); // and more importantly the key RSA_free(rsa); // free up what's left @@ -118,21 +116,28 @@ void *worker(void *unused) { // life cycle of a cracking pthread int_pow(2, ++e_bytes * 8, &e_byte_thresh); e_byte_thresh++; - // play with our key structure (do not try this at home!) - der[RSA_ADD_DER_OFF]++; - der[RSA_REL_DER_LEN - 1]++; + if(optimum) { + RSA_free(rsa); + easygen(RSA_OPTM_BITLEN - e_bytes * 8, e_bytes, der, RSA_OPT_DER_LEN, + &hash); + + if(!rsa) + error(X_KEY_GEN_FAILS); + } else { + // play with our key structure (do not try this at home!) + der[RSA_ADD_DER_OFF]++; + der[RSA_EXP_DER_LEN - RSA_PK_E_LENGTH - 1]++; - // and our prebuilt hash - SHA1_Init(&hash); // TODO: move to a function (is that thread safe?) - SHA1_Update(&hash, der, RSA_REL_DER_LEN); + // and our prebuilt hash + SHA1_Init(&hash); // TODO: move to a function + SHA1_Update(&hash, der, RSA_EXP_DER_LEN - RSA_PK_E_LENGTH); + } e_ptr--; // and move the pointer back } } - } - - if(rsa) // let our other threads free their (now useless) stuff RSA_free(rsa); + } if(verbose) printf("Thread exiting loop... (ID: 0x%X)\n", (uint32_t)pthread_self()); diff --git a/src/thread.h b/src/thread.h index 10f5ea7..3cd245d 100644 --- a/src/thread.h +++ b/src/thread.h @@ -1,7 +1,7 @@ #ifndef THREAD_H #define THREAD_H -void *worker(void *unused); +void *worker(void *params); void *monitor_proc(void *unused); #endif -- 2.11.4.GIT