From ca368f0fe17541a71cba6b1c6af064e89ab8155d Mon Sep 17 00:00:00 2001 From: Zachary Vance Date: Thu, 25 May 2017 00:43:10 -0700 Subject: [PATCH] Solve Set 1, Problem 6 (with one hint) --- Makefile | 5 +- english.c | 4 +- hamming.c | 26 ++++++ hamming.h | 2 + io.c | 33 ++++++-- io.h | 5 +- problems/set-1/4.html | 4 +- problems/set-1/6.html | 4 +- problems/set-1/7.html | 4 +- problems/set-1/8.html | 4 +- set1p4.test.c | 3 + set1p6.test.c | 182 ++++++++++++++++++++++++++++++++++++++++++ util.c | 32 ++++++++ util.h | 4 + xor.c | 14 ++-- xor.h | 4 +- xor_decrypt.c | 23 ++++-- 17 files changed, 320 insertions(+), 33 deletions(-) create mode 100644 hamming.c create mode 100644 hamming.h create mode 100644 set1p6.test.c diff --git a/Makefile b/Makefile index 356a2a3..e302ddb 100644 --- a/Makefile +++ b/Makefile @@ -14,12 +14,15 @@ set1p4.test: set1p4.test.c io.o xor_decrypt.o english.o util.o xor.o $(CC) -o $@ $? $(CFLAGS) set1p5.test: set1p5.test.c io.o util.o xor.o $(CC) -o $@ $? $(CFLAGS) -test: set1p1.test set1p2.test set1p3.test set1p4.test set1p5.test +set1p6.test: set1p6.test.c io.o util.o xor.o xor_decrypt.o english.o hamming.o + $(CC) -o $@ $? $(CFLAGS) +test: set1p1.test set1p2.test set1p3.test set1p4.test set1p5.test set1p6.test ./set1p1.test >/dev/null || echo "Set 1, Problem 1: Failed" ./set1p2.test >/dev/null || echo "Set 1, Problem 2: Failed" ./set1p3.test >/dev/null || echo "Set 1, Problem 3: Failed" ./set1p4.test >/dev/null || echo "Set 1, Problem 4: Failed" ./set1p5.test >/dev/null || echo "Set 1, Problem 5: Failed" + ./set1p6.test >/dev/null || echo "Set 1, Problem 6: Failed" clean: rm -f *.o a.out *.test %.o: %.c diff --git a/english.c b/english.c index 24273cd..950d882 100644 --- a/english.c +++ b/english.c @@ -6,7 +6,7 @@ float score_english_character(char c) { case 'e': case 't': case 'a': case 'o': case 'i': case 'n': return 3; break; case 'S': case 'H': case 'R': case 'D': case 'L': case 'U': return 2; break; case 's': case 'h': case 'r': case 'd': case 'l': case 'u': return 2; break; - case 0: return 0; break; + case '\000': return 0; break; default: break; } if (strchr("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz", c) != 0) return 1; @@ -19,7 +19,7 @@ float score_english_buf(char* possible_plaintext, int length) { for (i=0;i +#include + +int bits_set(unsigned char b) { + int distance=0; + while (b != 0) { + if (b%2) { b--; distance++; } + b=b/2; + } + return distance; +} + +int hamming_distance_buf(char* buf1, char* buf2, int length) { + int distance = 0; + int i; + for(i=0;i|%.*s|<", hex, length, buffer); + free(hex); return output; } void print_buffer(char* buffer, int length) { char* output = printable_buffer(buffer, length); - printf("%s\n", output); + printf("%*s\n", length, output); free(output); } + +int read_base64_file(char* path, char** ciphertext, int *ciphertext_length) { + char* ciphertext_base64=NULL; + int ciphertext_base64_length=0; + FILE *f = fopen(path, "r"); + int line_length=0; + int line_buf_length; + char* line=NULL; + while ((line_length = getline(&line, &line_buf_length, f))>0) { + if (line[line_length-1] == '\000') line_length--; + if (line[line_length-1] == '\n') line_length--; + ciphertext_base64 = realloc(ciphertext_base64, ciphertext_base64_length+line_length+1); + memcpy(ciphertext_base64+ciphertext_base64_length, line, line_length); + ciphertext_base64_length += line_length; + } + free(line); + fclose(f); + ciphertext_base64[ciphertext_base64_length]=0; + int succ = decode_base64(ciphertext_base64, *ciphertext, ciphertext_length); + free(ciphertext_base64); + return succ; +} diff --git a/io.h b/io.h index b930907..8ec6a11 100644 --- a/io.h +++ b/io.h @@ -1,7 +1,10 @@ +#define PRINT_BUFFER(BUF) { printf("Buffer BUF : ");print_buffer(BUF,sizeof(BUF)); } + int decode_hex(char* src, char* dest, int *destlen); int decode_base64(char* src, char* dest, int* destlen); void encode_base64(const char* src_bytes, int src_size, char* dest); void encode_hex(const char* src_bytes, int src_size, char* dest); char* printable_buffer(char* buffer, int length); void print_buffer(char* buffer, int length); -#define PRINT_BUFFER(BUF) { printf("Buffer BUF : ");print_buffer(BUF,sizeof(BUF)); } + +int read_base64_file(char* path, char** ciphertext, int *ciphertext_length); diff --git a/problems/set-1/4.html b/problems/set-1/4.html index 0676e2d..50f6cd0 100644 --- a/problems/set-1/4.html +++ b/problems/set-1/4.html @@ -46,7 +46,7 @@

Detect single-character XOR

One of the 60-character strings in - this file + this file has been encrypted by single-character XOR.

@@ -72,4 +72,4 @@ var s = document.getElementsByTagName('script')[0]; s.parentNode.insertBefore(ga, s); })();*/ - \ No newline at end of file + diff --git a/problems/set-1/6.html b/problems/set-1/6.html index f5afb6d..78e71a4 100644 --- a/problems/set-1/6.html +++ b/problems/set-1/6.html @@ -63,7 +63,7 @@

