PHDays CTF Quals 2013 bin300 solution

bin300.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

#include <gmp.h>
#include <pthread.h>
#include <semaphore.h>

/*
Complile:
  gcc bin300.c -lgmp -lpthread -Ofast -o solve && time ./solve <num threads>
*/

// key:  {L2 bytes} {L1 bytes}
// L1 determines the size of the table
#define L1 4
#define L2 5
#define KS (L1 + L2)

// how large is map (fewer collisions -> faster, but more memory)
#define ITEMS_ALLOC 8

#define CHUNK_COUNT (1 << 24)
#define CHUNK_MASK (CHUNK_COUNT - 1)
#define MAX_ITEMS_INCREMENT 512

// how many locks (fewer locks - slower because of waitings)
#define LOCK_COUNT (1 << 20)
#define LOCK_MASK (LOCK_COUNT - 1)

#define Vdec "6192128262312421513644888506697421915171917575080330421897398651929773466194971539791158995262083381167771056580666419101167108372547406447696753234781064"

#define ITEM_MIN_SIZE 12
#define HASH_SIZE (ITEM_MIN_SIZE - L1)

struct item {
    char hash[HASH_SIZE];
    char part1[L1];
};

struct chunk {
    unsigned short count;
    unsigned short allocated;
    struct item *items;
};

struct chunk chunks[CHUNK_COUNT];
pthread_mutex_t locks[LOCK_COUNT];

sem_t working_threads;
unsigned int thread_id[62];

unsigned int was_pwned = 0;

// large numbers
mpz_t p, g, v, rep_g[L1], rep_gh[L2], rep_ig[L1], rep_igh[L2], mask;
mpz_t steps1[L1][3];
mpz_t steps2[L2][3];
mpz_t inv_steps1[L1][3];
mpz_t inv_steps2[L2][3];

// alphabet
int group_size[3] = {10, 26, 26};
char group_char[3][32] = {"0123456789", "ABCDEFGHIJKLMNOPQRSTUVWXYZ", "abcdefghijklmnopqrstuvwxyz"};

// res = pow(g, (1 << bit) * m, p)
void powm(mpz_t res, mpz_t some_g, unsigned bit, unsigned m) {
    mpz_set(res, g);

    int i;
    mpz_powm_ui(res, some_g, m, p);
    for (i = 0; i < bit; i++) {
        mpz_powm_ui(res, res, 2, p);
    }
    return;
}

// make some precomputations, so need only 1 mulmod per bruteforce step
void init() {
    int i, j;

    mpz_init(p);
    mpz_init(g);
    mpz_init(mask);
    mpz_init(v);

    mpz_set_str(p, "10018627425667944010192184374616954034932336288972070602267764174849233338727414964592990350312034463496546535924460513481267263055398790908691402854122123", 10);
    mpz_set_str(v, Vdec, 10);

    mpz_set_str(g, "7548218116432136940925610514648634474612691039131890951895054656437277296127635726026902728136306678987800886118938655787775411887815467753774352743068577", 10);


    unsigned char str_mask[128];

    // make repeated(<KS> <00 KS times>)
    bzero(str_mask, sizeof(str_mask));
    for (i = 0; i < 64; i += KS + 1) {
        str_mask[i] = KS;
    }
    mpz_import(mask, 64, 1, 1, 1, 0, str_mask);
    mpz_powm(mask, g, mask, p);

    // make pow(g, repeated(<KS> <00 ... 00> <00 ... 01 ... 00>), p) and inverses
    for (j = 0; j < L1; j++) {
        bzero(str_mask, sizeof(str_mask));
        for (i = KS - j; i < 64; i += KS + 1) {
            str_mask[i] = 1;
        }
        mpz_init(rep_g[j]);
        mpz_init(rep_ig[j]);

        mpz_import(rep_g[j], 64, 1, 1, 1, 0, str_mask);
        mpz_powm(rep_g[j], g, rep_g[j], p);
        mpz_invert(rep_ig[j], rep_g[j], p);
    }

    // make pow(g, repeated(<KS> <00 ... 01 ... 00> <00 ... 00>), p) and inverses
    for (j = 0; j < L2; j++) {
        bzero(str_mask, sizeof(str_mask));
        for (i = L2 - j; i < 64; i += KS + 1) {
            str_mask[i] = 1;
        }
        mpz_init(rep_gh[j]);
        mpz_init(rep_igh[j]);

        mpz_import(rep_gh[j], 64, 1, 1, 1, 0, str_mask);
        mpz_powm(rep_gh[j], g, rep_gh[j], p);
        mpz_invert(rep_igh[j], rep_gh[j], p);
    }

    // make pow(repeated_g, 1, p), pow(repeated_g, 'A'-'9', p), etc. (for jump between chars groups)
    for (j = 0; j < L1; j++) {
        mpz_init(steps1[j][0]);
        mpz_init(steps1[j][1]);
        mpz_init(steps1[j][2]);
        mpz_init(inv_steps1[j][0]);
        mpz_init(inv_steps1[j][1]);
        mpz_init(inv_steps1[j][2]);

        powm(steps1[j][0], rep_g[j], 0, 1);
        powm(steps1[j][1], rep_g[j], 0, 'A'-'9');
        powm(steps1[j][2], rep_g[j], 0, 'a'-'Z');
        powm(inv_steps1[j][0], rep_ig[j], 0, 1);
        powm(inv_steps1[j][1], rep_ig[j], 0, 'A'-'9');
        powm(inv_steps1[j][2], rep_ig[j], 0, 'a'-'Z');
    }

    // make pow(repeated_gh, 1, p), pow(repeated_gh, 'A'-'9', p), etc. (for jump between chars groups)
    for (j = 0; j < L2; j++) {
        mpz_init(steps2[j][0]);
        mpz_init(steps2[j][1]);
        mpz_init(steps2[j][2]);
        mpz_init(inv_steps2[j][0]);
        mpz_init(inv_steps2[j][1]);
        mpz_init(inv_steps2[j][2]);

        powm(steps2[j][0], rep_igh[j], 0, 1);
        powm(steps2[j][1], rep_igh[j], 0, 'A'-'9');
        powm(steps2[j][2], rep_igh[j], 0, 'a'-'Z');
        powm(inv_steps2[j][0], rep_gh[j], 0, 1);
        powm(inv_steps2[j][1], rep_gh[j], 0, 'A'-'9');
        powm(inv_steps2[j][2], rep_gh[j], 0, 'a'-'Z');

    }
}

