fsmcipher.c

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

// Byte type [0, 256)--used for conversion and some indices
typedef unsigned char uchar;

#define STATES 256

// State type--the type of an ephemeral state in the state machine
typedef struct s_state {
	uchar chmap[STATES];  // Map from inbyte -> outbyte
	uchar stmap[STATES];  // Map from inbyte -> next state
} state;

// Machine type (represents the key)
typedef struct s_machine {
	state states[STATES];  // Valid states in the machine
	uchar current;      // Current state index
} machine;

uchar rand_byte() {
	static FILE *urand = NULL;
	uchar buf;
	if(!urand) {
		urand = fopen("/dev/urandom", "rb");
	}
	fread(&buf, sizeof(char), 1, urand);
	return buf;
}

#define MACH_STATE(mach) ((mach)->states[(mach)->current])

// Do a round (encryption forward, decryption reverse)
uchar do_round(machine *mach, uchar inbyte) {
	// Follow to the next state
	uchar ret = MACH_STATE(mach).chmap[inbyte];
	mach->current = MACH_STATE(mach).stmap[inbyte];
	return ret;
}

// Reverse a machine -- alter it such that it permits decryption instead of encryption
void rev_mach(machine *mach) {
	int state, byte;
	uchar revch[STATES];  // Holds the actual reverse character mapping while it is being constructed
	uchar revst[STATES];  // Holds outbyte -> next state 
	
	// For each state...
	for(state = 0; state < STATES; state++) {
		// Construct the reversed mapping
		for(byte = 0; byte < STATES; byte++) {
			revch[mach->states[state].chmap[byte]] = byte;
			revst[mach->states[state].chmap[byte]] = mach->states[state].stmap[byte];
		}

		// ...and copy the reversed mapping into that state
		for(byte = 0; byte < STATES; byte++) {
			mach->states[state].chmap[byte] = revch[byte];
			mach->states[state].stmap[byte] = revst[byte];
		}
	}
}

// Initialize a machine to a new identity state
// WARNING: This machine does not perform effective confidentiality!
void init_mach(machine *mach) {
	int state, byte;
	
	for(state = 0; state < STATES; state++) {
		for(byte = 0; byte < STATES; byte++) {
			mach->states[state].chmap[byte] = byte;
			mach->states[state].stmap[byte] = byte;
		}
	}

	mach->current = 0;
}

// Initialize a machine to a new, random state (a new random key)
void rand_mach(machine *mach) {
	int iteration, st;
	uchar state, byte1, byte2, temp;
	uchar stmap[STATES];

	// Initialize the machine to an identity...
	init_mach(mach);

	// ...then start swapping values to make random permutations
	// (it is important that these maps remain permutations such that encodings are unique)
	// (The upper bound is arguable.)
	for(iteration = 0; iteration < STATES * STATES; iteration++) {
		state = rand_byte();

		// Choose characters to swap
		byte1 = rand_byte();
		byte2 = rand_byte();
		// ...actually swap
		temp = mach->states[state].chmap[byte1];
		mach->states[state].chmap[byte1] = mach->states[state].chmap[byte2];
		mach->states[state].chmap[byte2] = temp;
	}

	// For a given byte, to fix large numbers of one-cycles, each stmap entry
	// in a byte is set to be an element of a permutation of the entire number
	// of states. This is especially effective against highly adversarial data
	// with low entropy, but it is not theoretically sound for, e.g.,
	// short-period patterns of bytes. An attacker may be able to enumerate all
	// two-cycles (there are STATES^2 of them), determine which of these
	// correspond to two-cycles in the key, and use this to leak information
	// about the key.
	for(iteration = 0; iteration < STATES; iteration++) {
		for(st = 0; st < STATES; st++) {
			stmap[st] = st;
		}
permute:
		for(st = 0; st < STATES * 2; st++) {
			byte1 = rand_byte();
			byte2 = rand_byte();
			temp = stmap[byte1];
			stmap[byte1] = stmap[byte2];
			stmap[byte2] = temp;
		}
		for(st = 0; st < STATES - 1; st++) {
			mach->states[stmap[st]].stmap[iteration] = stmap[st + 1];
		}
		mach->states[stmap[STATES - 1]].stmap[iteration] = stmap[0];
	}
}

