path: root/lib/lib.c

#include "lib.h"

static const unsigned char base64_encode[] =
	"ABCDEFGHIJKLMNOPQRSTUVWXYZ"
	"abcdefghijklmnopqrstuvwxyz"
	"0123456789+/";


static const unsigned char hex_encode[] =
	"0123456789abcdef";



/**
 * teset wheter a bit on the given position is 1
 */
static int bit_on(char test, int bit)
{
	char tmp;
	tmp = 1 << bit;
	tmp = test & tmp;

	return (int) tmp;
}


/**
 * returns true if the given string contains only printable or whitespace
 * characters
 */
int isprintable(char *string, int length)
{
	int i;

	for(i=0;i<length;i++) {
		if(!(isprint(string[i]) || isspace(string[i]))) {
			return 0;
		}
	}

	return 1;
}


/*
 * task the first three characters of encode and tranform it into the coresponding
 * for bytes in base64 and stores it in result
*/
static void three_bytes_to_base64(char * encode, int bytes_to_print, char *result)
{
	unsigned char one, two, three, four;
	unsigned char tmp;
	char ret[4];
	
	// first six bits
	one = encode[0] >> 2;
	ret[0] = base64_encode[one];
	if(bytes_to_print-- > 0)
		result[0] = ret[0];
	// second six bits
	// two last bits of first byte
	tmp = encode[0] & 0x03;
	two = encode[1] >> 4;
	tmp = tmp << 4;
	two = tmp | two;
	ret[1] = base64_encode[two];
	if(bytes_to_print-- > 0)
		result[1] = ret[1];
	// second six bits
	// two last bits of first byte
	// third six bits
	tmp = encode[1] & 0x0F;
	tmp = tmp << 2;
	three = encode[2] & 0xC0;
	three = three >> 6;
	three = tmp | three;
	ret[2] = base64_encode[three];
	if(bytes_to_print-- > 0)
		result[2] = ret[2];
	// last six bit11s
	four = encode[2] & 0x3F;
	ret[3] = base64_encode[four];
	ret[4] = '\0';
	if(bytes_to_print-- > 0)
		result[3] = ret[3];
}

void print_char_bit(char print)
{
	int i;
	for(i=0;i<8;i++) {
		if (bit_on(print,i))
			printf("1");
		else
			printf("0");
	}
}
/**
 * Transform four base64 encoded characters back to three bytes
 */

const char decodeCharacterTable[256] = {
	-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1
	,-1,62,-1,-1,-1,63,52,53,54,55,56,57,58,59,60,61,-1,-1,-1,-1,-1,-1,-1,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21
	,22,23,24,25,-1,-1,-1,-1,-1,-1,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,-1,-1,-1,-1,-1,
	-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
	-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1
	,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
	-1,-1,-1
};


void decode_four_base64_byte(char *string1, char *result)
{
	char buf[4];

	// map the bytes back to the orginial bitmap
	// A = 0
	buf[0] = decodeCharacterTable[(int)string1[0]];
	buf[1] = decodeCharacterTable[(int)string1[1]];
	buf[2] = decodeCharacterTable[(int)string1[2]];
	buf[3] = decodeCharacterTable[(int)string1[3]];

	// first byte is first six bits of base64 one and 2 bit of base64 second
	result[0] = ((buf[0] << 2) & 0xFC) | ((buf[1] >> 4) & 0x03);

	// second byte 4 bits of second base64 + 4 bits of third base64
	result[1] = ((buf[1] << 4) & 0xF0) | ((buf[2] >> 2) & 0x0F);

	// third byte 2 bits of third base54 + 6 bits of fourth base64
	result[2] = ((buf[2] & 0x03) << 6) | (buf[3] & 0x3F);

}


int decode_base64(char *string1, char *result)
{
	int i, j, padding;
	
	for(i=0, j=0;i<strlen(string1);i += 4, j +=3) {
		decode_four_base64_byte(&string1[i], &result[j]);
	}

	// handle padding in the last four bytes
	i -= 4;

	for(padding=0;i<strlen(string1);i++) {
		if (string1[i] == '=')
			padding++;
	}

	result[j-padding] = '\0';

	return (j-padding);

}

static char string_to_hex_map[] = {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06,
				   0x07, 0x08, 0x09, 0x0A, 0x0B, 0x0C, 0x0D,
				   0x0E, 0x0F};
