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

1 files changed, 29 insertions, 4 deletions

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 <model>\tSelect model (or ? to list them)\n");
     printf("  -l/--search <method>\tTry to find the keysig (implies -e)\n");
+    printf("  -t/--threads <nr>\tSpecify number of threads to find the keysig\n");
     printf("  -a/--kas <kas>\tForce KAS\n");
     printf("  -k/--key <key>\tForce key\n");
     printf("  -s/--sig <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();
         }