From 4a9770b8ba9d86db12779f5ae00366bce60a42ad Mon Sep 17 00:00:00 2001
From: Benedict <benedict@0xb8000.de>
Date: Sat, 19 Mar 2016 13:44:55 +0100
Subject: completed task6 nearly completly

just a few characters are still wrong in the key.
freqencies analysis has to be made more comprehensive
---
 Makefile |   2 +-
 lib.c    | 204 ++++++++++++++++++++++++++++++++++++++++++---------------------
 lib.h    |  17 ++++--
 task2.c  |  15 ++---
 task4.c  |  26 ++++----
 task5.c  |   6 +-
 task6.c  | 122 +++++++++++++++++++++++++++++++-------
 test.sh  |   9 +++
 8 files changed, 281 insertions(+), 120 deletions(-)

diff --git a/Makefile b/Makefile
index 74ffb3c..4e825ff 100644
--- a/Makefile
+++ b/Makefile
@@ -1,6 +1,6 @@
 LIB=lib.c
 CC=gcc
-CFLAGS := -g $(CFLAGS) 
+CFLAGS := -g -Wall $(CFLAGS) 
 
 all: task1 task2 task4 task5 task6
 
diff --git a/lib.c b/lib.c
index 252deb2..fc07022 100644
--- a/lib.c
+++ b/lib.c
@@ -6,6 +6,7 @@ static const unsigned char base64_encode[] =
 	"abcdefghijklmnopqrstuvwxyz"
 	"0123456789+/";
 
+
 static const unsigned char hex_encode[] =
 	"0123456789abcdef";
 
@@ -19,7 +20,6 @@ static int bit_on(char test, int bit)
 	char tmp;
 	tmp = 1 << bit;
 	tmp = test & tmp;
-	tmp = tmp >> bit;
 
 	return (int) tmp;
 }
@@ -29,7 +29,7 @@ static int bit_on(char test, int bit)
  * returns true if the given string contains only printable or whitespace
  * characters
  */