/*
 * This function converts the first char of a string into its corresponding 
 * hex value
 *
 * @return on Sucess return 0, if char is no valid hex value returns -1
 */
static int hex_char_to_bit(char toEncode)
{
	char encode;
	switch(toEncode) {
		case '0':
			encode = string_to_hex_map[0];
			break;
		case '1':
			encode = string_to_hex_map[1];
			break;
		case '2':
			encode = string_to_hex_map[2];
			break;
		case '3':
			encode = string_to_hex_map[3];
			break;
		case '4':
			encode = string_to_hex_map[4];
			break;
		case '5':
			encode = string_to_hex_map[5];
			break;
		case '6':
			encode = string_to_hex_map[6];
			break;
		case '7':
			encode = string_to_hex_map[7];
			break;
		case '8':
			encode = string_to_hex_map[8];
			break;
		case '9':
			encode = string_to_hex_map[9];
			break;
		case 'a':
			encode = string_to_hex_map[10];
			break;
		case 'b':
			encode = string_to_hex_map[11];
			break;
		case 'c':
			encode = string_to_hex_map[12];
			break;
		case 'd':
			encode = string_to_hex_map[13];
			break;
		case 'e':
			encode = string_to_hex_map[14];
			break;
		case 'f':
			encode = string_to_hex_map[15];
			break;
		default:
			return -1;
	}

	return encode;

}

/**
 * takes the first two hex characters of start and convert them to one byte 
 * with the coressponding value of the two hex chars
 */
static void two_char_hex(char *start, char *result)
{
	char first = hex_char_to_bit(start[0]);
	char second = hex_char_to_bit(start[1]);
	
	*result = first;
	*result = *result << 4;
	*result = *result | second;
}

/**
 * xor agianst a key. if the length of key is less than the length of
 * str1 than the key will be repeated
 * @param str1 string which should be xored agianst the given key
 * @param key 
 * @param result buffer where the result is stored
 */
void xor_string(char *str1, char *key, char *result, int length_key, int length_str1)
{
	int i, j;
	//int length_key = strlen(key);

	for(i=0, j=0;i<length_str1;i++,j++) {
		if (j >= length_key)
			j = 0;

		result[i] = str1[i] ^ key[j];
	}

	result[i] = '\0';
}


/**
 * transform the bytes in str1 into its correspond printable hex version
 * @param str1 binary strewam which should be converted
 * @param result buffer where the results should be stored
 * @param length legnth of str1 
 */
void hex_binary_to_string(char *str1, char *result, int length)
{
	int i, j, tmp = 0;

	for(i=0,j=0;i<length;i++, j+=2) {
		tmp = str1[i] & 0xF0;
		tmp = tmp >> 4;
		result[j] = hex_encode[tmp];
		tmp = str1[i] & 0x0F;
		result[j+1] = hex_encode[tmp];
	}

	result[j] = '\0';
}

/**
 * takes a  hex string and converts it to its correspond binary counterpart 
 */
int decode_hex_string(char *encode, char* result)
{
	int i;
	int length = strlen(encode);

	for(i = 0;i< length/2;i++)
		two_char_hex(&encode[i*2], &result[i]);

	return i;
}

/**
 * counts the frequent characters in a string an divide the number through the
 * total number of characters
 * @param string string where the frequent characters should be counted
 * @param length length of string
 */

static int frequent_histogramm_matchs(char *string, int length)
{
	int i;
	int hits = 0;
	char tmp;
	int number_frequent_characters[14] = { 0, 0, 0, 0, 0, 0, 0, 0 ,0 ,0 ,0 ,0, 0, 0};
	// frequent characters:
	// a c d e h i l m n o r s t u w
	double standard_frequencies[14] = { 8.1, 2.7, 4.2, 12.7, 6.0, 6.9, 4.0, 2.4, 6.7, 7.5, 5.9, 6.3, 9.0, 2.7 };

	// count frequent characters
	for(i=0;i<length;i++) {
		tmp = tolower(string[i]);	
		switch(tmp) {
			case 'a':
				number_frequent_characters[0]++;
				break;
			case 'c':
				number_frequent_characters[1]++;
				break;
			case 'd':
				number_frequent_characters[2]++;
				break;
			case 'e':
				number_frequent_characters[3]++;
				break;
			case 'h':
				number_frequent_characters[4]++;
				break;
			case 'i':
				number_frequent_characters[5]++;
				break;
			case 'l':
				number_frequent_characters[6]++;
				break;
			case 'm':
				number_frequent_characters[7]++;
				break;
			case 'n':
				number_frequent_characters[8]++;
				break;
			case 'o':
				number_frequent_characters[9]++;
				break;
			case 'r':
				number_frequent_characters[10]++;
				break;
			case 's':
				number_frequent_characters[11]++;
				break;
			case 't':
				number_frequent_characters[12]++;
				break;
			case 'u':
				number_frequent_characters[13]++;
				break;
		}
	}
	#define FREQ_AREA 0.7
	// compare frequncies with standard frequencies
	for(i=0;i<14;i++) {
		double freq =(double) ((double)number_frequent_characters[i]*100/(double)length);
		if((((standard_frequencies[i] * (1-FREQ_AREA) < freq)
			)&& ((standard_frequencies[i] * (1+FREQ_AREA)) > freq))) {
			hits++;
		}
	}
	return hits;
}

