commit 406aa4552a412082f67d3eb20a165c31fa4474d5
parent 3912bee57a60f9c2cea400325f5e129dae621fab
Author: Jack Sangdahl <jack@pngu.org>
Date: Sat, 4 Oct 2025 20:54:49 -0600
challenge 6: break repeating key xor
Diffstat:
6 files changed, 191 insertions(+), 0 deletions(-)
diff --git a/data/06.txt b/data/06.txt
@@ -0,0 +1,64 @@
+HUIfTQsPAh9PE048GmllH0kcDk4TAQsHThsBFkU2AB4BSWQgVB0dQzNTTmVS
+BgBHVBwNRU0HBAxTEjwMHghJGgkRTxRMIRpHKwAFHUdZEQQJAGQmB1MANxYG
+DBoXQR0BUlQwXwAgEwoFR08SSAhFTmU+Fgk4RQYFCBpGB08fWXh+amI2DB0P
+QQ1IBlUaGwAdQnQEHgFJGgkRAlJ6f0kASDoAGhNJGk9FSA8dDVMEOgFSGQEL
+QRMGAEwxX1NiFQYHCQdUCxdBFBZJeTM1CxsBBQ9GB08dTnhOSCdSBAcMRVhI
+CEEATyBUCHQLHRlJAgAOFlwAUjBpZR9JAgJUAAELB04CEFMBJhAVTQIHAh9P
+G054MGk2UgoBCVQGBwlTTgIQUwg7EAYFSQ8PEE87ADpfRyscSWQzT1QCEFMa
+TwUWEXQMBk0PAg4DQ1JMPU4ALwtJDQhOFw0VVB1PDhxFXigLTRkBEgcKVVN4
+Tk9iBgELR1MdDAAAFwoFHww6Ql5NLgFBIg4cSTRWQWI1Bk9HKn47CE8BGwFT
+QjcEBx4MThUcDgYHKxpUKhdJGQZZVCFFVwcDBVMHMUV4LAcKQR0JUlk3TwAm
+HQdJEwATARNFTg5JFwQ5C15NHQYEGk94dzBDADsdHE4UVBUaDE5JTwgHRTkA
+Umc6AUETCgYAN1xGYlUKDxJTEUgsAA0ABwcXOwlSGQELQQcbE0c9GioWGgwc
+AgcHSAtPTgsAABY9C1VNCAINGxgXRHgwaWUfSQcJABkRRU8ZAUkDDTUWF01j
+OgkRTxVJKlZJJwFJHQYADUgRSAsWSR8KIgBSAAxOABoLUlQwW1RiGxpOCEtU
+YiROCk8gUwY1C1IJCAACEU8QRSxORTBSHQYGTlQJC1lOBAAXRTpCUh0FDxhU
+ZXhzLFtHJ1JbTkoNVDEAQU4bARZFOwsXTRAPRlQYE042WwAuGxoaAk5UHAoA
+ZCYdVBZ0ChQLSQMYVAcXQTwaUy1SBQsTAAAAAAAMCggHRSQJExRJGgkGAAdH
+MBoqER1JJ0dDFQZFRhsBAlMMIEUHHUkPDxBPH0EzXwArBkkdCFUaDEVHAQAN
+U29lSEBAWk44G09fDXhxTi0RAk4ITlQbCk0LTx4cCjBFeCsGHEETAB1EeFZV
+IRlFTi4AGAEORU4CEFMXPBwfCBpOAAAdHUMxVVUxUmM9ElARGgZBAg4PAQQz
+DB4EGhoIFwoKUDFbTCsWBg0OTwEbRSonSARTBDpFFwsPCwIATxNOPBpUKhMd
+Th5PAUgGQQBPCxYRdG87TQoPD1QbE0s9GkFiFAUXR0cdGgkADwENUwg1DhdN
+AQsTVBgXVHYaKkg7TgNHTB0DAAA9DgQACjpFX0BJPQAZHB1OeE5PYjYMAg5M
+FQBFKjoHDAEAcxZSAwZOBREBC0k2HQxiKwYbR0MVBkVUHBZJBwp0DRMDDk5r
+NhoGACFVVWUeBU4MRREYRVQcFgAdQnQRHU0OCxVUAgsAK05ZLhdJZChWERpF
+QQALSRwTMRdeTRkcABcbG0M9Gk0jGQwdR1ARGgNFDRtJeSchEVIDBhpBHQlS
+WTdPBzAXSQ9HTBsJA0UcQUl5bw0KB0oFAkETCgYANlVXKhcbC0sAGgdFUAIO
+ChZJdAsdTR0HDBFDUk43GkcrAAUdRyonBwpOTkJEUyo8RR8USSkOEENSSDdX
+RSAdDRdLAA0HEAAeHQYRBDYJC00MDxVUZSFQOV1IJwYdB0dXHRwNAA9PGgMK
+OwtTTSoBDBFPHU54W04mUhoPHgAdHEQAZGU/OjV6RSQMBwcNGA5SaTtfADsX
+GUJHWREYSQAnSARTBjsIGwNOTgkVHRYANFNLJ1IIThVIHQYKAGQmBwcKLAwR
+DB0HDxNPAU94Q083UhoaBkcTDRcAAgYCFkU1RQUEBwFBfjwdAChPTikBSR0T
+TwRIEVIXBgcURTULFk0OBxMYTwFUN0oAIQAQBwkHVGIzQQAGBR8EdCwRCEkH
+ElQcF0w0U05lUggAAwANBxAAHgoGAwkxRRMfDE4DARYbTn8aKmUxCBsURVQf
+DVlOGwEWRTIXFwwCHUEVHRcAMlVDKRsHSUdMHQMAAC0dCAkcdCIeGAxOazkA
+BEk2HQAjHA1OAFIbBxNJAEhJBxctDBwKSRoOVBwbTj8aQS4dBwlHKjUECQAa
+BxscEDMNUhkBC0ETBxdULFUAJQAGARFJGk9FVAYGGlMNMRcXTRoBDxNPeG43
+TQA7HRxJFUVUCQhBFAoNUwctRQYFDE43PT9SUDdJUydcSWRtcwANFVAHAU5T
+FjtFGgwbCkEYBhlFeFsABRcbAwZOVCYEWgdPYyARNRcGAQwKQRYWUlQwXwAg
+ExoLFAAcARFUBwFOUwImCgcDDU5rIAcXUj0dU2IcBk4TUh0YFUkASEkcC3QI
+GwMMQkE9SB8AMk9TNlIOCxNUHQZCAAoAHh1FXjYCDBsFABkOBkk7FgALVQRO
+D0EaDwxOSU8dGgI8EVIBAAUEVA5SRjlUQTYbCk5teRsdRVQcDhkDADBFHwhJ
+AQ8XClJBNl4AC1IdBghVEwARABoHCAdFXjwdGEkDCBMHBgAwW1YnUgAaRyon
+B0VTGgoZUwE7EhxNCAAFVAMXTjwaTSdSEAESUlQNBFJOZU5LXHQMHE0EF0EA
+Bh9FeRp5LQdFTkAZREgMU04CEFMcMQQAQ0lkay0ABwcqXwA1FwgFAk4dBkIA
+CA4aB0l0PD1MSQ8PEE87ADtbTmIGDAILAB0cRSo3ABwBRTYKFhROHUETCgZU
+MVQHYhoGGksABwdJAB0ASTpFNwQcTRoDBBgDUkksGioRHUkKCE5THEVCC08E
+EgF0BBwJSQoOGkgGADpfADETDU5tBzcJEFMLTx0bAHQJCx8ADRJUDRdMN1RH
+YgYGTi5jMURFeQEaSRAEOkURDAUCQRkKUmQ5XgBIKwYbQFIRSBVJGgwBGgtz
+RRNNDwcVWE8BT3hJVCcCSQwGQx9IBE4KTwwdASEXF01jIgQATwZIPRpXKwYK
+BkdEGwsRTxxDSToGMUlSCQZOFRwKUkQ5VEMnUh0BR0MBGgAAZDwGUwY7CBdN
+HB5BFwMdUz0aQSwWSQoITlMcRUILTxoCEDUXF01jNw4BTwVBNlRBYhAIGhNM
+EUgIRU5CRFMkOhwGBAQLTVQOHFkvUkUwF0lkbXkbHUVUBgAcFA0gRQYFCBpB
+PU8FQSsaVycTAkJHYhsRSQAXABxUFzFFFggICkEDHR1OPxoqER1JDQhNEUgK
+TkJPDAUAJhwQAg0XQRUBFgArU04lUh0GDlNUGwpOCU9jeTY1HFJARE4xGA4L
+ACxSQTZSDxsJSw1ICFUdBgpTNjUcXk0OAUEDBxtUPRpCLQtFTgBPVB8NSRoK
+SREKLUUVAklkERgOCwAsUkE2Ug8bCUsNSAhVHQYKUyI7RQUFABoEVA0dWXQa
+Ry1SHgYOVBFIB08XQ0kUCnRvPgwQTgUbGBwAOVREYhAGAQBJEUgETgpPGR8E
+LUUGBQgaQRIaHEshGk03AQANR1QdBAkAFwAcUwE9AFxNY2QxGA4LACxSQTZS
+DxsJSw1ICFUdBgpTJjsIF00GAE1ULB1NPRpPLF5JAgJUVAUAAAYKCAFFXjUe
+DBBOFRwOBgA+T04pC0kDElMdC0VXBgYdFkU2CgtNEAEUVBwTWXhTVG5SGg8e
+AB0cRSo+AwgKRSANExlJCBQaBAsANU9TKxFJL0dMHRwRTAtPBRwQMAAATQcB
+FlRlIkw5QwA2GggaR0YBBg5ZTgIcAAw3SVIaAQcVEU8QTyEaYy0fDE4ITlhI
+Jk8DCkkcC3hFMQIEC0EbAVIqCFZBO1IdBgZUVA4QTgUWSR4QJwwRTWM=
diff --git a/lib/blocks.c b/lib/blocks.c
@@ -0,0 +1,25 @@
+#include "blocks.h"
+
+int block_transpose(const unsigned char *str, const int str_len,
+ const int num_blocks, unsigned char ***blocks) {
+ int block_len = str_len / num_blocks;
+ *blocks = (unsigned char **)malloc(num_blocks * sizeof(char *));
+ for (int i = 0; i < num_blocks; i++) {
+ (*blocks)[i] = (unsigned char *)malloc(block_len * sizeof(char));
+ for (int j = 0; j < block_len; j++)
+ (*blocks)[i][j] = str[i + j * num_blocks];
+ }
+ return block_len;
+}
+
+int chunk(const unsigned char *str, const int str_len, const int block_len,
+ unsigned char ***blocks) {
+ int num_blocks = str_len / block_len;
+ *blocks = (unsigned char **)malloc(num_blocks * sizeof(char *));
+ for (int i = 0; i < num_blocks; i++) {
+ (*blocks)[i] = (unsigned char *)malloc(block_len * sizeof(char));
+ for (int j = 0; j < block_len; j++)
+ (*blocks)[i][j] = str[i * block_len + j];
+ }
+ return num_blocks;
+}
diff --git a/lib/blocks.h b/lib/blocks.h
@@ -0,0 +1,8 @@
+#pragma once
+
+#include <stdlib.h>
+
+int block_transpose(const unsigned char *str, const int str_len,
+ const int num_blocks, unsigned char ***blocks);
+int chunk(const unsigned char *str, const int str_len, const int block_len,
+ unsigned char ***blocks);
diff --git a/lib/file.c b/lib/file.c
@@ -0,0 +1,20 @@
+#include "file.h"
+
+int read_file(const char *filename, char **res) {
+ int file_len = 0;
+ FILE *fptr = fopen(filename, "r");
+ if (!fptr) {
+ fprintf(stderr, "Error: %s (errno: %d)\n", strerror(errno), errno);
+ return -1;
+ }
+ fseek(fptr, 0, SEEK_END);
+ file_len = ftell(fptr);
+ rewind(fptr);
+ *res = (char *)malloc((file_len + 1) * sizeof(char));
+ if (fread((*res), file_len, sizeof(char), fptr) != 1) {
+ fprintf(stderr, "Error reading from file %s\n", filename);
+ return -1;
+ }
+ fclose(fptr);
+ return file_len;
+}
diff --git a/lib/file.h b/lib/file.h
@@ -0,0 +1,8 @@
+#pragma once
+
+#include <errno.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+int read_file(const char *filename, char **res);
diff --git a/src/06_break_repeating_key_xor.c b/src/06_break_repeating_key_xor.c
@@ -0,0 +1,66 @@
+// Break repeating-key XOR
+#include "base64.h"
+#include "blocks.h"
+#include "file.h"
+#include "stats.h"
+#include "xor.h"
+
+/*
+ * this challenge isn't conceptually hard, but it involves actual error-prone
+ * coding. the other challenges in this set are there to bring you up to speed.
+ * this one is there to qualify you. if you can do this one, you're probably
+ * just fine up to set 6.
+ * [data/06.txt] has been base64'd after being encrypted with repeating key xor.
+ * decrypt it. here's how:
+ * 1. let KEYSIZE be the guessed length of the key; try values from 2 to
+ * (say) 40.
+ * 2. write a function to compute the edit distance/hamming distance between two
+ * strings. the hamming distance is just the numnber of differing bits. the
+ * distance between: this is a test and: wokka wokka!!! is 37. make sure your
+ * code agrees before you proceed.
+ * 3. for each KEYSIZE, take the first KEYSIZE worth of bytes, and the second
+ * KEYSIZE worth of bytes, and find the edit distance between them. normalise
+ * this result by dividing it by KEYSIZE
+ * 4. the KEYSIZE with the smallest normalised 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
+ * 5. now that you probably know the KEYSIZE: break the ciphertext into blocks
+ * of KEYSIZE length
+ * 6. now transpose the blocks: make a block that is the first byte of every
+ * block, and a block that is the second byte of every block, adnd so on
+ * 7. solve each block as if it was a single-character xor. you already have
+ * code to do this. for each block, the single-byte xor key that procudes the
+ * best looking histogram is the repeating key xor key byte for that block. put
+ * them together and you have the key.
+ * this code is going to turn out to be surprisingly useful later on. breakting
+ * repeating-key xor ("vigenere") statistically is obviously an academic
+ * exercise, a "crypto 101" thing. but more people "know how" to break it than
+ * can actually break it, and a similar technique breaks something much more
+ * important.
+ */
+
+int main(void) {
+ char *input = NULL, *decoded = NULL;
+ unsigned char *xord = NULL, **blocks = NULL;
+ int file_len = read_file("data/06.txt", &input);
+ size_t decoded_len = base64_decode(input, file_len, &decoded);
+ size_t key_len =
+ find_xor_key_len((unsigned char *)decoded, decoded_len, 2, 40);
+ unsigned char *xor_key = (unsigned char *)malloc(key_len * sizeof(char));
+ block_transpose((unsigned char *)decoded, decoded_len, key_len, &blocks);
+ size_t i;
+ for (i = 0; i < key_len; i++) {
+ xor_key[i] = find_single_byte_xor(blocks[i], key_len, frequency_score);
+ printf("%c", xor_key[i]);
+ }
+ xor_key[i] = 0;
+ printf("\n");
+ int res = xor((unsigned char *)decoded, decoded_len, xor_key, key_len, &xord);
+ if (res != -1)
+ printf("%s\n", xord);
+ free(blocks);
+ free(input);
+ free(xord);
+ free(xor_key);
+ return 0;
+}
