/*
 * Portable C version of des() function
 *
 * Written by Phil Karn, put in the public domain [http://ka9q.net/code/des/]
 *
 * The code implementing the (DES-based) crypt() function was
 * written by Peter Bex in 2011. No copyright is claimed on that
 * code either.  This entire file falls under the public domain.
 */
#ifndef CRYPT_DES_C
#define CRYPT_DES_C

static void des(unsigned long[16][2],unsigned char[8],int,unsigned long);
static char *des_crypt(const char *, const char *, char *, int);
static void deskey(unsigned long[16][2],const unsigned char * /*,int*/);

#include "deskey.c"

/* Tables defined in the Data Encryption Standard documents
 * Three of these tables, the initial permutation, the final
 * permutation and the expansion operator, are regular enough that
 * for speed, we hard-code them. They're here for reference only.
 * Also, the S and P boxes are used by a separate program, gensp.c,
 * to build the combined SP box, Spbox[]. They're also here just
 * for reference. 
 */
#if 0
/* initial permutation IP */
const static unsigned char ip[] = {
	58, 50, 42, 34, 26, 18, 10,  2,
	60, 52, 44, 36, 28, 20, 12,  4,
	62, 54, 46, 38, 30, 22, 14,  6,
	64, 56, 48, 40, 32, 24, 16,  8,
	57, 49, 41, 33, 25, 17,  9,  1,
	59, 51, 43, 35, 27, 19, 11,  3,
	61, 53, 45, 37, 29, 21, 13,  5,
	63, 55, 47, 39, 31, 23, 15,  7
};

/* final permutation IP^-1 */
const static unsigned char fp[] = {
	40,  8, 48, 16, 56, 24, 64, 32,
	39,  7, 47, 15, 55, 23, 63, 31,
	38,  6, 46, 14, 54, 22, 62, 30,
	37,  5, 45, 13, 53, 21, 61, 29,
	36,  4, 44, 12, 52, 20, 60, 28,
	35,  3, 43, 11, 51, 19, 59, 27,
	34,  2, 42, 10, 50, 18, 58, 26,
	33,  1, 41,  9, 49, 17, 57, 25
};
/* expansion operation matrix */
const static unsigned char ei[] = {
	32,  1,  2,  3,  4,  5,
	 4,  5,  6,  7,  8,  9,
	 8,  9, 10, 11, 12, 13,
	12, 13, 14, 15, 16, 17,
	16, 17, 18, 19, 20, 21,
	20, 21, 22, 23, 24, 25,
	24, 25, 26, 27, 28, 29,
	28, 29, 30, 31, 32,  1 
};

/* The (in)famous S-boxes */
const static unsigned char sbox[8][64] = {
	/* S1 */
	14,  4, 13,  1,  2, 15, 11,  8,  3, 10,  6, 12,  5,  9,  0,  7,
	 0, 15,  7,  4, 14,  2, 13,  1, 10,  6, 12, 11,  9,  5,  3,  8,
	 4,  1, 14,  8, 13,  6,  2, 11, 15, 12,  9,  7,  3, 10,  5,  0,
	15, 12,  8,  2,  4,  9,  1,  7,  5, 11,  3, 14, 10,  0,  6, 13,

	/* S2 */
	15,  1,  8, 14,  6, 11,  3,  4,  9,  7,  2, 13, 12,  0,  5, 10,
	 3, 13,  4,  7, 15,  2,  8, 14, 12,  0,  1, 10,  6,  9, 11,  5,
	 0, 14,  7, 11, 10,  4, 13,  1,  5,  8, 12,  6,  9,  3,  2, 15,
	13,  8, 10,  1,  3, 15,  4,  2, 11,  6,  7, 12,  0,  5, 14,  9,

	/* S3 */
	10,  0,  9, 14,  6,  3, 15,  5,  1, 13, 12,  7, 11,  4,  2,  8,
	13,  7,  0,  9,  3,  4,  6, 10,  2,  8,  5, 14, 12, 11, 15,  1,
	13,  6,  4,  9,  8, 15,  3,  0, 11,  1,  2, 12,  5, 10, 14,  7,
	 1, 10, 13,  0,  6,  9,  8,  7,  4, 15, 14,  3, 11,  5,  2, 12,

	/* S4 */
	 7, 13, 14,  3,  0,  6,  9, 10,  1,  2,  8,  5, 11, 12,  4, 15,
	13,  8, 11,  5,  6, 15,  0,  3,  4,  7,  2, 12,  1, 10, 14,  9,
	10,  6,  9,  0, 12, 11,  7, 13, 15,  1,  3, 14,  5,  2,  8,  4,
	 3, 15,  0,  6, 10,  1, 13,  8,  9,  4,  5, 11, 12,  7,  2, 14,

	/* S5 */
	 2, 12,  4,  1,  7, 10, 11,  6,  8,  5,  3, 15, 13,  0, 14,  9,
	14, 11,  2, 12,  4,  7, 13,  1,  5,  0, 15, 10,  3,  9,  8,  6,
	 4,  2,  1, 11, 10, 13,  7,  8, 15,  9, 12,  5,  6,  3,  0, 14,
	11,  8, 12,  7,  1, 14,  2, 13,  6, 15,  0,  9, 10,  4,  5,  3,

	/* S6 */
	12,  1, 10, 15,  9,  2,  6,  8,  0, 13,  3,  4, 14,  7,  5, 11,
	10, 15,  4,  2,  7, 12,  9,  5,  6,  1, 13, 14,  0, 11,  3,  8,
	 9, 14, 15,  5,  2,  8, 12,  3,  7,  0,  4, 10,  1, 13, 11,  6,
	 4,  3,  2, 12,  9,  5, 15, 10, 11, 14,  1,  7,  6,  0,  8, 13,

	/* S7 */
	 4, 11,  2, 14, 15,  0,  8, 13,  3, 12,  9,  7,  5, 10,  6,  1,
	13,  0, 11,  7,  4,  9,  1, 10, 14,  3,  5, 12,  2, 15,  8,  6,
	 1,  4, 11, 13, 12,  3,  7, 14, 10, 15,  6,  8,  0,  5,  9,  2,
	 6, 11, 13,  8,  1,  4, 10,  7,  9,  5,  0, 15, 14,  2,  3, 12,

	/* S8 */
	13,  2,  8,  4,  6, 15, 11,  1, 10,  9,  3, 14,  5,  0, 12,  7,
	 1, 15, 13,  8, 10,  3,  7,  4, 12,  5,  6, 11,  0, 14,  9,  2,
	 7, 11,  4,  1,  9, 12, 14,  2,  0,  6, 10, 13, 15,  3,  5,  8,
	 2,  1, 14,  7,  4, 10,  8, 13, 15, 12,  9,  0,  3,  5,  6, 11
};

