/*
 * StuffIt 1-4 Password Cracker
 * written by Claude
 *
 * This code is released to the public domain.
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <signal.h>
#include <err.h>

/* character set for brute force is all printable ASCII */
static const char charset[] =
    "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!@#$%^&*()-_=+[]{}|;:',.<>?/`~ ";

typedef struct {
	uint32_t subkeys[16][2];
} StuffItDESKeySchedule;

unsigned long long total_tested = 0;
char last_password[9] = { 0 };
StuffItDESKeySchedule initial_ks;
int initial_ks_ready = 0;

void siginfo_handler(int sig);
void usage(char *p);
int parse_hex(const char *hex, uint8_t *out, size_t len);
uint32_t ReverseBits(uint32_t val);
int test_password(const uint8_t mkey[8], const uint8_t passblock[8]);
void brute_force(const uint8_t mkey[8], uint8_t *passblock, int pos, int max_len);
static void StuffItDESSetKey(const uint8_t key[8], StuffItDESKeySchedule *ks);
static inline void Encrypt(uint32_t *left, uint32_t right, uint32_t *subkey);
static void StuffItDESCrypt(uint8_t data[8], StuffItDESKeySchedule *ks, int enc);

int
main(int argc, char **argv)
{
	uint8_t mkey[8];
	uint8_t passblock[9] = {0};
	int wflag = 0;
	int min_len = -1, max_len = -1;

	if (argc < 2)
		usage(argv[0]);

	if (parse_hex(argv[1], mkey, 8) != 0)
		errx(1, "mkey must be 16 hex characters");

	if (argc == 3 && strcmp(argv[2], "-w") == 0)
		wflag = 1;
	else if (argc == 4) {
		min_len = atoi(argv[2]);
		max_len = atoi(argv[3]);
		if (min_len < 1)
			errx(1, "invalid min value");
		if (max_len > 8)
			errx(1, "invalid max value");
		if (min_len > max_len)
			errx(1, "min cannot be greater than max");
	} else
		usage(argv[0]);

	signal(SIGINFO, siginfo_handler);

	/* wordlist mode */
	if (wflag) {
		char line[256];

		while (fgets(line, sizeof(line), stdin)) {
			size_t len = strlen(line);
			if (len > 0 && line[len-1] == '\n')
				line[--len] = 0;
			if (len > 0 && line[len-1] == '\r')
				line[--len] = 0;
			if (len > 8)
				len = 8;

			memset(passblock, 0, sizeof(passblock));
			memcpy(passblock, line, len);

			/* for SIGINFO */
			strncpy(last_password, line, 8);
			last_password[8] = 0;

			total_tested++;
			if (test_password(mkey, passblock))
				printf("%s\n", line);
		}
		return 0;
	}

	/* brute force mode */
	for (int len = min_len; len <= max_len; len++) {
		memset(passblock, 0, sizeof(passblock));
		brute_force(mkey, passblock, 0, len);
	}

	return 0;
}

void
siginfo_handler(int sig)
{
	(void)sig;
	warnx("tested %llu passwords, last: %s", total_tested, last_password);
}

void
usage(char *p)
{
	printf("StuffIt 1-4 archive password cracker\n");
	printf("\n");
	printf("Usage:\n");
	printf("  %s <mkey_hex> <min> <max> - brute force length range\n", p);
	printf("  %s <mkey_hex> -w          - read passwords from stdin\n", p);
	printf("\n");
	printf("mkey_hex are 16 hex characters from the archive's 'MKey' "
	    "in its resource fork.\n");
	printf("\n");
	printf("Examples:\n");
	printf("\tgzip -cd rockyou.txt.gz | %s 590e0f73e71c9b60 -w\n", p);
	printf("\t%s 590e0f73e71c9b60 3 8\n", p);
	printf("\n");
	printf("Multiple passwords may verify against the hash, but will not "
	    "unlock the\n");
	printf("archive (and will likely crash StuffIt).  Let this keep "
	    "running while\n");
	printf("you try the most likely of the passwords found.\n");
	exit(1);
}