void group_pos_by_id(int id, int *g, int *p) {
    if (id < 10) {
        *g = 0; *p = id;
        return;
    }
    id -= 10;
    if (id < 26) {
        *g = 1; *p = id;
        return;
    }
    id -= 26;
    *g = 2; *p = id;
}

void acc_init_1(mpz_t acc, int firstval) {
    int i, j;
    mpz_set(acc, mask);
    for (j = 0; j < firstval; j++) {
        mpz_mul(acc, acc, steps1[0][0]);
        mpz_mod(acc, acc, p);
    }
    for (i = 1; i < L1; i++) {
        for (j = 0; j < '0'; j++) {
            mpz_mul(acc, acc, steps1[i][0]);
            mpz_mod(acc, acc, p);
        }
    }
    return;
}

void acc_init_2(mpz_t acc, int firstval) {
    int i, j;
    mpz_set(acc, v);
    for (j = 0; j < firstval; j++) {
        mpz_mul(acc, acc, steps2[0][0]);
        mpz_mod(acc, acc, p);
    }
    for (i = 1; i < L2; i++) {
        for (j = 0; j < '0'; j++) {
            mpz_mul(acc, acc, steps2[i][0]);
            mpz_mod(acc, acc, p);
        }
    }
}

void check_func_1(int hash[16], char groups[], char positions[]) {
    unsigned int index = hash[0] & CHUNK_MASK;
    int i;

    if (pthread_mutex_lock(&locks[hash[0] & LOCK_MASK])) {
        perror("MUTEX LOCK");
        exit(1);
    }

    // CRITICAL SECTION - MODIFY chunks[index]
    unsigned int item_count = chunks[index].count;
    unsigned int new_count;
    if (item_count == chunks[index].allocated ) {
        new_count = (item_count <= MAX_ITEMS_INCREMENT) ? item_count * 2 : item_count + MAX_ITEMS_INCREMENT;
        struct item *p = calloc(new_count, sizeof(struct item));
        if (p == NULL) {
            printf("Can't malloc :(\n");
            perror("malloc");
            exit(0);
        }
        memcpy(p, chunks[index].items, sizeof(struct item) * item_count);
        chunks[index].allocated = new_count;

        free(chunks[index].items);
        chunks[index].items = p;
    }
    chunks[index].count++;
    memcpy(chunks[index].items[item_count].hash, (char *)&hash[1], HASH_SIZE);
    for (i = 0; i < L1; i++) {
        chunks[index].items[item_count].part1[i] = group_char[groups[i]][positions[i]];
    }

    pthread_mutex_unlock(&locks[hash[0] & LOCK_MASK]);
}

void check_func_2(int hash[16], char groups[], char positions[]) {
    unsigned int index = hash[0] & CHUNK_MASK;
    int i, j;

    unsigned int item_count = chunks[index].count;
    struct item * items = chunks[index].items;
    for (i = 0; i < item_count; i++) {
        if (!memcmp(items[i].hash, &hash[1], HASH_SIZE)) {
            printf("POSSIBLE: ");
            for (j = L2 - 1; j >= 0; j--) {
                printf("%c", group_char[groups[j]][positions[j]]);
            }
            for (j = L1 - 1; j >= 0; j--) {
                printf("%c", items[i].part1[j]);
            }
            printf("\n");
            was_pwned++;
        }
    }
}

