utils/nwztools/upgtools/keysig_search.c

/***************************************************************************
 *             __________               __   ___.
 *   Open      \______   \ ____   ____ |  | _\_ |__   _______  ___
 *   Source     |       _//  _ \_/ ___\|  |/ /| __ \ /  _ \  \/  /
 *   Jukebox    |    |   (  <_> )  \___|    < | \_\ (  <_> > <  <
 *   Firmware   |____|_  /\____/ \___  >__|_ \|___  /\____/__/\_ \
 *                     \/            \/     \/    \/            \/
 * $Id$
 *
 * Copyright (C) 2012 Amaury Pouly
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 *
 * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY
 * KIND, either express or implied.
 *
 ****************************************************************************/
#include "keysig_search.h"
#include "misc.h"
#include "mg.h"
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <stdbool.h>

#define cprintf(col, ...) do {color(col); printf(__VA_ARGS__); }while(0)

/** 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
 *
 * This code tries to find the key and signature of a device using an upgrade
 * file. It more or less relies on brute force and makes the following assumptions.
 * It assumes the key and the signature are hexadecimal strings (it appears to be
 * true thus far). The code lists all possible keys and decrypts the first
 * 8 bytes of the file. If the decrypted signature happens to be an hex string,
 * the code reports the key and signature as potentially valid. Note that some
 * key/sig pairs may not be valid but since the likelyhood of decrypting a
 * random 8-byte sequence using an hex string key and to produce an hex string
 * is very small, there should be almost no false positive.
 *
 * Since the key is supposedly random, the code starts by looking at "balanced"
 * keys: keys with slightly more digits (0-9) than letters (a-f) and then moving
 * towards very unbalanced strings (only digits or only letters).
 */

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_alnum[256];
static bool is_init = false;

static void keysig_search_init()
{
    if(is_init) return;
    is_init = true;
    memset(is_hex, 0, sizeof(is_hex));
    for(int i = '0'; i <= '9'; i++)
    {
        is_alnum[i] = true;
        is_hex[i] = true;
    }
    for(int i = 'a'; i <= 'f'; i++)
        is_hex[i] = true;
    for(int i = 'A'; i <= 'F'; i++)
        is_hex[i] = true;
    for(int i = 'a'; i <= 'z'; i++)
        is_alnum[i] = true;
    for(int i = 'A'; i <= 'Z'; i++)
        is_alnum[i] = true;
}

static bool hex_validate_sig(uint8_t *arr)
{
    for(int i = 0; i < 8; i++)
        if(!is_hex[arr[i]])
            return false;
    return true;
}

static bool alnum_validate_sig(uint8_t *arr)
{
    for(int i = 0; i < 8; i++)
        if(!is_alnum[arr[i]])
            return false;
    return true;
}

struct upg_header_t
{
    uint8_t sig[NWZ_SIG_SIZE];
    uint32_t nr_files;
    uint32_t pad; // make sure structure size is a multiple of 8
} __attribute__((packed));

typedef bool (*sig_validate_fn_t)(uint8_t *key);

static bool check_key(uint8_t key[NWZ_KEY_SIZE], sig_validate_fn_t validate)
{
    struct upg_header_t hdr;
    mg_decrypt_fw(g_keysig_search.enc_buf, sizeof(hdr.sig), (void *)&hdr, key);
    if(validate(hdr.sig))
    {
        /* 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;
    }
    return false;
}

/** Hex search */

struct hex_chunk_t
{
    uint8_t key[NWZ_KEY_SIZE]; /* partially pre-filled key */
    bool upper_case; /* allow upper case in letters */
    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, hex_validate_sig);
    /* 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++;
    int step = (p % 2) ? 2 : 1; // skip significant bit at positions 1, 3, 5 and 7
    if(ch->rem_digits > 0)
    {
        ch->rem_digits--;
        /* NOTE (42) */
        for(int i = '0'; i <= '9'; i += step)
        {
            ch->key[p] = i;
            if(hex_rec(producer, ch))
                return true;
        }
        ch->rem_digits++;
    }
    if(ch->rem_letters > 0)
    {
        ch->rem_letters--;
        /* NOTE (42) */
        for(int i = 'a'; i <= 'f'; i += step)
        {
            ch->key[p] = i;
            if(hex_rec(producer, ch))
                return true;
        }
        if(ch->upper_case)
        {
            for(int i = 'A'; i <= 'F'; i += step)
            {
                ch->key[p] = i;
                if(hex_rec(producer, ch))
                    return true;
            }
        }
        ch->rem_letters++;
    }
    ch->pos--;
    return false;
}

static void *hex_worker(void *arg)
{
    (void) arg;
    while(true)
    {
        struct hex_chunk_t *ch = consumer_get(NULL);
        if(ch == NULL)
            break;
        hex_rec(false, ch);
    }
    return NULL;
}