int
parse_hex(const char *hex, uint8_t *out, size_t len)
{
	if (strlen(hex) != len * 2)
		return -1;

	for (size_t i = 0; i < len; i++) {
		int hi, lo;
		char c;

		c = hex[i * 2];
		if (c >= '0' && c <= '9')
			hi = c - '0';
		else if (c >= 'a' && c <= 'f')
			hi = c - 'a' + 10;
		else if (c >= 'A' && c <= 'F')
			hi = c - 'A' + 10;
		else
			return -1;

		c = hex[i * 2 + 1];
		if (c >= '0' && c <= '9')
			lo = c - '0';
		else if (c >= 'a' && c <= 'f')
			lo = c - 'a' + 10;
		else if (c >= 'A' && c <= 'F')
			lo = c - 'A' + 10;
		else
			return -1;

		out[i] = (hi << 4) | lo;
	}

	return 0;
}

int
test_password(const uint8_t mkey[8], const uint8_t passblock[8])
{
	StuffItDESKeySchedule ks;
	uint8_t archivekey[8], archiveiv[8], verifyblock[8];
	static const uint8_t initialkey[8] = {
		0x01, 0x23, 0x45, 0x67, 0x89, 0xab, 0xcd, 0xef
	};

	for (int i = 0; i < 8; i++)
		archivekey[i] = initialkey[i] ^ (passblock[i] & 0x7f);

	/* Initialize key schedule for initial key (once) */
	if (!initial_ks_ready) {
		StuffItDESSetKey(initialkey, &initial_ks);
		initial_ks_ready = 1;
	}

	/* Encrypt archive key with initial key */
	StuffItDESCrypt(archivekey, &initial_ks, 1);

	/* Decrypt MKey to get archive IV */
	memcpy(archiveiv, mkey, 8);
	StuffItDESSetKey(archivekey, &ks);
	StuffItDESCrypt(archiveiv, &ks, 0);

	/* Verify: encrypt first 4 bytes of IV + {0,0,0,4} */
	memcpy(verifyblock, archiveiv, 4);
	verifyblock[4] = verifyblock[5] = verifyblock[6] = 0;
	verifyblock[7] = 4;
	StuffItDESCrypt(verifyblock, &ks, 1);

	/* Check last 4 bytes match */
	return memcmp(verifyblock + 4, archiveiv + 4, 4) == 0;
}

void
brute_force(const uint8_t mkey[8], uint8_t *passblock, int pos, int max_len)
{
	int i;

	if (pos > 0) {
		for (i = 0; i < 8; i++)
			last_password[i] = passblock[i];
		last_password[8] = 0;

		if (test_password(mkey, passblock)) {
			/* found a match - convert to printable string */
			char pwd[9] = { 0 };
			for (i = 0; i < 8 && passblock[i]; i++)
				pwd[i] = passblock[i];
			printf("%s\n", pwd);
		}
		total_tested++;
	}

	if (pos >= max_len)
		return;

	for (i = 0; i < (int)sizeof(charset) - 1; i++) {
		passblock[pos] = charset[i];
		passblock[pos + 1] = 0;
		brute_force(mkey, passblock, pos + 1, max_len);
	}
	passblock[pos] = 0;
}

static inline
uint32_t RotateRight(uint32_t val, int n)
{
	return (val >> n) | (val << (32 - n));
}

uint32_t
ReverseBits(uint32_t val)
{
	val = ((val >> 1) & 0x55555555) | ((val & 0x55555555) << 1);
	val = ((val >> 2) & 0x33333333) | ((val & 0x33333333) << 2);
	val = ((val >> 4) & 0x0F0F0F0F) | ((val & 0x0F0F0F0F) << 4);
	val = ((val >> 8) & 0x00FF00FF) | ((val & 0x00FF00FF) << 8);
	return (val >> 16) | (val << 16);
}

