PHDays CTF Quals 2013 bin300 solution
#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; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment