Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10 5/3/83; site utcsrgv.UUCP
Path: utzoo!utcsrgv!outer
From: outer@utcsrgv.UUCP (Richard Outerbridge)
Newsgroups: net.sources
Subject: lucifer.c: a cryptographic algorithm
Message-ID: <3718@utcsrgv.UUCP>
Date: Tue, 3-Apr-84 00:43:21 EST
Article-I.D.: utcsrgv.3718
Posted: Tue Apr  3 00:43:21 1984
Date-Received: Tue, 3-Apr-84 00:53:55 EST
Organization: CSRG, University of Toronto
Lines: 547

This is a set of routines which implement the IBM LUCIFER algorithm.
They are derived from the article "LUCIFER: A Cryptographic Algorithm"
by Arthur Sorkin (CRYPTOLOGIA, Vol. 8, No. 1, January 1984), and the
FORTRAN routines published as appendices to the article.  LUCIFER was
developed by IBM in the early seventies, and is a direct predecessor
of the Data Encryption Standard.  It seems to be a MUCH weaker system,
even though it uses a 128-bit key and 16-byte data blocks.  The interface
to the cryptography lets you use one of several block encryption modes.
The program chunks along rather slowly as compared to UNIX crypt(1).
The speed could probably be increased by inspired table lookups.
As LUCIFER has been obsoleted by the DES, these routines are primarily
intended for academic research and non-UNIX (i.e. micro) systems with
'C' compilers but no cryptography.  If you modify them, please ensure
that taking the checksum of a null stream results in the hex value given
near the end of the file.

8404.02 	Richard Outerbridge	outer@utcsrgv

/************************* lucifer - applications ***********************/
/*					(programmed by R.W.Outerbridge)	*/

/* lucifer: encrypt/decrypt files with the IBM LUCIFER algorithm.
 *
 *	Usage: lucifer (+|-)([ecb]|<cbc|pcc|cks>) key1 <key2>
 *		       EN/DE  MODES OF OPERATION     KEYS
 *
 *	+ :	ENcrypt (default if MODE specified)
 *	- :	DEcrypt (presumes encrypted input)
 *
 *	Modes of Operation (choose ONE):
 *
 *	ecb : (default) Electronic Code Book.  Only uses one key.
 *		If simply "+" or "-" is specified, ecb is used.
 *	cbc : Cipher Block Chaining.  Uses two keys.
 *	pcc : Plaintext-Ciphertext Chaining.  Uses two keys.
 *		Performs automatic message authentication.
 *	cks : ChecKSum.  Generates a 128-bit checksum using two keys.
 *
 *	Both keys may be up to 16 characters long.  NON-ASCII MACHINES
 *	MAY GET DIFFERENT RESULTS.  Any character may be used in keys,
 *	but the one letter key "@", when used as "key1", will cause
 *	lucifer to use a preset default key for "key1".  This is used
 *	for verification and testing.  Failing to specify "key2", if
 *	required, will result in "key1" being used for both keys.  It
 *	is an error to omit "key1".  There is no provision for specifying
 *	arbitrary, absolute, bit-valued keys.
 *
 *	Lucifer reads from its stdin stream, and writes to its stdout stream.
 *	Mucking up the arguments will get you messages on the stderr stream.
 *	As painful as they are to use, long and complex keys are MUCH safer.
 *
 *					~~ Graven Cyphers, 8403.30
 *					   University of Toronto
 */

#include <stdio.h>
#define EN	0
#define DE	1
#define PCC	2
#define MODS	4

void ruderr(), copy16(), xor16();
void lucifer(), loadkey(), getkey(), put16(), resetIO();

char Block[16], Link[16], Temp[16], IV[16], KV[16];
char DFLTKY[16] = { 1,35,69,103,137,171,205,239,254,220,186,152,118,84,50,16 };
			/* 0x0123456789abcdeffedcba9876543210	*/

int Ecb(), Cbc(), Pcc(), Cks();
struct modes {
	char *name;
	int (*func)();
	};
struct modes ModsOp[MODS] = {
	{ "ecb", Ecb },
	{ "cbc", Cbc },
	{ "pcc", Pcc },
	{ "cks", Cks }	};