static inline uint32_t Nibble(const uint8_t key[8], int n)
{
	return (key[(n & 0x0f) >> 1] >> (((n ^ 1) & 1) << 2)) & 0x0f;
}

static const uint32_t DES_SPtrans[8][64] = {
	{0x02080800,0x00080000,0x02000002,0x02080802,0x02000000,0x00080802,0x00080002,0x02000002,0x00080802,0x02080800,0x02080000,0x00000802,0x02000802,0x02000000,0x00000000,0x00080002,0x00080000,0x00000002,0x02000800,0x00080800,0x02080802,0x02080000,0x00000802,0x02000800,0x00000002,0x00000800,0x00080800,0x02080002,0x00000800,0x02000802,0x02080002,0x00000000,0x00000000,0x02080802,0x02000800,0x00080002,0x02080800,0x00080000,0x00000802,0x02000800,0x02080002,0x00000800,0x00080800,0x02000002,0x00080802,0x00000002,0x02000002,0x02080000,0x02080802,0x00080800,0x02080000,0x02000802,0x02000000,0x00000802,0x00080002,0x00000000,0x00080000,0x02000000,0x02000802,0x02080800,0x00000002,0x02080002,0x00000800,0x00080802},
	{0x40108010,0x00000000,0x00108000,0x40100000,0x40000010,0x00008010,0x40008000,0x00108000,0x00008000,0x40100010,0x00000010,0x40008000,0x00100010,0x40108000,0x40100000,0x00000010,0x00100000,0x40008010,0x40100010,0x00008000,0x00108010,0x40000000,0x00000000,0x00100010,0x40008010,0x00108010,0x40108000,0x40000010,0x40000000,0x00100000,0x00008010,0x40108010,0x00100010,0x40108000,0x40008000,0x00108010,0x40108010,0x00100010,0x40000010,0x00000000,0x40000000,0x00008010,0x00100000,0x40100010,0x00008000,0x40000000,0x00108010,0x40008010,0x40108000,0x00008000,0x00000000,0x40000010,0x00000010,0x40108010,0x00108000,0x40100000,0x40100010,0x00100000,0x00008010,0x40008000,0x40008010,0x00000010,0x40100000,0x00108000},
	{0x04000001,0x04040100,0x00000100,0x04000101,0x00040001,0x04000000,0x04000101,0x00040100,0x04000100,0x00040000,0x04040000,0x00000001,0x04040101,0x00000101,0x00000001,0x04040001,0x00000000,0x00040001,0x04040100,0x00000100,0x00000101,0x04040101,0x00040000,0x04000001,0x04040001,0x04000100,0x00040101,0x04040000,0x00040100,0x00000000,0x04000000,0x00040101,0x04040100,0x00000100,0x00000001,0x00040000,0x00000101,0x00040001,0x04040000,0x04000101,0x00000000,0x04040100,0x00040100,0x04040001,0x00040001,0x04000000,0x04040101,0x00000001,0x00040101,0x04000001,0x04000000,0x04040101,0x00040000,0x04000100,0x04000101,0x00040100,0x04000100,0x00000000,0x04040001,0x00000101,0x04000001,0x00040101,0x00000100,0x04040000},
	{0x00401008,0x10001000,0x00000008,0x10401008,0x00000000,0x10400000,0x10001008,0x00400008,0x10401000,0x10000008,0x10000000,0x00001008,0x10000008,0x00401008,0x00400000,0x10000000,0x10400008,0x00401000,0x00001000,0x00000008,0x00401000,0x10001008,0x10400000,0x00001000,0x00001008,0x00000000,0x00400008,0x10401000,0x10001000,0x10400008,0x10401008,0x00400000,0x10400008,0x00001008,0x00400000,0x10000008,0x00401000,0x10001000,0x00000008,0x10400000,0x10001008,0x00000000,0x00001000,0x00400008,0x00000000,0x10400008,0x10401000,0x00001000,0x10000000,0x10401008,0x00401008,0x00400000,0x10401008,0x00000008,0x10001000,0x00401008,0x00400008,0x00401000,0x10400000,0x10001008,0x00001008,0x10000000,0x10000008,0x10401000},
	{0x08000000,0x00010000,0x00000400,0x08010420,0x08010020,0x08000400,0x00010420,0x08010000,0x00010000,0x00000020,0x08000020,0x00010400,0x08000420,0x08010020,0x08010400,0x00000000,0x00010400,0x08000000,0x00010020,0x00000420,0x08000400,0x00010420,0x00000000,0x08000020,0x00000020,0x08000420,0x08010420,0x00010020,0x08010000,0x00000400,0x00000420,0x08010400,0x08010400,0x08000420,0x00010020,0x08010000,0x00010000,0x00000020,0x08000020,0x08000400,0x08000000,0x00010400,0x08010420,0x00000000,0x00010420,0x08000000,0x00000400,0x00010020,0x08000420,0x00000400,0x00000000,0x08010420,0x08010020,0x08010400,0x00000420,0x00010000,0x00010400,0x08010020,0x08000400,0x00000420,0x00000020,0x00010420,0x08010000,0x08000020},
	{0x80000040,0x00200040,0x00000000,0x80202000,0x00200040,0x00002000,0x80002040,0x00200000,0x00002040,0x80202040,0x00202000,0x80000000,0x80002000,0x80000040,0x80200000,0x00202040,0x00200000,0x80002040,0x80200040,0x00000000,0x00002000,0x00000040,0x80202000,0x80200040,0x80202040,0x80200000,0x80000000,0x00002040,0x00000040,0x00202000,0x00202040,0x80002000,0x00002040,0x80000000,0x80002000,0x00202040,0x80202000,0x00200040,0x00000000,0x80002000,0x80000000,0x00002000,0x80200040,0x00200000,0x00200040,0x80202040,0x00202000,0x00000040,0x80202040,0x00202000,0x00200000,0x80002040,0x80000040,0x80200000,0x00202040,0x00000000,0x00002000,0x80000040,0x80002040,0x80202000,0x80200000,0x00002040,0x00000040,0x80200040},
	{0x00004000,0x00000200,0x01000200,0x01000004,0x01004204,0x00004004,0x00004200,0x00000000,0x01000000,0x01000204,0x00000204,0x01004000,0x00000004,0x01004200,0x01004000,0x00000204,0x01000204,0x00004000,0x00004004,0x01004204,0x00000000,0x01000200,0x01000004,0x00004200,0x01004004,0x00004204,0x01004200,0x00000004,0x00004204,0x01004004,0x00000200,0x01000000,0x00004204,0x01004000,0x01004004,0x00000204,0x00004000,0x00000200,0x01000000,0x01004004,0x01000204,0x00004204,0x00004200,0x00000000,0x00000200,0x01000004,0x00000004,0x01000200,0x00000000,0x01000204,0x01000200,0x00004200,0x00000204,0x00004000,0x01004204,0x01000000,0x01004200,0x00000004,0x00004004,0x01004204,0x01000004,0x01004200,0x01004000,0x00004004},
	{0x20800080,0x20820000,0x00020080,0x00000000,0x20020000,0x00800080,0x20800000,0x20820080,0x00000080,0x20000000,0x00820000,0x00020080,0x00820080,0x20020080,0x20000080,0x20800000,0x00020000,0x00820080,0x00800080,0x20020000,0x20820080,0x20000080,0x00000000,0x00820000,0x20000000,0x00800000,0x20020080,0x20800080,0x00800000,0x00020000,0x20820000,0x00000080,0x00800000,0x00020000,0x20000080,0x20820080,0x00020080,0x20000000,0x00000000,0x00820000,0x20800080,0x20020080,0x20020000,0x00800080,0x20820000,0x00000080,0x00800080,0x20020000,0x20820080,0x00800000,0x20800000,0x20000080,0x00820000,0x00020080,0x20020080,0x20800000,0x00000080,0x20820000,0x00820080,0x00000000,0x20000000,0x20800080,0x00020000,0x00820080}
};