- There's a file here. + There's a file here. It's been base64'd after being encrypted with repeating-key XOR.

@@ -151,4 +151,4 @@ var s = document.getElementsByTagName('script')[0]; s.parentNode.insertBefore(ga, s); })();*/ - \ No newline at end of file + diff --git a/problems/set-1/7.html b/problems/set-1/7.html index 39017cf..40d69fb 100644 --- a/problems/set-1/7.html +++ b/problems/set-1/7.html @@ -46,7 +46,7 @@

AES in ECB mode

The Base64-encoded content - in this file + in this file has been encrypted via AES-128 in ECB mode under the key 

"YELLOW SUBMARINE".
@@ -88,4 +88,4 @@ var s = document.getElementsByTagName('script')[0]; s.parentNode.insertBefore(ga, s); })();*/ - \ No newline at end of file + diff --git a/problems/set-1/8.html b/problems/set-1/8.html index 62144bf..d2b4fdb 100644 --- a/problems/set-1/8.html +++ b/problems/set-1/8.html @@ -45,7 +45,7 @@

Detect AES in ECB mode

- In this file + In this file are a bunch of hex-encoded ciphertexts.

@@ -76,4 +76,4 @@ var s = document.getElementsByTagName('script')[0]; s.parentNode.insertBefore(ga, s); })();*/ - \ No newline at end of file + diff --git a/set1p4.test.c b/set1p4.test.c index d33f572..e8cb72d 100644 --- a/set1p4.test.c +++ b/set1p4.test.c @@ -44,6 +44,8 @@ int main() { break; } } + fclose(fd); + free(ciphertext_hex); printf("Reading from file complete. Read %d lines.\n", candidate_ciphertext_count); decryption[CIPHERTEXT_LENGTH] = '\0'; // Make it a string. @@ -51,6 +53,7 @@ int main() { best_score = -1000; for(i=0;ibest_score) { best_score = score; memcpy(best_decryption, decryption, CIPHERTEXT_LENGTH+1); diff --git a/set1p6.test.c b/set1p6.test.c new file mode 100644 index 0000000..dc78da3 --- /dev/null +++ b/set1p6.test.c @@ -0,0 +1,182 @@ +#include +#include +#include +#include "english.h" +#include "hamming.h" +#include "io.h" +#include "util.h" +#include "xor.h" +#include "xor_decrypt.h" +#define MIN_KEYSIZE 2 +#define MAX_KEYSIZE 40 + +float score_repeating_xor_keysize(char* ciphertext, int ciphertext_size, int keysize) { + // The KEYSIZE with the smallest normalized edit distance is probably + // the key. You could proceed perhaps with the smallest 2-3 KEYSIZE + // values. Or take 4 KEYSIZE blocks instead of 2 and average the + // distances. + if (ciphertext_size < keysize*4) { + printf("in score_repeating_xor_keysize: attempted key size too large (%d vs %d)\n", keysize, ciphertext_size); + return -1; + } + float d01 = hamming_distance_buf(ciphertext+0*keysize, ciphertext+1*keysize, keysize) / keysize; + float d12 = hamming_distance_buf(ciphertext+1*keysize, ciphertext+2*keysize, keysize) / keysize; + float d23 = hamming_distance_buf(ciphertext+2*keysize, ciphertext+3*keysize, keysize) / keysize; + float d02 = hamming_distance_buf(ciphertext+0*keysize, ciphertext+2*keysize, keysize) / keysize; + float d13 = hamming_distance_buf(ciphertext+1*keysize, ciphertext+3*keysize, keysize) / keysize; + float d03 = hamming_distance_buf(ciphertext+0*keysize, ciphertext+3*keysize, keysize) / keysize; + return (d01+d12+d23+d02+d13+d03)/3; +} + +void find_repeating_xor_keysize(char* ciphertext, int ciphertext_length, + int min_keysize, int max_keysize, + int *keysize, float *keysize_score) { + int best_keysize; + int keysize_guess; + float best_keysize_score=1000; + float keysize_guess_score; + for(keysize_guess=MIN_KEYSIZE; keysize_guess<=MAX_KEYSIZE; keysize_guess++) { + keysize_guess_score = score_repeating_xor_keysize(ciphertext, ciphertext_length, keysize_guess); + if (keysize_guess_score < best_keysize_score) { + best_keysize=keysize_guess; + best_keysize_score=keysize_guess_score; + } + } + *keysize=best_keysize; + if (keysize_score != NULL) *keysize_score=best_keysize_score; +} + +int main() { + // Test hamming distance code + int hd = hamming_distance("this is a test", "wokka wokka!!!"); + if (hd==37) { + printf("Hamming distance: correct\n"); + } else { + printf("Hamming distance: incorrect\n"); + printf(" Expected: 37\n"); + printf(" Got: %d\n", hd); + } + + // Read the file + char *ciphertext = malloc(20000); + int ciphertext_length; + if(read_base64_file("problems/set-1/6.txt", &ciphertext, &ciphertext_length)) { + printf("Base64 decode: complete. Size: %d\n", ciphertext_length); + } else { + printf("Base64 decode: failed\n"); + exit(1); + } + + // Guess the keysize using hamming distances of keysize-sized chunks + int keysize; + float keysize_score; + find_repeating_xor_keysize(ciphertext, ciphertext_length, + MIN_KEYSIZE, MAX_KEYSIZE, + &keysize, &keysize_score); + if (keysize == 29) { + printf("Keysize guess: correct\n"); + } else { + printf("Guessed keysize: %d (%0.2f)\n", keysize, keysize_score); + printf("Keysize guess: incorrect\n"); + exit(1); + } + + // Check transpose code + char **transposed_simple = NULL; + int transpose_length_simple = 0; + transpose("ABCDEFG", 7, &transposed_simple, 3, &transpose_length_simple); + if (transpose_length_simple == 3) { + printf("Simple transpose: correct length\n"); + } else { + printf("Simple transpose: incorrect length\n"); + exit(1); + } + if (transposed_simple == NULL) { printf("no return\n"); exit(1); } + if (memcmp(transposed_simple[0], "ADG", 3)!=0) { printf("Transpose wrong %3s vs %3s.", "ADF", transposed_simple[0]); exit(1); } + if (memcmp(transposed_simple[1], "BE\000", 3)!=0) { printf("Transpose wrong %3s vs %4s.", "BE\\0", transposed_simple[1]); exit(1); } + if (memcmp(transposed_simple[2], "CF\000", 3)!=0) { printf("Transpose wrong %3s vs %4s.", "CF\\0", transposed_simple[2]); exit(1); } + printf("Simple transpose: correct\n"); + free(transposed_simple[0]); + free(transposed_simple[1]); + free(transposed_simple[2]); + free(transposed_simple); + + //Do transpose with sanity check + char **transposed = NULL; + int transpose_length = 0; + char *transpose_check = malloc(ciphertext_length); + transpose(ciphertext, ciphertext_length, &transposed, keysize, &transpose_length); + detranspose(transposed, keysize, transpose_check, ciphertext_length); + if (memcmp(ciphertext, transpose_check, ciphertext_length)==0) { + printf("Transpose: success\n"); + } else { + printf("Transpose: failed\n"); + exit(1); + } + free(transpose_check); + + // Find each key bit + char *key = malloc(keysize+1); + int i; + key[keysize]=0; + char **best_decryptions = calloc(sizeof(char*), keysize); + float best_score=0; + printf("transpose length: %d\n", transpose_length); + for (i=0; i + void fill(char* buffer1, int buf1_length, char* buffer2, int buf2_length) { int i; for (i=0;i #include "util.h" -void xor(char* buf1, char* buf2, char* buf3, int length) { +void xor(char* in1, char* in2, char* out, int length) { int i; for(i=0; i *best_score) { - *best_score = score; - strncpy(best_decryption, plaintext_buffer, ciphertext_length); - strncpy(best_candidate, candidates[ci], candidate_length); + if (score > top_score) { + top_score = score; + if (best_candidate != NULL) memcpy(best_candidate, candidates[ci], candidate_length); + if (best_decryption != NULL) memcpy(best_decryption, plaintext_buffer, ciphertext_length); } } + if (best_score != NULL) *best_score = top_score; + free(plaintext_buffer); + free(xor_buffer); } -void find_best_xor_candidate_buf(int length, char* ciphertext, int ciphertext_length, char* best_candidate, char* best_decryption, float* best_score) { +void find_best_xor_candidate_buf(int length, + char* ciphertext, int ciphertext_length, + char* best_candidate, char* best_decryption, float* best_score) { int num_candidates = 1; unsigned int i, j, ci; for (i=0; i