diff options
| -rw-r--r-- | Makefile | 2 | ||||
| -rw-r--r-- | lib.c | 204 | ||||
| -rw-r--r-- | lib.h | 17 | ||||
| -rw-r--r-- | task2.c | 15 | ||||
| -rw-r--r-- | task4.c | 26 | ||||
| -rw-r--r-- | task5.c | 6 | ||||
| -rw-r--r-- | task6.c | 122 | ||||
| -rw-r--r-- | test.sh | 9 |
8 files changed, 281 insertions, 120 deletions
@@ -1,6 +1,6 @@ LIB=lib.c CC=gcc -CFLAGS := -g $(CFLAGS) +CFLAGS := -g -Wall $(CFLAGS) all: task1 task2 task4 task5 task6 @@ -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,16 +402,16 @@ 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++; } } @@ -347,42 +419,42 @@ int hamming_distance_equal_length(char *string1, char *string2) } /** - * 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; } - - @@ -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__ */ @@ -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); @@ -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; } @@ -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); } @@ -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; } @@ -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 |