diff options
Diffstat (limited to 'util')
-rw-r--r-- | util/aes.c | 150 | ||||
-rw-r--r-- | util/aes.h | 40 | ||||
-rw-r--r-- | util/base64.c | 194 | ||||
-rw-r--r-- | util/base64.h | 25 | ||||
-rw-r--r-- | util/endian.c | 10 | ||||
-rw-r--r-- | util/endian.h | 7 | ||||
-rw-r--r-- | util/hamming.c | 49 | ||||
-rw-r--r-- | util/hamming.h | 14 | ||||
-rw-r--r-- | util/hex.c | 57 | ||||
-rw-r--r-- | util/hex.h | 12 | ||||
-rw-r--r-- | util/io.c | 76 | ||||
-rw-r--r-- | util/io.h | 23 | ||||
-rw-r--r-- | util/mersenne_twister.c | 68 | ||||
-rw-r--r-- | util/mersenne_twister.h | 5 | ||||
-rw-r--r-- | util/obj/aes.o | bin | 0 -> 6456 bytes | |||
-rw-r--r-- | util/obj/base64.o | bin | 0 -> 7880 bytes | |||
-rw-r--r-- | util/obj/endian.o | bin | 0 -> 1616 bytes | |||
-rw-r--r-- | util/obj/hamming.o | bin | 0 -> 4376 bytes | |||
-rw-r--r-- | util/obj/hex.o | bin | 0 -> 3128 bytes | |||
-rw-r--r-- | util/obj/io.o | bin | 0 -> 3696 bytes | |||
-rw-r--r-- | util/obj/pkcs7_padding.o | bin | 0 -> 2744 bytes | |||
-rw-r--r-- | util/obj/score.o | bin | 0 -> 4624 bytes | |||
-rw-r--r-- | util/obj/xor.o | bin | 0 -> 2968 bytes | |||
-rw-r--r-- | util/pkcs7_padding.c | 40 | ||||
-rw-r--r-- | util/pkcs7_padding.h | 20 | ||||
-rw-r--r-- | util/random.c | 6 | ||||
-rw-r--r-- | util/random.h | 3 | ||||
-rw-r--r-- | util/score.c | 116 | ||||
-rw-r--r-- | util/score.h | 39 | ||||
-rw-r--r-- | util/xor.c | 43 | ||||
-rw-r--r-- | util/xor.h | 27 |
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 *) ∈ + 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 Binary files differnew file mode 100644 index 0000000..bc408f1 --- /dev/null +++ b/util/obj/aes.o diff --git a/util/obj/base64.o b/util/obj/base64.o Binary files differnew file mode 100644 index 0000000..33e8b8e --- /dev/null +++ b/util/obj/base64.o diff --git a/util/obj/endian.o b/util/obj/endian.o Binary files differnew file mode 100644 index 0000000..8a1a4d4 --- /dev/null +++ b/util/obj/endian.o diff --git a/util/obj/hamming.o b/util/obj/hamming.o Binary files differnew file mode 100644 index 0000000..305be89 --- /dev/null +++ b/util/obj/hamming.o diff --git a/util/obj/hex.o b/util/obj/hex.o Binary files differnew file mode 100644 index 0000000..702cbbe --- /dev/null +++ b/util/obj/hex.o diff --git a/util/obj/io.o b/util/obj/io.o Binary files differnew file mode 100644 index 0000000..251d67d --- /dev/null +++ b/util/obj/io.o diff --git a/util/obj/pkcs7_padding.o b/util/obj/pkcs7_padding.o Binary files differnew file mode 100644 index 0000000..018a155 --- /dev/null +++ b/util/obj/pkcs7_padding.o diff --git a/util/obj/score.o b/util/obj/score.o Binary files differnew file mode 100644 index 0000000..474d034 --- /dev/null +++ b/util/obj/score.o diff --git a/util/obj/xor.o b/util/obj/xor.o Binary files differnew file mode 100644 index 0000000..3971fc6 --- /dev/null +++ b/util/obj/xor.o 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); |