-static int isprintable(char *string, int length)
+int isprintable(char *string, int length)
 {
 	int i;
 
@@ -86,41 +86,74 @@ static void three_bytes_to_base64(char * encode, int bytes_to_print, char *resul
 		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 one, two, three, tmp;
+	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
-	one = string1[0] << 2;
-	one = one & 0xFC;
-	tmp = string1[1] >> 4;
-	tmp = tmp & 0x03;
-	one = one | tmp;
+	result[0] = ((buf[0] << 2) & 0xFC) | ((buf[1] >> 4) & 0x03);
 
 	// second byte 4 bits of second base64 + 4 bits of third base64
-	two = string1[1] << 4;
-	tmp = string1[2] >> 2;
-	two = two | tmp;
+	result[1] = ((buf[1] << 4) & 0xF0) | ((buf[2] >> 2) & 0x0F);
 
 	// third byte 2 bits of third base54 + 6 bits of fourth base64
-	three = string1[2] << 6;
-	tmp =  string1[3];
-	three = three | tmp;
-	
-	printf("%c%c%c", one, two, three);
+	result[2] = ((buf[2] & 0x03) << 6) | (buf[3] & 0x3F);
+
 }
 
-void decode_base64(char *string1, char *result)
+
+int decode_base64(char *string1, char *result)
 {
-	int i;
+	int i, j, padding;
+	
+	for(i=0, j=0;i<strlen(string1);i += 4, j +=3) {
+		decode_four_base64_byte(&string1[i], &result[j]);
+	}
 
-	for(i=0;i<strlen(string1)-3;i++) {
-		decode_four_base64_byte(&string1[i*4], &result[i*3]);
+	// handle padding in the last four bytes
+	i -= 4;
+
+	for(padding=0;i<strlen(string1);i++) {
+		if (string1[i] == '=')
+			padding++;
 	}
-	// TODO handle = in base64 at the end
+
+	result[j-padding] = '\0';
+
+	return (j-padding);
+
 }
 
 static char string_to_hex_map[] = {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06,
@@ -237,18 +270,17 @@ void xor_string(char *str1, char *key, char *result, int length_key, int length_
  */
 void hex_binary_to_string(char *str1, char *result, int length)
 {
-	int i;
-	int tmp = 0;
+	int i, j, tmp = 0;
 
-	for(i=0;i<length/2;i++) {
+	for(i=0,j=0;i<length;i++, j+=2) {
 		tmp = str1[i] & 0xF0;
 		tmp = tmp >> 4;
-		result[i*2] = hex_encode[tmp];
+		result[j] = hex_encode[tmp];
 		tmp = str1[i] & 0x0F;
-		result[(i*2)+1] = hex_encode[tmp];
+		result[j+1] = hex_encode[tmp];
 	}
 
-	result[i*2] = '\0';
+	result[j] = '\0';
 }
 
 /**
@@ -270,30 +302,70 @@ int decode_hex_string(char *encode, char* result)
  * total number of characters
  * @param string string where the frequent characters should be counted
  * @param length length of string
- * @return number between 0 and 100 (percentage) of frequent characters
  */
 
-static int score_based_on_frequent_characters(char *string, int length)
+static int frequent_histogramm_matchs(char *string, int length)
 {
-	int number = 0;
 	int i;
+	int hits = 0;
 	char tmp;
+	int number_frequent_characters[10] = { 0, 0, 0, 0, 0, 0 ,0 ,0 ,0 ,0};
+	// a e h i n o r s t u
+	double standard_frequencies[10] = { 8.1, 12.7, 6.0, 6.9, 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]);	
-		if( tmp == 'e' || tmp == 'a' || tmp == 'i' || tmp == 'o'
-			|| tmp == 'u' )
-			number++;
+		switch(tmp) {
+			case 'a':
+				number_frequent_characters[0]++;
+				break;
+			case 'e':
+				number_frequent_characters[1]++;
+				break;
+			case 'h':
+				number_frequent_characters[2]++;
+				break;
+			case 'i':
+				number_frequent_characters[3]++;
+				break;
+			case 'n':
+				number_frequent_characters[4]++;
+				break;
+			case 'o':
+				number_frequent_characters[5]++;
+				break;
+			case 'r':
+				number_frequent_characters[6]++;
+				break;
+			case 's':
+				number_frequent_characters[7]++;
+				break;
+			case 't':
+				number_frequent_characters[8]++;
+				break;
+			case 'u':
+				number_frequent_characters[9]++;
+				break;
+		}
 	}
-
-	return ((number*100)/length);
+	#define FREQ_AREA 0.8
+	// compare frequncies with standard frequencies
+	for(i=0;i<10;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
  */
 
-int encode_to_base64(char *encode, char *result)
+void encode_to_base64(char *encode, char *result)
 {
 	int length = strlen(encode);
 	
@@ -318,7 +390,7 @@ int encode_to_base64(char *encode, char *result)
 /**
  * prints and base64 encoded string
  */
-int print_base64_string(char *string)
+void print_base64_string(char *string)
 {
 	// after 76 charactes line break
 	
@@ -330,59 +402,59 @@ int print_base64_string(char *string)
  * @parma string2 second string
  * @return returns the hamming distance
  */
-int hamming_distance_equal_length(char *string1, char *string2)
+int hamming_distance_equal_length(char *string1, char *string2, int length)
 {
 	char tmp;
 	int i, j;
 	int hamming_distance = 0;
 
-	for(i=0;i<strlen(string1);i++) {
+	for(i=0;i<length;i++) {
 		tmp = string1[i] ^ string2[i];
 		for(j = 0; j < 8; j++) {
-			if ( bit_on(tmp, j))
+			if (bit_on(tmp, j))
 				hamming_distance++;
 		}
 	}
 	return hamming_distance;
 }
 
-/**
- * returns true if the given strings may represent human language
- */
-int string_looks_like_it_is_human_language(char *string, int length)
-{
-	// string has to be printable and a score bigger than 20
-	// to be assumed to be human language
-	if (!isprintable(string, length))
-		return 0;
-	if (score_based_on_frequent_characters(string, length) < 20)
-		return 0;
-
-	return 1;
-}
-
 /**
  * test every byte on the string as key and returns the found keys
  */
-int brute_force_single_byte_xor(char *string, int length, char* keys)
+char brute_force_single_byte_xor(char *string, int length, struct key_and_freq *ret)
 {
-	int i, number_found_keys=0;
+	int i;
 	char *xor_tmp;
 	char single_byte_key;
-	
-	xor_tmp = malloc(length);
+	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_looks_like_it_is_human_language(xor_tmp, length)) {
-			keys[number_found_keys++] = single_byte_key;
-			printf("%s\n", xor_tmp);
+		
+		// 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);
 		}
+		
 	}
-	keys[number_found_keys] = '\0';
+	
+	ret->key = key;
+	ret->hits= max_hits;
 
-	return number_found_keys;
+	return key;
 }
-
-
diff --git a/lib.h b/lib.h
index a0986e7..3e2a309 100644
--- a/lib.h
+++ b/lib.h
@@ -7,16 +7,21 @@
 #include <stdlib.h>
 #include <ctype.h>
 
+struct key_and_freq {
+	char key;
+	int hits;
+};
 
+void print_char_bit(char);
 void xor_string(char *str1, char *key, char *result, int length_key, int length_str1);
 void hex_binary_to_string(char *str1, char *result, int length);
 int decode_hex_string(char *encode, char* result);
-int encode_to_base64(char *encode, char *result);
-void decode_base64(char *string1, char *result);
-int print_base64_string(char *string);
-int hamming_distance_equal_length(char *string1, char *string2);
-int brute_force_single_byte_xor(char *string, int length, char *keys);
-
+void encode_to_base64(char *encode, char *result);
+int decode_base64(char *string1, char *result);
+void print_base64_string(char *string);
+int hamming_distance_equal_length(char *string1, char *string2, int length);
+char brute_force_single_byte_xor(char *string, int length, struct key_and_freq *tmp);
+int isprintable(char *string, int length);
 
 
 #endif /* __CYRPTO_LIB__ */
diff --git a/task2.c b/task2.c
index b675244..1847103 100644
--- a/task2.c
+++ b/task2.c
@@ -6,16 +6,17 @@ int main(int argc, char**argv)
 	if (argc != 3)
 		return 1;
 	
-
-	char *xor_string_tmp = malloc(strlen(argv[1]));
-	char *result = malloc(strlen(argv[1]));
-	char *str1 = malloc(strlen(argv[1]));
-	char *str2 = malloc(strlen(argv[2]));
+	int length_arg_1 = strlen(argv[1]);
+	int length_arg_2 = strlen(argv[2]);
+	char *xor_string_tmp = malloc(length_arg_1+1);
+	char *result = malloc(length_arg_1*2+1);
+	char *str1 = malloc(length_arg_1+1);
+	char *str2 = malloc(length_arg_2+1);
 
 	decode_hex_string(argv[1], str1);
 	decode_hex_string(argv[2], str2);
-	xor_string(str1, str2, xor_string_tmp, strlen(argv[2]), strlen(argv[1]));
-	hex_binary_to_string(xor_string_tmp, result, strlen(argv[1]));
+	xor_string(str1, str2, xor_string_tmp, length_arg_2, length_arg_1);
+	hex_binary_to_string(xor_string_tmp, result, (length_arg_1/2));
 	printf("%s\n", result);
 
 	free(xor_string_tmp);
diff --git a/task4.c b/task4.c
index a1b7b28..11fab98 100644
--- a/task4.c
+++ b/task4.c
@@ -1,19 +1,17 @@
 
 #include "lib.h"
 
-void main() {
+int main() {
 	/** read the file */
 	FILE *fp;
-	int bytes_read;
 	int malloc_size = 62;
 	int line_number = 0;
 	int j;
+	char key;
 	char *string = malloc(malloc_size);
 	char *string2 = malloc(malloc_size);
 	char *cleartext = malloc(malloc_size);
-	char *keys = malloc(255);
-	char single_key;
-	int length;
+	struct key_and_freq tmp;
 
 	fp = fopen("4.txt", "r");
 
@@ -23,19 +21,17 @@ void main() {
 	}
 	
 	while (fscanf(fp, "%61c", string) != EOF) {
+		tmp.hits = 0;
 		j = decode_hex_string(string, string2);
-		length = brute_force_single_byte_xor(string2, j, keys);
-		if (length > 0) {
-			printf("line %i:\n", line_number);
-			for(j=0;j<length;j++) {
-				single_key = keys[j];
-				xor_string(string2, &single_key, cleartext, 1, 60);
-				printf("%s\n", cleartext);
-			}
-		}
+		key = brute_force_single_byte_xor(string2, j, &tmp);
+		xor_string(string2, &key, cleartext, 1, j);
+		if ((!isprintable(cleartext, j)) || (tmp.hits < 10))
+			continue;
+		
+		printf("%s", cleartext);
 		line_number++;
 	}
 
 	fclose(fp);
-
+	return 0;
 }
diff --git a/task5.c b/task5.c
index f110e30..15e4568 100644
--- a/task5.c
+++ b/task5.c
@@ -3,13 +3,13 @@
 /*
  * implements task 5 of set 1 of matanso challange
  */
-void main()
+int main()
 {
 	char *stanze = "Burning 'em, if you ain't quick and nimble\nI go crazy when I hear a cymbal";
 	
 	char *result = malloc(strlen(stanze));
-	char *printable = malloc(strlen(stanze)*5);
+	char *printable = malloc(strlen(stanze)*2+1);
 	xor_string(stanze, "ICE", result, 3, strlen(stanze));
-	hex_binary_to_string(result, printable, 2*strlen(stanze));
+	hex_binary_to_string(result, printable, strlen(stanze));
 	printf("%s\n", printable);
 }
diff --git a/task6.c b/task6.c
index aff1d39..949d0ec 100644
--- a/task6.c
+++ b/task6.c
@@ -1,13 +1,42 @@
 #include "lib.h"
 
-void main()
+/**
+ * split ciphertext in blocks of size blocksize
+ * @return returns an array of string of size with blocksize elements
+ */
+
+
+char **transpose_blocks(char *ciphertext, int blocksize, int length)
 {
-	/*FILE *fp;
-	int keysize;
-	char *file_content, *chipertext, *block1, *block2;
-	int file_size = 61;
-	int min_hamming_distance;
+	char **blocks;
+	int i, j;
+	int number_blocks = length / blocksize;
+
+	blocks = malloc(blocksize*(sizeof(char*)));
+
+	for(i=0;i<blocksize;i++) {
+		blocks[i] = malloc(number_blocks+1);
+	}
 
+	for(j=0;j<blocksize;j++) {
+		for(i=0;i<number_blocks;i++) {
+			blocks[j][i] = ciphertext[(i*blocksize)+j];
+		}
+	}
+
+	return blocks;
+}
+
+int main()
+{
+	FILE *fp;
+	int keysize;
+	char ch;
+	char *file_content, *new_file_content, *chiphertext, *block1, *block2;
+	int file_size = 60, file_pos = 0;
+	int i; 
+	double min_hamming_distance, tmp;
+	
 	fp = fopen("6.txt", "r");
 
 	if (fp == NULL) {
@@ -17,35 +46,84 @@ void main()
 	
 	file_content = malloc(file_size);
 
+	if (file_content == NULL) {
+		perror("out of memory");
+		exit(1);
+	}
+
 	// read data and decode it from base64
 	// result is not a hex strin or?
 
-	while (fscanf(fp, "%60c", file_content) != EOF) {
-		file_size += 61;
-		file_content = realloc(file_content, file_size);
+	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(file_content, (file_size+60));
+			if (new_file_content != NULL) {
+				file_content = new_file_content;
+				file_size += 60;
+			}
+			else {
+				printf("error allocating memory\n");
+				exit(1);
+			}
+		}
+		file_content[file_pos++] = ch;
 	}
+	file_content[file_pos] = '\0';
 
-	ciphertext = malloc(file_size);
-	decode_base64(file_content, ciphertext);
+	int ciphertext_len = 0;
+
+	chiphertext = malloc(file_pos+1);
+	ciphertext_len = decode_base64(file_content, chiphertext);
 
 	block1 = malloc(41);
 	block2 = malloc(41);
 
-	// split ciphertext in blocks of size 2 to 40
-	for(keysize=2; keysize < 40; keysize++) {
-		strncpy(block1, ciphertext, keysize);
-		strncpy(block2, &ciphertext[keysize+1], keysize);
-
-		tmp = hamming_distance(block1, block2);
-		tmp = tmp / keysize;
+	// max. hamming distacne is 100.
+	min_hamming_distance = 101;
 
-		if (tmp < min_hamming_distance)
+	int j=0;
+	// split ciphertext in 4 blocks of size 2 to 40
+	// and compute hamming distance of these blocks
+	for(i=2; i <= 40; i++) {
+		for(j=0;j< ciphertext_len/i;j++) {
+			memcpy(block1, &chiphertext[j], i);
+			block1[i+1] = '\0';
+			memcpy(block2, &chiphertext[j+i], i);
+			block2[i+1] = '\0';
+		
+			tmp += (double) hamming_distance_equal_length(block1, block2, i);
+		}
+		tmp = ((double)tmp / (double) (ciphertext_len/i)/ (double)i);
+		if (tmp <= min_hamming_distance) {
 			min_hamming_distance = tmp;
+			keysize = i;
+		}
 	}
+	
+	int number_blocks = ciphertext_len/keysize;
+	printf("use keysize: %i with hammind_distance: %f, number of blocks:%i\n", keysize, min_hamming_distance, number_blocks);
+	// split into keysize blcoks and transpose them 
+	char **transposed_blocks = transpose_blocks(chiphertext, keysize, ciphertext_len);
 
-	printf("keysize: %i\n", min_hamming_distance);
+	char key[keysize+1];
+	struct key_and_freq tmp_NOT_USED_HERE;
+
+	for(i=0;i<keysize;i++) {
+		key[i] = brute_force_single_byte_xor(transposed_blocks[i],
+					number_blocks, &tmp_NOT_USED_HERE);
+	}
 
+	key[keysize+1] = '\0';	
+	char *cleartext = malloc(ciphertext_len+1);
+	// xor with all single byte keys on the whole data
+	cleartext[ciphertext_len] = '\0';
+	xor_string(chiphertext, key, cleartext, keysize, ciphertext_len);
 
-	// transpose the blocks
-*/	
+	printf("%s\n", cleartext);
+	printf("used key: %s\n", key);
+	return 0;
 }
diff --git a/test.sh b/test.sh
index 780a12b..80ae42f 100644
--- a/test.sh
+++ b/test.sh
@@ -36,6 +36,15 @@ test_set1_challenge2() {
 	test_compare_string "$OUTPUT" "$EXCEPTED"
 }
 
+test_set1_challenge4() {
+	echo "test: set1, challenge 4:"
+	OUTPUT=$(./task4)
+	EXCEPTED="Now that the party is jumping"
+
+	test_compare_string "$OUTPUT" "$EXCEPTED"
+}
+
 test_set1_challenge1
 test_set1_challenge2
+test_set1_challenge4
 test_set1_challenge5
-- 
cgit v1.2.3-70-g09d2