/* 32-bit permutation function P used on the output of the S-boxes */
const static unsigned char p32i[] = {	
	16,  7, 20, 21,
	29, 12, 28, 17,
	 1, 15, 23, 26,
	 5, 18, 31, 10,
	 2,  8, 24, 14,
	32, 27,  3,  9,
	19, 13, 30,  6,
	22, 11,  4, 25
};
#endif

/* Combined SP lookup table, linked in
 * For best results, ensure that this is aligned on a 32-bit boundary;
 * Borland C++ 3.1 doesn't guarantee this!
 */
#include "dessp.c"
/*extern unsigned long Spbox[8][64];*/		/* Combined S and P boxes */

/* Primitive function F.
 * Input is r, subkey array in keys, output is XORed into l.
 * Each round consumes eight 6-bit subkeys, one for
 * each of the 8 S-boxes, 2 longs for each round.
 * Each long contains four 6-bit subkeys, each taking up a byte.
 * The first long contains, from high to low end, the subkeys for
 * S-boxes 1, 3, 5 & 7; the second contains the subkeys for S-boxes
 * 2, 4, 6 & 8 (using the origin-1 S-box numbering in the standard,
 * not the origin-0 numbering used elsewhere in this code)
 * See comments elsewhere about the pre-rotated values of r and Spbox.
 *
 * The application of the salt is pretty simple: We take the output of
 * the E() expansion function (which generates a 48-bit value from the
 * 32-bit Rn-1 value) and "salt" it.  The salt is 24 bits; if the nth
 * bit is set, the nth bit in E(Rn-1) is swapped with the n+24th bit
 * in the expansion.  There is no explicit "expansion process" or E table
 * in this code, but the operations performed to obtain the "work" variable
 * just before the salt is applied correspond to this process (that's
 * what the earlier comment about "we hard-code them" is about).
 *
 * The only good documentation of the salting process I was able to find
 * is "Unix Password Encryption Considered Insecure" by Philip Leong and
 * Chris Tham;  http://members.value.com.au/christie/usenix91.htm
 *
 * If you want to understand DES first, "The DES Algorithm Illustrated"
 * by J. Orlin Grabbe is a good read: http://orlingrabbe.com/des.htm
 */
