/* tcrypt.c
 * Code to use TEA and XXT algorithms for hashing passwords.
 * It is well known that these algorithms are very bad for hashing.
 * This is especially true of TEA and especialyl using Davies-Meyer.
 *
 * But it hard to argue with the compactness of the algorithms.
 *
 * runs a set of tests to check the algorithms, you can use another TEA
 * implementation as teacrypt_other and uncomment a line for a better
 * comparison.
 */
/******************************************************************************/
/** EVERYTHING BELOW THIS LINE IS MINE ****************************************/
/******************************************************************************/
#include <assert.h>
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>

#define NR(x) (sizeof(x)/sizeof*(x))

#define RD_BE32(src, offset) (((src)[offset]*16777216L)|((src)[(offset)+1]*65536L)|((src)[(offset)+2]*256)|(src)[(offset)+3])
#define RD_LE32(src, offset) (((src)[(offset)+3]*16777216L)|((src)[(offset)+2]*65536L)|((src)[(offset)+1]*256)|(src)[offset])

static inline void teaenc(uint32_t v[2], uint32_t k[4]) {
	unsigned i;
	uint32_t delta=0x9e3779b9, sum=0;
	for(i=0;i<32;i++) {
		sum+=delta;
		v[0]+=((v[1]<<4)+k[0])^(v[1]+sum)^((v[1]>>5)+k[1]);
		v[1]+=((v[0]<<4)+k[2])^(v[0]+sum)^((v[0]>>5)+k[3]);
	}
}

#if 0
/* unpacks as ./0123456789a-zA-Z */
static inline void unpack(char *ret, uint32_t v[2]) {
	unsigned i;
	uint32_t curr;
	for(i=0,curr=v[0];i<11;i++,ret++) {
		*ret=curr&63;
		curr>>=6;

#if 1
	  	/* implementation I like best */
		if(i==0) curr|=v[1]<<(32-6); /* add another 6 bits to the buffer */
		if(i==5) curr=(v[1]>>(32-28)); /* add last 26 bits to the buffer, bottom two bits overlap */
#else
		/* one possible implementation */
		if(i==4) curr|=v[1]<<(32-30); /* add another 30 bits to the buffer */
		if(i==9) curr=(v[1]>>(32-4)); /* add last 4 bits to the buffer, top 0 padded */
#endif

		/* convert to a base64 system (this code only works for ASCII) */
		if(*ret>=0 && *ret<12) *ret+='.'; else
		if(*ret>=12 && *ret<38) *ret+='A'-12; else
		if(*ret>=38 && *ret<64) *ret+='a'-38;
	}
	*ret=0; /* null terminate */
}
#endif

/* unpacks as ./0123456789a-zA-Z
 * length is the number of 32-bit words */
static inline void unpack(char *ret, size_t length, uint32_t *v) {

#if 1
	uint32_t x; /* buffer for current value */
	int xlen, vlen;


	xlen=0;
	vlen=0;
	x=0;

	while(length>0 || xlen>0) {
		if(xlen<6) {
			if(length>0) {
				x|=(*v>>vlen)<<xlen;
				xlen+=16;
				vlen+=16;
				if(vlen>=32) {
					v++;
					length--;
					vlen=0;
				}
			} else {
				xlen=6; /* pad remaining */
			}
		}
		*ret=x&63;

		/* convert to a base64 system (this code only works for ASCII) */
		if(*ret>=0 && *ret<12) *ret+='.'; else
		if(*ret>=12 && *ret<38) *ret+='A'-12; else
		if(*ret>=38 && *ret<64) *ret+='a'-38;

		ret++;
		x>>=6;
		xlen-=6;
	}
	*ret=0;


#else
	unsigned i,
		p, /* number of bits used in v[i] */
		n, /* number of bits remaining in sum */
		sum; /* current value */

	for(i=0,n=0,p=0,sum=0;i<length;ret++,n-=6,sum>>=6) {
		if(n<6) {
			// printf("%s():need more (i=%d p=%d n=%d)\n", __func__, i, p, n);
			sum|=(v[i]>>p)<<n;
			p+=32-n;
			n=32;
			if(p>=32) {
				i++;
				p-=32;
				// printf("%s():next word (i=%d p=%d)\n", __func__, i, p);
			}
		}

		*ret=sum&63;
		/* convert to a base64 system (this code only works for ASCII) */
		if(*ret>=0 && *ret<12) *ret+='.'; else
		if(*ret>=12 && *ret<38) *ret+='A'-12; else
		if(*ret>=38 && *ret<64) *ret+='a'-38;
	}
	*ret=0;
#endif
}