/**
 * encode the given string into base64 and stores it in result
 */

void encode_to_base64(char *encode, char *result)
{
	int length = strlen(encode);
	
	int rounds = length / 3;
	int bytes_last_round = length % 3;
	int i;

	for (i=0;i<rounds;i++) {
		three_bytes_to_base64(encode + i*3,4, &result[i*4]);
	}
	// in der letzen runde nicht mehr alle ausgeben
	// nur noch 3-leftover
	if (bytes_last_round > 0) {
		three_bytes_to_base64(encode + i*3, 1+bytes_last_round, &result[i*4]);

		for(i=0;i<(3-bytes_last_round);i++)
			result[i*4+(1+bytes_last_round)] = '=';
	}

}

/**
 * prints and base64 encoded string
 */
void print_base64_string(char *string)
{
	// after 76 charactes line break
	
}

/**
 * compute the hamming distance (number of different bits) of two string
 * @param string1 first string
 * @parma string2 second string
 * @return returns the hamming distance
 */
int hamming_distance_equal_length(char *string1, char *string2, int length)
{
	char tmp;
	int i, j;
	int hamming_distance = 0;

	for(i=0;i<length;i++) {
		tmp = string1[i] ^ string2[i];
		for(j = 0; j < 8; j++) {
			if (bit_on(tmp, j))
				hamming_distance++;
		}
	}
	return hamming_distance;
}

/**
 * test every byte on the string as key and returns the found keys
 */
char brute_force_single_byte_xor(char *string, int length, struct key_and_freq *ret)
{
	int i;
	char *xor_tmp;
	char single_byte_key;
	char key = 'A';
	int max_hits = 0;
	int tmp_hits = 0;

	xor_tmp = malloc(length+1);

//	printf("NEW STINGT TO BREAK\n");
	// test for every byte
	for(i=1;i<255;i++) {
		single_byte_key = (char) i;
		xor_string(string, &single_byte_key, xor_tmp, 1, length);
		
		// if string contains not printable characters it is not
		// the cleartext
		if (!isprintable(xor_tmp, length))
			continue;
		
		tmp_hits = frequent_histogramm_matchs(xor_tmp, length);

		if (tmp_hits > max_hits) {
			max_hits = tmp_hits;
			key = single_byte_key;
			//printf("Key: %c, hits: %i\n", key, max_hits);
		}
		
	}
	
	ret->key = key;
	ret->hits= max_hits;

	return key;
}


/**
 * reads a base64 an decode it
 * @param file path of the file
 * @param out writes file in this buffer, allocated by this method
 */
int read_base64_file(const char *file, char **out)
{
	char ch;
	FILE *fp;
	int file_size = 60;
	char *new_file_content;
	int file_pos = 0;

	fp = fopen(file, "r");

	if (fp == NULL) {
		printf("Error open file\n");
		exit(1);
	}
	
	*out = malloc(file_size);

	if (*out == NULL) {
		perror("out of memory");
		exit(1);
	}

	// read data and decode it from base64
	while ( (ch = fgetc(fp)) != EOF) {
		// ignore new lines as this is part of base64
		if (ch == '\n' || ch == '\r')
			continue;

		if (file_pos+1 >= file_size) {
			new_file_content = realloc(*out, (file_size+60));
			if (new_file_content != NULL) {
				*out = new_file_content;
				file_size += 60;
			}
			else {
				printf("error allocating memory\n");
				exit(1);
			}
		}
		(*out)[file_pos++] = ch;
	}
	return file_pos;

}