#define	F(l,r,key){\
	work = ((r >> 4) | (r << 28));\
	work = (work & ~salt_odd) | ((work & salt_odd) >> 16) | ((work & salt_odd) << 16);\
	work ^= key[0];\
	l ^= Spbox[6][work & 0x3f];\
	l ^= Spbox[4][(work >> 8) & 0x3f];\
	l ^= Spbox[2][(work >> 16) & 0x3f];\
	l ^= Spbox[0][(work >> 24) & 0x3f];\
	work = (r & ~salt_even) | ((r & salt_even) >> 16) | ((r & salt_even) << 16);\
	work ^= key[1];\
	l ^= Spbox[7][work & 0x3f];\
	l ^= Spbox[5][(work >> 8) & 0x3f];\
	l ^= Spbox[3][(work >> 16) & 0x3f];\
	l ^= Spbox[1][(work >> 24) & 0x3f];\
}
/* Encrypt or decrypt a block of data in ECB mode */
static void
des(ks,block,rounds,salt)
unsigned long ks[16][2];	/* Key schedule */
unsigned char block[8];		/* Data block */
int rounds;			/* The number of iterations to run DES */
unsigned long salt;             /* Binary salt */
{
	unsigned long left,right,work,salt_odd,salt_even;

	/* Read input block and place in left/right in big-endian order */
	left = ((unsigned long)block[0] << 24)
	 | ((unsigned long)block[1] << 16)
	 | ((unsigned long)block[2] << 8)
	 | (unsigned long)block[3];
	right = ((unsigned long)block[4] << 24)
	 | ((unsigned long)block[5] << 16)
	 | ((unsigned long)block[6] << 8)
	 | (unsigned long)block[7];

	/* Read input block and place in left/right in big-endian order */
	left = ((unsigned long)block[0] << 24)
	 | ((unsigned long)block[1] << 16)
	 | ((unsigned long)block[2] << 8)
	 | (unsigned long)block[3];
	right = ((unsigned long)block[4] << 24)
	 | ((unsigned long)block[5] << 16)
	 | ((unsigned long)block[6] << 8)
	 | (unsigned long)block[7];

	/* Because ks[i][0] contains all odd 6-bit pairs and
	 * ks[i][1] contains all even pairs, salt needs to be
	 * modified accordingly.
	 * salt is 24 bits but needs to be applied to both halves
	 * of each key.
	 */
	salt_odd = ((salt >> 18) & 0x3f) << 8;
	salt_odd |= (salt >> 6) & 0x3f;
	salt_odd |= salt_odd << 16;

	salt_even = ((salt >> 12) & 0x3f) << 8;
	salt_even |= salt & 0x3f;
	salt_even |= salt_even << 16;

	while(rounds-- > 0) {
		/* Hoey's clever initial permutation algorithm, from
		 * Outerbridge (see Schneier p 478)
		 *
		 * The convention here is the same as Outerbridge:
		 * rotate each register left by 1 bit, i.e., so that
		 * "left" contains permuted input bits 2, 3, 4, ... 1
		 * and "right" contains 33, 34, 35, ... 32 (using
		 * origin-1 numbering as in the FIPS). This allows us
		 * to avoid one of the two rotates that would
		 * otherwise be required in each of the 16 rounds.
		 */
		work = ((left >> 4) ^ right) & 0x0f0f0f0f;
		right ^= work;
		left ^= work << 4;
		work = ((left >> 16) ^ right) & 0xffff;
		right ^= work;
		left ^= work << 16;
		work = ((right >> 2) ^ left) & 0x33333333;
		left ^= work;
		right ^= (work << 2);
		work = ((right >> 8) ^ left) & 0xff00ff;
		left ^= work;
		right ^= (work << 8);
		right = (right << 1) | (right >> 31);
		work = (left ^ right) & 0xaaaaaaaa;
		left ^= work;
		right ^= work;
		left = (left << 1) | (left >> 31);
		/* Required on 64-bit platforms (salting messes up otherwise) */
		left &= 0xffffffff;
		right &= 0xffffffff;
		
		/* Now do the 16 rounds */
		F(left,right,ks[0]);
		F(right,left,ks[1]);
		F(left,right,ks[2]);
		F(right,left,ks[3]);
		F(left,right,ks[4]);
		F(right,left,ks[5]);
		F(left,right,ks[6]);
		F(right,left,ks[7]);
		F(left,right,ks[8]);
		F(right,left,ks[9]);
		F(left,right,ks[10]);
		F(right,left,ks[11]);
		F(left,right,ks[12]);
		F(right,left,ks[13]);
		F(left,right,ks[14]);
		F(right,left,ks[15]);

		/* Inverse permutation, also from
		 * Hoey via Outerbridge and Schneier */
		right = (right << 31) | (right >> 1);
		work = (left ^ right) & 0xaaaaaaaa;
		left ^= work;
		right ^= work;
		left = (left >> 1) | (left  << 31);
		work = ((left >> 8) ^ right) & 0xff00ff;
		right ^= work;
		left ^= work << 8;
		work = ((left >> 2) ^ right) & 0x33333333;
		right ^= work;
		left ^= work << 2;
		work = ((right >> 16) ^ left) & 0xffff;
		left ^= work;
		right ^= work << 16;
		work = ((right >> 4) ^ left) & 0x0f0f0f0f;
		left ^= work;
		right ^= work << 4;

		/* 'And' is for 64bit platforms (salting messes up otherwise) */
		work = left & 0xffffffff;
		left = right & 0xffffffff;
		right = work;
	}

	/* Put the block back into the user's buffer with final swap */
	block[0] = left >> 24;
	block[1] = left >> 16;
	block[2] = left >> 8;
	block[3] = left;
	block[4] = right >> 24;
	block[5] = right >> 16;
	block[6] = right >> 8;
	block[7] = right;
}
#undef F