/*
uchar in_cycle_with(machine *mach, uchar state, uchar byte, int period) {
	uchar st = state;

	while(period-- > 0) {
		if((st = mach->states[st].stmap[byte]) == state) {
			return 1;
		}
	}

	return 0;
}

void whiten_mach(machine *mach) {
	int state, byte;
	uchar temp;

	// Key whitening: attempt to eliminate all 1 and 2 cycles in the key.
	// Ideally, try to build very long cycles.
whiten:
	for(state = 0; state < STATES; state++) {
		for(byte = 0; byte < STATES; byte++) {
			if(in_cycle_with(mach, state, byte, 16)) {
				mach->states[state].stmap[byte] = rand_byte();
				goto whiten;
			}
		}
	}
}
*/

int period_of(machine *mach, uchar in) {
	short count = 0;
	short visited[STATES] = {};

	while(1) {
		do_round(mach, in);
		if(visited[mach->current]) break;
		visited[mach->current] = ++count;
		if(count > STATES + 1) {
			fprintf(stderr, "BUG: ran out of states (count = %d) while finding period of byte %03d\n", count, (int) in);
			exit(7);
		}
	}

	return count - visited[mach->current] + 1;
}

void write_mach(machine *mach, FILE *out) {
	fwrite(mach, sizeof(machine), 1, out);
}

void read_mach(machine *mach, FILE *in) {
	fread(mach, sizeof(machine), 1, in);
}

void usage(void) {
	printf("Usage:\n"
		  " e <key>: Encrypt stdin to stdout\n"
		  " d <key>: Decrypt stdin to stdout\n"
		  " n: Write a new random key to stdout\n"
		  " i: Write an identity key to stdout\n"
		  " K <key>: Check a key\n");
}

int main(int argc, char **argv) {
	machine mach;
	FILE *key;
	char op;
	int byte;

	if(argc < 2) {
		printf("Improper number of arguments\n");
		usage();
		return 1;
	}

	op = argv[1][0];
	switch(op) {
		case 'e': case 'd':
			if(argc < 3) {
				printf("Missing key argument\n");
				usage();
				return 2;
			}
			key = fopen(argv[2], "rb");
			if(!key) {
				printf("Bad filename: %s\n", argv[2]);
				usage();
				return 3;
			}
			read_mach(&mach, key);
			if(op == 'd') {
				rev_mach(&mach);
			}
			while((byte = getchar()) != EOF) {
				putchar((int) do_round(&mach, (uchar) byte));
			}
			break;

		case 'n':
			fprintf(stderr, "Generating key...\n");
			rand_mach(&mach);
			fprintf(stderr, "Writing key...\n");
			write_mach(&mach, stdout);
			break;

		case 'i':
			init_mach(&mach);
			write_mach(&mach, stdout);
			break;

		case 'K':
			if(argc < 3) {
				printf("Missing key argument\n");
				usage();
				return 2;
			}
			key = fopen(argv[2], "rb");
			if(!key) {
				printf("Bad filename: %s\n", argv[2]);
				usage();
				return 3;
			}
			read_mach(&mach, key);
			{
				int min, max, absmin, absmax, period;
				int state;
				short min_hist[STATES + 1] = {}, max_hist[STATES + 1] = {};

				printf("Periods for constant sequences:\n");
				for(byte = 0; byte < STATES; byte++) {
					for(state = 0; state < STATES; state++) {
						mach.current = state;
						period = period_of(&mach, byte);
						if(state == 0) {
							min = period;
							max = period;
						}
						if(period < min) min = period;
						if(period > max) max = period;
					}

					printf("%03d: %03d/%03d\t", byte, min, max);
					if((byte + 1) % 8 == 0) putchar('\n');

					min_hist[min]++;
					max_hist[max]++;

					if(byte == 0) {
						absmin = min;
						absmax = max;
					}
					if(min < absmin) absmin = min;
					if(max > absmax) absmax = max;
				}

				printf("Absolute minimum/maximum period: %03d/%03d\n", absmin, absmax);
				printf("Minimum period histogram:\n");
				for(period = 0; period <= STATES; period++)
					if(min_hist[period] > 0)
						printf("%hd states have period %d\n", min_hist[period], period);
				printf("Maximum period histogram:\n");
				for(period = 0; period <= STATES; period++)
					if(max_hist[period] > 0)
						printf("%hd states have period %d\n", max_hist[period], period);
			}
			break;

		default:
			usage();
			return 1;
	}
	return 0;
}