main(argc, argv)
int argc;
char **argv;
	{
	int (*xeqtr)();
	int step, ende, edio, ok, i;

	argv++; argc--;
	if(argc > 3 || argc < 2) ruderr();

	for(step=0; argc > 0; step++) {
		switch(step) {
		case 0:	/* set en/de and/or default mode	*/
			if(*argv[0] == '+' || *argv[0] == '-') {
				ende = (*argv[0] == '+') ? EN : DE;
				*argv[0]++ = NULL;
				if(*argv[0] == NULL) {
					xeqtr = Ecb;	/* default mode	*/
					edio = ende;
					argv++; argc--;
					break;
					}
				}
			else ende = EN;

			for(i=ok=0; i<MODS && !ok; i++) {
				if(strcmp(argv[0], ModsOp[i].name) == 0) {
					xeqtr = ModsOp[i].func;
					ok = 1;
					}
				}
			if(!ok) {
				fprintf(stderr, "Lucifer: unknown mode >%s<.\n", argv[0]);
				ruderr();
				}
			while(*argv[0]) *argv[0]++ = NULL;
			argv++; argc--;

			/* set appropriate IO modes	*/
			if(xeqtr == Cks) edio = EN|PCC;	/* IO kludge	*/
			else if(xeqtr == Pcc) edio = ende|PCC;
			else edio = ende;

		/* falling through....	*/
		case 1: /* get the key and IV, if needed and present	*/
			if(strcmp(argv[0], "@") == 0) copy16(DFLTKY, KV);
			else getkey(argv[0], KV);
			argv++; argc--;
			
			/* if nothing left, but an IV needed, use the key	*/
			if(argc == 0) {
				if(xeqtr != Ecb) copy16(KV, IV);
				break;
				}
			else if(xeqtr == Ecb) {
				fprintf(stderr, "Lucifer: (warning) - key2 ignored.\n");
				while(*argv[0]) *argv[0]++ = NULL;
				argv++; argc--;
				break;
				}

			else getkey(argv[0], IV);
			argv++; argc--;
			break;

		default:
			fprintf(stderr, "Lucifer: Programming error!\n");
			exit(1);
			break;
			}	/* switch	*/
		}	/* argument parsing	*/

	resetIO(stdin, stdout, edio);
	(*xeqtr)(ende);		/* ta-da!  Take it away xeqtr!	*/
	exit(0);
	}	/* end of main	*/

void ruderr() {
	fprintf(stderr, "Usage: lucifer (+|-)([ecb]|<cbc|pcc|cks>) key1 <key2>\n");
	exit(1);
	}

Cbc(e_d)	/* Cipher Block Chaining		*/
int e_d;	/* Ciphertext errors are self-healing.	*/
	{
	loadkey(KV);
	copy16(IV, Link);
	while(get16(Block) != EOF) {
		if(e_d == DE) copy16(Block, Temp);
		else xor16(Block, Link);
		lucifer(Block, e_d);
		if(e_d == DE) {
			xor16(Block, Link);
			copy16(Temp, Link);
			}
		else copy16(Block, Link);
		put16(Block);
		}
	return;
	}

Cks(e_d)	/* CBC authentication checksum generator	*/
int e_d;	/* The banks use this for verifications.	*/
	{
	int i, j, k;
	long count = 0;
	loadkey(KV);
	copy16(IV, Link);
	while(get16(Block) != EOF) {
		xor16(Block, Link);
		lucifer(Block, e_d);
		copy16(Block, Link);
		count += 16L;
		}
	fprintf(stdout, ": %0ld bytes\t: ", count);
	for(i=j=0; i<4; i++) {
		for(k=0; k<4; k++, j++) fprintf(stdout, "%02x", Link[j]&0377);
		putc(' ', stdout);
		}
	fprintf(stdout, ":\n");
	return;
	}