static void
StuffItDESSetKey(const uint8_t key[8], StuffItDESKeySchedule *ks)
{
	for (int i = 0; i < 16; i++) {
		uint32_t subkey1 = ((Nibble(key, i) >> 2) | (Nibble(key, i + 13) << 2));
		subkey1 |= ((Nibble(key, i + 11) >> 2) | (Nibble(key, i + 6) << 2)) << 8;
		subkey1 |= ((Nibble(key, i + 3) >> 2) | (Nibble(key, i + 10) << 2)) << 16;
		subkey1 |= ((Nibble(key, i + 8) >> 2) | (Nibble(key, i + 1) << 2)) << 24;
		uint32_t subkey0 = ((Nibble(key, i + 9) | (Nibble(key, i) << 4)) & 0x3f);
		subkey0 |= ((Nibble(key, i + 2) | (Nibble(key, i + 11) << 4)) & 0x3f) << 8;
		subkey0 |= ((Nibble(key, i + 14) | (Nibble(key, i + 3) << 4)) & 0x3f) << 16;
		subkey0 |= ((Nibble(key, i + 5) | (Nibble(key, i + 8) << 4)) & 0x3f) << 24;
		ks->subkeys[i][0] = ReverseBits(subkey1);
		ks->subkeys[i][1] = ReverseBits(subkey0);
	}
}