static inline void load_saltpass(char *m, size_t len, const char *plaintext, const char salt[2]) {
	unsigned i;

	memset(m, 0, len);
	/* load salt */
	for(i=0;i<2;i++) {
		m[i]=salt[i];
	}
	/* load plaintext into remaining bytes, looping over them */
	for(;plaintext[i-2];i++) {
		int pos=i%len;
		/* swap nibbles of previous cell and add key */
		m[pos]=((m[pos]<<4)|((unsigned)m[pos]>>4))+plaintext[i-2];
	}
}

/* little endian version */
static inline void load_saltpass2(uint32_t k[4], const char *plaintext, const char salt[2]) {
	unsigned i;

	k[0]=k[1]=k[2]=k[3]=0; /* clear the key space */

	/* load salt */
	for(i=0;i<2;i++) {
		k[i/4]|=(uint32_t)salt[i]<<(8*i);
	}

	/* load plain text*/
	while(*plaintext) {
		/* TODO: swap nibbles */
		k[i/4]|=(uint32_t)*plaintext++<<(8*i);
		i=(i+1)%16;
	}

}

/* my implementation of a tea password hash.
 * NOTE: this algorithm is not secure
 * This is a degenerate case of Davies-Meyer:
 *   start hash is 0, we only use 1 message block, and h XOR 0 is a no-op
 */
const char *teacrypt(const char *plaintext, const char salt[2]) {
	static char ret[16];
	unsigned i;
	uint32_t k[4]; /* 128-bit key */
	uint32_t v[2]; /* encrypted value - 64-bit */

	load_saltpass(ret, NR(ret), plaintext, salt);

	/* load combined password and salt into key area */
	for(i=0;i<NR(k);i++) {
		k[i]=RD_LE32(ret, i*4);
	}

	// printf("--- KEY --- k: 0x%08x 0x%08x 0x%08x 0x%08x\n", k[0], k[1], k[2], k[3]);

	memset(ret, 0, sizeof ret); /* remove key data */

	memset(v, 0, sizeof v); /* start with a hash of 0 */

	teaenc(v, k); /* modifies v to encrypt it */

	memset(k, 0, sizeof k); /* remove key data */

	/* load salt */
	for(i=0;i<2;i++) {
		ret[i]=salt[i];
	}

	// printf("--- ENC --- v0: 0x%08x v1: 0x%08x\n", v[0], v[1]);

	unpack(ret+i, NR(v), v);
	return ret;
}

const char *teacrypt2(const char *plaintext, const char salt[2]) {
	static char ret[16];
	unsigned i;
	uint32_t k[4]; /* 128-bit key */
	uint32_t v[2]; /* encrypted value - 64-bit */

	load_saltpass2(k, plaintext, salt);

	// printf("--- KEY --- k: 0x%08x 0x%08x 0x%08x 0x%08x\n", k[0], k[1], k[2], k[3]);

	memset(ret, 0, sizeof ret); /* remove key data */

	memset(v, 0, sizeof v); /* start with a hash of 0 */

	teaenc(v, k); /* modifies v to encrypt it */

	memset(k, 0, sizeof k); /* remove key data */

	/* load salt */
	for(i=0;i<2;i++) {
		ret[i]=salt[i];
	}

	// printf("--- ENC --- v0: 0x%08x v1: 0x%08x\n", v[0], v[1]);

	unpack(ret+i, NR(v), v);
	return ret;
}

