[TOOL] Keyfinder - Cryptographic Analyzing Tool

From: SecuriTeam (support_at_securiteam.com)
Date: 02/14/05

  • Next message: SecuriTeam: "[UNIX] Perl PerlIO_Debug() Buffer Overflow (Suidperl)" 
    To: list@securiteam.com
Date: 14 Feb 2005 13:33:12 +0200

    The following security advisory is sent to the securiteam mailing list, and can be found at the SecuriTeam web site: http://www.securiteam.com
    - - promotion

    The SecuriTeam alerts list - Free, Accurate, Independent.

    Get your security news from a reliable source.
    http://www.securiteam.com/mailinglist.html

    - - - - - - - - -

      Keyfinder - Cryptographic Analyzing Tool
    ------------------------------------------------------------------------

    SUMMARY

    DETAILS

    Keyfinder analyzes files for public/private keys, encrypted or compressed
    data. It identified such areas by measuring the entropy, arithmetical mean
    and counter checking, and dumps appropriate file sections.

    Tool code:
    /*
     * 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;
    }

    ADDITIONAL INFORMATION

    The information has been provided by THC.
    The original article can be found at: <http://www.thc.org/releases.php>
    http://www.thc.org/releases.php

    ========================================

    This bulletin is sent to members of the SecuriTeam mailing list.
    To unsubscribe from the list, send mail with an empty subject line and body to: list-unsubscribe@securiteam.com
    In order to subscribe to the mailing list, simply forward this email to: list-subscribe@securiteam.com

    ====================
    ====================

    DISCLAIMER:
    The information in this bulletin is provided "AS IS" without warranty of any kind.
    In no event shall we be liable for any damages whatsoever including direct, indirect, incidental, consequential, loss of business profits or special damages.

  • Next message: SecuriTeam: "[UNIX] Perl PerlIO_Debug() Buffer Overflow (Suidperl)"

    Relevant Pages