static inline
void Encrypt(uint32_t *left, uint32_t right, uint32_t *subkey)
{
	uint32_t u = right ^ subkey[0];
	uint32_t t = RotateRight(right, 4) ^ subkey[1];
	*left ^= DES_SPtrans[0][(u >> 2) & 0x3f] ^ DES_SPtrans[2][(u >> 10) & 0x3f] ^
	         DES_SPtrans[4][(u >> 18) & 0x3f] ^ DES_SPtrans[6][(u >> 26) & 0x3f] ^
	         DES_SPtrans[1][(t >> 2) & 0x3f] ^ DES_SPtrans[3][(t >> 10) & 0x3f] ^
	         DES_SPtrans[5][(t >> 18) & 0x3f] ^ DES_SPtrans[7][(t >> 26) & 0x3f];
}

static inline
uint32_t ReadBE32(const uint8_t *p)
{
	return ((uint32_t)p[0] << 24) | ((uint32_t)p[1] << 16) | ((uint32_t)p[2] << 8) | p[3];
}

static inline
void WriteBE32(uint8_t *p, uint32_t v)
{
	p[0] = (v >> 24);
	p[1] = (v >> 16);
	p[2] = (v >> 8);
	p[3] = v;
}

static void
StuffItDESCrypt(uint8_t data[8], StuffItDESKeySchedule *ks, int enc)
{
	uint32_t left = ReverseBits(ReadBE32(&data[0]));
	uint32_t right = ReverseBits(ReadBE32(&data[4]));

	right = RotateRight(right, 29);
	left = RotateRight(left, 29);

	if (enc) {
		for (int i = 0; i < 16; i += 2) {
			Encrypt(&left, right, ks->subkeys[i]);
			Encrypt(&right, left, ks->subkeys[i + 1]);
		}
	} else {
		for (int i = 15; i > 0; i -= 2) {
			Encrypt(&left, right, ks->subkeys[i]);
			Encrypt(&right, left, ks->subkeys[i - 1]);
		}
	}

	left = RotateRight(left, 3);
	right = RotateRight(right, 3);

	WriteBE32(&data[0], ReverseBits(right));
	WriteBE32(&data[4], ReverseBits(left));
}