Pcc(e_d)	/* Plaintext-Ciphertext feedback block Chaining */
int e_d;	/* This is the best, but if you lose >1< bit...	*/
	{
	int i, j;
	loadkey(KV);
	copy16(IV, Link);
	while(get16(Block) != EOF) {
		if(e_d == DE) {
			copy16(Block, Temp);
			lucifer(Temp, DE);
			xor16(Link, Temp);
			}
		else {
			xor16(Link, Block);
			lucifer(Link, EN);
			}
		put16(Link);
		xor16(Link, Block);
		}
	if(e_d == DE) {
		lucifer(Temp, EN);
		xor16(Link, Temp);
		for(i=j=0; i<16; i++) j += (Link[i] ^ IV[i])&0377;
		if(j != 0) {
			fprintf(stderr, "Lucifer: Corrupt authenticator (%03x)!\n", j);
			exit(1);
			}
		}
	else {
		xor16(Link, IV);
		lucifer(Link, EN);
		put16(Link);
		}
	return;
	}

Ecb(e_d)	/* Electronic Code Book	: simple substitution	*/
int e_d;	/* Yawn.  For static data and random access.	*/
	{
	loadkey(KV);
	while(get16(Block) != EOF) {
		lucifer(Block, e_d);
		put16(Block);
		}
	return;
	}

void copy16(from, to)
register char *from, *to;
	{
	register char *ep;
	ep = &to[16];
	while(to<ep) *to++ = *from++;
	return;
	}

void xor16(to, with)
register char *to, *with;
	{
	register char *ep;
	ep = &to[16];
	while(to<ep) *to++ ^= *with++;
	return;
	}

/*			(rwo/8403.30.14:52/V2.1)			*/
/**************************** lucifer - applications ********************/
/******************************** lucifer *******************************/

/* LUCIFER is a cryptographic algorithm developed by IBM in the early
 *	seventies.  It was a predecessor of the DES, and is much simpler
 *	than that algorithm.  In particular, it has only two substitution
 *	boxes and just one permutation box.  The permutation box is only
 *	eight bits wide.  It does, however, use a 128 bit key and operates
 *	on sixteen byte data blocks...
 *
 *	This implementation of LUCIFER was crafted by Graven Cyphers at the
 *	University of Toronto, Canada, with programming assistance from
 *	Richard Outerbridge.  It is based on the FORTRAN routines which
 *	concluded Arthur Sorkin's article "LUCIFER: A Cryptographic Algorithm",
 *	CRYPTOLOGIA, Volume 8, Number 1, January 1984, pp22-42.	 The interested
 *	reader should refer to that article rather than this program for more
 *	details on LUCIFER.
 *
 *	These routines bear little resemblance to the actual LUCIFER algorithm,
 *	which has been severely twisted in the interests of speed.  They do
 *	perform the same transformations, and are believed to be UNIX portable.
 *	The package was developed for use on UNIX-like systems lacking crypto
 *	facilities.  They are not very fast, but the cipher is very strong.
 *	The routines in this file are suitable for use as a subroutine library
 *	after the fashion of crypt(3).  When linked together with applications
 *	routines they can also provide a high-level cryptographic system.
 */

/*	#include <stdio.h>
	#define EN	0
	#define DE	1	*/
#include <ctype.h>

/* IO variables.  resetIO() must be called to initialise them	*/
static int Ed_IO, End, Twice;
static char Save0[16], Save1[16], *Former, *Last;
static FILE *Finp, *Foutp;

static char Key[16];	/* master key table			*/

static char DP[8][8] = { 	/* Diffusion Pattern schedule	*/
	{ 7,6,2,1,5,0,3,4 },
	{ 0,7,3,2,6,1,4,5 },
	{ 1,0,4,3,7,2,5,6 },
	{ 2,1,5,4,0,3,6,7 },
	{ 3,2,6,5,1,4,7,0 },
	{ 4,3,7,6,2,5,0,1 },
	{ 5,4,0,7,3,6,1,2 },
	{ 6,5,1,0,4,7,2,3 },    };

