--- /dev/null
+/*
+ * Keyfinder - finds crypto keys, encrypted data and compressed data in files
+ * by analyzing the entropy of parts of the file.
+ *
+ * (c) 2005 by van Hauser / THC <vh@thc.org> www.thc.org
+ * The GPL 2.0 applies to this code.
+ *
+ * Based on the paper "Playing hide and seek with stored keys" by Shamir and
+ * van Someren. www.ncipher.com/products/files/papers/anguilla/keyhide2.pdf
+ *
+ * In my experiments I went however a different route to identify keys which
+ * seems to be better when identifying keys.
+ * The paper evaluates 60 byte chunks on their entropy, and depending on the
+ * number of consecutive chunks with high entropies, this could be the key.
+ * This tool evalutes the full key size for the entropy, increasing by an
+ * approx 10% of the key size windows. Hence if the key is 1024 bit = 128 byte
+ * long, the window size is 10, and the file size is 500 bytes, it looks at
+ * the randomness from bytes 0-128, then 10-138, next 20-148 etc.
+ * Additionally to measuring the entropy, I added checking for the
+ * arithmetical mean, and detecting couting bytes up- and downwards in the
+ * beginning, middle or end of the file.
+ * By having three randomness checks and evaluating the full key size with a
+ * sliding window, the best keyfinding measures are in place, and much better
+ * than in the described paper.
+ *
+ * However still beware: you will 1) receive some false positives, and 2)
+ * Keyfinder can not find the exact start/end region of the key, it will
+ * usually be some bytes before or after the reported file area.
+ *
+ * For usage hints, type "keyfinder -h"
+ *
+ * To compile: gcc -o keyfinder keyfinder.c -lm
+ *
+ */
+
+#include <stdio.h>
+#include <sys/types.h>
+#include <sys/stat.h>
+#include <fcntl.h>
+#include <unistd.h>
+#include <stdlib.h>
+#include <string.h>
+#include <ctype.h>
+#include <math.h>
+
+#define MINIMUM_RANDOMNESS 85
+#define KEY_SIZE 128
+#define WINDOW_SIZE 10
+#define DUMP_ROWS 16
+
+int minimal_randomness = MINIMUM_RANDOMNESS;
+char *prg;
+int ext_entropy;
+int ext_mean;
+int debug = 0;
+
+void help() {
+ printf("Keyfinder v1.0 (c) 2005 by van Hauser / THC <vh@thc.org> www.thc.org\n");
+ printf("\nSyntax: %s [-k KEY_SIZE] [-w WINDOW_SIZE] [-r MINIMUM_RANDOMNESS] FILE\n", prg);
+ printf("\nOptions:\n");
+ printf(" -k KEY_SIZE Key size to look for (default: %d byte [%d bit])\n", KEY_SIZE, KEY_SIZE * 8);
+ printf(" -w WINDOW_SIZE Window size to check (default: %d byte)\n", WINDOW_SIZE);
+ printf(" -r MINIMUM_RANDOMNESS Minimum %% of randomness for keys (default: %d%%)\n", MINIMUM_RANDOMNESS);
+ printf(" -d Print debug output\n");
+ printf("\nFinds binary crypto keys, crypto data and compressed data in files.\n");
+ printf("The result is an indicator where the key could be, not a byte exact match.\n");
+ printf("The randomness is calculated by the entropy, the arithmetic mean value and a\n");
+ printf("counting check. Read more information in the header of the keyfinder.c file.\n");
+ printf("Note: If -k is specified but not -w, -w will be 10%% of -k.\n");
+ printf("Hints: (1) the smaller -k, the smaller should be -r\n");
+ printf(" (2) the smaller -r the more false positives\n");
+ printf(" (3) -w should be 1/8 to 1/20 of -k\n");
+ printf(" (4) -k values are 128/256/512 byte for RSA/asymmetric keys\n");
+ printf(" (5) -k 512 -> -r 95; -k 128 -> -r 85 \n");
+ exit(-1);
+}
+
+/* Why is log2() in libm not working?? what a fucking #!+~$$!! */
+#define log2of10 3.32192809488736234787
+static double log2_(double x) {
+ return (log2of10 * (log10(x)));
+}
+
+void calculate_randomness(unsigned char *buf, int buflen) {
+ double ent = 0.0;
+ double mean = 0.0;
+ double datasum = 0.0;
+ unsigned long ccount[256];
+ double prob[256];
+ int i, j = 0;
+
+ for (i = 0; i < 256; i++)
+ ccount[i] = 0;
+
+ for (i = 0; i < buflen; i++)
+ ccount[buf[i]]++;
+
+ for (i = 0; i < 256; i++) {
+ prob[i] = (double) ccount[i] / buflen;
+ datasum += ((double) i) * ccount[i]; /**/
+ }
+
+ for (i = 0; i < 256; i++) {
+ if (prob[i] > 0.0) {
+ ent += prob[i] * log2_((1.0 / prob[i]));
+// printf("%f += %f * %f\n", ent, prob[i], log2_((1.0 / prob[i])));
+ }
+ }
+
+ mean = datasum / buflen; /**/
+ ext_mean = (mean - 127.5) / 1.275;
+ if (ext_mean < 0)
+ ext_mean = ext_mean * -1;
+ ext_mean = 100 - ext_mean;
+
+ ext_entropy = (ent * 100) / 8;
+
+ if (debug) {
+ printf("Entropy: %f bits (8 is totally random)\n", ent);
+ printf("Mean: %1.4f (127.5 is totally random)\n", mean);
+ }
+
+ if (ext_entropy + ext_mean >= minimal_randomness) {
+ /* check for counting in the beginning */
+ for (i = 0; i < 8 && j == 0; i++)
+ if (buf[i] + 1 != buf[i + 1])
+ j = 1;
+ if (j == 0)
+ j = 2;
+ if (j == 1)
+ j = 0;
+ for (i = 0; i < 8 && j == 0; i++)
+ if (buf[i] - 1 != buf[i++ + 1])
+ j = 1;
+ if (j == 0)
+ j = 2;
+ if (j == 1)
+ j = 0;
+
+ /* check for counting in the middle */
+ for (i = 0; i < 8 && j == 0; i++)
+ if (buf[((buflen/2) - i) - 4] != buf[((buflen/2) - i) - 3] + 1)
+ j = 1;
+ if (j == 0)
+ j = 2;
+ if (j == 1)
+ j = 0;
+ for (i = 0; i < 8 && j == 0; i++)
+ if (buf[((buflen/2) - i) - 4] != buf[((buflen/2) - i) - 3] - 1)
+ j = 1;
+ if (j == 0)
+ j = 2;
+ if (j == 1)
+ j = 0;
+
+ /* check for counting in the end */
+ for (i = 1; i <= 8 && j == 0; i++)
+ if (buf[buflen - i] != buf[(buflen - i) - 1] + 1)
+ j = 1;
+ if (j == 0)
+ j = 2;
+ if (j == 1)
+ j = 0;
+ for (i = 1; i <= 8 && j == 0; i++)
+ if (buf[buflen - i] != buf[(buflen - i) - 1] - 1)
+ j = 1;
+ if (j == 0)
+ j = 2;
+ if (j == 1)
+ j = 0;
+
+ if (j == 2) {
+ if (debug)
+ printf("Counting detected, false positive, ignoring...\n");
+ ext_mean = 0;
+ ext_entropy = 0;
+ }
+ }
+}
+
+void dump_asciihex(unsigned char *string, int length, unsigned int offset) {
+ unsigned char *p = (unsigned char *) string;
+ unsigned char lastrow_data[16];
+ unsigned int rows = length / DUMP_ROWS;
+ unsigned int lastrow = length % DUMP_ROWS;
+ unsigned int i, j;
+
+ for (i = 0; i < rows; i++) {
+ printf("%08hx: ", i * 16 + offset);
+ for (j = 0; j < DUMP_ROWS; j++) {
+ printf("%02x", p[(i * 16) + j]);
+ if (j % 2 == 1)
+ printf(" ");
+ }
+ printf(" [ ");
+ for (j = 0; j < DUMP_ROWS; j++) {
+ if (isprint(p[(i * 16) + j]))
+ printf("%c", p[(i * 16) + j]);
+ else
+ printf(".");
+ }
+ printf(" ]\n");
+ }
+ if (lastrow > 0) {
+ memset(lastrow_data, 0, sizeof(lastrow_data));
+ memcpy(lastrow_data, p + length - lastrow, lastrow);
+ printf("%08hx: ", i * 16 + offset);
+ for (j = 0; j < lastrow; j++) {
+ printf("%02x", p[(i * 16) + j]);
+ if (j % 2 == 1)
+ printf(" ");
+ }
+ while(j < DUMP_ROWS) {
+ printf(" ");
+ if (j % 2 == 1)
+ printf(" ");
+ j++;
+ }
+ printf(" [ ");
+ for (j = 0; j < lastrow; j++) {
+ if (isprint(p[(i * 16) + j]))
+ printf("%c", p[(i * 16) + j]);
+ else
+ printf(".");
+ }
+ while(j < DUMP_ROWS) {
+ printf(" ");
+ j++;
+ }
+ printf(" ]\n");
+ }
+}
+
+void dump_found(char *buf, int key_size, unsigned int block_count, int entropy, int mean) {
+ printf("Found at block %u (Entropy is %d%% | Mean Deviation is %d%% = %d%%):\n", block_count * 64, entropy, mean, (entropy + mean) / 2);
+ dump_asciihex(buf, key_size, block_count * 64);
+ printf("\n");
+}
+
+int main(int argc, char *argv[]) {
+ int key_size = KEY_SIZE;
+ int window_size = 0;
+ char *fn;
+ FILE *f;
+ char *buf;
+ int i;
+ int reading;
+ unsigned int block_count = 0;
+
+ prg = argv[0];
+
+ if (argc < 2 || strcmp(argv[1], "-h") == 0 || strncmp(argv[1], "--h", 3) == 0)
+ help();
+
+ while ((i = getopt(argc, argv, "dw:r:k:")) >= 0) {
+ switch(i) {
+ case 'd':
+ debug = 1;
+ break;
+ case 'w':
+ window_size = atoi(optarg);
+ break;
+ case 'r':
+ minimal_randomness = atoi(optarg);
+ break;
+ case 'k':
+ key_size = atoi(optarg);
+ break;
+ default:
+ help();
+ }
+ }
+
+ if (key_size != KEY_SIZE) {
+ if (window_size == 0)
+ window_size = (key_size / 10) - 1;
+ } else
+ window_size = WINDOW_SIZE;
+
+ if (key_size < 20 || key_size > 65535 || window_size < 1 || window_size >= key_size || minimal_randomness < 1 || minimal_randomness > 99) {
+ fprintf(stderr, "Error: Wrong Values! Limits: 20 < key_size < 65535; 1 < window_size < key_size; 1 < minimal_randomness < 100\n");
+ exit(-1);
+ }
+
+ if (key_size < window_size * 8)
+ fprintf(stderr, "Warning: The window size is too large, -w should be 1/8 to 1/16 of -k\n");
+
+ if (optind + 1 != argc)
+ help();
+
+ fn = argv[argc - 1];
+
+ if ((f = fopen(fn, "r")) == NULL) {
+ fprintf(stderr, "Error: Can not open file %s\n", fn);
+ exit(-1);
+ }
+
+ if ((buf = malloc(key_size + window_size)) == NULL) {
+ fprintf(stderr, "Error: malloc() failed\n");
+ exit(-1);
+ }
+ memset(buf, 0, key_size + window_size);
+
+ printf("Analyzing %s:\n", fn);
+// if (debug)
+ printf("[Key Size: %d byte/%d bit, Window Size: %d byte, Minimal Randomness: %d%%]\n", key_size, key_size * 8, window_size, minimal_randomness);
+
+ minimal_randomness = minimal_randomness * 2;
+
+ if ((reading = fread(buf, 1, key_size, f)) > 0) {
+ calculate_randomness(buf, reading);
+ if ((ext_entropy + ext_mean) >= minimal_randomness && reading == key_size)
+ dump_found(buf, key_size, block_count, ext_entropy, ext_mean);
+ if (reading == key_size)
+ reading = window_size;
+ while (!feof(f) && reading == window_size) {
+ if ((reading = fread(buf + key_size, 1, window_size, f)) > 0) {
+ ++block_count;
+ memmove(buf, buf + reading, key_size);
+ calculate_randomness(buf, key_size);
+ if ((ext_entropy + ext_mean) >= minimal_randomness)
+ dump_found(buf, key_size, block_count, ext_entropy, ext_mean);
+ }
+ }
+ }
+
+ return 0;
+}
projects / oweals / thc-archive.git / blobdiff