static int a64toi_initialized = 0;
static int _crypt_a64toi[128];

static char *des_crypt(key, salt, output, output_size)
const char *key;
const char *salt;
char *output;
int output_size;
{
	unsigned char key_block[8];
	unsigned long ks[16][2];
	unsigned char result[8] = {0, 0, 0, 0, 0, 0, 0, 0};
	int i, j, c, rounds, salt_size;
	unsigned long salt_value = 0;
	unsigned long tmp;
	
	if (!a64toi_initialized) {
		for (i = 0; i < 64; ++i)
			_crypt_a64toi[_crypt_itoa64[i]] = i;
		a64toi_initialized = 1;
	}

	/* Use up 8 bytes of the password, using only the lower 7 bits
	 * of each byte in the password (shifted to the left).
	 * Pad with NUL if the password is shorter than 8 bytes.
	 */
	for (i = 0; i < 8; ++i) {
		if (*key != '\0') {
			key_block[i] = *key << 1;
			++key;
		} else {
			key_block[i] = 0;
		}
	}

	deskey(ks, key_block);

	if (*salt == '_') {
		salt_size = 4;
		if (output_size < 20)
			return NULL;

		/* The rest of the key is XORed into the key block
		 * after it is run through the unmodified DES
		 * algorithm (ie, salt = 0).
		 */
		while (*key != '\0') {
			des(ks, key_block, 1, 0);
			
			for (i = 0; i < 8; ++i) {
				if (*key != '\0') {
					key_block[i] ^= *key << 1;
					++key;
				}
			}
			
			deskey(ks, key_block);
		}

		*output++ = *salt++; /* copy underscore */
		
		/* Determine iteration count and also copy this data.
		 * The rounds are stored in reverse order; with the
		 * least significant group of six bits first.
		 */
		rounds  = _crypt_a64toi[(int)*salt&0x7f];
		*output++ = *salt++;
		rounds |= _crypt_a64toi[(int)*salt&0x7f] << 6;
		*output++ = *salt++;
		rounds |= _crypt_a64toi[(int)*salt&0x7f] << 12;
		*output++ = *salt++;
		rounds |= _crypt_a64toi[(int)*salt&0x7f] << 18;
		*output++ = *salt++;
	} else {
		salt_size = 2;
		rounds = 25;
		if (output_size < 13)
			return NULL;
	}

	for(i = 0; i < salt_size; ++i) {
		c = _crypt_a64toi[(int)salt[i]&0x7f];
		/* Each group of 6 bits is in reverse order: 012345 => 543210 */
		for (j = 0; j < 6; ++j) {
			salt_value <<= 1;
			salt_value |= c & 1;
			c >>= 1;
		}
		*output++ = salt[i];
	}
	/* Generate the final 24-bits binary salt value */
	salt_value <<= 24-(salt_size*6);

	des(ks, result, rounds, salt_value);

	tmp = ((unsigned long)result[0]<<16) |
		((unsigned long)result[1]<<8) |
		(unsigned long)result[2];
	*output++ = _crypt_itoa64[(tmp >> 18)&0x3f];
	*output++ = _crypt_itoa64[(tmp >> 12)&0x3f];
	*output++ = _crypt_itoa64[(tmp >> 6)&0x3f];
	*output++ = _crypt_itoa64[tmp&0x3f];
	tmp = ((unsigned long)result[3]<<16) |
		((unsigned long)result[4]<<8) |
		(unsigned long)result[5];
	*output++ = _crypt_itoa64[(tmp >> 18)&0x3f];
	*output++ = _crypt_itoa64[(tmp >> 12)&0x3f];
	*output++ = _crypt_itoa64[(tmp >> 6)&0x3f];
	*output++ = _crypt_itoa64[tmp&0x3f];
	tmp = ((unsigned long)result[6]<<10) |
		((unsigned long)result[7]<<2);
	*output++ = _crypt_itoa64[(tmp >> 12)&0x3f];
	*output++ = _crypt_itoa64[(tmp >> 6)&0x3f];
	*output = _crypt_itoa64[tmp&0x3f];

	return output;
}
#endif /* CRYPT_DES_C */