A somewhat efficient collision table implementation

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;
}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s