static char Pbox[256] = {	/* precomputed Permutations	*/
	  0,  2,  1,  3, 64, 66, 65, 67, 32, 34, 33, 35, 96, 98, 97, 99,
	  8, 10,  9, 11, 72, 74, 73, 75, 40, 42, 41, 43,104,106,105,107,
	128,130,129,131,192,194,193,195,160,162,161,163,224,226,225,227,
	136,138,137,139,200,202,201,203,168,170,169,171,232,234,233,235,
	  4,  6,  5,  7, 68, 70, 69, 71, 36, 38, 37, 39,100,102,101,103,
	 12, 14, 13, 15, 76, 78, 77, 79, 44, 46, 45, 47,108,110,109,111,
	132,134,133,135,196,198,197,199,164,166,165,167,228,230,229,231,
	140,142,141,143,204,206,205,207,172,174,173,175,236,238,237,239,
	 16, 18, 17, 19, 80, 82, 81, 83, 48, 50, 49, 51,112,114,113,115,
	 24, 26, 25, 27, 88, 90, 89, 91, 56, 58, 57, 59,120,122,121,123,
	144,146,145,147,208,210,209,211,176,178,177,179,240,242,241,243,
	152,154,153,155,216,218,217,219,184,186,185,187,248,250,249,251,
	 20, 22, 21, 23, 84, 86, 85, 87, 52, 54, 53, 55,116,118,117,119,
	 28, 30, 29, 31, 92, 94, 93, 95, 60, 62, 61, 63,124,126,125,127,
	148,150,149,151,212,214,213,215,180,182,181,183,244,246,245,247,
	156,158,157,159,220,222,221,223,188,190,189,191,252,254,253,255 };

/* precomputed nibble substitutions.  note that S0 (not S1!) values are <<4	*/
static char S0[16] = { 48,64,112,144,224,192,208,160,240,96,176,32,80,128,0,16 };
static char S1[16] = { 14,3,12,6,7,8,0,1,4,11,13,15,9,5,2,10 };

/* Shadow masks	*/
static char Smask[16] = { 128,64,32,16,8,4,2,1 };

/* lucifer: the actual algorithm.  Assumes chars are 8 bits.  If not, the
	high bytes will be undefined on return (either 0's or 1's).	*/
void lucifer(bytes, edf)
char *bytes;	/* points to a 16-byte array	*/
int edf;	/* 0 = encrypt, 1 = decrypt	*/
	{
	register char *cp, *sp, *dp, val;
	register int k, j, kc, ks, i;
	char *h0, *h1, *sbs;

	h0 = &bytes[0];		/* the "lower" half	*/
	h1 = &bytes[8];		/* the "upper" half	*/
	kc = (edf == DE) ? 8 : 0;

	for(i=0; i<16; i++) {
		if(edf == DE) kc = (++kc)&017;
		ks = Key[kc]&0377;	/* the "first" byte of key, this round	*/
		sbs = Smask;

		for(j=0; j<8; j++) {
			cp = &h1[j];
			/* nibbles are selected by the bits of ks	*/
			if(ks&*sbs++) val = S0[(*cp>>4)&017] | S1[*cp&017];
			else val = S0[*cp&017] | S1[(*cp>>4)&017];

			/* xor the just-S'd byte with the next byte of key and permute	*/
			val = Pbox[(val ^ Key[kc])&0377];

			/* fiddle bits in the "lower" half	*/
			dp = &DP[j][0];
			sp = Smask;
			for(k=0; k<8; k++) {
				cp = &h0[*dp++];
				*cp ^= (val&*sp++);
				}

			if(j<7 || (edf == DE)) kc = (++kc)&017;
			}

		/* swap (virtual) halves	*/
		cp = h0;
		h0 = h1;
		h1 = cp;
		}

	/* REALLY swap halves	*/
	dp = &bytes[0];
	cp = &bytes[8];
	for(sp=cp; dp<sp; dp++, cp++) {
		val = *dp;
		*dp = *cp;
		*cp = val;
		}
	return;
	} 

void loadkey(keystr)		/* sets master key	*/
register char *keystr;
	{
	register char *ep, *cp;
	cp = Key;
	ep = &Key[16];
	while(cp < ep) *cp++ = *keystr++;
	return;
	}

/* getkey: using up to 16 bytes of aptr, makeup a 16 byte key in savp.
	aptr must be NULL terminated, savp 16 bytes long.  The key
	returned in savp is aptr encrypted with itself ONCE.	*/ 