static bool hex_producer_list(bool upper_case, int nr_digits, int nr_letters)
{
    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.upper_case = upper_case;
    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 stop = hex_producer_list(false, 5, 3) // 5 digits, 3 letters: 0.281632
        || hex_producer_list(false, 6, 2) // 6 digits, 2 letters: 0.234693
        || hex_producer_list(false, 4, 4) // 4 digits, 4 letters: 0.211224
        || hex_producer_list(false, 7, 1) // 7 digits, 1 letters: 0.111759
        || hex_producer_list(false, 3, 5) // 3 digits, 5 letters: 0.101388
        || hex_producer_list(false, 2, 6) // 2 digits, 6 letters: 0.030416
        || hex_producer_list(false, 8, 0) // 8 digits, 0 letters: 0.023283
        || hex_producer_list(false, 1, 7) // 1 digits, 7 letters: 0.005214
        || hex_producer_list(false, 0, 8);// 0 digits, 8 letters: 0.000391
    if(!stop)
        producer_stop();
    return NULL;
}

void *hex_producer_up(void *arg)
{
    (void) arg;
    // sorted by probability:
    // TODO sort
    bool stop = hex_producer_list(true, 5, 3) // 5 digits, 3 letters: 0.281632
        || hex_producer_list(true, 6, 2) // 6 digits, 2 letters: 0.234693
        || hex_producer_list(true, 4, 4) // 4 digits, 4 letters: 0.211224
        || hex_producer_list(true, 7, 1) // 7 digits, 1 letters: 0.111759
        || hex_producer_list(true, 3, 5) // 3 digits, 5 letters: 0.101388
        || hex_producer_list(true, 2, 6) // 2 digits, 6 letters: 0.030416
        || hex_producer_list(true, 8, 0) // 8 digits, 0 letters: 0.023283
        || hex_producer_list(true, 1, 7) // 1 digits, 7 letters: 0.005214
        || hex_producer_list(true, 0, 8);// 0 digits, 8 letters: 0.000391
    if(!stop)
        producer_stop();
    return NULL;
}

/** Alphanumeric search */

struct alnum_chunk_t
{
    uint8_t key[NWZ_KEY_SIZE]; /* partially pre-filled key */
    int pos;
};

static bool alnum_rec(bool producer, struct alnum_chunk_t *ch)
{
    /* we list the first 5 pos in generator, and remaining 3 in workers */
    if(producer && ch->pos == 4)
    {
        //printf("yield(%.8s,%d)\n", ch->key, ch->pos);
        return producer_yield(ch, sizeof(struct alnum_chunk_t));
    }
    /* filled the key ? */
    if(!producer && ch->pos == NWZ_KEY_SIZE)
        return check_key(ch->key, alnum_validate_sig);
    /* 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++;
    /* NOTE (42) */
    int step = (p % 2) ? 2 : 1; // skip significant bit at positions 1, 3, 5 and 7
    for(int i = '0'; i <= '9'; i += step)
    {
        ch->key[p] = i;
        if(alnum_rec(producer, ch))
            return true;
    }
    /* NOTE (42) */
    for(int i = 'a'; i <= 'z'; i += step)
    {
        ch->key[p] = i;
        if(alnum_rec(producer, ch))
            return true;
    }
    ch->pos--;
    return false;
}

static void *alnum_worker(void *arg)
{
    (void) arg;
    while(true)
    {
        struct alnum_chunk_t *ch = consumer_get(NULL);
        if(ch == NULL)
            break;
        alnum_rec(false, ch);
    }
    return NULL;
}

void *alnum_producer(void *arg)
{
    (void) arg;
    struct alnum_chunk_t ch;
    cprintf(BLUE, "    Listing alphanumeric keys\n");
    memset(ch.key, ' ', 8);
    ch.pos = 0;
    if(!alnum_rec(true, &ch))
        producer_stop();
    return NULL;
}

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)
{
    /* init producer */
    producer_init();
    /* init search */
    keysig_search_init();
    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_XDIGITS)
    {
        worker_fn = hex_worker;
        producer_fn = hex_producer;
    }
    else if(method == KEYSIG_SEARCH_XDIGITS_UP)
    {
        worker_fn = hex_worker;
        producer_fn = hex_producer_up;
    }
    else if(method == KEYSIG_SEARCH_ALNUM)
    {
        worker_fn = alnum_worker;
        producer_fn = alnum_producer;
    }
    else
    {
        printf("Invalid method\n");
        return false;
    }
    /* 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] =
{
    [KEYSIG_SEARCH_NONE] =
    {
        .name = "none",
        .comment = "don't use",
    },
    [KEYSIG_SEARCH_XDIGITS] =
    {
        .name = "xdigits",
        .comment = "Try to find an hexadecimal string keysig"
    },
    [KEYSIG_SEARCH_XDIGITS_UP] =
    {
        .name = "xdigits-up",
        .comment = "Try to find an hexadecimal string keysig, including upper case"
    },
    [KEYSIG_SEARCH_ALNUM] =
    {
        .name = "alnum",
        .comment = "Try to find an alphanumeric string keysig"
    },
};