Skip to content

Instantly share code, notes, and snippets.

@hellman

hellman/bin300.c

Last active Dec 10, 2015
Embed
What would you like to do?
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
You can’t perform that action at this time.