void getkey(aptr, savp)
register char *aptr, *savp;
	{
	register int i;
	register char *store;
	store = savp;

	/* copy aptr into savp; NULL aptr	*/
	for(i=0; i<16 && (*aptr != NULL); i++) {
		*savp++ = toascii(*aptr);
		*aptr++ = NULL;
		}
	while(*aptr) *aptr++ = NULL;
	if(i == 0) savp++;	/* aptr could have been NULL	*/

	/* expand savp out to 16 bytes of "something" and encrypt it	*/
	for(aptr=store, savp--; i<16;) store[i++] = (*aptr++ + *savp++)&0377;
	loadkey(store);
	lucifer(store, EN);
	return;
	}

/* Input/Output: ENcrypting is straightforward (almost).  gets and puts
 *	are done immediately.  The last block is padded with NULLs and the 
 *	number of NULLs; if there were an even 16 bytes in the last block
 *	no padding is done (unless Ed_IO != 0, ie Ed_IO == 2) and instead
 *	a single '0' is output and EOF returned.  DEcrypting is more
 *	complicated (sigh).  Writes are delayed by two reads.  On EOF,
 *	if in the middle of a block, there has either been an error OR
 *	there were no NULLs.  Any pending output is written and EOF 
 *	returned.  If EOF occurs at the start of a block, and if Ed_IO != 1
 *	(ie Ed_IO == 3), the oldest output block is written and the next
 *	output block is depadded and written.  Else the oldest output
 * 	block is written, and the last output block is ignored.  (In this
 *	case the last output block was the authenticator, which Pcc()
 *	regenerates itself).  WARNING: when decrypting, calls to put16() &
 *	get16() MUST be interleaved, ie get16(), put16(), get16() ..., or
 *	else utter nonsense will result from the delayed writing.
 */

void put16(block)
register char *block;
	{
	register char *ep, *to;
	ep = &block[16];
	if(Ed_IO&DE) {
		to = Former;
		while(block<ep) *to++ = *block++;
		to = Former;
		Former = Last;
		Last = to;
		}
	else vraiput(block, ep);
	return;
	}

get16(input)
char *input;
	{
	register int i, j;
	register char *cp;
	if(End == 1) return(EOF);	/* no more input	*/

	if(Ed_IO&DE) {	/* DECRYPTION	*/
		if((i = vraiget(input)) == 16) {
			if(Twice == 2) vraiput(Former, &Former[16]);
			else Twice++;
			}
		else {		/* EOF on input */
			End = 1;
			if(i != 0) {	/* no NULLs,  or an error	*/
				if(Twice == 2) vraiput(Former, &Former[16]);
				if(Twice >= 1) vraiput(Last, &Last[16]);
				}
			else {	/* an even 16 bytes	*/
				if(Ed_IO == DE && (Twice == 2)) vraiput(Former, &Former[16]);
				if(Twice >= 1) {	/* then there are NULLs	*/
					if(Ed_IO == DE) cp = Last;
					else cp = Former;
					i = cp[15]&037;
					if(i>16) i = 0;	/* hmmmm.	*/
					vraiput(cp, &cp[16-i]);
					}
				}
			return(EOF);
			}
		}
	else {	/* ENCRYPTION	*/
		if((i = vraiget(input)) != 16) {
			End = 1;
			if(i == 0 && (Ed_IO == EN)) {
				putc('0', Foutp);
				return(EOF);
				}
			for(j=i; j<16; j++) input[j] = NULL;
			input[15] = 16-i;
			}
		}

	return(0);
	}

static vraiput(cp, ep)
register char *cp, *ep;
	{
	while(cp<ep) putc(*cp++, Foutp);
	return;
	}

static vraiget(into)
register char *into;
	{
	register int i, j;	
	for(i=0; i<16 && ((j = getc(Finp)) != EOF); i++) *into++ = j;
	return(i);
	}

/* (re)set IO variables.  Call before any IO on a new stream.	*/
void resetIO(fin, fout, mode)
register FILE *fin, *fout;
register int mode;
	{
	End = Twice = 0;
	Ed_IO = mode;
	Finp = fin;
	Foutp = fout;
	Former = Save0;
	Last = Save1;
	return;
	}

/*	lucifer cks @ < /dev/null 
 *	: 16 bytes	: ab1b6fc7 60ec21b3 5a7cee07 fba37826 :
 *			(rwo/8403.30.14:52/V2.1)			*/
/**************************** lucifer ***********************************/