// #define MX ( (((z>>5)^(y<<2))+((y>>3)^(z<<4)))^((sum^y)+(k[(p&3)^e]^z)) )
// #define MX ( (z >> 5 ^ y << 2) + (y >> 3 ^ z << 4) ^ (sum ^ y) + (k[p & 3 ^ e] ^ z) )
// #define MX (z>>5^y<<2)+(y>>3^z<<4)^(sum^y)+(k[p&3^e]^z)
static inline void xxtenc(size_t length, uint32_t *v, uint32_t k[4]) {
	uint32_t z=v[length-1], y, sum=0, e;
	unsigned q, p;

	assert(length>1);

	// printf("%s():len=%d\n", __func__, length);
	// printf("--- KEY --- k: 0x%08x 0x%08x 0x%08x 0x%08x\n", k[0], k[1], k[2], k[3]);
	// printf("--- ENC --- v0: 0x%08x v1: 0x%08x\n", v[0], v[1]);

	/* 32 cycles for a length=2, which is 64 rounds */
	q=6+52/length;
	// printf("%s(): %d cycles (%d rounds)\n", __func__, q, q*length);
	while(q-->0) {
		sum+=0x9e3779b9; /* delta */
		e=sum>>2&3;
		for(p=0;p<=length-1;p++) {
			if(p<length-1) {
				y=v[p+1];
			} else {
				y=v[0];
			}
			v[p]+=(((z>>5)^(y<<2))+((y>>3)^(z<<4)))^((sum^y)+(k[(p&3)^e]^z));
			z=v[p];
		}
	}
}

/* This is a degenerate case of Davies-Meyer:
 *   start hash is 0, we only use 1 message block, and h XOR 0 is a no-op
 */
const char *xxtcrypt(const char *plaintext, const char *salt) {
	static char ret[16]; /* must be big enough to hold 128-bit key */
	uint32_t k[128/32]; /* 128-bit key */
	uint32_t v[2]; /* encrypted value - 64-bit*/
	unsigned i;

	load_saltpass(ret, NR(ret), plaintext, salt);

	/* load combined password and salt into key area */
	for(i=0;i<NR(k);i++) {
		k[i]=RD_LE32(ret, i*4);
	}

	memset(v, 0, sizeof v); /* start with a hash of 0 */

	memset(ret, 0, sizeof ret); /* remove key data */

	xxtenc(NR(v), v, k); /* modifies v to encrypt it */

	memset(k, 0, sizeof k); /* remove key data */

	/* load salt */
	for(i=0;i<2;i++) {
		ret[i]=salt[i];
	}

	unpack(ret+i, NR(v), v);
	return ret;
}

/* load keys returns new offset */
static inline unsigned load_k4(unsigned ofs, uint32_t k[4], const char *plaintext, size_t saltlen, const char *salt) {
	unsigned ki, i;

	ki=0;

	k[0]=k[1]=k[2]=k[3]=0; /* clear the key space */

	for(;ofs<saltlen;ofs++) {
		k[ki/4]|=(uint32_t)salt[ofs]<<(8*ki);
		ki=(ki+1)%(4*4); /* 4 bytes per word, 4 words per key */
	}

	for(i=ofs-saltlen;plaintext[i];i++,ofs++) {
		k[ki/4]|=(uint32_t)plaintext[i]<<(8*ki);
		ki=(ki+1)%(4*4); /* 4 bytes per word, 4 words per key */
	}
	return ofs;
}

#define XXT_CRYPT_GENSALT_LEN 6

/* */
char *xxtcrypt2(size_t max, char *dest, const char *plaintext, size_t saltlen, const char *salt, size_t bits, int format) {
	unsigned ofs, i;
	uint32_t k[128/32]; /* 128-bit key */
	uint32_t v[bits/32], lastv[bits/32]; /* encrypted value - 64-bit*/
	size_t magic_len;

	switch(format) {
		case 0: /* pretty format */
			if(bits<100) {
				magic_len=6+2;
			} else if(bits<1000) {
				magic_len=6+3;
			} else if(bits<10000) {
				magic_len=6+4;
			} else {
				printf("Excessive bits for a password hasher (bits=%d)\n", bits);
				return 0;
			}

			/* TODO: check max and fail if too short */
			if(max<magic_len+saltlen+1+(2+4*sizeof v)/3+1) {
				printf("won't fit!!\n");
				return 0;
			}
			break;
		case 1: /* most compact format - must know bits and saltlen beforehand */
			if(max<saltlen+(2+4*sizeof v)/3+1) {
				printf("won't fit!!\n");
				return 0;
			}
			break;
	}

	memset(v, 0, sizeof v); /* start with a hash of 0 */

	ofs=0;
	do {
		ofs=load_k4(ofs, k, plaintext, saltlen, salt); /* load next chunk */

		memcpy(lastv, v, sizeof v); /* copy the old value of v */
		xxtenc(NR(v), v, k); /* modifies v to encrypt it */
		for(i=0;i<NR(v);i++) {
			v[i]^=lastv[i]; /* the XOR step in Davies-Meyer */
		}
		// printf("bits=%d vsz=%d ofs=%d saltlen=%d\n", bits, NR(v), ofs, saltlen);
	} while(plaintext[ofs-saltlen]);

	memset(k, 0, sizeof k); /* remove key data */

	switch(format) {
		case 0: /* pretty format */
			/* place header and salt */
			i=snprintf(dest, max, "$sxxt%u$%.*s$", bits, saltlen, salt);
			break;
		case 1: /* most compact format - must know bits and saltlen beforehand */
			memcpy(dest, salt, saltlen);
			i=saltlen;
			break;
	}


	unpack(dest+i, NR(v), v);
	return dest;
}