void * do_bruteforce( int my_thread_id, int part_len, void (init_func(mpz_t, int)), void (check_func(int*, char*, char*)), mpz_t steps[][3], mpz_t inv_steps[][3] ) {
    int my_group, my_position;
    group_pos_by_id(my_thread_id, &my_group, &my_position);

    sem_wait(&working_threads);

    printf("I'm thread %d, group %d, position %d. My char is %c\n", my_thread_id, my_group, my_position, group_char[my_group][my_position]);

    // do
    char positions[KS];   // 0-9, 0-25, 0-25
    char groups[KS];    // 0 for 0-9;  1 for A-Z;  2 for a-z
    char direction[KS]; // 1 up,  -1 down

    int i, j;

    for (i = 0; i < part_len; i++) {
        positions[i] = 0;
        groups[i] = 0;
        direction[i] = 1;
    }
    positions[0] = my_position;
    groups[0] = my_group;

    mpz_t acc;
    mpz_init(acc);
    init_func(acc, group_char[my_group][my_position]);

    unsigned int hash[32];
    while (1) {
        size_t count;
        mpz_export(hash, &count, 1, 4, -1, 0, acc);

        check_func(hash, groups, positions);

        // iter
        int pos, group, dir;
        unsigned int index = 1;
        int add = 1;
        while (add) {
            if (index >= part_len) {
                printf("END Thread %d, group %d, position %d\n", my_thread_id, my_group, my_position);
                sem_post(&working_threads);
                return;
            }

            pos = positions[index];
            group = groups[index];
            dir = direction[index];

            // next char
            if (pos == 25 && group == 2 && dir == 1) {
                direction[index] = -1;
                index += 1;
                continue;
            }

            if (pos == 0 && group == 0 && dir == -1) {
                direction[index] = 1;
                index += 1;
                continue;
            }

            // next/prev group
            add = 0;

            positions[index] += dir; // 1 or -1

            if (positions[index] >= group_size[group]) {
                groups[index] += 1;
                positions[index] = 0;
                mpz_mul(acc, acc, steps[index][group + 1]); // new_group
                mpz_mod(acc, acc, p);
                break;
            }

            if (positions[index] == -1) {
                groups[index] -= 1;
                positions[index] = group_size[group - 1] - 1;
                mpz_mul(acc, acc, inv_steps[index][group]); // old_group
                mpz_mod(acc, acc, p);
                break;
            }

            // next/prev pos in same group
            if (dir == 1) {
                mpz_mul(acc, acc, steps[index][0]);
                mpz_mod(acc, acc, p);
                break;
            }
            else {
                mpz_mul(acc, acc, inv_steps[index][0]);
                mpz_mod(acc, acc, p);
                break;
            }
        }
    }
}

void * stage1(void *arg) {
    int my_thread_id = *(int*)arg;
    return do_bruteforce(my_thread_id, L1, acc_init_1, check_func_1, steps1, inv_steps1);
}

void * stage2(void *arg) {
    int my_thread_id = *(int*)arg;
    return do_bruteforce(my_thread_id, L2, acc_init_2, check_func_2, steps2, inv_steps2);
}

int main(int argc, char *argv[]) {
    pthread_t thread[62];
    unsigned int i, j, nthreads=8;

    if (argc == 2)
        nthreads = atoi(argv[1]);

    printf("Allocating hashmap...\n");
    for (i = 0; i < CHUNK_COUNT; i++) {
        chunks[i].items = calloc(ITEMS_ALLOC, sizeof(struct item));
        chunks[i].count = 0;
        chunks[i].allocated = ITEMS_ALLOC;
    }
    perror("malloc");

    printf("\nPrecomputing...\n");
    init();
    printf("Precomputations done\n");

    sem_init(&working_threads, 0, nthreads);

    printf("\nSTAGE1\n");
    for (i = 0; i < 62; i++) {
        thread_id[i] = i;
        int result = pthread_create(&thread[i], NULL, stage1, &thread_id[i]);
        if (result != 0) {
            perror("Can't start thread");
            return -1;
        }
    }
    for (i = 0; i < 62; i++) {
        pthread_join(thread[i], NULL);
    }

    printf("\nSTAGE2\n");
    for (i = 0; i < 62; i++) {
        thread_id[i] = i;
        int result = pthread_create(&thread[i], NULL, stage2, &thread_id[i]);
        if (result != 0) {
            perror("Can't start thread");
            return -1;
        }
    }
    for (i = 0; i < 62; i++) {
        pthread_join(thread[i], NULL);
    }

    printf("RESULT: WAS_PWNED: %d\n", was_pwned);
    return 0;
}