Here is a bit of code implementing the generalized birthday attack, that maybe some might find useful. I am not an incredibly proficient C-programmer and I have not checked for memory leaks in this code, since my computer does not have Valgrind (but at least #frees = #mallocs!). Nonetheless, it seems pretty fast on even larger instances.
It can be use as basis when implementing various algorithm such as Stern’s algorithm or the BKW algorithm.
If you find errors or improvements, feel free to post it in the comments.
//////////////////////////////////////////////////////////////////////////////// // Carl Löndahl, 2013 // www.grocid.net //////////////////////////////////////////////////////////////////////////////// #include <stdio.h> #include <stdint.h> #include <stdlib.h> #include <inttypes.h> #define BITS_IN_WORD 5 #define TOTAL_ELEMENT_LENGTH 10 #define NUMBER_OF_ELEMENTS_IN_BLOCK 32 #define NUMBER_OF_BLOCKS (1<<BITS_IN_WORD) #define MASK (NUMBER_OF_BLOCKS-1); #define ITERATIONS 4 //////////////////////////////////////////////////////////////////////////////////////////// typedef struct element { uint64_t content[TOTAL_ELEMENT_LENGTH]; } element_t; inline void print_binary(uint64_t word) { uint32_t s; for (s = 0; s < BITS_IN_WORD; ++s) printf("%d", (uint8_t)((word>>(BITS_IN_WORD-1-s)) & 1)); printf(" "); } inline void random_fill(element_t *target) { uint32_t s; for (s = 0; s < TOTAL_ELEMENT_LENGTH; ++s) { target->content[s] = rand() & MASK; } } //////////////////////////////////////////////////////////////////////////////////////////// int main (int argc, char const *argv[]) { // counting variables uint32_t s, t, q, p; // indexing_block gives which element block should index the element uint32_t indexing_block = 0, to_table, from_table, block_size; uint64_t index; element_t *block[2], *target_block, *from_block; // to keep track of the number of elements in each block uint32_t occupied[2][NUMBER_OF_BLOCKS]; uint32_t block_index[NUMBER_OF_BLOCKS]; uint32_t target_occupied; // allocate the blocks from which we iterate back-and-forth ))<>(( block[0] = malloc(NUMBER_OF_BLOCKS*NUMBER_OF_ELEMENTS_IN_BLOCK*sizeof(element_t)); block[1] = malloc(NUMBER_OF_BLOCKS*NUMBER_OF_ELEMENTS_IN_BLOCK*sizeof(element_t)); // cache offsets and init+reset sizes for(s = 0; s < NUMBER_OF_BLOCKS; ++s) { block_index[s] = NUMBER_OF_ELEMENTS_IN_BLOCK*s; occupied[0][s] = NUMBER_OF_ELEMENTS_IN_BLOCK; occupied[1][s] = 0; } // fill storage with (truly) random junk for(s = 0; s < NUMBER_OF_BLOCKS*NUMBER_OF_ELEMENTS_IN_BLOCK; ++s) { random_fill(block[0]+s); } //////////////////////////////////////////////////////////////////////////////////////////// // perform this [ITERATIONS] many times. for (indexing_block = 0; indexing_block < ITERATIONS; ++indexing_block) { // determine which block to be the target block to_table = (indexing_block & 1) ^ 1; from_table = (indexing_block & 1); // for each block in the table for (p = 0; p < NUMBER_OF_BLOCKS; ++p) { from_block = block[from_table] + block_index[p]; block_size = occupied[from_table][p]; // add all pairs in block for (s = 0; s < block_size; ++s) { for (t = s + 1; t < block_size; ++t) { // determine the target block index = from_block[s].content[indexing_block] ^ from_block[t].content[indexing_block]; // if there is free place in the target if (occupied[to_table][index] < NUMBER_OF_ELEMENTS_IN_BLOCK) { target_occupied = occupied[to_table][index]; target_block = block[to_table] + block_index[index]; // put the result of the pair in the target variable for (q = 0; q < TOTAL_ELEMENT_LENGTH; ++q) { target_block[target_occupied].content[q] = from_block[s].content[q] ^ from_block[t].content[q]; } // note the increase of elements occupied[to_table][index]++; } } } } // reset the from-block sizes for(s = 0; s < NUMBER_OF_BLOCKS; ++s) { occupied[from_table][s] = 0; } } //////////////////////////////////////////////////////////////////////////////////////////// free(block[0]); free(block[1]); return 0; }