#include <time.h>
/* fills with salt data */
void gensalt(size_t salt_len, char *salt, int (*rand_func)(void), unsigned randomitity) {
	unsigned randness, i, pool;

	/* pool starts with no randomness */
	pool=time(NULL);
	randness=0;

	for(i=0;i<salt_len;i++) {
		if(randness<64) {
			pool^=rand_func();
			randness+=randomitity; /* rand_func adds a certain amount of randness */
		}

		/* */
		salt[i]=pool%64;
		pool/=64;
		randness/=64;

		/* convert to a base64 system (this code only works for ASCII) */
		if(salt[i]>=0 && salt[i]<12) salt[i]+='.'; else
		if(salt[i]>=12 && salt[i]<38) salt[i]+='A'-12; else
		if(salt[i]>=38 && salt[i]<64) salt[i]+='a'-38;
	}
}

static void xxt_test(void) {
	const char *test_pass[] = {
		"hello",
		"tHIs Is A tEst",
		"",
		"    "
		"xxxxxxxxxxxxxxxxyyyyy",
	};
	const char test_salt[][2] = {
		"48",
		"ws",
	};
	const struct test_vectors_xxt64 {
		int pass_fl;
		uint32_t k[4], plain[2], cipher[2];
	} test_vectors_xxt64[] = {
		/* these are byteswapped and should fail */
		{ 0, { 0x00000000, 0x00000000, 0x00000000, 0x00000000 }, { 0x00000000, 0x00000000 }, { 0xab043705, 0x808c5d57 } },
		{ 0, { 0x01020408, 0x10204080, 0xfffefcf8, 0xf0e0c080 }, { 0x00000000, 0x00000000 }, { 0xd1e78be2, 0xc746728a } },
		{ 0, { 0x9e3779b9, 0x9b9773e9, 0xb979379e, 0x6b695156 }, { 0xffffffff, 0xffffffff }, { 0x67ed0ea8, 0xe8973fc5 } },
		{ 0, { 0x01020408, 0x10204080, 0xfffefcf8, 0xf0e0c080 }, { 0xfffefcf8, 0xf0e0c080 }, { 0x8c3707c0, 0x1c7fccc4 } },
		/* these should pass */
		{ 1, { 0x00000000, 0x00000000, 0x00000000, 0x00000000 }, { 0x00000000, 0x00000000 }, { 0x053704ab, 0x575d8c80 } },
		{ 1, { 0x08040201, 0x80402010, 0xf8fcfeff, 0x80c0e0f0 }, { 0x00000000, 0x00000000 }, { 0xe28be7d1, 0x8a7246c7 } },
		{ 1, { 0xb979379e, 0xe973979b, 0x9e3779b9, 0x5651696b }, { 0xffffffff, 0xffffffff }, { 0xa80eed67, 0xc53f97e8 } },
		{ 1, { 0x08040201, 0x80402010, 0xf8fcfeff, 0x80c0e0f0 }, { 0xf8fcfeff, 0x80c0e0f0 }, { 0xc007378c, 0xc4cc7f1c } },
	};

	const struct test_vectors_xxt128 {
		int pass_fl;
		uint32_t k[4], plain[4], cipher[4];
	} test_vectors_xxt128[] = {
		{ 1, { 0xaaaaaaaa, 0xaaaaaaaa, 0xaaaaaaaa, 0xaaaaaaaa }, { 0x08040201, 0x80402010, 0xf8fcfeff, 0x80c0e0f0 }, { 0x069fa1c0, 0x39d6b0eb, 0xf727aa25, 0xd0b2c64c } },
		{ 1, { 0xb979379e, 0xe973979b, 0x9e3779b9, 0x5651696b }, { 0x08040201, 0x80402010, 0xf8fcfeff, 0x80c0e0f0 }, { 0xfd15b801, 0xd194482e, 0x43da5535, 0x8a869d4c } },
	};

	unsigned i, j;

	for(i=0;i<NR(test_vectors_xxt64);i++) {
		uint32_t v[2];
		int pass_fl;
		memcpy(v, test_vectors_xxt64[i].plain, sizeof v);
		xxtenc(NR(v), v, test_vectors_xxt64[i].k);
		pass_fl=v[0]==test_vectors_xxt64[i].cipher[0] && v[1]==test_vectors_xxt64[i].cipher[1];
		/* some vectors are supposed to fail, they have a 0 pass_fl */
		if(pass_fl==test_vectors_xxt64[i].pass_fl) {
			printf("Vector #%u 64-bit passed.\n", i);
		} else {
			printf("Vector #%u 64-bit failed.\n", i);
			printf("--- ORG --- v0: 0x%08x v1: 0x%08x\n", test_vectors_xxt64[i].cipher[0], test_vectors_xxt64[i].cipher[1]);
			printf("--- GEN --- v0: 0x%08x v1: 0x%08x\n", v[0], v[1]);
		}
	}

	for(i=0;i<NR(test_vectors_xxt128);i++) {
		uint32_t v[4];
		int pass_fl;
		memcpy(v, test_vectors_xxt128[i].plain, sizeof v);
		xxtenc(NR(v), v, test_vectors_xxt128[i].k);
		pass_fl=
			v[0]==test_vectors_xxt128[i].cipher[0]
			&& v[1]==test_vectors_xxt128[i].cipher[1]
			&& v[2]==test_vectors_xxt128[i].cipher[2]
			&& v[3]==test_vectors_xxt128[i].cipher[3];

		/* some vectors are supposed to fail, they have a 0 pass_fl */
		if(pass_fl==test_vectors_xxt128[i].pass_fl) {
			printf("Vector #%u 128-bit passed.\n", i);
		} else {
			printf("Vector #%u 128-bit failed.\n", i);
			printf("--- ORG --- v0: 0x%08x 0x%08x 0x%08x 0x%08x\n",
				test_vectors_xxt128[i].cipher[0],
				test_vectors_xxt128[i].cipher[1],
				test_vectors_xxt128[i].cipher[2],
				test_vectors_xxt128[i].cipher[3]
			);
			printf("--- GEN --- v0: 0x%08x 0x%08x 0x%08x 0x%08x\n", v[0], v[1], v[2], v[3]);
		}
	}

	for(i=0;i<NR(test_salt);i++) {
		char buf[128];
		for(j=0;j<NR(test_pass);j++) {
			printf("S='%.2s' P='%s'\n", test_salt[i], test_pass[j]);
			// printf("	1 : %s\n", teacrypt_other(test_pass[j], test_salt[i]));     /* compare against */
			printf("	2a: %s\n", teacrypt(test_pass[j], test_salt[i]));
			printf("	2b: %s\n", teacrypt2(test_pass[j], test_salt[i]));
			printf("	3 : %s\n", xxtcrypt(test_pass[j], test_salt[i]));

			printf("	4a: %s\n", xxtcrypt2(sizeof buf, buf, test_pass[j], 2, test_salt[i], 64, 1));
			printf("	4b: %s\n", xxtcrypt2(sizeof buf, buf, test_pass[j], 2, test_salt[i], 64, 0));
			printf("	5a: %s\n", xxtcrypt2(sizeof buf, buf, test_pass[j], 2, test_salt[i], 128, 1));
			printf("	5b: %s\n", xxtcrypt2(sizeof buf, buf, test_pass[j], 2, test_salt[i], 128, 0));
		}
	}

	/* generate some salt values */
	srand((unsigned)time(NULL));
	for(i=0;i<8;i++) {
		char buf[16];
		memset(buf, 0, sizeof buf);
		gensalt(NR(buf), buf, rand, RAND_MAX/2);
		printf("generated: \"%.*s\"\n", NR(buf), buf);
	}
}

int main(void) {
	xxt_test();
	return 0;
}