Information wants to be free...

Cracker for XOR-Encrypted Binary Files

There is weakness that may appear when XOR-encrypting binary files. Many kinds of binary files contains lots of NULL-characters, meaning the encryption key will inadvertently be revealed at these locations, due to the nature of the XOR operation.

I hacked together a small program that uses Markov chains to look for repeats in printable characters. The result of the program is a string that may contain the encryption key, if the key is susceptible to this kind of "attack".

Take a look at the code:

#include <stdio.h>
#include <stdlib.h>

#define FILTER_FROM 0x20
#define FILTER_TO 0x7e
#define RANGE ((FILTER_TO - FILTER_FROM) + 1)

/* For tuning. */
#define PASS_LIMIT 64
#define DIVIDE 1.1

typedef struct markov_s {
  int count;
  char current;
  char next;
} markov_t;

static markov_t chains[RANGE * RANGE];

static int markov_cmp(const void *p1, const void *p2)
{
  if (((markov_t *)p1)->count < ((markov_t *)p2)->count)
    return 1;
  else if (((markov_t *)p1)->count > ((markov_t *)p2)->count)
    return -1;
  else
    return 0;
}

static char markov_next(markov_t *chain, char current)
{
  int i;

  for (i = 0; i < (RANGE * RANGE); i++) {
    if (chain[i].current == current) {
      chain[i].count /= DIVIDE; /* Divide possibilty. */
      return chain[i].next;
    }
  }
  
  return -1;
}

int main(void)
{
  int current, next, limit;

  for (current = FILTER_FROM; current <= FILTER_TO; current++) {
    for (next = FILTER_FROM; next <= FILTER_TO; next++) {
      chains[((current - 0x20) * RANGE) + (next - 0x20)].count = 0;
      chains[((current - 0x20) * RANGE) + (next - 0x20)].current = current;
      chains[((current - 0x20) * RANGE) + (next - 0x20)].next = next;
    }
  }

  while ((current = fgetc(stdin)) != EOF) {
    if (current >= 0x20 && current <= 0x7e)
      break;
  }
  if (current == EOF)
    return 1;

  while ((next = fgetc(stdin)) != EOF) {
    if (next >= 0x20 && next <= 0x7e) {
      chains[((current - 0x20) * RANGE) + (next - 0x20)].count++;
      current = next;
    }
  }

  qsort(chains, RANGE * RANGE, sizeof(markov_t), markov_cmp);

  current = chains[0].current;
  for (limit = 0; limit < PASS_LIMIT; limit++) {
    printf("%c", current);
    current = markov_next(chains, current);
    /* Sort again after division. */
    qsort(chains, RANGE * RANGE, sizeof(markov_t), markov_cmp);
    if (current == -1)
      break;
  }
  printf("\n");

  return 0;
}
          


Topic: Scripts and Code, by Kjetil @ 01/12-2012, Article Link