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;
}