From 37f95f67fec2b2460903ffa5255b1beeba1731fd Mon Sep 17 00:00:00 2001 From: Amaury Pouly Date: Thu, 27 Oct 2016 23:06:16 +0200 Subject: nwztools/upgtools: rewrite keysig brute force search The new search has two new features: - it takes advantage of the fact that DES keys are only 56-bit long (and not 64) - it is now multithreaded As a proof of concept, I ran it on the A10 series firmware upgrade and was able to find the key in a few seconds using 4 threads. The search is still limited to ascii hex passwords (seems to work on all devices I have tried thus far). Change-Id: Ied080286d2bbdc493a6ceaecaaadba802b429666 --- utils/nwztools/upgtools/Makefile | 2 +- utils/nwztools/upgtools/keysig_search.c | 344 ++++++++++++++++++++++++-------- utils/nwztools/upgtools/keysig_search.h | 10 +- utils/nwztools/upgtools/mg.cpp | 13 +- utils/nwztools/upgtools/misc.c | 1 - utils/nwztools/upgtools/misc.h | 2 +- utils/nwztools/upgtools/upgtool.c | 33 ++- 7 files changed, 299 insertions(+), 106 deletions(-) diff --git a/utils/nwztools/upgtools/Makefile b/utils/nwztools/upgtools/Makefile index ad83c0e4c6..35d5bfabff 100644 --- a/utils/nwztools/upgtools/Makefile +++ b/utils/nwztools/upgtools/Makefile @@ -5,7 +5,7 @@ LD=g++ PROFILE= CFLAGS=-g $(PROFILE) -std=c99 -W -Wall $(DEFINES) `pkg-config --cflags openssl` `pkg-config --cflags libcrypto++` CXXFLAGS=-g $(PROFILE) -W -Wall $(DEFINES) `pkg-config --cflags openssl` `pkg-config --cflags libcrypto++` -LDFLAGS=$(PROFILE) `pkg-config --libs openssl` `pkg-config --libs libcrypto++` -lcrypt +LDFLAGS=$(PROFILE) `pkg-config --libs openssl` `pkg-config --libs libcrypto++` -lcrypt -lpthread BINS=upgtool all: $(BINS) diff --git a/utils/nwztools/upgtools/keysig_search.c b/utils/nwztools/upgtools/keysig_search.c index 7652efa233..2740dc1461 100644 --- a/utils/nwztools/upgtools/keysig_search.c +++ b/utils/nwztools/upgtools/keysig_search.c @@ -23,6 +23,118 @@ #include "mg.h" #include #include +#include +#include + +/** Generic search code */ + +/* The generator sends chunks to the workers. The exact type of chunks depends + * on the method used. */ +static struct +{ + pthread_mutex_t mutex; /* mutex for the whole structure */ + pthread_cond_t avail_cond; /* condition to signal available or stop */ + pthread_cond_t req_cond; /* condition to signal request or stop */ + bool stop; /* if true, stop searcg */ + void *chunk; /* pointer to chunk (NULL if not available) */ + size_t chunk_sz; /* chunk size */ +}g_producer; + +/* init producer */ +static void producer_init(void) +{ + pthread_cond_init(&g_producer.avail_cond, NULL); + pthread_cond_init(&g_producer.req_cond, NULL); + pthread_mutex_init(&g_producer.mutex, NULL); + g_producer.stop = false; + g_producer.chunk = NULL; + g_producer.chunk_sz = 0; +} + +/* consumer get: called by worker to get a new chunk, return NULL to stop */ +static void *consumer_get(size_t *sz) +{ + pthread_mutex_lock(&g_producer.mutex); + /* loop until stop or new chunk */ + while(true) + { + /* stop if requested */ + if(g_producer.stop) + { + pthread_mutex_unlock(&g_producer.mutex); + return NULL; + } + if(g_producer.chunk) + break; + /* request a new chunk */ + pthread_cond_signal(&g_producer.req_cond); + /* wait for availability */ + pthread_cond_wait(&g_producer.avail_cond, &g_producer.mutex); + } + void *c = g_producer.chunk; + if(sz) + *sz = g_producer.chunk_sz; + g_producer.chunk = NULL; + pthread_mutex_unlock(&g_producer.mutex); + /* request a new chunk, so that if other consumers are waiting, the producer + * will also wake them up */ + pthread_cond_signal(&g_producer.req_cond); + return c; +} + +/* stop: called by worker to stop the search */ +static void consumer_stop(void) +{ + pthread_mutex_lock(&g_producer.mutex); + /* set stop */ + g_producer.stop = true; + /* wake up everyone */ + pthread_cond_broadcast(&g_producer.req_cond); + pthread_cond_broadcast(&g_producer.avail_cond); + pthread_mutex_unlock(&g_producer.mutex); +} + +/* producer yield: called by generator to give a new chunk, return true to stop */ +static bool producer_yield(void *chunk, size_t sz) +{ + pthread_mutex_lock(&g_producer.mutex); + /* wait until stop or request */ + while(true) + { + /* stop if requested */ + if(g_producer.stop) + { + pthread_mutex_unlock(&g_producer.mutex); + return true; + } + /* if the chunk is empty, fill it */ + if(g_producer.chunk == NULL) + break; + /* otherwise wait for request */ + pthread_cond_wait(&g_producer.req_cond, &g_producer.mutex); + } + g_producer.chunk = malloc(sz); + memcpy(g_producer.chunk, chunk, sz); + g_producer.chunk_sz = sz; + /* signal availability */ + pthread_cond_signal(&g_producer.avail_cond); + pthread_mutex_unlock(&g_producer.mutex); + return false; +} + +static void producer_stop(void) +{ + pthread_mutex_lock(&g_producer.mutex); + /* if we are not already stopping and there is a chunk still waiting to + * be consumed, wait until next request */ + if(!g_producer.stop && g_producer.chunk) + pthread_cond_wait(&g_producer.req_cond, &g_producer.mutex); + /* set stop */ + g_producer.stop = true; + /* wake up everyone */ + pthread_cond_broadcast(&g_producer.avail_cond); + pthread_mutex_unlock(&g_producer.mutex); +} /* Key search methods * @@ -41,16 +153,18 @@ * towards very unbalanced strings (only digits or only letters). */ -static uint8_t g_cipher[8]; -static keysig_notify_fn_t g_notify; -static uint8_t g_key[8]; -static void *g_user; +static struct +{ + pthread_mutex_t mutex; + uint8_t *enc_buf; + size_t enc_buf_sz; + bool found_keysig; + uint8_t key[NWZ_KEY_SIZE]; /* result */ + uint8_t sig[NWZ_SIG_SIZE]; /* result */ +}g_keysig_search; + static bool is_hex[256]; static bool is_init = false; -static uint64_t g_tot_count; -static uint64_t g_cur_count; -static int g_last_percent; -static int g_last_subpercent; static void keysig_search_init() { @@ -71,105 +185,169 @@ static inline bool is_full_ascii(uint8_t *arr) return true; } -static inline bool check_stupid() +struct upg_header_t { - uint8_t res[8]; - // display progress - g_cur_count++; - int percent = (g_cur_count * 100ULL) / g_tot_count; - int subpercent = ((g_cur_count * 1000ULL) / g_tot_count) % 10; - if(percent != g_last_percent) - { - cprintf(RED, "%d%%", percent); - fflush(stdout); - g_last_subpercent = 0; - } - if(subpercent != g_last_subpercent) + uint8_t sig[NWZ_SIG_SIZE]; + uint32_t nr_files; + uint32_t pad; // make sure structure size is a multiple of 8 +} __attribute__((packed)); + +static bool check_key(uint8_t key[NWZ_KEY_SIZE]) +{ + struct upg_header_t hdr; + mg_decrypt_fw(g_keysig_search.enc_buf, sizeof(hdr.sig), (void *)&hdr, key); + if(is_full_ascii(hdr.sig)) { - cprintf(WHITE, "."); - fflush(stdout); + /* the signature looks correct, so decrypt the header futher to be sure */ + mg_decrypt_fw(g_keysig_search.enc_buf, sizeof(hdr), (void *)&hdr, key); + /* we expect the number of files to be small and the padding to be 0 */ + if(hdr.nr_files == 0 || hdr.nr_files > 10 || hdr.pad != 0) + return false; + cprintf(RED, " Found key: %.8s (sig=%.8s, nr_files=%u)\n", key, hdr.sig, (unsigned)hdr.nr_files); + pthread_mutex_lock(&g_keysig_search.mutex); + g_keysig_search.found_keysig = true; + memcpy(g_keysig_search.key, key, NWZ_KEY_SIZE); + memcpy(g_keysig_search.sig, hdr.sig, NWZ_SIG_SIZE); + pthread_mutex_unlock(&g_keysig_search.mutex); + consumer_stop(); + return true; } - g_last_percent = percent; - g_last_subpercent = subpercent; - - mg_decrypt_fw(g_cipher, 8, res, g_key); - if(is_full_ascii(res)) - return g_notify(g_user, g_key, res); return false; } -static bool search_stupid_rec(int rem_digit, int rem_letter, int pos) +/** Hex search */ + +struct hex_chunk_t { - if(pos == 8) - return check_stupid(); - if(rem_digit > 0) + uint8_t key[NWZ_KEY_SIZE]; /* partially pre-filled key */ + int pos; + int rem_letters; + int rem_digits; +}; + +static bool hex_rec(bool producer, struct hex_chunk_t *ch) +{ + /* we list the first 4 pos in generator, and remaining 4 in workers */ + if(producer && ch->pos == 4) + { + //printf("yield(%.8s,%d,%d,%d)\n", ch->key, ch->pos, ch->rem_digits, ch->rem_letters); + return producer_yield(ch, sizeof(struct hex_chunk_t)); + } + /* filled the key ? */ + if(!producer && ch->pos == NWZ_KEY_SIZE) + return check_key(ch->key); + /* list next possibilities + * + * NOTE (42) Since the cipher is DES, the key is actually 56-bit: the least + * significant bit of each byte is an (unused) parity bit. We thus only + * generate keys where the least significant bit is 0. */ + int p = ch->pos++; + if(ch->rem_digits > 0) { - for(int i = '0'; i <= '9'; i++) + ch->rem_digits--; + /* NOTE (42) */ + for(int i = '0'; i <= '9'; i += 2) { - g_key[pos] = i; - if(search_stupid_rec(rem_digit - 1, rem_letter, pos + 1)) + ch->key[p] = i; + if(hex_rec(producer, ch)) return true; } + ch->rem_digits++; } - if(rem_letter > 0) + if(ch->rem_letters > 0) { - for(int i = 'a' - 1; i <= 'f'; i++) + ch->rem_letters--; + /* NOTE (42) */ + for(int i = 'a'; i <= 'f'; i += 2) { - g_key[pos] = i; - if(search_stupid_rec(rem_digit, rem_letter - 1, pos + 1)) + ch->key[p] = i; + if(hex_rec(producer, ch)) return true; } + ch->rem_letters++; } + ch->pos--; return false; } -static bool search_stupid(int rem_digit, int rem_letter) +static void *hex_worker(void *arg) { - cprintf(WHITE, "\n Looking for keys with "); - cprintf(RED, "%d", rem_digit); - cprintf(WHITE, " digits and "); - cprintf(RED, "%d", rem_letter); - cprintf(WHITE, " letters..."); - fflush(stdout); - return search_stupid_rec(rem_digit, rem_letter, 0); + (void) arg; + while(true) + { + struct hex_chunk_t *ch = consumer_get(NULL); + if(ch == NULL) + break; + hex_rec(false, ch); + } + return NULL; } -bool keysig_search_ascii_stupid(uint8_t *cipher, keysig_notify_fn_t notify, void *user) +static bool hex_producer_list(int nr_digits, int nr_letters) { - keysig_search_init(); - memcpy(g_cipher, cipher, 8); - g_notify = notify; - g_user = user; - // compute number of possibilities - g_cur_count = 0; - g_tot_count = 1; - g_last_percent = -1; - for(int i = 0; i < 8; i++) - g_tot_count *= 16ULL; - cprintf(WHITE, " Search space:"); - cprintf(RED, " %llu", (unsigned long long)g_tot_count); + struct hex_chunk_t ch; + cprintf(BLUE, " Listing keys with %d letters and %d digits\n", nr_letters, + nr_digits); + memset(ch.key, ' ', 8); + ch.pos = 0; + ch.rem_letters = nr_letters; + ch.rem_digits = nr_digits; + return hex_rec(true, &ch); +} + +void *hex_producer(void *arg) +{ + (void) arg; // sorted by probability: - bool ret = search_stupid(5, 3) // 5 digits, 3 letters: 0.281632 - || search_stupid(6, 2) // 6 digits, 2 letters: 0.234693 - || search_stupid(4, 4) // 4 digits, 4 letters: 0.211224 - || search_stupid(7, 1) // 7 digits, 1 letters: 0.111759 - || search_stupid(3, 5) // 3 digits, 5 letters: 0.101388 - || search_stupid(2, 6) // 2 digits, 6 letters: 0.030416 - || search_stupid(8, 0) // 8 digits, 0 letters: 0.023283 - || search_stupid(1, 7) // 1 digits, 7 letters: 0.005214 - || search_stupid(0, 8);// 0 digits, 8 letters: 0.000391 - cprintf(OFF, "\n"); - return ret; + bool stop = hex_producer_list(5, 3) // 5 digits, 3 letters: 0.281632 + || hex_producer_list(6, 2) // 6 digits, 2 letters: 0.234693 + || hex_producer_list(4, 4) // 4 digits, 4 letters: 0.211224 + || hex_producer_list(7, 1) // 7 digits, 1 letters: 0.111759 + || hex_producer_list(3, 5) // 3 digits, 5 letters: 0.101388 + || hex_producer_list(2, 6) // 2 digits, 6 letters: 0.030416 + || hex_producer_list(8, 0) // 8 digits, 0 letters: 0.023283 + || hex_producer_list(1, 7) // 1 digits, 7 letters: 0.005214 + || hex_producer_list(0, 8);// 0 digits, 8 letters: 0.000391 + if(!stop) + producer_stop(); + return NULL; } -bool keysig_search_ascii_brute(uint8_t *cipher, keysig_notify_fn_t notify, void *user) +typedef void *(*routine_t)(void *); + +bool keysig_search(int method, uint8_t *enc_buf, size_t buf_sz, + keysig_notify_fn_t notify, void *user, int nr_threads) { - (void) cipher; - (void) notify; - (void) user; + /* init producer */ + producer_init(); + /* init search */ keysig_search_init(); - cprintf(RED, "Unimplemented\n"); - return false; + pthread_mutex_init(&g_keysig_search.mutex, NULL); + g_keysig_search.enc_buf = enc_buf; + g_keysig_search.enc_buf_sz = buf_sz; + g_keysig_search.found_keysig = false; + /* get methods */ + routine_t worker_fn = NULL; + routine_t producer_fn = NULL; + if(method == KEYSIG_SEARCH_ASCII_HEX) + { + worker_fn = hex_worker; + producer_fn = hex_producer; + } + /* create workers */ + pthread_t *worker = malloc(sizeof(pthread_t) * nr_threads); + pthread_t producer; + for(int i = 0; i < nr_threads; i++) + pthread_create(&worker[i], NULL, worker_fn, NULL); + pthread_create(&producer, NULL, producer_fn, NULL); + /* wait for all threads */ + pthread_join(producer, NULL); + for(int i = 0; i < nr_threads; i++) + pthread_join(worker[i], NULL); + free(worker); + if(g_keysig_search.found_keysig) + notify(user, g_keysig_search.key, g_keysig_search.sig); + return g_keysig_search.found_keysig; } struct keysig_search_desc_t keysig_search_desc[KEYSIG_SEARCH_LAST] = @@ -177,19 +355,11 @@ struct keysig_search_desc_t keysig_search_desc[KEYSIG_SEARCH_LAST] = [KEYSIG_SEARCH_NONE] = { .name = "none", - .fn = NULL, .comment = "don't use", }, - [KEYSIG_SEARCH_ASCII_STUPID] = + [KEYSIG_SEARCH_ASCII_HEX] = { .name = "ascii-hex", - .fn = keysig_search_ascii_stupid, .comment = "Try to find an hexadecimal ascii string keysig" }, - [KEYSIG_SEARCH_ASCII_BRUTE] = - { - .name = "ascii-brute", - .fn = keysig_search_ascii_brute, - .comment = "Brute force all ASCII keys" - }, }; diff --git a/utils/nwztools/upgtools/keysig_search.h b/utils/nwztools/upgtools/keysig_search.h index 9009a73284..f419e2621c 100644 --- a/utils/nwztools/upgtools/keysig_search.h +++ b/utils/nwztools/upgtools/keysig_search.h @@ -23,30 +23,30 @@ #include #include +#include #include "fwp.h" enum keysig_search_method_t { KEYSIG_SEARCH_NONE = 0, KEYSIG_SEARCH_FIRST, - KEYSIG_SEARCH_ASCII_STUPID = KEYSIG_SEARCH_FIRST, - KEYSIG_SEARCH_ASCII_BRUTE, + KEYSIG_SEARCH_ASCII_HEX = KEYSIG_SEARCH_FIRST, KEYSIG_SEARCH_LAST }; /* notify returns true if the key seems ok */ typedef bool (*keysig_notify_fn_t)(void *user, uint8_t key[NWZ_KEY_SIZE], uint8_t sig[NWZ_SIG_SIZE]); -/* returns true if a key was accepted by notify */ -typedef bool (*keysig_search_fn_t)(uint8_t *cipher, keysig_notify_fn_t notify, void *user); struct keysig_search_desc_t { const char *name; const char *comment; - keysig_search_fn_t fn; }; struct keysig_search_desc_t keysig_search_desc[KEYSIG_SEARCH_LAST]; +bool keysig_search(int method, uint8_t *enc_buf, size_t buf_sz, + keysig_notify_fn_t notify, void *user, int nr_threads); + #endif /* __keysig_search_h__ */ diff --git a/utils/nwztools/upgtools/mg.cpp b/utils/nwztools/upgtools/mg.cpp index 21659ff3cf..f02b67375a 100644 --- a/utils/nwztools/upgtools/mg.cpp +++ b/utils/nwztools/upgtools/mg.cpp @@ -28,24 +28,23 @@ using namespace CryptoPP; namespace { - ECB_Mode< DES >::Decryption g_dec; - ECB_Mode< DES >::Encryption g_enc; - inline int dec_des_ecb(void *in, int size, void *out, uint8_t *key) { + ECB_Mode< DES >::Decryption dec; if(size % 8) return 42; - g_dec.SetKey(key, 8); - g_dec.ProcessData((byte*)out, (byte*)in, size); + dec.SetKey(key, 8); + dec.ProcessData((byte*)out, (byte*)in, size); return 0; } inline int enc_des_ecb(void *in, int size, void *out, uint8_t *key) { + ECB_Mode< DES >::Encryption enc; if(size % 8) return 42; - g_enc.SetKey(key, 8); - g_enc.ProcessData((byte*)out, (byte*)in, size); + enc.SetKey(key, 8); + enc.ProcessData((byte*)out, (byte*)in, size); return 0; } } diff --git a/utils/nwztools/upgtools/misc.c b/utils/nwztools/upgtools/misc.c index 00832cd585..108235e7fd 100644 --- a/utils/nwztools/upgtools/misc.c +++ b/utils/nwztools/upgtools/misc.c @@ -31,7 +31,6 @@ char RED[] = { 0x1b, 0x5b, 0x31, 0x3b, '3', '1', 0x6d, '\0' }; char GREEN[] = { 0x1b, 0x5b, 0x31, 0x3b, '3', '2', 0x6d, '\0' }; char YELLOW[] = { 0x1b, 0x5b, 0x31, 0x3b, '3', '3', 0x6d, '\0' }; char BLUE[] = { 0x1b, 0x5b, 0x31, 0x3b, '3', '4', 0x6d, '\0' }; -char WHITE[] = { 0x1b, 0x5b, 0x31, 0x3b, '3', '7', 0x6d, '\0' }; static bool g_color_enable = true; diff --git a/utils/nwztools/upgtools/misc.h b/utils/nwztools/upgtools/misc.h index 4e8294f1ee..96666a2eff 100644 --- a/utils/nwztools/upgtools/misc.h +++ b/utils/nwztools/upgtools/misc.h @@ -34,7 +34,7 @@ typedef char color_t[]; -extern color_t OFF, GREY, RED, GREEN, YELLOW, BLUE, WHITE; +extern color_t OFF, GREY, RED, GREEN, YELLOW, BLUE; void *xmalloc(size_t s); void color(color_t c); void enable_color(bool enable); diff --git a/utils/nwztools/upgtools/upgtool.c b/utils/nwztools/upgtools/upgtool.c index 065cede63c..3a8cf6174b 100644 --- a/utils/nwztools/upgtools/upgtool.c +++ b/utils/nwztools/upgtools/upgtool.c @@ -47,6 +47,7 @@ static int g_model_index = -1; static char *g_kas = NULL; static char *g_key = NULL; static char *g_sig = NULL; +static int g_nr_threads = 1; enum keysig_search_method_t g_keysig_search = KEYSIG_SEARCH_NONE; @@ -74,6 +75,18 @@ struct nwz_model_t char *sig; }; +/** Firmware format + * + * The firmware starts with the MD5 hash of the entire file (except the MD5 hash + * itself of course). This is used to check that the file was not corrupted. + * The remaining of the file is encrypted (using DES) with the model key. The + * encrypted part starts with a header containing the model signature and the + * number of files. Since the header is encrypted, decrypting the header with + * the key and finding the right signature serves to authenticate the firmware. + * The header is followed by N entries (where N is the number of files) giving + * the offset, within the file, and size of each file. Note that the files in + * the firmware have no name. */ + struct upg_md5_t { uint8_t md5[16]; @@ -81,7 +94,7 @@ struct upg_md5_t struct upg_header_t { - char sig[NWZ_SIG_SIZE]; + uint8_t sig[NWZ_SIG_SIZE]; uint32_t nr_files; uint32_t pad; // make sure structure size is a multiple of 8 } __attribute__((packed)); @@ -166,6 +179,7 @@ struct nwz_model_t g_model_list[] = /* The following keys were obtained by brute forcing firmware upgrades, * someone with a device needs to confirm that they work */ { "nw-a82x", HAS_KEY | HAS_SIG, "", "4df06482", "07fa0b6e" }, + { "nwz-a1x", HAS_KEY | HAS_SIG, "", "ec2888e2", "f62ced8a" }, }; static int digit_value(char c) @@ -286,7 +300,8 @@ static int get_key_and_sig(bool is_extract, void *encrypted_hdr) { cprintf(BLUE, "keysig Search\n"); cprintf_field(" Method: ", "%s\n", keysig_search_desc[g_keysig_search].name); - bool ok = keysig_search_desc[g_keysig_search].fn(encrypted_hdr, &upg_notify_keysig, keysig); + bool ok = keysig_search(g_keysig_search, encrypted_hdr, 8, + &upg_notify_keysig, keysig, g_nr_threads); cprintf(GREEN, " Result: "); cprintf(ok ? YELLOW : RED, "%s\n", ok ? "Key found" : "No key found"); if(!ok) @@ -576,6 +591,7 @@ static void usage(void) printf(" -c/--no-color\t\tDisable color output\n"); printf(" -m/--model \tSelect model (or ? to list them)\n"); printf(" -l/--search \tTry to find the keysig (implies -e)\n"); + printf(" -t/--threads \tSpecify number of threads to find the keysig\n"); printf(" -a/--kas \tForce KAS\n"); printf(" -k/--key \tForce key\n"); printf(" -s/--sig \tForce sig\n"); @@ -594,7 +610,7 @@ int main(int argc, char **argv) if(argc <= 1) usage(); - + while(1) { static struct option long_options[] = @@ -610,10 +626,11 @@ int main(int argc, char **argv) {"sig", required_argument, 0, 's'}, {"extract", no_argument, 0, 'e'}, {"create", no_argument, 0 ,'c'}, + {"threads", required_argument, 0, 't'}, {0, 0, 0, 0} }; - int c = getopt_long(argc, argv, "?dnfo:m:l:a:k:s:ec", long_options, NULL); + int c = getopt_long(argc, argv, "?dnfo:m:l:a:k:s:ect:", long_options, NULL); if(c == -1) break; switch(c) @@ -665,6 +682,14 @@ int main(int argc, char **argv) case 'c': create = true; break; + case 't': + g_nr_threads = strtol(optarg, NULL, 0); + if(g_nr_threads < 1 || g_nr_threads > 128) + { + cprintf(GREY, "Invalid number of threads\n"); + return 1; + } + break; default: abort(); } -- cgit v1.2.3