summaryrefslogtreecommitdiff
path: root/util
diff options
context:
space:
mode:
Diffstat (limited to 'util')
-rw-r--r--util/aes.c150
-rw-r--r--util/aes.h40
-rw-r--r--util/base64.c194
-rw-r--r--util/base64.h25
-rw-r--r--util/endian.c10
-rw-r--r--util/endian.h7
-rw-r--r--util/hamming.c49
-rw-r--r--util/hamming.h14
-rw-r--r--util/hex.c57
-rw-r--r--util/hex.h12
-rw-r--r--util/io.c76
-rw-r--r--util/io.h23
-rw-r--r--util/mersenne_twister.c68
-rw-r--r--util/mersenne_twister.h5
-rw-r--r--util/obj/aes.obin0 -> 6456 bytes
-rw-r--r--util/obj/base64.obin0 -> 7880 bytes
-rw-r--r--util/obj/endian.obin0 -> 1616 bytes
-rw-r--r--util/obj/hamming.obin0 -> 4376 bytes
-rw-r--r--util/obj/hex.obin0 -> 3128 bytes
-rw-r--r--util/obj/io.obin0 -> 3696 bytes
-rw-r--r--util/obj/pkcs7_padding.obin0 -> 2744 bytes
-rw-r--r--util/obj/score.obin0 -> 4624 bytes
-rw-r--r--util/obj/xor.obin0 -> 2968 bytes
-rw-r--r--util/pkcs7_padding.c40
-rw-r--r--util/pkcs7_padding.h20
-rw-r--r--util/random.c6
-rw-r--r--util/random.h3
-rw-r--r--util/score.c116
-rw-r--r--util/score.h39
-rw-r--r--util/xor.c43
-rw-r--r--util/xor.h27
31 files changed, 1024 insertions, 0 deletions
diff --git a/util/aes.c b/util/aes.c
new file mode 100644
index 0000000..85269ae
--- /dev/null
+++ b/util/aes.c
@@ -0,0 +1,150 @@
+#include <assert.h>
+#include <stddef.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <stdint.h>
+#include <openssl/conf.h>
+#include <openssl/err.h>
+#include <openssl/aes.h>
+#include "aes.h"
+#include "xor.h"
+#include "endian.h"
+#include "pkcs7_padding.h"
+
+/*** utilitary stuff for EVP interface ***/
+
+EVP_CIPHER_CTX *evp_init() {
+ return EVP_CIPHER_CTX_new();
+}
+
+void evp_cleanup(EVP_CIPHER_CTX *ctx) {
+ EVP_CIPHER_CTX_free(ctx);
+}
+
+void handle_evp_errors() {
+ ERR_print_errors_fp(stderr);
+}
+
+/*
+ * ECB mode (electronic code book) implemented with EVP
+ * high-level OpenSSL interface. in its simplest definition:
+ * the message is divided into blocks, padded, then each
+ * block is encrypted separately.
+*/
+
+int evp_ecb_encrypt(EVP_CIPHER_CTX *ctx, unsigned char *in, int in_len, unsigned char *key, unsigned char *out) {
+ int curr_out_len = 0, total_len = 0;
+ if (1 != EVP_EncryptInit_ex(ctx, EVP_aes_128_ecb(), NULL, key, NULL))
+ return -1;
+ if (1 != EVP_EncryptUpdate(ctx, out, &curr_out_len, in, in_len))
+ return -1;
+ total_len = curr_out_len;
+ if (1 != EVP_EncryptFinal_ex(ctx, out + curr_out_len, &curr_out_len))
+ return -1;
+ total_len += curr_out_len;
+ return total_len;
+}
+
+int evp_ecb_decrypt(EVP_CIPHER_CTX *ctx, unsigned char *in, int in_len, unsigned char *key, unsigned char *out) {
+ int curr_out_len = 0, total_len = 0;
+ if (1 != EVP_DecryptInit_ex(ctx, EVP_aes_128_ecb(), NULL, key, NULL))
+ return -1;
+ if (1 != EVP_DecryptUpdate(ctx, out, &curr_out_len, in, in_len))
+ return -1;
+ total_len = curr_out_len;
+ if (1 != EVP_DecryptFinal_ex(ctx, out + curr_out_len, &curr_out_len))
+ return -1;
+ total_len += curr_out_len;
+ return total_len;
+}
+
+/*
+ * CBC mode (cipher block chaining). in CBC mode, each block of
+ * plaintext is XOR'd with the previous ciphertext block before
+ * being encrypted. this way, each ciphertext block depends on all
+ * plaintext blocks processed up to that point.
+ */
+
+int cbc_encrypt(unsigned char *in, int in_len, unsigned char *key, unsigned char *iv, unsigned char *out) {
+ unsigned char *padded;
+ ssize_t padded_len = add_padding((uint8_t*) in, in_len, AES_BLOCK_SIZE, &padded);
+ if (padded_len == -1)
+ return -1;
+ assert(padded_len % AES_BLOCK_SIZE == 0);
+ int num_of_blocks = padded_len / AES_BLOCK_SIZE;
+ unsigned char *curr_out = out, *curr_in = padded;
+ unsigned char *prev_out = iv, *xor_d;
+ AES_KEY ak;
+ AES_set_encrypt_key(key, 128, &ak);
+ for (int i = 0; i < num_of_blocks; i++) {
+ xor_d = xor(curr_in, prev_out, AES_BLOCK_SIZE);
+ AES_encrypt(xor_d, curr_out, &ak);
+ prev_out = curr_out;
+ curr_in += AES_BLOCK_SIZE;
+ curr_out += AES_BLOCK_SIZE;
+ free(xor_d);
+ }
+ free(padded);
+ return curr_out - out;
+}
+
+int cbc_decrypt(unsigned char *in, int in_len, unsigned char *key, unsigned char *iv, unsigned char *out) {
+ //full number of blocks is expected
+ assert(in_len % AES_BLOCK_SIZE == 0);
+ int num_of_blocks = in_len / AES_BLOCK_SIZE;
+ unsigned char *curr_out = out, *curr_in = in;
+ unsigned char *prev_in = iv, *xor_d;
+ size_t bytes_decrypted = 0;
+ AES_KEY ak;
+ AES_set_decrypt_key(key, 128, &ak);
+ for (int i = 0; i < num_of_blocks; i++) {
+ AES_decrypt(curr_in, curr_out, &ak);
+ xor_d = xor(curr_out, prev_in, AES_BLOCK_SIZE);
+ memcpy(curr_out, xor_d, AES_BLOCK_SIZE);
+ prev_in = curr_in;
+ curr_in += AES_BLOCK_SIZE;
+ curr_out += AES_BLOCK_SIZE;
+ bytes_decrypted += AES_BLOCK_SIZE;
+ free(xor_d);
+ }
+ ssize_t pad_len = padding_len(out, bytes_decrypted);
+ if (pad_len == -1)
+ return -1;
+ return bytes_decrypted - (size_t) pad_len;
+}
+
+int ctr_encrypt(unsigned char *in, int in_len, unsigned char *key, uint64_t nonce, unsigned char *out) {
+ AES_KEY ak;
+ AES_set_encrypt_key(key, 128, &ak);
+ //prepare staring 'in' block
+ //first nonce, second little endian, third goes the counter
+ unsigned char *ctr_in_block = malloc(16);
+ if (ctr_in_block == NULL)
+ return 0;
+ uint8_t *nonce_bytes = bytes_le_order(nonce);
+ memcpy(ctr_in_block, nonce_bytes, 8);
+ uint64_t counter = 0;
+ unsigned char *counter_bytes, *ctr_out_block = malloc(16);
+ if (ctr_out_block == NULL) {
+ free(ctr_in_block);
+ return 0;
+ }
+ for (int i = 0; i < in_len; i++) {
+ if (i % 16 == 0) {
+ //encrypt new counter block
+ counter_bytes = bytes_le_order(counter++);
+ memcpy(ctr_in_block + 8, counter_bytes, 8);
+ AES_encrypt(ctr_in_block, ctr_out_block, &ak);
+ free(counter_bytes);
+ }
+ out[i] = in[i] ^ ctr_out_block[i % 16];
+ }
+ free(ctr_in_block);
+ free(ctr_out_block);
+ return 1;
+}
+
+int ctr_decrypt(unsigned char *in, int in_len, unsigned char *key, uint64_t nonce, unsigned char *out) {
+ return ctr_encrypt(in, in_len, key, nonce, out);
+}
diff --git a/util/aes.h b/util/aes.h
new file mode 100644
index 0000000..b37dd46
--- /dev/null
+++ b/util/aes.h
@@ -0,0 +1,40 @@
+#include <openssl/evp.h>
+
+//initializes EVP context
+EVP_CIPHER_CTX *evp_init();
+
+//cleans up EVP context
+void evp_cleanup(EVP_CIPHER_CTX *ctx);
+
+//error handling function
+void handle_evp_errors();
+
+/*
+ * encrypts/decrypts AES-encoded data in ECB mode. takes byte string 'in',
+ * its length, & the key (128bit). writes output to 'out' and
+ * returns its size or -1 if anything goes wrong.
+ * handle_evp_errors() can be used to print error messages.
+ */
+int evp_ecb_encrypt(EVP_CIPHER_CTX *ctx, unsigned char *in, int in_len, unsigned char *key, unsigned char *out);
+int evp_ecb_decrypt(EVP_CIPHER_CTX *ctx, unsigned char *in, int in_len, unsigned char *key, unsigned char *out);
+
+/*
+ * encrypts/decrypts AES-encoded data in CBC mode using low-level OpenSSL
+ * interface. takes byte string 'in', its length, the key, & 'iv'
+ * (128bit). writes output to 'out' and returns its size of -1
+ * if anything goes wrong. handle_evp_errors() can be used
+ * to pint error messages. CBC also handles padding
+ */
+int cbc_encrypt(unsigned char *in, int in_len, unsigned char *key, unsigned char *iv, unsigned char *out);
+int cbc_decrypt(unsigned char *in, int in_len, unsigned char *key, unsigned char *iv, unsigned char *out);
+
+/*
+ * encrypts/decrypts AES-encoded data in CTR mode using low-level
+ * OpenSSL interface. takes byte string 'in' its length, the key
+ * & the nonce. writes output to 'out' (its length should be the
+ * same as 'in' length). returns 0 on error, 1 on success.
+ * encryption and decryption methods are identical.
+ * no padding is made, as it is not needed.
+ */
+int ctr_encrypt(unsigned char *in, int in_len, unsigned char *key, uint64_t nonce, unsigned char *out);
+int ctr_decrypt(unsigned char *in, int in_len, unsigned char *key, uint64_t nonce, unsigned char *out);
diff --git a/util/base64.c b/util/base64.c
new file mode 100644
index 0000000..7406aa5
--- /dev/null
+++ b/util/base64.c
@@ -0,0 +1,194 @@
+#include <ctype.h>
+#include <math.h> //not part of c stdlib, so compile with -lm to link
+#include <assert.h>
+#include <string.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include "base64.h"
+
+//*** encoding ***//
+static size_t base64_encoded_length(size_t bytes_len) {
+ return (size_t)(4 * ceil(bytes_len / 3.0));
+}
+
+static char encode_char(sextet s) {
+ char res;
+ assert(s < 64);
+ if (s < 26)
+ //0..25 -> 'A'...'Z'
+ res = 'A' + s;
+ else if (s < 52)
+ //26...51 -> 'a'...'z'
+ res = 'a' + (s - 26);
+ else if (s < 62)
+ //52...61 -> '0'...'9'
+ res = '0' + (s - 52);
+ else if (s == 62)
+ res = '+';
+ else
+ res = '/';
+ return res;
+}
+
+static void encode_1byte(uint8_t byte1, char *encoded) {
+ sextet s[2];
+ s[0] = byte1 >> 2;
+ s[1] = (byte1 & 0x03) << 4;
+ *encoded++ = encode_char(s[0]);
+ *encoded++ = encode_char(s[1]);
+ *encoded++ = '=';
+ *encoded = '=';
+}
+
+static void encode_2byte(uint8_t byte1, uint8_t byte2, char *encoded) {
+ sextet s[3];
+ s[0] = byte1 >> 2;
+ s[1] = ((byte1 & 0x03) << 4) | (byte2 >> 4);
+ s[2] = (byte2 & 0x0F) << 2;
+ for (int i = 0; i < 3; i++)
+ *encoded++ = encode_char(s[i]);
+ *encoded = '=';
+}
+
+static void encode_3byte(uint8_t byte1, uint8_t byte2, uint8_t byte3, char *encoded) {
+ sextet s[4];
+ s[0] = byte1 >> 2;
+ s[1] = ((byte1 & 0x03) << 4) | (byte2 >> 4);
+ s[2] = ((byte2 & 0x0F) << 2) | (byte3 >> 6);
+ s[3] = byte3 & 0x3F;
+ for (int i = 0; i < 4; i++)
+ *encoded++ = encode_char(s[i]);
+}
+
+char *base64_encode(uint8_t *from, size_t len) {
+ long padded_bytes;
+ size_t to_len;
+ char *to, *curr;
+ //first determine size of required result buffer
+ //then malloc (with 1 extra byte for '\0')
+ to_len = base64_encoded_length(len);
+ to = (char*) malloc(to_len + 1);
+ if (to == NULL)
+ return NULL;
+ //handle 3 bytes at a time,
+ //converting into 4 sextets
+ curr = to;
+ for (unsigned long i = 0; i < len / 3; i++) {
+ encode_3byte(*from, *(from + 1), *(from + 2), curr);
+ from += 3;
+ curr += 4;
+ }
+ //convert leftover bytes (if any)
+ padded_bytes = len - 3 * (len / 3);
+ if (padded_bytes == 1)
+ encode_1byte(*from, curr);
+ else if (padded_bytes == 2)
+ encode_2byte(*from, *(from + 1), curr);
+ //aformentioned zero-terminate
+ to[to_len] = '\0';
+ return to;
+}
+
+//*** decoding ***//
+#define WRONG_CHAR 64
+
+static uint8_t decode_char(char c) {
+ uint8_t res;
+ assert(isalnum(c) || c == '+' || c == '/');
+ if (isupper(c))
+ res = c - 'A';
+ else if (islower(c))
+ res = c - 'a' + 26;
+ else if (isdigit(c))
+ res = c - '0' + 52;
+ else if (c == '+')
+ res = 62;
+ else if (c == '/')
+ res = 63;
+ else {
+ fprintf(stderr, "unsupported char: %c\n", c);
+ res = WRONG_CHAR;
+ }
+ return res;
+}
+
+static void decode_1byte(char *from, uint8_t *to) {
+ //read/decode 2 sextets
+ uint8_t s1 = decode_char(*from);
+ uint8_t s2 = decode_char(*(from + 1));
+ //check for error
+ assert(s1 != WRONG_CHAR);
+ assert(s2 != WRONG_CHAR);
+ //combine 2 sextets (12 bits) into single byte
+ uint8_t byte1 = (s1 << 2) | (s2 >> 4);
+ *to++ = byte1;
+}
+
+static void decode_2byte(char *from, uint8_t *to) {
+ //read/decode 3 sextets
+ uint8_t s1 = decode_char(*from);
+ uint8_t s2 = decode_char(*(from + 1));
+ uint8_t s3 = decode_char(*(from + 2));
+ //check for error
+ assert(s1 != WRONG_CHAR);
+ assert(s2 != WRONG_CHAR);
+ assert(s3 != WRONG_CHAR);
+ //combine 3 sextets (18 bits) into single byte
+ uint8_t byte1 = (s1 << 2) | (s2 >> 4);
+ uint8_t byte2 = (s2 << 4) | (s3 >> 2);
+ *to++ = byte1;
+ *to++ = byte1;
+}
+
+static void decode_3byte(char *from, uint8_t *to) {
+ //read/decode 4 sextets
+ uint8_t s1 = decode_char(*from);
+ uint8_t s2 = decode_char(*(from + 1));
+ uint8_t s3 = decode_char(*(from + 2));
+ uint8_t s4 = decode_char(*(from + 3));
+ //check for error
+ assert(s1 != WRONG_CHAR);
+ assert(s2 != WRONG_CHAR);
+ assert(s3 != WRONG_CHAR);
+ assert(s4 != WRONG_CHAR);
+ //combine 4 sextets (24 bits) into single byte
+ uint8_t byte1 = (s1 << 2) | (s2 >> 4);
+ uint8_t byte2 = (s2 << 4) | (s3 >> 2);
+ uint8_t byte3 = (s3 << 6) | s4;
+ *to++ = byte1;
+ *to++ = byte1;
+ *to++ = byte3;
+}
+
+uint8_t *base64_decode(char *from, size_t *len) {
+ assert(from != NULL && len != NULL);
+ size_t text_len = strlen(from);
+ //risky assumption data is properly padded...
+ //so always use 4-character blocks
+ assert(text_len % 4 == 0);
+ //analyze padding...
+ char last = from[text_len - 1], pre_last = from[text_len - 2];
+ int last_block_len = 3;
+ if (last == '=')
+ last_block_len = (pre_last == '=') ? 1 : 2;
+ //determine size of decoded bytes
+ size_t bytes_len = (text_len / 4 - 1) * 3 + last_block_len;
+ uint8_t *to = malloc(bytes_len);
+ if (to == NULL) {
+ perror("malloc");
+ return NULL;
+ }
+ //read 4-bytes and write 3-bytes on each loop
+ unsigned long i;
+ for (i = 0; i < text_len / 4 - 1; i++)
+ decode_3byte(&from[4 * i], &to[3 * i]);
+ //handle last block (ideally with padding)
+ if (last_block_len == 3)
+ decode_3byte(&from[4 * i], &to[3 * i]);
+ else if (last_block_len == 1)
+ decode_1byte(&from[4 * i], &to[3 * i]);
+ else if (last_block_len == 2)
+ decode_2byte(&from[4 * i], &to[3 * i]);
+ *len = bytes_len;
+ return to;
+}
diff --git a/util/base64.h b/util/base64.h
new file mode 100644
index 0000000..85279de
--- /dev/null
+++ b/util/base64.h
@@ -0,0 +1,25 @@
+#include <stdint.h>
+#include <stddef.h>
+
+typedef uint8_t sextet;
+static size_t base64_encoded_length(size_t bytes_len);
+static char encode_char(sextet s);
+static void encode_1byte(uint8_t byte1, char *encoded);
+static void encode_2byte(uint8_t byte1, uint8_t byte2, char *encoded);
+static void encode_3byte(uint8_t byte1, uint8_t byte2, uint8_t byte3, char *encoded);
+/*
+ * encodes to BASE64, returns pointer to newly allocated
+ * zero-terminated string or NULL if error.
+ * make sure to free() string!!
+ */
+char *base64_encode(uint8_t *from, size_t len);
+static uint8_t decode_char(char c);
+static void decode_1byte(char *from, uint8_t *to);
+static void decode_2byte(char *from, uint8_t *to);
+static void decode_3byte(char *from, uint8_t *to);
+/*
+ * accept a NULL-terminated string, decode it as BASE64,
+ * returns a pointer to newly allocated byte array or NULL
+ * if error. writes the size of array to *len.
+ */
+uint8_t *base64_decode(char *from, size_t *len);
diff --git a/util/endian.c b/util/endian.c
new file mode 100644
index 0000000..ea3549a
--- /dev/null
+++ b/util/endian.c
@@ -0,0 +1,10 @@
+#include <stdlib.h>
+#include "endian.h"
+
+uint8_t *bytes_le_order(uint64_t in) {
+ uint8_t *res_ptr = malloc(8);
+ uint8_t *in_ptr = (uint8_t *) &in;
+ for (int i = 0; i < 8; i ++)
+ res_ptr[i] = is_big_endian() ? in_ptr[8 - i] : in_ptr[i];
+ return res_ptr;
+}
diff --git a/util/endian.h b/util/endian.h
new file mode 100644
index 0000000..014703f
--- /dev/null
+++ b/util/endian.h
@@ -0,0 +1,7 @@
+#include <stdint.h>
+
+static const uint16_t be_test = 1;
+#define is_big_endian() ((* (char *) &be_test) == 0)
+
+//returns bytes in little endian order (smallest first)
+uint8_t *bytes_le_order(uint64_t in);
diff --git a/util/hamming.c b/util/hamming.c
new file mode 100644
index 0000000..d9a1aad
--- /dev/null
+++ b/util/hamming.c
@@ -0,0 +1,49 @@
+#include <assert.h>
+#include <string.h>
+#include "hamming.h"
+
+/*
+ * precalculated number 1-bits in corresponding bytes from 0 to 255 or
+ * (00000000 -> 0) to (11111111 -> 8). formatted as a readable 16x16 table.
+ * see htpps://en.wikipedia.org/wiki/Hamming_weight for more.
+ * precalculated table version is not most efficient approach,
+ * but simplest by use of 'precalculate_pop_count'.
+ */
+static size_t table[] = {
+//0 1 2 3 4 5 6 7 8 9 A B C D E F
+ 0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4, //0x0
+ 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5, //0x1
+ 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5, //0x2
+ 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6, //0x3
+ 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5, //0x4
+ 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6, //0x5
+ 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6, //0x6
+ 3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7, //0x7
+ 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5, //0x8
+ 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6, //0x9
+ 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6, //0xA
+ 3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7, //0xB
+ 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6, //0xC
+ 3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7, //0xD
+ 3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7, //0xE
+ 4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8 //0xF
+};
+
+size_t pop_count(uint8_t byte) {
+ return table[byte];
+}
+
+size_t hamming_distance(char *s1, char *s2) {
+ size_t len1 = strlen(s1), len2 = strlen(s2), distance = 0;
+ assert(len1 == len2);
+ for (unsigned long i = 0; i < len1; i++)
+ distance += pop_count(s1[i] ^ s2[i]);
+ return distance;
+}
+
+size_t hamming_distance_bytes(uint8_t *b1, uint8_t *b2, size_t len) {
+ size_t distance = 0;
+ for (unsigned long i = 0; i < len; i++)
+ distance += pop_count(b1[i] ^ b2[i]);
+ return distance;
+}
diff --git a/util/hamming.h b/util/hamming.h
new file mode 100644
index 0000000..f9e382a
--- /dev/null
+++ b/util/hamming.h
@@ -0,0 +1,14 @@
+#include <stdint.h>
+#include <stddef.h>
+
+//returns number of 1-bits set in a byte.
+//(so called "population count".. see wikipedia)
+size_t pop_count(uint8_t byte);
+
+//takes two NULL-terminated strings of same length.
+//returns number of differing bits.
+size_t hamming_distance(char *s1, char *s2);
+
+//takes two byte arrays of same length & their length
+//returns number of differing bits.
+size_t hamming_distance_bytes(uint8_t *b1, uint8_t *b2, size_t len);
diff --git a/util/hex.c b/util/hex.c
new file mode 100644
index 0000000..dc446c8
--- /dev/null
+++ b/util/hex.c
@@ -0,0 +1,57 @@
+#include "hex.h"
+#include <assert.h>
+#include <stddef.h>
+#include <stdint.h>
+#include <stdlib.h>
+
+static uint8_t char_to_four_bits(char c) {
+ uint8_t res;
+ if (c >= '0' && c <= '9')
+ res = c - '0';
+ else if (c >= 'a' && c <= 'f')
+ res = c - 'a' + 10;
+ else if (c >= 'A' && c <= 'F')
+ res = c - 'A' + 10;
+ else {
+ fprintf(stderr, "to_byte: unrecognised hex char: %c\n", c);
+ res = 16;
+ }
+ return res;
+}
+
+static char four_bits_to_char(uint8_t b) {
+ assert(b < 16);
+ return "0123456789abcdef"[b];
+}
+
+uint8_t *read_hex(char *hex_str, size_t hex_len) {
+ assert(hex_len % 2 == 0);
+ size_t bytes_len = hex_len / 2;
+ uint8_t *bytes = malloc(bytes_len);
+ if (bytes == NULL)
+ return NULL;
+ for (unsigned long i = 0; i < bytes_len; i++) {
+ char c1 = hex_str[2 * i], c2 = hex_str[2 * i + 1];
+ uint8_t high = char_to_four_bits(c1), low = char_to_four_bits(c2);
+ if (high == 16 || low == 16) { //this is an error
+ free(bytes);
+ return NULL;
+ }
+ bytes[i] = high << 4 | low;
+ }
+ return bytes;
+}
+
+char *write_hex(uint8_t *bytes, size_t bytes_len) {
+ size_t hex_len = bytes_len * 2 + 1; // +1 because '\0'
+ char *hex = malloc(hex_len);
+ if (hex == NULL)
+ return NULL;
+ for (unsigned long i = 0; i < bytes_len; i++) {
+ uint8_t high = bytes[i] >> 4, low = bytes[i] & 0x0F;
+ hex[2 * i] = four_bits_to_char(high);
+ hex[2 * i + 1] = four_bits_to_char(low);
+ }
+ hex[hex_len - 1] = '\0';
+ return hex;
+}
diff --git a/util/hex.h b/util/hex.h
new file mode 100644
index 0000000..ba91103
--- /dev/null
+++ b/util/hex.h
@@ -0,0 +1,12 @@
+#include <stdint.h>
+#include <stdio.h>
+/*
+ * accepts null-terminated hex-string (ie. "4AE6" or "4ae6")
+ * which should contain even number of hex digits.
+ * return corresponding malloc'd byte buffer
+ * whose length is half of the input string's
+ */
+static uint8_t char_to_four_bits(char c);
+static char four_bits_to_char(uint8_t b);
+uint8_t *read_hex(char *hex_str, size_t hex_len);
+char *write_hex(uint8_t *bytes, size_t bytes_len);
diff --git a/util/io.c b/util/io.c
new file mode 100644
index 0000000..09a8aa0
--- /dev/null
+++ b/util/io.c
@@ -0,0 +1,76 @@
+#include <assert.h>
+#include <ctype.h>
+#include <stdlib.h>
+#include "io.h"
+
+uint8_t *get_file_contents(FILE *stream, size_t *len) {
+ assert(len != NULL && stream != NULL);
+ size_t num_bytes;
+ uint8_t *buffer;
+ //jump to eof to determine size
+ if (fseek(stream, 0, SEEK_END) == -1) {
+ perror("fseek");
+ return NULL;
+ }
+ long pos = ftell(stream);
+ if (pos == -1) {
+ perror("ftell");
+ return NULL;
+ } else
+ num_bytes = (size_t) pos;
+ //jump back to beginning
+ if (fseek(stream, 0, SEEK_SET) == -1) {
+ perror("fseek");
+ return NULL;
+ }
+ buffer = malloc(num_bytes);
+ if (buffer == NULL) {
+ perror("malloc");
+ return NULL;
+ }
+ if (fread(buffer, 1, num_bytes, stream) != num_bytes) {
+ fprintf(stderr, "fread() failed\n");
+ free(buffer);
+ return NULL;
+ }
+ *len = num_bytes;
+ return buffer;
+}
+
+char *read_non_space(FILE *stream) {
+ int c, ix = 0;
+ char *str = malloc(START_SZ); //this means we have START_SZ - 1 chars available
+ size_t remaining_chars = START_SZ - 1, buf_sz = START_SZ;
+ for (;;) {
+ c = fgetc(stream);
+ if (feof(stream))
+ break;
+ if (ferror(stream)) {
+ perror("fgetc");
+ return NULL;
+ }
+ if (isspace(c))
+ continue;
+ if (remaining_chars == 0) {
+ remaining_chars = buf_sz - 1;
+ if (buf_sz < MAX_SZ)
+ buf_sz *= 2;
+ else {
+ fprintf(stderr, "input larger than %ld bytes (too large)\n", MAX_SZ);
+ return NULL;
+ }
+ char *str_new = realloc(str, buf_sz);
+ if (str_new == NULL) {
+ free(str);
+ return NULL;
+ } else
+ str = str_new;
+ }
+ //append char to buffer
+ str[ix++] = c;
+ remaining_chars--;
+ }
+ //hopefully we've allocated enough space to append NULL-byte...
+ str[ix] = '\0';
+ return str;
+}
diff --git a/util/io.h b/util/io.h
new file mode 100644
index 0000000..893e56a
--- /dev/null
+++ b/util/io.h
@@ -0,0 +1,23 @@
+#include <stdint.h>
+#include <stdio.h>
+
+#define START_SZ 512
+#define MAX_SZ (1UL << 24)
+//^ 16MB buffer is largest we allow
+
+/*
+ * reads whole contents of a file as byte buffer.
+ * allocates new buffer with size equal to file length in bytes.
+ * writes a size of that buffer in '*len', then returns a pointer
+ * to that new buffer. fseek() is used to determine file size,
+ * so this won't work on streams lacking support for seek(), eg. pipes.
+ * returns NULL and prints an error message if anything goes wrong!!
+ */
+uint8_t *get_file_contents(FILE *stream, size_t *len);
+
+/*
+ * reads all non-spaces characters from the stream (although
+ * skips SPC, TAB, EOL) and returns a newly allocated
+ * NULL-terminated string, or NULL if something goes wrong.
+ */
+char *read_non_space(FILE *stream);
diff --git a/util/mersenne_twister.c b/util/mersenne_twister.c
new file mode 100644
index 0000000..2d3059f
--- /dev/null
+++ b/util/mersenne_twister.c
@@ -0,0 +1,68 @@
+/*
+ * base on pseudocode from
+ * https://en.wikipedia.org/wiki/Mersenne_Twister
+ * MT19937 version (32-bit word)
+ */
+
+#include "mersenne_twister.h"
+
+//MT-32 algorithm coefficients
+#define W 32UL
+#define N 624UL
+#define M 397UL
+#define R 31UL
+#define A 0x9908B0DFUL
+#define U 11UL
+#define D 0xFFFFFFFFUL
+#define S 7UL
+#define B 0x9D2C5680UL
+#define T 15UL
+#define C 0xEFC60000UL
+#define L 18UL
+#define F 1812433253UL //initialization constant
+
+//derived constants
+#define LOWER_MASK ((1UL << R) - 1)
+#define UPPER_MASK (~LOWER_MASK)
+
+//global state
+static uint32_t MT[N], idx = N + 1; //essentially unseeded
+
+//generate next 'N' values
+static void twist() {
+ for (uint32_t i = 0; i < N; i++) {
+ uint32_t x = (MT[i] & UPPER_MASK) + (MT[(i + 1) % N] & LOWER_MASK);
+ uint32_t x_a = x >> 1;
+ if ((x % 2) != 0)
+ x_a ^= A;
+ MT[i] = MT[(i + M) % N] ^ x_a;
+ }
+ idx = 0;
+}
+
+void set_state(uint32_t *new_state) {
+ idx = N;
+ for (uint32_t i = 0; i < N; i++)
+ MT[i] = *new_state++;
+}
+
+void seed(uint32_t seed) {
+ idx = N;
+ MT[0] = seed;
+ for (uint32_t i = 1; i < N; i++)
+ MT[i] = F * (MT[i - 1] ^ (MT[i - 1] >> (W - 2))) + i;
+}
+
+uint32_t extract() {
+ if (idx >= N) {
+ if (idx > N)
+ seed(5489); //default seed
+ twist();
+ }
+ uint32_t y = MT[idx++];
+ y ^= (y >> U) & D;
+ y ^= (y << S) & B;
+ y ^= (y << T) & C;
+ y ^= (y >> L);
+ return y;
+}
diff --git a/util/mersenne_twister.h b/util/mersenne_twister.h
new file mode 100644
index 0000000..dc2d3cf
--- /dev/null
+++ b/util/mersenne_twister.h
@@ -0,0 +1,5 @@
+#include <stdint.h>
+
+void seed(uint32_t seed);
+uint32_t extract();
+void set_state(uint32_t *new_state);
diff --git a/util/obj/aes.o b/util/obj/aes.o
new file mode 100644
index 0000000..bc408f1
--- /dev/null
+++ b/util/obj/aes.o
Binary files differ
diff --git a/util/obj/base64.o b/util/obj/base64.o
new file mode 100644
index 0000000..33e8b8e
--- /dev/null
+++ b/util/obj/base64.o
Binary files differ
diff --git a/util/obj/endian.o b/util/obj/endian.o
new file mode 100644
index 0000000..8a1a4d4
--- /dev/null
+++ b/util/obj/endian.o
Binary files differ
diff --git a/util/obj/hamming.o b/util/obj/hamming.o
new file mode 100644
index 0000000..305be89
--- /dev/null
+++ b/util/obj/hamming.o
Binary files differ
diff --git a/util/obj/hex.o b/util/obj/hex.o
new file mode 100644
index 0000000..702cbbe
--- /dev/null
+++ b/util/obj/hex.o
Binary files differ
diff --git a/util/obj/io.o b/util/obj/io.o
new file mode 100644
index 0000000..251d67d
--- /dev/null
+++ b/util/obj/io.o
Binary files differ
diff --git a/util/obj/pkcs7_padding.o b/util/obj/pkcs7_padding.o
new file mode 100644
index 0000000..018a155
--- /dev/null
+++ b/util/obj/pkcs7_padding.o
Binary files differ
diff --git a/util/obj/score.o b/util/obj/score.o
new file mode 100644
index 0000000..474d034
--- /dev/null
+++ b/util/obj/score.o
Binary files differ
diff --git a/util/obj/xor.o b/util/obj/xor.o
new file mode 100644
index 0000000..3971fc6
--- /dev/null
+++ b/util/obj/xor.o
Binary files differ
diff --git a/util/pkcs7_padding.c b/util/pkcs7_padding.c
new file mode 100644
index 0000000..99f79d6
--- /dev/null
+++ b/util/pkcs7_padding.c
@@ -0,0 +1,40 @@
+#include <assert.h>
+#include <stddef.h>
+#include <string.h>
+#include <stdlib.h>
+#include <inttypes.h>
+#include "pkcs7_padding.h"
+
+size_t calc_padding_len(size_t data_len, size_t block_len) {
+ return block_len - (data_len % block_len);
+}
+
+ssize_t add_padding(uint8_t *data, size_t data_len, size_t block_len, uint8_t **padded_data) {
+ size_t padding_len = calc_padding_len(data_len, block_len);
+ size_t padded_len = data_len + padding_len;
+ uint8_t *new_data;
+ assert(data && padded_data);
+ assert(data_len >= 0);
+ assert(block_len > 1 && block_len < 256); //refer to RFC-2315
+ new_data = malloc(padded_len);
+ if (new_data == NULL)
+ return -1;
+ (void) memcpy(new_data, data, data_len);
+ for (size_t i = 0; i < padded_len; i++)
+ new_data[i] = padding_len;
+ *padded_data = new_data;
+ return padded_len;
+}
+
+ssize_t padding_len(uint8_t *padded_data, size_t data_len) {
+ assert(padded_data);
+ if (data_len < 1)
+ return -1;
+ uint8_t n = padded_data[data_len - 1];
+ if (n > data_len || n == 0)
+ return -1;
+ for (unsigned int i = 2; i <= n; i++)
+ if (padded_data[data_len - i] != n)
+ return -1; //padding error... abort
+ return (ssize_t) n;
+}
diff --git a/util/pkcs7_padding.h b/util/pkcs7_padding.h
new file mode 100644
index 0000000..7677606
--- /dev/null
+++ b/util/pkcs7_padding.h
@@ -0,0 +1,20 @@
+#include <stdlib.h>
+#include <inttypes.h>
+
+size_t calc_padding_len(size_t data_len, size_t block_len);
+
+/*
+ * accepts a byte string, its length and 'block_len'.
+ * pads the byte string, allocates a new buffer to contain
+ * the string & the padding, copies data, appends padding
+ * bytes, and writes the result to '*padded_data'.
+ * returns size of the padded block or -1 if error.
+*/
+ssize_t add_padding(uint8_t *data, size_t data_len, size_t block_len, uint8_t **padded_data);
+
+/*
+ * accepts a byte string and its length. determines how much padding
+ * should be added to the string and returns number of bytes to be
+ * trimmed from the end of string, or -1 if error.
+*/
+ssize_t padding_len(uint8_t *padded_data, size_t data_len);
diff --git a/util/random.c b/util/random.c
new file mode 100644
index 0000000..b1a9081
--- /dev/null
+++ b/util/random.c
@@ -0,0 +1,6 @@
+#include <stdlib.h>
+#include "random.h"
+
+void init_with_random_bytes(unsigned char *data, size_t data_len) {
+ arc4random_buf(data, data_len);
+}
diff --git a/util/random.h b/util/random.h
new file mode 100644
index 0000000..096a60b
--- /dev/null
+++ b/util/random.h
@@ -0,0 +1,3 @@
+#include <stddef.h>
+
+void init_with_random_bytes(unsigned char *data, size_t data_len);
diff --git a/util/score.c b/util/score.c
new file mode 100644
index 0000000..ff5777c
--- /dev/null
+++ b/util/score.c
@@ -0,0 +1,116 @@
+#include <assert.h>
+#include <string.h>
+#include <stdlib.h>
+#include <ctype.h>
+#include <limits.h>
+#include "score.h"
+#include "hex.h"
+#include "xor.h"
+
+static int cmp_by_freq(const void *x, const void *y) {
+ const struct freq *sx = x;
+ const struct freq *sy = y;
+ return sy->freq - sx->freq; //descending order
+}
+
+static int char_canonical_order(char c) {
+ assert((c >= 'a' && c <= 'z') || c == ' ');
+ char canonical_order[] = FREQ_ORDER;
+ char *cp = strchr(canonical_order, c);
+ return cp - canonical_order;
+}
+
+/*
+ * this scoring function is based on frequency of english letters.
+ * we count occurences of all letters and space and sort them
+ * based on frequencies, producing a permutation of 26 letters (and Space character).
+ * then add up distances between positions of top N letters (20, for example (SIGNIFICANT_LETTERS constant)) of our orders
+ * with the canonical order.
+ */
+static int score_step(uint8_t *str, size_t len, int n, size_t start, size_t step) {
+ assert(str != NULL);
+ assert(n >= 1 && n <= ALPHABET_SZ + 1); //+1 for space character
+ struct freq f[ALPHABET_SZ + 1];
+ for (int i = 0; i < ALPHABET_SZ + 1; i++) {
+ struct freq j;
+ if (i == ALPHABET_SZ)
+ j.c = ' ';
+ else
+ j.c = 'a' + i;
+ j.freq = 0;
+ f[i] = j;
+ }
+ //count frequencies
+ int score = 0;
+ for (size_t i = start; i < len; i += step) {
+ char c = str[i];
+ if (c >= 'a' && c <= 'z')
+ f[c - 'a'].freq++;
+ else if (c >= 'A' && c <= 'Z')
+ f[c - 'A'].freq++;
+ else if (c == ' ')
+ f[ALPHABET_SZ].freq++;
+ else if (!ispunct(c))
+ score += n; //"penalty" for non-punctuation characters
+ }
+ //sort & calculate final score!
+ qsort(f, ALPHABET_SZ + 1, sizeof(struct freq), cmp_by_freq);
+ for (int i = 0; i < n; i++)
+ score += abs(char_canonical_order(f[i].c) - i);
+ return score;
+}
+
+static int score(uint8_t *str, size_t len, int n) {
+ return score_step(str, len, n, 0, 1);
+}
+
+int best_score_hex(char *hex_str, char **res_str) {
+ size_t hex_len = strlen(hex_str);
+ size_t bytes_len = hex_len / 2;
+ uint8_t *bytes = read_hex(hex_str, hex_len);
+ return best_score_raw(bytes, bytes_len, res_str);
+}
+
+int best_score_raw(uint8_t *bytes, size_t bytes_len, char **res_str) {
+ int min_score = INT_MAX;
+ uint8_t *best_string;
+ uint8_t cypher, key = 0;
+ for (;;) {
+ //xor them with key
+ uint8_t *xor_d = xor_with_byte_key(bytes, key, bytes_len);
+ //score string & check for improvement
+ int curr_score = score(xor_d, bytes_len, SIGNIFICANT_LETTERS);
+ if (curr_score < min_score) {
+ min_score = curr_score;
+ cypher = key;
+ best_string = xor_d;
+ } else
+ free(xor_d);
+ key++;
+ if (key == 0)
+ break; //pass complete
+ }
+ char *best_str_terminated = malloc(bytes_len + 1);
+ memcpy(best_str_terminated, best_string, bytes_len);
+ best_str_terminated[bytes_len] = '\0';
+ free(best_string);
+ *res_str = best_str_terminated;
+ return min_score;
+}
+
+uint8_t best_key_step(uint8_t *bytes, size_t bytes_len, size_t start, size_t step) {
+ int min_score = INT_MAX;
+ uint8_t best_key = 0, key = 0;
+ for (;;) {
+ uint8_t *xor_d = xor_with_byte_key(bytes, key, bytes_len);
+ int curr_score = score_step(xor_d, bytes_len, SIGNIFICANT_LETTERS, start, step);
+ if (curr_score < min_score) {
+ min_score = curr_score;
+ best_key = key;
+ }
+ free(xor_d);
+ if (++key == 0)
+ break; //pass complete
+ }
+ return best_key;
+}
diff --git a/util/score.h b/util/score.h
new file mode 100644
index 0000000..ce0eb31
--- /dev/null
+++ b/util/score.h
@@ -0,0 +1,39 @@
+#include <stdio.h>
+#include <stdint.h>
+
+#define ALPHABET_SZ 26
+#define SIGNIFICANT_LETTERS 20
+#define FREQ_ORDER " etaoinshrdlcumwfgypbvkjxqz"
+//^ see https://en.wikipedia.org/wiki/Letter_frequency
+
+struct freq {
+ char c;
+ int freq;
+};
+
+static int cmp_by_freq(const void *x, const void *y);
+static int char_canonical_order(char c);
+static int score_step(uint8_t *str, size_t len, int n, size_t start, size_t step);
+static int score(uint8_t *str, size_t len, int n);
+
+/*
+ * returns a best score for the encoded string in hex and inits
+ * res_str, which points to the best string.
+ * it is malloc'd (so free() it!!!)
+ * "score" is a measurement of how likely the input string is
+ * to be human readable. lower score == better
+ */
+int best_score_hex(char *hex_str, char **res_str);
+
+/*
+ * returns a best score for byte buffer and inits res_str,
+ * which points to the best string.
+ * it is malloc'd (so free() it!!!)
+ */
+int best_score_raw(uint8_t *bytes, size_t bytes_len, char **res_str);
+
+/*
+ * returns the key corresponding to the best score for byte buffer when
+ * only every step'th byte starting from byte 'start' is taken into accont
+ */
+uint8_t best_key_step(uint8_t *bytes, size_t bytes_len, size_t start, size_t step);
diff --git a/util/xor.c b/util/xor.c
new file mode 100644
index 0000000..231c943
--- /dev/null
+++ b/util/xor.c
@@ -0,0 +1,43 @@
+#include <assert.h>
+#include <stdlib.h>
+#include <string.h>
+#include "hex.h"
+#include "xor.h"
+
+uint8_t *xor(uint8_t *b1, uint8_t *b2, size_t len) {
+ uint8_t *res = malloc(len);
+ if (res == NULL) {
+ printf("out of bounds\n");
+ return NULL;
+ }
+ for (uint i = 0; i < len; i++)
+ res[i] = b1[i] ^ b2[i];
+ return res;
+}
+
+char *xor_hex(char *s1, char *s2) {
+ assert(strlen(s1) == strlen(s2));
+ size_t hex_len = strlen(s1), bytes_len = hex_len / 2;
+ uint8_t *b1 = read_hex(s1, hex_len);
+ uint8_t *b2 = read_hex(s2, hex_len);
+ uint8_t *res = xor(b1, b2, bytes_len);
+ return write_hex(res, bytes_len);
+}
+
+uint8_t *xor_with_byte_key(uint8_t *msg, uint8_t key, size_t len) {
+ return xor_with_repeating_key(msg, len, &key, 1);
+}
+
+uint8_t *xor_with_repeating_key(uint8_t *msg, size_t msg_len, uint8_t *key, size_t key_len) {
+ uint8_t *res = malloc(msg_len);
+ if (res == NULL) {
+ printf("out of bounds\n");
+ return NULL;
+ }
+ uint j = 0;
+ for (uint i = 0; i < msg_len; i++) {
+ res[i] = msg[i] ^ key[j];
+ j = (j + 1) % key_len;
+ }
+ return res;
+}
diff --git a/util/xor.h b/util/xor.h
new file mode 100644
index 0000000..fdf6a15
--- /dev/null
+++ b/util/xor.h
@@ -0,0 +1,27 @@
+#include <stdio.h>
+#include <inttypes.h>
+
+/*
+ * return bitwise xor of two byte buffers of the same length
+ * the resulting byte buffer is malloc'd (so free() it!!!)
+ */
+uint8_t *xor(uint8_t *b1, uint8_t *b2, size_t len);
+
+/*
+ * return bitwise xor of two buffers represented as hex strings
+ * result will be encoded as hex string. the resuling string
+ * is malloc'd (so free() it!!!)
+ */
+char *xor_hex(char *s1, char *s2);
+
+/*
+ * returns bitwise xor of a single byte key and provided byte message
+ * the resuling byte buffer is malloc'd (so free() it!!!)
+ */
+uint8_t *xor_with_byte_key(uint8_t *msg, uint8_t key, size_t len);
+
+/*
+ * returns bitwise xor of a single byte key and provided byte message
+ * the resuling byte buffer is malloc'd (so free() it!!!)
+ */
+uint8_t *xor_with_repeating_key(uint8_t *msg, size_t msg_len, uint8_t *key, size_t key_len);