Tools/keyfinder.c

   1 /*
   2  * Keyfinder - finds crypto keys, encrypted data and compressed data in files
   3  *             by analyzing the entropy of parts of the file.
   4  *
   5  * (c) 2005 by van Hauser / THC <vh@thc.org> www.thc.org
   6  * The GPL 2.0 applies to this code.
   7  *
   8  * Based on the paper "Playing hide and seek with stored keys" by Shamir and
   9  * van Someren. www.ncipher.com/products/files/papers/anguilla/keyhide2.pdf
  10  *
  11  * In my experiments I went however a different route to identify keys which
  12  * seems to be better when identifying keys.
  13  * The paper evaluates 60 byte chunks on their entropy, and depending on the
  14  * number of consecutive chunks with high entropies, this could be the key.
  15  * This tool evalutes the full key size for the entropy, increasing by an
  16  * approx 10% of the key size windows. Hence if the key is 1024 bit = 128 byte
  17  * long, the window size is 10, and the file size is 500 bytes, it looks at
  18  * the randomness from bytes 0-128, then 10-138, next 20-148 etc.
  19  * Additionally to measuring the entropy, I added checking for the
  20  * arithmetical mean, and detecting couting bytes up- and downwards in the
  21  * beginning, middle or end of the file.
  22  * By having three randomness checks and evaluating the full key size with a
  23  * sliding window, the best keyfinding measures are in place, and much better
  24  * than in the described paper.
  25  *
  26  * However still beware: you will 1) receive some false positives, and 2)
  27  * Keyfinder can not find the exact start/end region of the key, it will
  28  * usually be some bytes before or after the reported file area.
  29  *
  30  * For usage hints, type "keyfinder -h"
  31  *
  32  * To compile: gcc -o keyfinder keyfinder.c -lm
  33  *
  34  */
  35
  36 #include <stdio.h>
  37 #include <sys/types.h>
  38 #include <sys/stat.h>
  39 #include <fcntl.h>
  40 #include <unistd.h>
  41 #include <stdlib.h>
  42 #include <string.h>
  43 #include <ctype.h>
  44 #include <math.h>
  45
  46 #define MINIMUM_RANDOMNESS  85
  47 #define KEY_SIZE           128
  48 #define WINDOW_SIZE         10
  49 #define DUMP_ROWS           16
  50
  51 int minimal_randomness = MINIMUM_RANDOMNESS;
  52 char *prg;
  53 int ext_entropy;
  54 int ext_mean;
  55 int debug = 0;
  56
  57 void help() {
  58   printf("Keyfinder v1.0 (c) 2005 by van Hauser / THC <vh@thc.org> www.thc.org\n");
  59   printf("\nSyntax: %s [-k KEY_SIZE] [-w WINDOW_SIZE] [-r MINIMUM_RANDOMNESS] FILE\n", prg);
  60   printf("\nOptions:\n");
  61   printf("    -k KEY_SIZE            Key size to look for (default: %d byte [%d bit])\n", KEY_SIZE, KEY_SIZE * 8);
  62   printf("    -w WINDOW_SIZE         Window size to check (default: %d byte)\n", WINDOW_SIZE);
  63   printf("    -r MINIMUM_RANDOMNESS  Minimum %% of randomness for keys (default: %d%%)\n", MINIMUM_RANDOMNESS);
  64   printf("    -d                     Print debug output\n");
  65   printf("\nFinds binary crypto keys, crypto data and compressed data in files.\n");
  66   printf("The result is an indicator where the key could be, not a byte exact match.\n");
  67   printf("The randomness is calculated by the entropy, the arithmetic mean value and a\n");
  68   printf("counting check. Read more information in the header of the keyfinder.c file.\n");
  69   printf("Note:  If -k is specified but not -w, -w will be 10%% of -k.\n");
  70   printf("Hints: (1) the smaller -k, the smaller should be -r\n");
  71   printf("       (2) the smaller -r the more false positives\n");
  72   printf("       (3) -w should be 1/8 to 1/20 of -k\n");
  73   printf("       (4) -k values are 128/256/512 byte for RSA/asymmetric keys\n");
  74   printf("       (5) -k 512 -> -r 95; -k 128 -> -r 85 \n");
  75   exit(-1);
  76 }
  77
  78 /* Why is log2() in libm not working?? what a fucking #!+~$$!! */
  79 #define log2of10 3.32192809488736234787
  80 static double log2_(double x) {
  81  return (log2of10 * (log10(x)));
  82 }
  83
  84 void calculate_randomness(unsigned char *buf, int buflen) {
  85   double ent = 0.0;
  86   double mean = 0.0;
  87   double datasum = 0.0;
  88   unsigned long ccount[256];
  89   double prob[256];
  90   int i, j = 0;
  91
  92   for (i = 0; i < 256; i++)
  93     ccount[i] = 0;
  94
  95   for (i = 0; i < buflen; i++)
  96     ccount[buf[i]]++;
  97
  98   for (i = 0; i < 256; i++) {
  99     prob[i] = (double) ccount[i] / buflen;
 100     datasum += ((double) i) * ccount[i]; /**/
 101   }
 102
 103   for (i = 0; i < 256; i++) {
 104     if (prob[i] > 0.0) {
 105       ent += prob[i] * log2_((1.0 / prob[i]));
 106 //      printf("%f += %f * %f\n", ent, prob[i], log2_((1.0 / prob[i])));
 107     }
 108   }
 109
 110   mean = datasum / buflen; /**/
 111   ext_mean = (mean - 127.5) / 1.275;
 112   if (ext_mean < 0)
 113     ext_mean = ext_mean * -1;
 114   ext_mean = 100 - ext_mean;
 115
 116   ext_entropy = (ent * 100) / 8;
 117
 118   if (debug) {
 119     printf("Entropy: %f bits (8 is totally random)\n", ent);
 120     printf("Mean: %1.4f (127.5 is totally random)\n", mean);
 121   }
 122
 123   if (ext_entropy + ext_mean >= minimal_randomness) {
 124   /* check for counting in the beginning */
 125     for (i = 0; i < 8 && j == 0; i++)
 126       if (buf[i] + 1 != buf[i + 1])
 127         j = 1;
 128     if (j == 0)
 129       j = 2;
 130     if (j == 1)
 131       j = 0;
 132     for (i = 0; i < 8 && j == 0; i++)
 133       if (buf[i] - 1 != buf[i++ + 1])
 134         j = 1;
 135     if (j == 0)
 136       j = 2;
 137     if (j == 1)
 138       j = 0;
 139
 140     /* check for counting in the middle */
 141     for (i = 0; i < 8 && j == 0; i++)
 142       if (buf[((buflen/2) - i) - 4] != buf[((buflen/2) - i) - 3] + 1)
 143         j = 1;
 144     if (j == 0)
 145       j = 2;
 146     if (j == 1)
 147       j = 0;
 148     for (i = 0; i < 8 && j == 0; i++)
 149       if (buf[((buflen/2) - i) - 4] != buf[((buflen/2) - i) - 3] - 1)
 150         j = 1;
 151     if (j == 0)
 152       j = 2;
 153     if (j == 1)
 154       j = 0;
 155
 156     /* check for counting in the end */
 157     for (i = 1; i <= 8 && j == 0; i++)
 158       if (buf[buflen - i] != buf[(buflen - i) - 1] + 1)
 159         j = 1;
 160     if (j == 0)
 161       j = 2;
 162     if (j == 1)
 163       j = 0;
 164     for (i = 1; i <= 8 && j == 0; i++)
 165       if (buf[buflen - i] != buf[(buflen - i) - 1] - 1)
 166         j = 1;
 167     if (j == 0)
 168       j = 2;
 169     if (j == 1)
 170       j = 0;
 171
 172     if (j == 2) {
 173       if (debug)
 174         printf("Counting detected, false positive, ignoring...\n");
 175       ext_mean = 0;
 176       ext_entropy = 0;
 177     }
 178   }
 179 }
 180
 181 void dump_asciihex(unsigned char *string, int length, unsigned int offset) {
 182     unsigned char *p = (unsigned char *) string;
 183     unsigned char lastrow_data[16];
 184     unsigned int rows = length / DUMP_ROWS;
 185     unsigned int lastrow = length % DUMP_ROWS;
 186     unsigned int i, j;
 187
 188     for (i = 0; i < rows; i++) {
 189         printf("%08hx:  ", i * 16 + offset);
 190         for (j = 0; j < DUMP_ROWS; j++) {
 191             printf("%02x", p[(i * 16) + j]);
 192             if (j % 2 == 1)
 193                 printf(" ");
 194         }
 195         printf("   [ ");
 196         for (j = 0; j < DUMP_ROWS; j++) {
 197             if (isprint(p[(i * 16) + j]))
 198                 printf("%c", p[(i * 16) + j]);
 199             else
 200                 printf(".");
 201         }
 202         printf(" ]\n");
 203     }
 204     if (lastrow > 0) {
 205         memset(lastrow_data, 0, sizeof(lastrow_data));
 206         memcpy(lastrow_data, p + length - lastrow, lastrow);
 207         printf("%08hx:  ", i * 16 + offset);
 208         for (j = 0; j < lastrow; j++) {
 209             printf("%02x", p[(i * 16) + j]);
 210             if (j % 2 == 1)
 211                 printf(" ");
 212         }
 213         while(j < DUMP_ROWS) {
 214             printf("  ");
 215             if (j % 2 == 1)
 216                 printf(" ");
 217             j++;
 218         }
 219         printf("   [ ");
 220         for (j = 0; j < lastrow; j++) {
 221             if (isprint(p[(i * 16) + j]))
 222                 printf("%c", p[(i * 16) + j]);
 223             else
 224                 printf(".");
 225         }
 226         while(j < DUMP_ROWS) {
 227             printf(" ");
 228             j++;
 229         }
 230         printf(" ]\n");
 231     }
 232 }
 233
 234 void dump_found(char *buf, int key_size, unsigned int block_count, int entropy, int mean) {
 235   printf("Found at block %u (Entropy is %d%% | Mean Deviation is %d%% = %d%%):\n", block_count * 64, entropy, mean, (entropy + mean) / 2);
 236   dump_asciihex(buf, key_size, block_count * 64);
 237   printf("\n");
 238 }
 239
 240 int main(int argc, char *argv[]) {
 241   int key_size = KEY_SIZE;
 242   int window_size = 0;
 243   char *fn;
 244   FILE *f;
 245   char *buf;
 246   int i;
 247   int reading;
 248   unsigned int block_count = 0;
 249
 250   prg = argv[0];
 251
 252   if (argc < 2 || strcmp(argv[1], "-h") == 0 || strncmp(argv[1], "--h", 3) == 0)
 253     help();
 254
 255   while ((i = getopt(argc, argv, "dw:r:k:")) >= 0) {
 256     switch(i) {
 257       case 'd':
 258         debug = 1;
 259         break;
 260       case 'w':
 261         window_size = atoi(optarg);
 262         break;
 263       case 'r':
 264         minimal_randomness = atoi(optarg);
 265         break;
 266       case 'k':
 267         key_size = atoi(optarg);
 268         break;
 269       default:
 270         help();
 271     }
 272   }
 273
 274   if (key_size != KEY_SIZE) {
 275     if (window_size == 0)
 276       window_size = (key_size / 10) - 1;
 277   } else
 278     window_size = WINDOW_SIZE;
 279
 280   if (key_size < 20 || key_size > 65535 || window_size < 1 || window_size >= key_size || minimal_randomness < 1 || minimal_randomness > 99) {
 281     fprintf(stderr, "Error: Wrong Values! Limits: 20 < key_size  < 65535; 1 < window_size < key_size; 1 < minimal_randomness < 100\n");
 282     exit(-1);
 283   }
 284
 285   if (key_size < window_size * 8)
 286     fprintf(stderr, "Warning: The window size is too large, -w should be 1/8 to 1/16 of -k\n");
 287
 288   if (optind + 1 != argc)
 289     help();
 290
 291   fn = argv[argc - 1];
 292
 293   if ((f = fopen(fn, "r")) == NULL) {
 294     fprintf(stderr, "Error: Can not open file %s\n", fn);
 295     exit(-1);
 296   }
 297
 298   if ((buf = malloc(key_size + window_size)) == NULL) {
 299     fprintf(stderr, "Error: malloc() failed\n");
 300     exit(-1);
 301   }
 302   memset(buf, 0, key_size + window_size);
 303
 304   printf("Analyzing %s:\n", fn);
 305 //  if (debug)
 306     printf("[Key Size: %d byte/%d bit, Window Size: %d byte, Minimal Randomness: %d%%]\n", key_size, key_size * 8, window_size, minimal_randomness);
 307
 308   minimal_randomness = minimal_randomness * 2;
 309
 310   if ((reading = fread(buf, 1, key_size, f)) > 0) {
 311     calculate_randomness(buf, reading);
 312     if ((ext_entropy + ext_mean) >= minimal_randomness && reading == key_size)
 313       dump_found(buf, key_size, block_count, ext_entropy, ext_mean);
 314     if (reading == key_size)
 315       reading = window_size;
 316     while (!feof(f) && reading == window_size) {
 317       if ((reading = fread(buf + key_size, 1, window_size, f)) > 0) {
 318         ++block_count;
 319         memmove(buf, buf + reading, key_size);
 320         calculate_randomness(buf, key_size);
 321         if ((ext_entropy + ext_mean) >= minimal_randomness)
 322           dump_found(buf, key_size, block_count, ext_entropy, ext_mean);
 323       }
 324     }
 325   }
 326
 327   return 0;
 328 }